Research of Just-in-time Scheduling for Assembly Job Shop

doi:10.3901/JME.2021.05.157

Abstract

Abstract: Although job shop scheduling problem (JSP) has been extensively and intensively studied in the past few decades, most research aims at minimizing regular measures. The scheduling of the problems with regular measures only needs to process as early as possible. Compared with regular measures, minimizing the sum of earliness/tardiness penalties is a non-regular measure. For the scheduling problems with non-regular measures, it is impossible to optimize the goal by processing all the operations as early as possible, and the schedule generation process must be more complicated. Aiming at the scheduling problem with earliness and tardiness penalties, the subject of research is expanded from simple job shop (JSP) to assembly job shop (AJSP) to explore the general law of earliness and tardiness scheduling problems more widely. A three-stage adjustment heuristic is designed to generate a schedule, and the heuristic is combined with genetic algorithm for experimental analysis. Compared with the results of optimal results, the efficiency and effectiveness of the heuristic is proved. In addition, experimental results also reveal the impact of different methods in the process of generating a schedule, which may serve as guidelines for future research.

Key words: assembly job shop scheduling, earliness and tardiness cost, genetic algorithm, heuristic

CLC Number:

TP301

LÜ Haili, ZHU Jiatao, WANG Zhengguo, WU Shu. Research of Just-in-time Scheduling for Assembly Job Shop[J]. Journal of Mechanical Engineering, 2021, 57(5): 157-165.

References

[1] BAKER K,SCUDDER G. Sequencing with earliness and tardiness penalties:A review[J]. Operations Research,1990,38(1):22-36.
[2] SOURD F,KEDAD-SIDHOUM S. The one-machine problem with earliness and tardiness penalties[J]. Journal of Scheduling,2003,6(6):533-549.
[3] BECK J C,REFALO P. A hybrid approach to scheduling with earliness and tardiness costs[J]. Annals of Operations Research,2003,118(1-4):49-71.
[4] MOSLEHI G,MIRZAEE M,VASEI M,et al. Two-machine flow shop scheduling to minimize the sum of maximum earliness and tardiness[J]. International Journal of Production Economics,2009,122(2):763-773.
[5] DOULABI S H H,AVAZBEIGI M,ARAB S,et al. An effective hybrid simulated annealing and two mixed integer linear formulations for just-in-time open shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology,2012,59(9-12):1143-1155.
[6] REY G Z,BEKRAR A,TRENTESAUX D,et al. Solving the flexible job-shop just-in-time scheduling problem with quadratic earliness and tardiness costs[J]. The International Journal of Advanced Manufacturing Technology,2015,81(1):9-12.
[7] AL-SALEM M,BEDOYA V L,RABADI G. Heuristic and exact algorithms for the two-machine just in time job shop scheduling problem[J]. Mathematical Problems in Engineering,2016(PT.11):6591632.1-6591632.11.
[8] 李凯,周超,马英. 考虑释放时间的单机JIT调度问题[J]. 运筹与管理,2016,25(3):71-77. LI Kai,ZHOU Chao,MA Ying. single machine JIT scheduling problem considering the release time[J]. Operations Research and Management Science,2016,25(3):71-77.
[9] LEE C Y,CHOI J Y. A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights[J]. Computers & Operations Research,1995,22(8):857-869.
[10] 桂玲. 带有交货时间窗的提前/拖期调度问题研究[D].武汉:华中科技大学,2017. GUI Ling. Research on early/tardy scheduling problem with due windows[D]. Wuhan:Huazhong University of Science and Technology,2017.
[11] BAPTISTE P,FLAMINI M,SOURD F. Lagrangian bounds for just-in-time job-shop scheduling[J]. Computers and Operations Research,2008,35(3):906-915.
[12] SANTOS A G D,ARAUJO R P,ARROYO J E C. A combination of evolutionary algorithm,mathematical programming,and a new local search procedure for the just-in-time job-shop scheduling problem[C]//Learning and Intelligent Optimization,4th International Conference,LION 4,Venice,Italy,January 18-22,2010.
[13] 李海宁,孙树栋,杨宏安. TS/MP混合算法求解作业车间JIT调度问题[J]. 计算机集成制造系统,2012,18(6):1176-1181. LI Haining,SUN Shudong,YANG Hongan. Tabu search and mathematical programming for just-in-time job shop scheduling[J]. Computer Integrated Manufacturing Systems,2012,18(6):1176-1181.
[14] 杨宏安,齐亮亮,李锦远,等. 求解作业车间JIT调度问题的VNS/MP混合算法[J]. 计算机集成制造系统,2014,20(2):414-423. YANG Hongan,QI Liangliang,LI Jinyuan,et al. Hybrid algorithm of VNS/MP for JIT job-shop scheduling problem[J]. Computer Integrated Manufacturing Systems. 2014,20(2):414-423.
[15] AHMADIAN M M,SALEHIPOUR A,CHENG T C E. A meta-heuristic to solve the just-in-time job-shop scheduling problem[J]. European Journal of Operational Research,2020.
[16] MONETTE J,DEVILLE Y,HENTENRYCK P V. Just-in-time scheduling with constraint programming[C]//International Conference on Automated Planning & Scheduling. DBLP,2009.
[17] FAALAND B,SCHMITT T. Scheduling tasks with due dates in a fabrication/assembly process[J]. Operations Research,1987,35(3):378-388.
[18] 杨宏安,孙启峰,孙树栋,等. 基于遗传算法的作业车间提前/延迟调度问题[J]. 计算机集成制造系统,2011,17(8):1798-1805. YANG Hongan,SUN Qifeng,SUN Shudong,et al. Job shop earliness/tardiness scheduling problems based on genetic algrorithm[J]. Computer Integrated Manufacturing Systems,2011,17(8):1798-1805.
[19] BÜRGY R,BÜLBÜL K. The job shop scheduling problem with convex costs[J]. European Journal of Operational Research,2018,268(1):82-100.
[20] ROACH A,NAGI R. A hybrid GA-SA algorithm for just-in-time scheduling of multi-level assemblies[M]. Oxford:Pergamon Press,Inc. 1996.
[21] AGRAWAL A,HARHALAKIS G,MINIS I,et al. ‘Just-in-time’ production of large assemblies[J]. IIE Transactions,1996,28(8):653-667.
[22] CHEN K,JI P. A mixed integer programming model for advanced planning and scheduling(APS)[J]. European Journal of Operational Research,2007,181(1):515-522.
[23] CHEN K J,JI P. Development of a genetic algorithm for scheduling products with a multi-level structure[J]. International Journal of Advanced Manufacturing Technology,2007,33(11):1229-1236.
[24] SPRECHER A,KOLISCH R,DREXL A. Semi-active,active,and non-delay schedules for the resource-constrained project scheduling problem[J]. European Journal of Operational Research,1995,80(1):94-102.
[25] BEAN J C. Genetic algorithms and random keys for sequencing and optimization[J]. Informs Journal on Computing,1994,6:154-160.
[26] FOGEL D B. An introduction to simulated evolutionary optimization[J]. IEEE Transactions on Neural Networks,1994,5(1):3-14.