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

doi:10.3901/JME.2021.04.227

Abstract

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

CLC Number:

TP18

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.

References

[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.