批量投放与交付的柔性动态Job Shop调度问题及其调度仿真研究

doi:10.3901/JME.2020.14.231

摘要/Abstract

摘要： 基于汽车零部件生产企业制造系统，提出一种工件批量投放与交付的柔性动态Job shop调度问题，工件以批量方式动态陆续投放，整批交付，车间中具有多种类型的机器集合，以批工件总拖期及拖期批工件百分比作为调度目标。由于问题属于强NP困难问题，采用离散事件动态系统仿真方法对问题进行了仿真调度试验研究。提出问题的离散事件仿真建模中批工件投放时间与交货期的设置方法，设计6个新的调度规则，与选择的文献中所提出的9个调度规则一并纳入仿真调度试验。对仿真调度进行试验设计，采用单因素方差分析和验后比较对试验结果进行统计处理，并详细分析15个调度规则对所提调度问题的求解性能。结果表明，所提出的EMDD.b（Equivalent modified earliest due date for batch）规则在各种试验参数配置下均表现出最优的性能，所提出的其他一些新规则在两个调度目标（或某个调度目标）下也表现出较好性能。

关键词: Job shop, 动态调度, 柔性调度, 调度规则, 离散事件系统仿真

Abstract: A flexible dynamic Job shop scheduling problem with jobs releasing and delivering both in batches, which arises from the context of auto-parts production systems, is addressed. In the problem, jobs are released to workshop successively in batches over time; a batch should be delivered as a whole when all the jobs in it are finished. In the shop, there are several types of machines, each of which consists of some identical machines. Total tardiness of all batches under consideration and the proportion of tardy batches are taken as two performance measures. For the problem being strongly NP-hard, a scheduling experiment is conducted by discrete event dynamic system simulation. In the modeling of discrete event system, setting methods of the release times and the due dates of job batches are proposed. A total of fifteen dispatching rules, including six new proposed dispatching rules and nine dispatching rules selected from literature, are put into the scheduling experiment. Performance evaluations are conducted by one-way analysis of variance and post-hoc comparisons with the experiment results. The evaluations indicate that a new proposed dispatching rule, equivalent modified earliest due date for batch(EMDD.b), has the overwhelming superiority to the other rules under consideration, and the five other new proposed rules also perform well with respect to the one or two performance measures.

Key words: Job shop, dynamic scheduling, flexible scheduling, dispatching rule, discrete event system simulation

中图分类号:

TH186

熊禾根, 吴健, 阳光灿. 批量投放与交付的柔性动态Job Shop调度问题及其调度仿真研究[J]. 机械工程学报, 2020, 56(14): 231-244.

XIONG Hegen, WU Jian, YANG Guangcan. Scheduling Simulation for Flexible Dynamic Job Shop Scheduling Problem with Jobs Releasing and Delivering Both in Batches[J]. Journal of Mechanical Engineering, 2020, 56(14): 231-244.

参考文献

