双资源约束的鲁棒Job Shop调度问题研究

doi:10.3901/JME.2021.04.227

机械工程学报 ›› 2021, Vol. 57 ›› Issue (4): 227-239.doi: 10.3901/JME.2021.04.227

扫码分享

双资源约束的鲁棒Job Shop调度问题研究

肖世昌¹, 吴自高², 孙树栋², 金梅³

1. 上海海事大学物流工程学院上海 201306;
2. 西北工业大学机电学院西安 710072;
3. 中国航发西安航空发动机有限公司西安 710021

收稿日期:2020-04-07 修回日期:2020-10-08 出版日期:2021-02-20 发布日期:2021-04-28
通讯作者: 肖世昌(通信作者),男,1987年出生,博士,讲师。主要研究方向为物流/制造系统建模及调度优化算法。E-mail:scxiao@shmtu.edu.cn;xiaoshichangx@163.com
作者简介:吴自高,男,1989年出生,博士研究生。主要研究方向为生产调度优化。E-mail:feirenzhanshen@126.com;孙树栋,男,1963年出生,博士,教授,博士研究生导师。主要研究方向为先进制造系统,机器人控制。E-mail:sdsun@nwpu.edu.cn;金梅,女,1967年出生,研究员级高级工程师。主要研究方向为企业信息化,制造系统集成和制造执行系统等。E-mail:mail_jinmei@126.com
基金资助:
国家自然科学基金（51775435）、上海市科技创新行动计划软科学重点（20692193300）和上海高校青年教师培养资助计划（ZZSH20010）资助项目。

Research on the Dual-resource Constrained Robust Job Shop Scheduling Problems

XIAO Shichang¹, WU Zigao², SUN Shudong², JIN Mei³

1. Logistics Engineering College, Shanghai Maritime University, Shanghai 201306;
2. School of Mechanical Engineering, Northwestern Polytechnical University, Xi'an 710072;
3. AECC Xi'an Aero-Engine Ltd., Xi'an 710021

Received:2020-04-07 Revised:2020-10-08 Online:2021-02-20 Published:2021-04-28

摘要/Abstract

摘要： 针对机器-工人双资源约束下加工时间具有随机性的Job shop调度问题（Job shop scheduling problems，JSSP），考虑工人熟练程度差异和工人数量不足的约束，采用鲁棒调度的方法建立机器-工人双资源约束的鲁棒Job shop调度模型（Dual-resource constrained robust JSSP，DR-RJSSP）。鉴于DR-RJSSP同时考虑工人合理指派和双目标优化，提出机器-工人两阶段指派方法，在主动降低加工时间随机扰动的同时最小化工人约束对调度性能的影响。其次，提出多目标混合分布估计算法求解DR-RJSSP，以得到兼顾调度性能和鲁棒性的Pareto解集。最后，采用8组仿真算例将所提出的兼顾工人熟练程度和负载均衡的指派策略与基于熟练程度的指派策略和随机指派策略进行对比，验证了所提指派策略的Pareto优化性能。此外，通过对制造企业调度案例的仿真分析，验证了基于两阶段指派策略的MO-HEDA求解DR-RJSSP的有效性。

关键词: 双资源, 鲁棒Job shop调度问题, 两阶段指派策略, 鲁棒性

Abstract: The Job shop scheduling problems with stochastic processing times under machine-worker dual resource constraints is studied. Considering the difference in worker proficiency and the insufficient number of workers, a robust scheduling approach is adopted, and then the machine-worker dual-resource constrained robust Job shop scheduling problems model (DR-RJSSP) is formulated. Because of the requirements of DR-RJSSP for workers' rational assignment and bi-objective optimization, a heuristic based on a two-stage assignment strategy is proposed, which can minimize the random disturbances of the processing times as well as its impact on scheduling efficiency. Thereafter, a multi-objective hybrid estimation of distribution algorithm is employed to solve the DR-RJSSP. Thereby, the solution set considers both the performance and the robustness of the schedule can be obtained. At last, the proposed two-stage assignment strategy(TSAS) is compared with the proficiency-based assignment strategy as well as the machine-worker randomly assigned strategy through simulation experiments. Finally, eight standard instances and a problem instance obtained from a manufacturing company are employed. According to the simulation results, the Pareto optimization performance of the proposed TSAS and its effectiveness to solve the Job shop scheduling problem of the actual manufacturing system are verified.

Key words: dual-resource, robust job shop scheduling problems, two-stage assignment strategy, robustness

中图分类号:

TP18

肖世昌, 吴自高, 孙树栋, 金梅. 双资源约束的鲁棒Job Shop调度问题研究[J]. 机械工程学报, 2021, 57(4): 227-239.

XIAO Shichang, WU Zigao, SUN Shudong, JIN Mei. Research on the Dual-resource Constrained Robust Job Shop Scheduling Problems[J]. Journal of Mechanical Engineering, 2021, 57(4): 227-239.

参考文献

