产品可合并的多炉灶出餐调度模型与算法

doi:10.3969/j.issn.1007-7375.2023.01.014

摘要/Abstract

摘要： 为了解决在用餐高峰期餐饮企业外卖出餐速度慢的问题，根据餐厅外卖出餐中“多炉灶同时工作，订单包含多种菜品，相同订单同时取货，相同菜品可合并”的特点，构建订单完成时间满足率为目标的双层调度模型。双层模型的下层是以平行机调度为基础思路的多炉灶菜品包调度模型，可得到炉灶加工计划；上层是以背包问题为基础思路的订单选择模型，可确定订单完成时间。为了保证模型的求解效率，将静态模型扩展应用于动态调度的现实场景，设计针对性的遗传算法。算例实验结果表明，相比于最紧急菜品优先、最长加工时间优先、最热门菜品优先3种启发式策略，本模型的调度方法订单完成率最高，超时时间最短。

关键词: 出餐调度, 多炉灶, 产品可合并, 遗传算法

Abstract: The scheduling of cooking stoves during the peak period is the key activity to "shorten the waiting time, improve customer satisfaction and achieve revenue growth" for the catering enterprises with take-out business. Based on the characteristics, which are “multiple stoves, variety of dishes in one order with a same pick-up time, same dishes can be combined”, a double-layer scheduling model is constructed. In the model, the lower layer is a multi-stove dish-package scheduling model based on parallel machine scheduling, and the upper is an order selection model based on knapsack problem. In order to solve the model in a reasonable time and extend the model to the dynamic scheduling case, a specific genetic algorithm is proposed. Numerical experiment is designed to evaluate the convergence and efficiency of the algorithm, meanwhile the solution is compared with 3 common strategies, which are the most urgent next, the longest process next and the most popular dish next. The results show that this model can achieve the highest order-finishing rate and the shortest overtime.

Key words: meal scheduling, multiple stoves, mergeable products, genetic algorithm

中图分类号:

戴韬, 范湘琪, 吴勇. 产品可合并的多炉灶出餐调度模型与算法[J]. 工业工程, 2023, 26(1): 123-129,145.

DAI Tao, FAN Xiangqi, WU Yong. Multi-stove Scheduling Model and Algorithm with Mergeable Products[J]. Industrial Engineering Journal, 2023, 26(1): 123-129,145.

参考文献