[1] BAKER K R, BERTRAND J W M. An investigation of due-date assignment rules with constrained tightness[J]. Journal of Operations Management, 1981, 1(3):109-120.
[2] HOLTHAUS O. Design of efficient job shop scheduling rules[J]. Computers & Industrial Engineering, 1997, 33(1-2):249-252.
[3] HOLTHAUS O, RAJENDRAN C. Efficient dispatching rules for scheduling in a job shop[J]. International Journal of Production Economics, 1997, 48(1):87-105.
[4] RAJENDRAN C, HOLTHAUS O. A comparative study of dispatching rules in dynamic flowshops and job shops[J]. European Journal of Operational Research, 1999, 116(1):156-170.
[5] AYDIN M E, ÖZTEMEL E. Dynamic job-shop scheduling using reinforcement learning gents[J]. Robotics and Autonomous Systems, 2000, 33(2-3):169-178.
[6] 万国华. 用模糊调度系统求解动态Job Shop问题[J]. 系统工程理论与实践, 2001(8):97-101. WAN Guohua. Using fuzzy scheduling system for solving a dynamic job shop problem[J]. Systems Engineering-Theory & Practice, 2001(8):97-101.
[7] SABUNCUOGLU I, COMLEKCI A. Operation-based flowtime estimation in a dynamic job shop[J]. Omega, 2002, 30(6):423-442.
[8] DOMINIC P D D, KALIYAMOORTHY S, KUMAR M S. Efficient dispatching rules for dynamic job shop scheduling[J]. International Journal of Advanced Manu-Facturing Technology, 2004, 24(1-2):70-75.
[9] 刘琳, 谷寒雨, 席裕庚. 工件到达时间未知的动态车间滚动重调度[J]. 机械工程学报, 2008, 44(5):68-75. LIU Lin, GU Hanyu, XI Yugeng. Reschedluing algorithm based on rolling horizon decomposition for a dynamic job shop with uncertain arriving time[J]. Journal of Mecha-nical Engineering, 2008, 44(5):68-75.
[10] KAPANOGLU M, ALIKALFA M. Learning IF-THEN priority rules for dynamic job shops using genetic algorithms[J]. Robotics and Computer Integrated Manu-facturing, 2011, 27(1):47-55.
[11] KORYTKOWSKI P, WIŚNIEWSKI T, RYMASZEWSKI S. An evolutionary simulation-based optimization approach for dispatching scheduling[J]. Simulation Modelling Practice and Theory, 2013, 35(6):69-85.
[12] SCHOLZ-REITER B, HILDEBRANDT T, TAN Y. Effective and efficient scheduling of dynamic job shops:Combining the shifting bottleneck procedure with variable neighbourhood search[J]. CIRP Annals-Manufacturing Technology, 2013, 62(1):423-426.
[13] PERGHER I, ALMEIDA A T. A multi-attribute, rank-dependent utility model for selecting dispatching rules[J]. Journal of Manufacturing Systems, 2018, 46(1):264-271.
[14] 范华丽, 熊禾根, 蒋国璋, 等. 基于遗传规划的动态作业车间调度规则生成[J]. 计算机集成制造系统, 2018, 24(4):876-885. FAN Huali, XIONG Hegen, JIANG Guozhang, et al. Research on the generation of dispatching rules for dynamic Job-shop scheduling problem based on genetic programming algorithm[J]. Computer Integrated Manu-facturing Systems, 2018, 24(4):876-885.
[15] VINOD V, SRIDHARAN R. Scheduling a dynamic job shop production system with sequence-dependent setups:An experimental study[J]. Robotics and Computer-Integrated Manufacturing, 2008, 24(3):435-449.
[16] SHARMA P, JAIN A. Performance analysis of dispatching rules in a stochastic dynamic job shop manu-facturing system with sequence-dependent setup times:Simulation approach[J]. CIRP Journal of Manufacturing Science and Technology, 2015, 10(8):110-119.
[17] 汪双喜, 张超勇, 刘琼, 等. 不同再调度周期下的柔性作业车间动态调度[J]. 计算机集成制造系统, 2014, 20(10):2470-2478. WANG Shuangxi, ZHANG Chaoyong, LIU Qiong, et al. Flexible job shop dynamic scheduling under different rescheduling period[J]. Computer Integrated Manufacturing Systems, 2014, 20(10):2470-2478.
[18] SHEN Xiaoning, YAO Xin. Mathematical modeling and multi-objective evolutionary algorithms applied to dynamic flexible job shop scheduling problems[J]. Information Sciences, 2015, 298(3):198-224.
[19] ZHOU Yong, YANG Jianjun. Automatic design of scheduling policies for dynamic flexible job shop sche-duling by multi-objective genetic programming based hyper-heuristic[J]. Procedia CIRP, 2019, 79:439-444.
[20] MOHANASUNDARAM K M, NATARAJAN K, VISWANATHKUMAR G, et al. Scheduling rules for dynamic shops that manufacture multi-level jobs[J]. Computers & Industrial Engineering, 2003, 44(1):119-131.
[21] THIAGARAJAN S, RAJENDRAN C. Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs[J]. Computers & Industrial Engineering, 2005, 49(4):463-503.
[22] 边志兴. 作业车间的模糊动态调度问题研究[J]. 中国管理科学, 2008, 16(8):76-83. BIAN Zhixing. Study on the fuzzy dynamic scheduling under the job shop environments[J]. Chinese Journal of Management Science, 2008, 16(8):76-83.
[23] HOLTHAUS O. Scheduling in job shops with machine breakdowns:An experimental study[J]. Computers and Industrial Engineering, 1999, 36(99):137-162.
[24] KUTANOGLU E, SABUNCUOGLU I. Experimental investigation of iterative simulation-based scheduling in a dynamic and stochastic job shop[J]. Journal of Manufacturing Systems, 2001, 20(4):264-279.
[25] ADIBI M A, ZANDIEH M, AMIRI M. Multi-objective scheduling of dynamic job shop using variable neigh-borhood search[J]. Expert Systems with Applications, 2010, 37(1):282-287.
[26] QIU X, LAU H Y K. An AIS-based hybrid algorithm with PDRs for multi-objective dynamic online job shop scheduling problem[J]. Applied Soft Computing, 2013, 13(3):1340-1351.
[27] SWEENEY K D, SWEENEY Ⅱ D C, CAMPBELL J F. The performance of priority dispatching rules in a complex job shop:A study on the Upper Mississippi River[J]. International Journal of Production Economics, 2019, 216(10):154-172.
[28] SHAHRABI J, ADIBI M A, MAHOOTCHI M. A reinforcement learning approach to parameter estimation in dynamic job shop scheduling[J]. Computers & Industrial Engineering, 2017, 110(8):75-82.
[29] 连坤雷, 张超勇, 高亮, 等. 一种基于改进遗传算法的多目标动态调度优化[J]. 中国制造业信息化, 2010, 39(3):13-17. LIAN Kunlei, ZHANG Chaoyong, GAO Liang, et al. An improved genetic algorithm for multi-objective dynamic scheduling optimization[J]. Manufacturing Information Engineering of China, 2010, 39(3):13-17.
[30] 王万良, 王磊, 王海燕, 等. 基于混合差分进化算法的作业车间动态调度[J]. 计算机集成制造系统, 2012, 18(3):531-539. WANG Wanliang, WANG Lei, WANG Haiyan, et al. Dyamic job shop scheduling based on hybrid differential evolution algorithm[J]. Computer Integrated Manufacturing Systems, 2012, 18(3):531-539.
[31] KUNDAKCI N, KULAK O. Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem[J]. Computers & Industrial Engineering, 2016, 96(6):31-51.
[32] 熊禾根, 李建军, 孔建益, 等. 考虑工序相关性的动态Job shop调度问题启发式算法[J]. 机械工程学报, 2006, 42(8):50-55. XIONG Hegen, LI Jianjun, KONG Jianyi, et al. Heuristic method for dynamic job shop scheduling problem with operation relativity[J]. Journal of Mechanical Engineering, 2006, 42(8):50-55.
[33] XIONG Hegen, FAN Huali, JIANG Guozhang. A simulation-based study of dispatching rules in a dynamic job shop scheduling problem with batch release and extended technical precedence constraints[J]. European Journal of Operational Research, 2017, 257(1):13-24.
[34] JACKSON J R. Jobshop-like queueing systems[J]. Management Science, 1963, 10(1):518-521.
[35] LENSTRA J K, RINNOOY KAN A H G, BRUCKER P. Complexity of machine scheduling problems[J]. Annals of Discrete Mathematics, 1977, 1(12):343-362.
[36] PERGHER I, ALMEIDA A T. A multi-attribute, rank-dependent utility model for selecting dispatching rules[J]. Journal of Manufacturing Systems, 2018, 46(1):264-271.
[37] KENYON G, CANEL C NEUREUTHER B D. The impact of lot-sizing on net profits and cycle times in the n-job, m-machine job shop with both discrete and batch processing[J]. International Journal of Production Economics, 2005, 97(3):263-278.
[38] SUBRAMANIAMV, RAMESHT, LEE G K, et al. Job shop scheduling with dynamic fuzzy selection of dispa-tching rules[J]. The International Journal of Advanced Manufacturing Technology, 2000, 16(10):759-764.
[39] CHANG F R. A study of due-date assignment rules with constrained tightness in a dynamic job shop[J]. Computers & Industrial Engineering, 1996, 31(1-2):205-208.
[40] GÜÇDEMIR H, SELIMH. Customer centric production planning and control in job shops:A simulation optimization approach. Journal of Manufacturing Systems[J], 2017, 43(4):100-116.
[41] GÜÇDEMIR H, SELIMH. Integrating simulation mode-lling and multi criteria decision making for customer focused scheduling in job shops[J]. Simulation Modelling Practice and Theory, 2018, 88(11):17-31.
[42] BLOCHER J D, CHHAJED D, LEUNG M. Customer order scheduling in a general job shop environment[J]. Decision Sciences, 1998, 29(4):951-981.
[43] 徐华, 张庭. 混合离散蝙蝠算法求解多目标柔性作业车间调度[J]. 机械工程学报, 2016, 52(18):201-212. XU Hua, ZHANG Ting. Hybrid discrete bat algorithm for solving the multi-objective flexible job shop scheduling problem[J]. Journal of Mechanical Engineering, 2016, 52(18):201-212.
[44] 何彦, 王乐祥, 李育锋, 等. 一种面向机械车间柔性工艺路线的加工任务节能调度方法[J]. 机械工程学报, 2016, 52(19):168-179. HE Yan, WANG Lexiang, LI Yufeng, et al. A scheduling method for reducing energy consumption of machining job shops considering the flexible process plan[J]. Journal of Mechanical Engineering, 2016, 52(19):168-179.
[45] 李聪波, 沈欢, 李玲玲, 等. 面向能耗的多工艺路线柔性作业车间分批优化调度模型[J]. 机械工程学报, 2017, 53(5):12-23. LI Congbo, SHEN Huan, LI Lingling, et al. A batch splitting flexible job shop scheduling model for energy saving under alternative process plans[J]. Journal of Mechanical Engineering, 2017, 53(5):12-23.