[1] LAWRENCE S R,SEWELL E C. Heuristic,optimal,static,and dynamic schedules when processing times are uncertain[J]. Journal of Operations Management,1997,15(1):71-82.
[2] SINGER M. Forecasting policies for scheduling a stochastic due date Job shop[J]. International Journal of Production Research,2000,38(15):3623-3637.
[3] OUELHADJ D,PETROVIC S. A survey of dynamic scheduling in manufacturing systems[J]. Journal of Scheduling,2009,12(4):417-431.
[4] AYTUG H,LAWLEY M A,MCKAY K,et al. Executing production schedules in the face of uncertainties:A review and some future directions[J]. European Journal of Operational Research,2005,161(1):86-110.
[5] XIAO S,SUN S,JIN J. Surrogate measures for the robust scheduling of stochastic job shop scheduling problems[J]. Energies,2017,10(4):543.
[6] 张映锋,赵曦滨,孙树栋,等. 一种基于物联技术的制造执行系统实现方法与关键技术[J]. 计算机集成制造系统,2012,18(12):2634-2642. ZHANG Yingfeng,ZHAO Xibin,SUN Shudong,et al. Implementing method and key technologies for IoT-based manufacturing execution system[J]. Computer Integrated Manufacturing Systems,2012,18(12):2634-2642.
[7] ZHANG Y,ZHANG G,WANG J,et al. Real-time information capturing and integration framework of the internet of manufacturing things[J]. International Journal of Computer Integrated Manufacturing,2012,121-126(8):4059-4063.
[8] HERROELEN W,LEUS R. Project scheduling under uncertainty:Survey and research potentials[J]. European Journal of Operational Research,2005,165(2):289-306.
[9] SABUNCUOGLU I,GOREN S. Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research[J]. International Journal of Computer Integrated Manufacturing,2009,22(2):138-157.
[10] XIONG J,XING L N,CHEN Y W. Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns[J]. International Journal of Production Economics,2013,141(1):112-126.
[11] WU Z,SUN S,XIAO S. Risk measure of job shop scheduling with random machine breakdowns[J]. Computers & Operations Research,2018(99):1-12.
[12] MEHTA S V,UZSOY R. Predictable scheduling of a single machine subject to breakdowns[J]. International Journal of Computer Integrated Manufacturing,1999,12(1):15-38.
[13] LI J,HUANG Y,NIU X. A branch population genetic algorithm for dual-resource constrained Job shop scheduling problem[J]. Computers & Industrial Engineering,2016,102:113-131.
[14] 李兢尧,孙树栋,黄媛,等. 双资源约束作业车间调度算法研究[J]. 机械工程学报,2010,46(22):175-181. LI Jingyao,SUN Shudong,HUANG Yuan,et al. Algorithm for dual resource constrained Job Shop scheduling[J]. Journal of Mechanical Engineering,2010,46(22):175-181.
[15] AGNETIS A,MURGIA G,SBRILLI S. A Job shop scheduling problem with human operators in handicraft production[J]. International Journal of Production Research,2013,52(13):3820-3831.
[16] MENCÍA R,SIERRA M R,MENCÍA C,et al. A genetic algorithm for Job-shop scheduling with operators enhanced by weak Lamarckian evolution and search space narrowing[J]. Natural Computing,2013,13(2):179-192.
[17] GU J,GU M,CAO C,et al. A novel competitive co-evolutionary quantum genetic algorithm for stochastic Job shop scheduling problem[J]. Computers & Operations Research,2010,37(5):927-937.
[18] HORNG S C,LIN S S,YANG F Y. Evolutionary algorithm for stochastic Job shop scheduling with random processing time[J]. Expert Systems with Applications,2012,39(3):3603-3610.
[19] LEI D. Simplified multi-objective genetic algorithms for stochastic Job shop scheduling[J]. Applied Soft Computing,2011,11(8):4991-4996.
[20] JAMILI A. Robust Job shop scheduling problem:Mathematical models,exact and heuristic algorithms[J]. Expert Systems with Applications,2016,55:341-350.
[21] 肖世昌,孙树栋,国欢,等. 求解随机Job shop调度问题的混合分布估计算法[J]. 机械工程学报,2015,51(20):27-35. XIAO Shichang,SUN Shudong,GUO Huan,et al. Hybrid estimation of distribution algorithm for solving the stochastic Job shop scheduling problem[J]. Journal of Mechanical Engineering,2015,51(20):27-35.
[22] HO Y C,SREENIVAS R S,VAKILI P. Ordinal optimization of DEDS[J]. Discrete Event Dynamic Systems,1992,2(1):61-88.
[23] DANIELS R L,KOUVELIS P. Robust scheduling to hedge against processing time uncertainty in single-stage production[J]. Management Science,1995,41(2):363-376.
[24] GOREN S,SABUNCUOGLU I. Robustness and stability measures for scheduling:single-machine environment[J]. IIE Transactions,2008,40(1):66-83.
[25] JORGE L V,DAVID W S,STORER R H. Robustness measures and robust scheduling for Job shops[J]. IIE Transactions,1994,26(5):32-43.
[26] GOREN S,SABUNCUOGLU I,KOC U. Optimization of schedule stability and efficiency under processing time variability and random machine breakdowns in a Job shop environment[J]. Naval Research Logistics,2012,59(1):26-38.
[27] SALMASNIA A,KHATAMI M,KAZEMZADEH R B,et al. Bi-objective single machine scheduling problem with stochastic processing times[J]. TOP,2015,23(1):275-297.
[28] CHAARI T,CHAABANE S,LOUKIL T,et al. A genetic algorithm for robust hybrid flow shop scheduling[J]. International Journal of Computer Integrated Manufacturing,2011,24(9):821-833.
[29] WU S D,BYEON E S,STORER R H. A graph-theoretic decomposition of the Job shop scheduling problem to achieve scheduling robustness[J]. Operations Research,1999,47(1):113-124.
[30] SIERRA M R,MENCÍA C,VARELA R. New schedule generation schemes for the job-shop problem with operators[J]. Journal of Intelligent Manufacturing,2013,26(3):511-525.
[31] DEB K,PRATAP A,AGARWAL S,et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[32] 肖世昌,孙树栋,杨宏安. 混合分布估计算法求解随机Job shop提前/拖期调度问题[J]. 控制与决策,2015(10):1854-1860. XIAO Shichang,SUN Shudong,YANG Hongan. Hybrid estimation of distribution algorithm for stochastic Job shop scheduling with earliness/tardiness penalty[J]. Control & Decision,2015(10):1854-1860.
[33] ONTGOMERY D C. Design and analysis of experiments[M]. New York:Wiley,1976.
[34] HMADIZAR F,GHAZANFARI M,FATEMI GHOMI S M T. Group shops scheduling with makespan criterion subject to random release dates and processing times[J]. Computers & Operations Research,2010,37(1):152-162.
[35] MUTH J F,THOMPSON G L. Industrial scheduling[M]. New Jersey:Prentice-Hall,1963.
[36] LAWRENCE S. Resource constrained project scheduling:an experimental investigation of heuristic scheduling techniques (Supplement)[D]. Pennsylvania:Carnegie-Mellon University,1984.

