Batching and scheduling in a multi-machine flow shop. (English) Zbl 1153.90431
Summary: We study the problem of batching and scheduling \(n\) jobs in a flow shop comprising \(m, m\geq 2\), machines. Each job has to be processed on machines \(1,\cdots ,m\) in this order. Batches are formed on each machine. A machine dependent setup time precedes the processing of each batch. Jobs of the same batch are processed on each machine sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs of the same batch formed on machine \(l\) become available for a downstream operation on machine \(l+1\) at the same time when the processing of the last job of the batch on machine \(l\) has been finished. The objective is to minimize maximum job completion time. We establish several properties of an optimal schedule and develop polynomial time algorithms for important special cases. They are improvements over the existing methods with regard to their generality and time efficiency.
References:
| [1] | Bukchin, J., & Masin, M. (2004). Multi-objective lot splitting for a single product m-machine flow shop line. IIE Transactions, 36, 191–202. · Zbl 1056.90080 · doi:10.1080/07408170490245487 |
| [2] | Bukchin, J., Tzur, M., & Jaffe, M. (2002). Lot splitting to minimize average flow-time in a two machine flow shop. IIE Transactions, 34, 953–970. |
| [3] | Cheng, T. C. E., Lin, B. M. T., & Toker, A. (2000). Makespan minimization in the two-machine flowshop batch scheduling problem. Naval Research Logistics, 47, 128–144. · Zbl 0973.90031 · doi:10.1002/(SICI)1520-6750(200003)47:2<128::AID-NAV4>3.0.CO;2-# |
| [4] | Chin, H. N., & Chang, J. H. (2005, to appear). Cost models for lot streaming in a multistage flow shop, Omega. |
| [5] | Glass, C. A., Potts, C. N., & Strusevich, V. A. (2001). Scheduling batches with sequential job processing for two-machine flow and open shops. INFORMS Journal on Computing, 13, 120–137. · Zbl 1238.90064 · doi:10.1287/ijoc.13.2.120.10521 |
| [6] | Huq, F., Cutright, K., & Martin, C. (2004). Employee scheduling and makespan minimization in a flow shop with multiprocessor work stations: a case study. Omega, 32, 121–129. · doi:10.1016/j.omega.2003.09.014 |
| [7] | Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61–68. · Zbl 1349.90359 · doi:10.1002/nav.3800010110 |
| [8] | Kalir, A. A., & Sarin, S. C. (2000). Evaluation of potential benefits of lot streaming in flow shop systems. International Journal of Production Economics, 66, 131–142. · doi:10.1016/S0925-5273(99)00115-2 |
| [9] | Li, C.-L., & Xiao, W.-Q. (2004). Lot streaming with supplier-manufacturer coordination. Naval Research Logistics, 51, 522–542. · Zbl 1054.90024 · doi:10.1002/nav.20013 |
| [10] | Mosheiov, G., & Oron, D. (2004). A note on flow-shop and job-shop batch scheduling with identical processing-time jobs. European Journal of Operational Research, 161, 285–291. · Zbl 1067.90049 · doi:10.1016/j.ejor.2003.09.010 |
| [11] | Mosheiov, G., Oron, D., & Ritov, Y. (2004). Flow-shop batch scheduling with identical processing-time jobs. Naval Research Logistics, 51, 783–799. · Zbl 1075.90031 · doi:10.1002/nav.20028 |
| [12] | Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: a review. European Journal of Operational Research, 120, 228–249. · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8 |
| [13] | Potts, C. N., & Van Wassenhove, L. N. (1992). Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity. Journal of the Operational Research Society, 43, 395–406. · Zbl 0756.90050 |
| [14] | Tanaev, V. S., Kovalyov, M. Y., & Shafransky, Y. M. (1998). Scheduling theory. Group technologies. Minsk: IEC NASB (in Russian). |
| [15] | Tanaev, V. S., Gordon, V. S., & Shafransky, Y. M. (1994). Scheduling theory. One-stage systems. Dordrect: Kluwer Academic. · Zbl 0827.90079 |
| [16] | Tanaev, V. S., Sotskov, Y. N., & Strusevich, V. A. (1995). Scheduling theory. Multi-stage systems. Dordrecht: Kluwer Academic. · Zbl 0925.90224 |
| [17] | Trietsch, D., & Baker, K. R. (1993). Basic techniques for lot streaming. Operations Research, 41, 1065–1076. · Zbl 0791.90026 · doi:10.1287/opre.41.6.1065 |
| [18] | Webster, S., & Baker, K. R. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43, 692–703. · Zbl 0857.90062 · doi:10.1287/opre.43.4.692 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
