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

Multi-stove Scheduling Model and Algorithm with Mergeable Products

作　　者：戴韬[1] 范湘琪 吴勇 DAI Tao;FAN Xiangqi;WU Yong(Glorious Sun School of Management,Donghua University,Shanghai 200051,China)

机构地区：[1]东华大学旭日工商管理学院,上海200051

出　　处：《工业工程》2023年第1期123-129,145,共8页Industrial Engineering Journal

基　　金：国家自然科学基金资助项目(71872037,71801035)。

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

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

分 类 号：TB497[一般工业技术] TS972.32[轻工技术与工程]