Three-Machine Flowshop Scheduling Problem to Minimize Total Completion Time with Bounded Setup and Processing Times
DOI:
https://doi.org/10.7494/dmms.2007.1.2.5Keywords:
scheduling, flowshop, dominance relations, bounded processing and setup timesAbstract
The three-machine flowshop scheduling problem to minimize total completion time is studied where setup times are treated as separate from processing times. Setup and processing times of all jobs on all machines are unknown variables before the actual occurrence of these times. The lower and upper bounds for setup and processing times of each job on each machine is the only information that is available. In such a scheduling environment, there may not exist a unique schedule that remains optimal for all possible realizations of setup and processing times. Therefore, it is desired to obtain a set of dominating schedules (which dominate all other schedules) if possible. The objective for such a scheduling environment is to reduce the size of dominating schedule set. We obtain global and local dominance relations for a three-machine flowshop scheduling problem. Furthermore, we illustrate the use of dominance relations by numerical examples and conduct computational experiments on randomly generated problems to measure the effectiveness of the developed dominance
relations. The computational experiments show that the developed dominance relations are quite helpful in reducing the size of dominating schedules.
References
Allahverdi A. (2006). Two-machine flowshop scheduling problem to minimize total completion time with bounded setup and processing times. International Journal of Production Economics, 103(1), pp. 386–400. DOI: https://doi.org/10.1016/j.ijpe.2005.10.002.
Allahverdi A. (2000). Minimizing mean flowtime in a two-machine flowshop with sequence-independent setup times. Computers & Operations Research, 27(2), pp. 111–127. DOI: https://doi.org/10.1016/S0305-0548(99)00010-6
Allahverdi A. & Al-Anzi F.S. (2006). A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times. European Journal of Operational Research, 169(3), pp. 767–780. DOI: https://doi.org/10.1016/j.ejor.2004.07.074
Allahverdi A., Ng C.T., Cheng T.C.E. & Kovalyov M.Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), pp. 985–1032. DOI: https://doi.org/10.1016/j.ejor.2006.06.060
Allahverdi A., Aldowaisan T. & Sotskov Y.N. (2003). Two-machine flowshop scheduling problem to minimize makespan or total completion time with random and bounded setup times. International Journal of Mathematics and Mathematical Sciences, 2003(39), pp. 2475–2486. DOI: https://doi.org/10.1155/S016117120321019X
Allahverdi A., Gupta J.N.D. & Aldowaisan T. (1999). A review of scheduling research involving setup considerations. Omega, 27(2), pp. 219–239. DOI: https://doi.org/10.1016/S0305-0483(98)00042-5
Allahverdi A. & Sotskov Y.N. (2003). Two-machine flowshop minimum-length scheduling problem with random and bounded processing times. International Transactions in Operational Research, 10(1), pp. 65–76. DOI: https://doi.org/10.1111/1475-3995.00393
Bagga P.C. & Khurana K. (1986). Two-machine flowshop with separated sequence-independent setup times: Mean completion time criterion. Indian Journal of Management and Systems, 2(1), pp. 47–57.
Chandrasekaran C., Rajendran C., Chetty O.V.K. & Hanumanna D. (2007). Metaheuristics for solving economic lot scheduling problems (ELSP) using time-varying lot-sizes approach. European Journal of Industrial Engineering, 1(2), pp. 152–181. DOI: https://doi.org/10.1504/EJIE.2007.014107.
Johnson S.M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), pp. 61–68. DOI: https://doi.org/10.1002/nav.3800010110.
Kim S.C. & Bobrowski P.M. (1997). Scheduling jobs with uncertain setup times and sequence dependency. Omega, 25(4), pp. 437–447. DOI: https://doi.org/10.1016/S0305-0483(97)00013-3.
Lai T.-C. & Sotskov Y.N. (1999). Sequencing with uncertain numerical data for makespan minimisation. Journal of the Operational Research Society, 50(3), pp. 230–243. DOI: https://doi.org/10.1057/palgrave.jors.2600690.
Lai T.-C., Sotskov Y.N., Sotskova N.Yu. & Werner F. (1997). Optimal makespan scheduling with given bounds of processing times. Mathematical and Computer Modelling, 26(3), pp. 67–86. DOI: https://doi.org/10.1016/S0895-7177(97)00132-5.
Li X., Ye N., Xu X. & Sawhey R. (2007). Influencing factors of job waiting time variance on a single machine. European Journal of Industrial Engineering, 1(1), pp. 56–73. DOI: https://doi.org/10.1504/EJIE.2007.012654.
Logendran R., Carson S. & Hanson E. (2005). Group scheduling in flexible flow shops. International Journal of Production Economics, 96(2), pp. 143–155. DOI: https://doi.org/10.1016/j.ijpe.2004.03.011.
Sotskov Y.N., Allahverdi A. & Lai T.-C. (2004). Flowshop scheduling problem to minimize total completion time with random and bounded processing times. Journal of the Operational Research Society, 55(3), pp. 277–286. DOI: https://doi.org/10.1057/palgrave.jors.2601682.
Tang L. & Huang L. (2007). Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production. International Journal of Production Economics, 105(2), pp. 357–371. DOI: https://doi.org/10.1016/j.ijpe.2004.04.011.
