TY - GEN
T1 - A proposal of a menu planning algorithm for two-phase cooking by busy persons
AU - Funabiki, Nobuo
AU - Taniguchi, Shiho
AU - Matsushima, Yukiko
AU - Nakanishi, Toru
PY - 2011/9/19
Y1 - 2011/9/19
N2 - For busy persons such as working people, students, and nurturing parents, it is very hard to spend a long time in cooking foods by themselves at home after working for long hours on weekdays. As one solution, the cooking process can be divided into two phases, where the preparation steps for foods that they will eat on the following weekdays are performed on a weekend, and the final steps for some foods are finished on the eating day in a short time. Then, the task of generating a menu planning with this two-phase cooking becomes a complex problem to satisfy the limited cooking time. In this paper, we formulate this time-constrained menu planning problem with the two-phase cooking, and prove the NP-completeness of its decision problem through the reduction from the NP-complete knapsack problem. Then, we present its heuristic algorithm based on a simple greedy method for the knapsack problem, where foods are sequentially selected into the menu in descending order of food priorities. We apply the algorithm to the generation of one week menu plan from 53 food candidates, where the result verifies the effectiveness of our approach.
AB - For busy persons such as working people, students, and nurturing parents, it is very hard to spend a long time in cooking foods by themselves at home after working for long hours on weekdays. As one solution, the cooking process can be divided into two phases, where the preparation steps for foods that they will eat on the following weekdays are performed on a weekend, and the final steps for some foods are finished on the eating day in a short time. Then, the task of generating a menu planning with this two-phase cooking becomes a complex problem to satisfy the limited cooking time. In this paper, we formulate this time-constrained menu planning problem with the two-phase cooking, and prove the NP-completeness of its decision problem through the reduction from the NP-complete knapsack problem. Then, we present its heuristic algorithm based on a simple greedy method for the knapsack problem, where foods are sequentially selected into the menu in descending order of food priorities. We apply the algorithm to the generation of one week menu plan from 53 food candidates, where the result verifies the effectiveness of our approach.
KW - Menu planning
KW - algorithm
KW - finishing phase
KW - preparation phase
KW - two-phase cooking
UR - http://www.scopus.com/inward/record.url?scp=80052758628&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80052758628&partnerID=8YFLogxK
U2 - 10.1109/CISIS.2011.112
DO - 10.1109/CISIS.2011.112
M3 - Conference contribution
AN - SCOPUS:80052758628
SN - 9780769543734
T3 - Proceedings of the International Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2011
SP - 668
EP - 673
BT - Proceedings of the International Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2011
T2 - 5th International Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2011
Y2 - 30 June 2011 through 2 July 2011
ER -