||In this research, we consider the problem of scheduling n jobs on hybrid flow shop with job splitting property, and our objective is to minimize the maximum completion time. In the past, the majority of scheduling studies assumed that each job can be processed on at most one machine at a time. In the real word, there are many cases that have different types of products and each type of products have numbers of units need to go through a production line. In order to make these products finished as soon as possible, it is normal to schedule each unit of the same product on different machines at the same time.|
In this research, we assume that there are two identical parallel machines in the first stage and a single machine in second stage, and the setup time of each job are independent. We use a branch and bound algorithm to find the optimal solution for this problem. In this algorithm, we propose the lower bound and upper bound for this scheduling problem and we use some dominance rules to eliminate unnecessary nodes to improve the efficiency of our algorithm. Finally, we implement this algorithm by JAVA, and we conduct the computational analysis.
|| Fattahi, P. et al. (2013), “A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations”, Applied Mathematical Modelling , Vol. 38, pp. 119–134|
 Brah, Shaukat A. et al. (1991) ”Branch and bound algorithm for the flowshop with multiple processors”, European Journal of Operation Research, Vol.51, pp. 88- 99.
 Portmann, M.C. et al. (1997) ”Branch and bound crossed with GA to solve hybrid fowshops”, European Journal of Operation Research, Vol. 107, pp.389-400.
 Allaoui, H. et al. (2004) ”Integrating simulation and optimization to schedule a hybrid flowshop with maintenance constraints”, Computers & Industrial Engineering, Vol. 47, pp.431– 450.
 Kim, Y.D. et al. (2004) ”Parallel machine scheduling considering a job-splitting property” , International Journal of Production Research, Vol. 42, pp.4531– 4546.
 Kis, Tamás et al. (2005) “A review of exact solution methods for the non-preemptive multiprocessor flowshop problem”, European Journal of Operation Research, Vol.164, pp.592-608.
 Xing Wenxun et al. (2000) “Parallel machine scheduling with splitting jobs”, Discrete Applied Mathematics, Vol.103, pp.259-269.
 Shim Sang-Oh et al. (2008) “A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property”, Computers & Operations Research, Vol. 35, pp.863 - 875
 Ruiz Ruben et al. (2010) “The hybrid flow shop scheduling problem”, European Journal of Operational Research, Vol.205, pp.1–18
 Rajendran, C. et al. (1992) ”Scheduling in n-job, m-stage floswhop with parallel processors to minimize makespan”, International Journal of Production Economics, Vol.27, pp.137–143.
 Gupta, J.N.D. et al. (1997) “Scheduling a two-stage hybrid flow shop with parallel machines at the first stage”, Annals of Operation Research, Vol.69 pp.171-191
 Gupta, J.N.D. et al. (1988) ”Two-stage hybrid flow shop scheduling problem”, Journal of the Operational Research Society Vol. 39, pp.359-364.
 Potts, C.N. et al. (1992) “Integrating scheduling with batching and lotsizing: a review of algorithm and complexity”, The Journal of the Operational Research Society Vol. 43(5), pp.395-406.
 Xing, W. et al. (1998) “Splitting parallel machine scheduling (in Chinese)”, Operation. Research Transactions”, Vol. 2, pp.30-41.
 Hoogeveen, J.A. et al. (1996) “Preemptive scheduling in a two-stage multiprocessors flow shop is NP-hard”, European Journal of Operational Research, Vol.89(1), pp.172-175.
[16 ] Haouari Mohamed et al. (2006) “Optimal Scheduling of a Two-Stage Hybrid Flow Shop”, Mathematical Methods of Operations Research, Volume 64, pp 107-124.