[1] 李胜蓝, 江立华. 新型劳动时间控制与虚假自由——外卖骑手的劳动过程研究[J]. 社会学研究, 2020, 35(6): 91-112
LI Shenglan, JIANG Lihua. A new mode of labor time control and fake experience of freedom — a study on the labor process of take-out platform riders[J]. Sociological Studies, 2020, 35(6): 91-112
[2] 余海燕, 蒋仁莲. 基于众包平台的外卖实时配送订单分配与路径优化研究[J]. 工业工程与管理, 2022, 27(2): 146-152.
YU Haiyan, JIANG Renlian. Study on the real-time order allocation and routing problem of takeout food distribution on crowdsourcing platform[J]. Industrial Engineering and Management, 2022, 27(2): 146-152.
[3] 王婷婷, 杨琴, 黄琳, 等. 基于顾客行为特征的超市收银口优化调度方案[J]. 计算机工程与应用, 2016, 52(3): 266-270
WANG Tingting, YANG Qin, HUANG Lin, et al. Optimization scheduling of retail checkout based on customers' behavior[J]. Computer Engineering and Applications, 2016, 52(3): 266-270
[4] 井彩霞, 吴瑞强, 贾兆红. 并行分批排序综述[J]. 运筹与管理, 2020, 29(1): 223-239
JING Caixia, WU Ruiqiang, JIA Zhaohong. A review of parallel batch scheduling[J]. Operations Research and Management Science, 2020, 29(1): 223-239
[5] LI Y, LI S. Scheduling jobs with sizes and delivery times on identical parallel batch machines[J]. Theoretical Computer Science, 2020, 841(11): 1-9
[6] OZTURK O. A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time[J]. European Journal of Operational Research, 2020, 286(2): 432-443
[7] ZHANG M, TAN Y, ZHU J, et al. A competitive and cooperative migrating birds optimization algorithm for vary-sized batch splitting scheduling problem of flexible Job-Shop with setup time[J]. Simulation Modelling Practice and Theory, 2020, 100: 102065
[8] 苏生, 战德臣, 徐晓飞. 一种并行机多产品厂短期调度连续时间模型[J]. 计算机集成制造系统, 2006, 12(4): 494-498
SU Sheng, ZHAN Dechen, XU Xiaofei. Continuous time model for short term scheduling of multi-product plant with parallel lines[J]. Computer Integrated ManufacturingSystems, 2006, 12(4): 494-498
[9] ABU-MARRUL V, MARTINELLI R, HAMACHER S, et al. Matheuristics for a parallel machine scheduling problem with non-anticipatory family setup times: Application in the offshore oil and gas industry[J]. Computers & Operations Research, 2021, 128: 105162
[10] ZHOU S, JIN M, DU N. Energy-efficient scheduling of a single batch processing machine with dynamic job arrival times[J]. Energy, 2020, 209: 118420
[11] LIN Y, YIN T. Generating bicriteria schedules for correlated parallel machines involving tardy jobs and weighted completion time[J/OL]. Annals of Operations Research, 2021, (2021-04-18). https://doi.org/10.1007/s10479-021-04043-x.
[12] 黄方明, 陆志强, 崔维伟. 平行机系统生产调度与维护计划联合优化[J]. 工业工程与管理, 2013, 18(4): 49-55
HUANG Fangming, LU Zhiqiang, CUI Weiwei. Integrated preventive maintenance planning and production scheduling on parallel machine[J]. Industrial Engineering and Management, 2013, 18(4): 49-55
[13] 马鑫, 廖哲文. 装箱问题在物流领域的研究回顾与分析——基于美国科学情报研究所科研数据库 (Web of Science, 1989 ~ 2018) 的科学计量分析[J]. 科技促进发展, 2019, 15(7): 675-683
MA Xin, LIAO Zhewen. Review and analysis of research on bin packing problem in logistics field—Scientometric analysis based on web of science database (1989 ~ 2018)[J]. Science & Technology for Development, 2019, 15(7): 675-683
[14] 张煜, 田维, 马杰. 集装箱船舶装箱排序问题优化模型及其决策方法[J]. 武汉理工大学学报, 2016, 38(6): 39-48
ZHANG Yu, TIAN Wei, MA Jie. Optimal model and make-decision of sequencing and bin packing problem for container vessel[J]. Journal of Wuhan University of Technology, 2016, 38(6): 39-48
[15] 曹欢欢, 陈峰. 面向汽车整车出厂物流的两阶段组合装箱调度优化模型与算法研究[J]. 工业工程与管理, 2016, 21(3): 50-58
CAO Huanhuan, CHEN Feng. Research on models and algorithms of two-stage combinatorial bin packing problem of vehicle outbound logistics[J]. Industrial Engineering and Management, 2016, 21(3): 50-58
[16] 张源凯, 胡祥培, 黄敏芳, 等. 网上超市拆分订单合并打包策略经济决策模型[J]. 管理科学学报, 2019, 22(10): 24-36
ZHANG Yuankai, HU Xiangpei, HUANG Minfang, et al. Economic decision model for package consolidation in fulfilling split orders of online supermarkets[J]. Journal of Management Sciences in China, 2019, 22(10): 24-36
[17] 曾创锋, 刘建军, 陈庆新, 等. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118
ZHENG Chuangfeng, LIU Jianjun, CHEN Qingxin, et al. A genetic algorithm-iterative greedy algorithm for a kind of unrelated parallel machine scheduling problem[J]. Industrial Engineering Journal, 2021, 24(2): 110-118
[18] 杨帆, 方成刚, 洪荣晶, 等. 改进遗传算法在车间调度问题中的应用[J]. 南京工业大学学报 (自然科学版) , 2021, 43(4): 480-485
YANG Fan, FANG Chenggang, HONG Rongjing, et al. Application of improved genetic algorithm in job-shop scheduling problem[J]. Journal of Nanjing Tech University (Natural Science Edition) , 2021, 43(4): 480-485
[19] 刘雪红, 张涛, 彭兆, 等. 面向医疗器械企业灭菌工艺的不同容量平行机批调度[J]. 工业工程, 2021, 24(1): 82-89
LIU Xuehong, ZHANG Tao, PENG Zhao, et al. Batch scheduling of parallel machines with different capacity for sterilization process in medical equipment enterprises[J]. Industrial Engineering Journal, 2021, 24(1): 82-89
[20] 刘海涛, 邓停铭, 唐健均, 等. 大规模柔性作业车间调度问题分解建模和求解方法[J]. 机械设计与制造, 2021(5): 68-71
LIU Haitao, DENG Tingming, TANG Jianjun, et al. Decomposition modeling and solving method for large scale flexible job shop scheduling problem[J]. Machinery Design & Manufacture, 2021(5): 68-71