A polynomial-time algorithm for a flow-shop batching problem with equal-length operations. (English) Zbl 1230.90087
Summary: A flow-shop batching problem with consistent batches is considered in which the processing times of all jobs on each machine are equal to \(p\) and all batch set-up times are equal to \(s\). In such a problem, one has to partition the set of jobs into batches and to schedule the batches on each machine. The processing time of a batch \(B_{i}\) is the sum of processing times of operations in \(B_{i}\) and the earliest start of \(B_{i}\) on a machine is the finishing time of \(B_{i}\) on the previous machine plus the set-up time \(s\). T. C. E. Cheng et al. [Nav. Res. Logist. 47, No. 2, 128–144 (2000; Zbl 0973.90031)] provided an \(O(n)\) pseudopolynomial-time algorithm for solving the special case of the problem with two machines. G. Mosheiov and D. Oron [Eur. J. Oper. Res. 161, No. 1, 285–291 (2005; Zbl 1067.90049)] developed an algorithm of the same time complexity for the general case with more than two machines. C. T. Ng and M. Y. Kovalyov [J. Sched. 10, No. 6, 353–364 (2007; Zbl 1153.90431)] improved the pseudopolynomial complexity to \(O(\sqrt{n})\). In this paper, we provide a polynomial-time algorithm of time complexity \(O(\log^{3} n)\).
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Brucker, P. (2004). Scheduling algorithms. Berlin: Springer. · Zbl 1060.90034 |
| [2] | Cheng, T. C. E., Lin, B. M. T., & Toker, A. (2000). Makespan minimization in the two-machine flow-shop 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-# |
| [3] | Mosheiov, G., & Oron, D. (2005). 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 |
| [4] | Mosheiov, G., & Oron, D. (2006). Single machine scheduling with batch-dependent setup times. Information Processing Letters, 98, 73–78. · Zbl 1187.68097 · doi:10.1016/j.ipl.2005.12.003 |
| [5] | Mosheiov, G., & Oron, D. (2008). Open-shop batch scheduling with identical jobs. European Journal of Operational Research, 187, 1282–1292. · Zbl 1137.90511 · doi:10.1016/j.ejor.2006.03.068 |
| [6] | 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 |
| [7] | Mosheiov, G., Oron, D., & Ritov, Y. (2005). Minimizing flow-time on a single machine with integer batch sizes. Operations Research Letters, 33, 497–501. · Zbl 1195.90043 · doi:10.1016/j.orl.2004.09.007 |
| [8] | Naddeff, D., & Santos, C. (1988). One-pass batching algorithms for the one-machine batching problem. Discrete Applied Mathematics, 21, 133–145. · Zbl 0661.90044 · doi:10.1016/0166-218X(88)90049-2 |
| [9] | Ng, C. T., & Kovalyov, M. Y. (2007). Batching and scheduling in a multi-machine flow shop. Journal of Scheduling, 10, 353–364. · Zbl 1153.90431 · doi:10.1007/s10951-007-0041-9 |
| [10] | Santos, C., & Magazine, M. (1985). Batching in single operation manufacturing systems. Operations Research Letters, 4, 99–103. · Zbl 0572.90051 · doi:10.1016/0167-6377(85)90011-2 |
| [11] | Shallcross, D. F. (1992). A polynomial algorithm for a one machine batching problem. Operations Research Letters, 11, 213–218. · Zbl 0760.90059 · doi:10.1016/0167-6377(92)90027-Z |
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.
