Abstract: An important production planning problem is how to best schedule jobs (or lots) when each job consists of a large number of identical parts. This problem is often approached by breaking each job/lot into sublots (termed lot streaming). When the total number of transfer sublots in lot streaming is large, the computational effort to calculate job completion time can be significant. However, researchers have largely neglected this computation time issue. To provide a practical method for production scheduling for this situation, we propose a method to address the n-job, m-machine, and lot streaming flow-shop scheduling problem. We consider the variable sublot sizes, setup time, and the possibility that transfer sublot sizes may be bounded because of capacity constrained transportation activities. The proposed method has three stages: initial lot splitting, job sequencing optimization with efficient calculation of the makespan/total flow time criterion, and transfer adjustment. Computational experiments are conducted to confirm the effectiveness of the three-stage method. The experiments reveal that relative to results reported on lot streaming problems for five standard datasets, the proposed method saves substantial computation time and provides better solutions, especially for large-size problems.

一种流水车间批量调度的高效计算三阶段优化方法

[1]Baker KR, 1995. Lot streaming in the two-machine flow shop with setup times. Ann Oper Res, 57(1):1-11.

[2]Biskup D, Feldmann M, 2006. Lot streaming with variable sublots: an integer programming formulation. J Oper Res Soc, 57(3):296-303.

[3]Chakaravarthy GV, Marimuthu S, Sait AN, 2013. Performance evaluation of proposed differential evolution and particle swarm optimization algorithms for scheduling m-machine flow shops with lot streaming. J Intell Manuf, 24(1):175-191.

[4]Chakaravarthy GV, Marimuthu S, Ponnambalam SG, et al., 2014. Improved sheep flock heredity algorithm and artificial bee colony algorithm for scheduling m-machine flow shops lot streaming with equal size sub-lot problems. Int J Prod Res, 52(5):1509-1527.

[5]Cheng M, Mukherjee NJ, Sarin SC, 2013. A review of lot streaming. Int J Prod Res, 51(23-24):7023-7046.

[6]Davendra D, Senkerik R, Zelinka I, et al., 2014. Utilising the chaos-induced discrete self organising migrating algorithm to solve the lot-streaming flowshop scheduling problem with setup time. Soft Comput, 18(4):669-681.

[7]Defersha FM, Chen MY, 2010. A hybrid genetic algorithm for flowshop lot streaming with setups and variable sublots. Int J Prod Res, 48(6):1705-1726.

[8]Defersha FM, Chen MY, 2011. A genetic algorithm for one-job m-machine flowshop lot streaming with variable sublots. Int J Oper Res, 10(4):458-468.

[9]Han YY, Gong DW, Jin YC, et al., 2016. Evolutionary multi-objective blocking lot-streaming flow shop scheduling with interval processing time. Appl Soft Comput, 42:229-245.

[10]Kim K, Jeong IJ, 2009. Flow shop scheduling with no-wait flexible lot streaming using an adaptive genetic algorithm. Int J Adv Manuf Technol, 44(11-12):1181-1190.

[11]Kumar S, Bagchi TP, Sriskandarajah C, 2000. Lot streaming and scheduling heuristics for m-machine no-wait flowshops. Comput Ind Eng, 38(1):149-172.

[12]Liu JY, 2008. Single-job lot streaming in m-1 two-stage hybrid flowshops. Eur J Oper Res, 187(3):1171-1183.

[13]Liu SC, 2003. A heuristic method for discrete lot streaming with variable sublots in a flow shop. Int J Adv Manuf Technol, 22(9-10):662-668.

[14]Marimuthu S, Ponnambalam SG, Jawahar N, 2008. Evolutionary algorithms for scheduling m-machine flow shop with lot streaming. Robot Comput Integr Manuf, 24(1): 125-139.

[15]Marimuthu S, Ponnambalam SG, Jawahar N, 2009. Threshold accepting and ant-colony optimization algorithms for scheduling m-machine flow shops with lot streaming. J Mater Process Technol, 209(2):1026-1041.

[16]Martin CH, 2009. A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming. Omega, 37(1): 126-137.

[17]Mukherjee NJ, Sarin SC, Singh S, 2017. Lot streaming in the presence of learning in sublot-attached setup times and processing times. Int J Prod Res, 55(6):1623-1639.

[18]Nejati M, Mahdavi I, Hassanzadeh R, et al., 2014. Multi-job lot streaming to minimize the weighted completion time in a hybrid flow shop scheduling problem with work shift constraint. Int J Adv Manuf Technol, 70(1-4):501-514.

[19]Nejati M, Mahdavi I, Hassanzadeh R, et al., 2016. Lot streaming in a two-stage assembly hybrid flow shop scheduling problem with a work shift constraint. J Ind Prod Eng, 33(7):459-471.

[20]Onwubolu G, Davendra D, 2006. Scheduling flow shops using differential evolution algorithm. Eur J Oper Res, 171(2): 674-692.

[21]Pan QK, Suganthan PN, Liang JJ, et al., 2011. A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem. Expert Syst Appl, 38(4):3252-3259.

[22]Reiter S, 1966. A system for managing job-shop production. J Bus, 39(3):371-393.

[23]Sarin SC, Kalir AA, Chen M, 2008. A single-lot, unified cost-based flow shop lot-streaming problem. Int J Prod Econ, 113(1):413-424.

[24]Storn R, Price K, 1997. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces. J Glob Optim, 11(4):341-359.

[25]Tasgetiren MF, Pan QK, Suganthan PN, et al., 2013. A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem. Comput Oper Res, 40(7):1729-1743.

[26]Tseng CT, Liao CJ, 2008. A discrete particle swarm optimization for lot-streaming flowshop scheduling problem. Eur J Oper Res, 191(2):360-373.

[27]Ventura JA, Yoon SH, 2013. A new genetic algorithm for lot-streaming flow shop scheduling with limited capacity buffers. J Intell Manuf, 24(6):1185-1196.

[28]Wang L, Pan QK, Suganthan PN, et al., 2010. A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems. Comput Oper Res, 37(3):509-520.