Two-stage scheduling on batch and single machines with limited waiting time constraint

Abstract

This study addresses the problem of two-stage scheduling on batch and single machines with limited waiting time constraint; thus, the makespan is minimized. A mixed-integer linear programming model is proposed for this problem. Three tight lower bounds and a heuristic algorithm are developed. The worst-case performance of the proposed algorithm is discussed. A hybrid differential evolution algorithm is also developed to improve the solution quantity. Numerical results show that the hybrid algorithm is capable of obtaining high-quality solutions and exhibits a competitive performance

Keywords

batch machine / flow shop / makespan / limited waiting time

References

[1] Ahmadi J H, Ahmadi R H, Dasu S, Tang C S (1992). Batching and scheduling jobs on batch and discrete processors. Operations Research, 39(4): 750–763

[2] Chung T P, Sun H, Liao C J (2016). Two new approaches for a two-stage hybrid flow shop problem with a single batch processing machine under waiting time constraint. Computers & Industrial Engineering, in press160;

[3] Fu Q, Sivakumar A I, Li K P (2012). Optimisation of flow-shop scheduling with batch processor and limited buffer. International Journal of Production Research, 50(8): 2267–2285

[4] Gong H, Tang L, Duin C W (2010). A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times. Computers & Operations Research, 37(5): 960–969 

[5] Hoogeveen H, Velde S (1998). Scheduling by positional completion times: analysis of a two-stage flow shop problem with a batching machine. Mathematical Programming, 82(1-2): 273–289

[6] Huang Z, Shi Z, Zhang C, Shi L (2017). A note on “Two new approaches for a two-stage hybrid flow shop problem with a single batch processing machine under waiting time constrain”. Computers & Industrial Engineering, 110: 590–593 

[7] Shao W, Pi D (2015). A self-guided differential evolution with neighborhood search for permutation flow shop scheduling. Expert Systems with Applications, 51: 161–176

[8] Storn R, Price K (1997). Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4): 341–359

[9] Su L H (2003). A hybrid two-stage flow shop with limited waiting time constraints. Computers & Industrial Engineering, 44(3): 409–424

[10] Wang H Y, Lu Y B, Peng W L (2013). Permutation flow-shop scheduling using a hybrid differential evolution algorithm. International Journal of Computing Science and Mathematics, 4(3): 298–307

[11] Yang D L, Chern M S (1995). A two-machine flow shop scheduling problem with limited waiting time constraints. Computers & Industrial Engineering, 28(1): 63–70

[12] Zhang C, Shi Z, Huang Z, Wu Y, Shi L (2017). Flow shop scheduling with a batch processor and limited buffer. International Journal of Production Research, 55(11): 3217–3233

Rights & permissions

The Author(s) 2017. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)