Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/CISIS.2011.112 | Complex, Intelligent and Software Intensive Systems |
Keywords | Field | DocType |
decision problem,limited cooking time,knapsack problem,two-phase cooking,time-constrained menu planning problem,week menu plan,busy persons,menu planning algorithm,np-complete knapsack problem,cooking process,menu planning,complex problem,greedy algorithms,algorithm,planning,cost function,heuristic algorithm,satisfiability,computational complexity | Decision problem,Mathematical optimization,Planning algorithms,Computer science,Heuristic (computer science),Greedy algorithm,Knapsack problem,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
978-0-7695-4373-4 | 3 | 1.01 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nobuo Funabiki | 1 | 227 | 69.87 |
| Shiho Taniguchi | 2 | 3 | 1.01 |
| Yukiko Matsushima | 3 | 7 | 3.11 |
| Toru Nakanishi | 4 | 210 | 38.25 |