双资源约束的鲁棒Job Shop调度问题研究

Research on the Dual-resource Constrained Robust Job Shop Scheduling Problems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	梁志珍, 王晓佳. 双资源约束的柔性作业车间鲁棒调度方法[J]. 机械工程学报, 2024, 60(6): 114-126.
[2]	李鑫, 杨宇, 程健, 程军圣. 基于鲁棒不平衡凸包分类的锥齿轮箱故障诊断方法[J]. 机械工程学报, 2023, 59(8): 32-41.
[3]	郭鑫, 颜黎明, 田顺, 杨阳. 基于自校正模型的永磁同步电机鲁棒预测转矩控制^*[J]. 电气工程学报, 2021, 16(3): 9-16.
[4]	李琰, 吴妍瑜, 徐天奇. 电力信息耦合网络电力侧对信息侧鲁棒性影响研究 ^*[J]. 电气工程学报, 2020, 15(4): 27-34.
[5]	俞沛宙,杨刚,杨继辉,张宇华,薛花,黄珂. 基于自适应反推的永磁同步电动机转速控制策略^*[J]. 电气工程学报, 2020, 15(3): 38-43.
[6]	蒋正荣,黎佳慧,张智瑜. 高压除尘电源中的移相控制技术[J]. 电气工程学报, 2019, 14(1): 61-65.
[7]	周亚勤, 杨长祺, 吕佑龙, 金永乔, 张洁. 双资源约束的航天结构件车间生产调度方法[J]. 机械工程学报, 2018, 54(9): 55-63.
[8]	张永昌,焦健,刘杰. 电压型PWM整流器无模型预测电流控制[J]. 电气工程学报, 2018, 13(6): 1-6.
[9]	魏琼, 焦宗夏, 吴帅, 王君, 汤亮. 气动伺服加载系统的非线性复合控制[J]. 机械工程学报, 2017, 53(14): 217-224.
[10]	张永昌,高素雨. 考虑延时补偿的永磁同步电机电流预测控制[J]. 电气工程学报, 2016, 11(3): 13-20.
[11]	刘阔, 孙名佳, 吴玉亮, 朱铁军. 无温度传感器的数控机床进给轴热误差补偿^*[J]. 机械工程学报, 2016, 52(15): 162-169.
[12]	余卓平, 徐松云, 熊璐, 广学令. 集成式电子液压制动系统鲁棒性液压力控制[J]. 机械工程学报, 2015, 51(16): 22-28.
[13]	韦进文;陈燕玲;覃禾群;郭俊杰. 基于广义叉积鲁棒性的识别式数据拟合[J]. , 2011, 47(14): 7-12.
[14]	李兢尧;孙树栋;黄媛;王宁. 双资源约束作业车间调度算法研究[J]. , 2010, 46(22): 175-181.
[15]	周吴;何晓平;苏伟;张凤田;李柏林. 基于误差灵敏度的静电刚度式谐振微加速度计频率鲁棒性设计[J]. , 2010, 46(10): 14-18.