{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:49:53Z","timestamp":1760233793075,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T00:00:00Z","timestamp":1614038400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>As the number of users who cook their own food increases, there is increasing demand for an optimal cooking procedure for multiple dishes, but the optimal cooking procedure varies from user to user due to the difference of each user\u2019s cooking skill and environment. In this paper, we propose a system of presenting optimal cooking procedures that enables parallel cooking of multiple recipes. We formulate the problem of deciding optimal cooking procedures as a task scheduling problem by creating a task graph for each recipe. To reduce execution time, we propose two extensions to the preprocessing and bounding operation of PDF\/IHS, a sequential optimization algorithm for the task scheduling problem, each taking into account the cooking characteristics. We confirmed that the proposed algorithm can reduce execution time by up to 44% compared to the base PDF\/IHS, and increase execution time by about 900 times even when the number of required searches increases by 10,000 times. In addition, through the experiment with three recipes for 10 participants each, it was confirmed that by following the optimal cooking procedure for a certain menu, the actual cooking time was reduced by up to 13 min (14.8% of the time when users cooked freely) compared to the time when users cooked freely.<\/jats:p>","DOI":"10.3390\/a14020067","type":"journal-article","created":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T12:40:16Z","timestamp":1614084016000},"page":"67","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Cooking Procedure Presentation System for Multiple Recipes and Investigating Its Effect"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1643-1916","authenticated-orcid":false,"given":"Jin","family":"Nakabe","sequence":"first","affiliation":[{"name":"Nara Institute of Science and Technology, Nara 630-0192, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0281-1205","authenticated-orcid":false,"given":"Teruhiro","family":"Mizumoto","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technology, Osaka University, Osaka 565-0871, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8519-3352","authenticated-orcid":false,"given":"Hirohiko","family":"Suwa","sequence":"additional","affiliation":[{"name":"Nara Institute of Science and Technology, Nara 630-0192, Japan"},{"name":"Institute of Physical and Chemical Research, Center for Advanced Intelligence Project (AIP), Tokyo 103-0027, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1579-3237","authenticated-orcid":false,"given":"Keiichi","family":"Yasumoto","sequence":"additional","affiliation":[{"name":"Nara Institute of Science and Technology, Nara 630-0192, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,23]]},"reference":[{"key":"ref_1","unstructured":"(2020, December 19). Cookpad Inc.. Available online: https:\/\/cookpad.com\/."},{"key":"ref_2","unstructured":"(2020, December 19). Allrecipes.com Inc.. Available online: https:\/\/www.allrecipes.com\/."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1002\/scj.4690231305","article-title":"A parallel optimization algorithm for minimum execution-time multiprocessor scheduling problem","volume":"23","author":"Kasahara","year":"1992","journal-title":"Syst. Comput. Jpn."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Matsushima, Y., and Funabiki, N. (2015, January 12\u201316). Practices of Cooking-Step Scheduling Algorithm for Homemade Cooking. Proceedings of the 2015 IIAI 4th International Congress on Advanced Applied Informatics, Washington, DC, USA.","DOI":"10.1109\/IIAI-AAI.2015.189"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Van Laarhoven, P.J., and Aarts, E.H. (1987). Simulated annealing. Simulated Annealing: Theory and Applications, Springer.","DOI":"10.1007\/978-94-015-7744-1"},{"key":"ref_6","first-page":"346","article-title":"Modeling of the Simultaneous Table Scheduling Problem and Dynamic Scheduling for this Problem","volume":"54","author":"Yamabuki","year":"2018","journal-title":"Soc. Instrum. Control Eng."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"JAMDSM0076","DOI":"10.1299\/jamdsm.2018jamdsm0076","article-title":"An approach to cooking process scheduling for a family restaurant","volume":"12","author":"Kimura","year":"2018","journal-title":"J. Adv. Mech. Des. Syst. Manuf."},{"key":"ref_8","first-page":"63","article-title":"Design and Validation of Rules for a Cooking Process Scheduling Model","volume":"11","author":"Zhou","year":"2018","journal-title":"IPSJ Trans. Math. Model. Appl."},{"key":"ref_9","first-page":"1","article-title":"Disjunctive Constraints Using Integer Range for Food Preparation Scheduling Considering Machine Type","volume":"2020","author":"Ishino","year":"2020","journal-title":"Spec. Interest Group Tech. Rep. IPSJ"},{"key":"ref_10","unstructured":"Coffman, E.G., and Bruno, J.L. (1976). Computer and Job-Shop Scheduling Theory, John Wiley & Sons."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1287\/opre.9.6.841","article-title":"Parallel sequencing and assembly line problems","volume":"9","author":"Hu","year":"1961","journal-title":"Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1109\/TC.1984.1676376","article-title":"Practical multiprocessor scheduling algorithms for efficient parallel processing","volume":"33","author":"Kasahara","year":"1984","journal-title":"IEEE Trans. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1109\/TC.1973.5009153","article-title":"Bounds on the number of processors and time for multiprocessor optimal schedules","volume":"100","author":"Fernandez","year":"1973","journal-title":"IEEE Trans. Comput."},{"key":"ref_14","first-page":"1","article-title":"A Reduction Algorithm of Branching Nodes for Solving Task Scheduling Problems","volume":"7","author":"Nakamura","year":"2014","journal-title":"Inf. Process. Soc. Jpn. PRO"},{"key":"ref_15","unstructured":"Matsuse, H., Nakamura, A., Tominaga, H., and Maekawa, Y. (2016, January 10). Reducing the Number of Search Nodes in Task Scheduling Problem Using Hash Table of DF\/IHS Method. Proceedings of the 78th National Convention of IPSJ, Kanagawa, Japan."},{"key":"ref_16","first-page":"17","article-title":"A Sppedup Method for PDF\/IHS by Reducing of Branching Nodes in Task Scheduling Problems","volume":"11","author":"Matsuse","year":"2018","journal-title":"IPSJ Trans. Adv. Comput. Syst."},{"key":"ref_17","first-page":"149","article-title":"B-017 Evaluation of a Parallelized Branch and Bound Method for the Task Scheduling Problem Considering Communication Overhead","volume":"13","author":"Shibuya","year":"2014","journal-title":"Forum Inf. Technol."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Utsunomiya, M., Shioda, R., and Kai, M. (2011, January 23\u201326). Heuristic search based on branch and bound method for task scheduling considering communication overhead. Proceedings of the 2011 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, Victoria, BC, Canada.","DOI":"10.1109\/PACRIM.2011.6032902"},{"key":"ref_19","unstructured":"(2020, December 19). Development of Parallelized Solver for Task Scheduling Problems with Communication Delays: Improvements of Search Effectiveness Using Optimal Scheduling of Sub-Task-Graphs. Available online: http:\/\/hdl.handle.net\/10928\/813."},{"key":"ref_20","unstructured":"(2020, December 19). Detecting Hierarchically Structured Macro-Tasks within a Task Graph and Its Task Scheduling Method. Available online: http:\/\/hdl.handle.net\/10928\/1133."},{"key":"ref_21","first-page":"340","article-title":"Computers and Intractability: A Guide to the Theory of Np-Completeness","volume":"44","author":"Garey","year":"1979","journal-title":"Rev. Esc. Enferm. Usp"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1109\/TC.1972.5008918","article-title":"Optimal scheduling strategies in a multiprocessor system","volume":"100","author":"Ramamoorthy","year":"1972","journal-title":"IEEE Trans. Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/67\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:27:16Z","timestamp":1760160436000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,23]]},"references-count":22,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["a14020067"],"URL":"https:\/\/doi.org\/10.3390\/a14020067","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,2,23]]}}}