A note on flow-shop and job-shop batch scheduling with identical processing-time jobs. (English) Zbl 1067.90049
Summary: We address a batch scheduling problem of \(n\) identical processing time jobs on an \(m\)-machine flow-shop and a 2-machine job-shop. The objective is makespan minimization. Both problems are shown to be solved in \(O(n)\).
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Cheng, T. C.E.; Lin, B. M.T.; Toker, A., Makespan minimization in the two-machine flowshop batch scheduling problem, Naval Research Logistics, 47, 128-144 (2000) · Zbl 0973.90031 |
| [2] | C.T. Ng, M.Y. Kovalyov, Batching and scheduling in a multi-machine flow-shop, in submission; C.T. Ng, M.Y. Kovalyov, Batching and scheduling in a multi-machine flow-shop, in submission · Zbl 1153.90431 |
| [3] | Potts, C. N.; Kovalyov, M., Scheduling with batching: A review, European Journal of Operational Research, 120, 228-249 (2000) · Zbl 0953.90028 |
| [4] | Pinedo, M., Scheduling: Theory, Algorithms and Systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1145.90393 |
| [5] | Lenstra, J. K.; Rinnooy Kan, A. R.K., Computational complexity of discrete optimization problems, Annals of Discrete Mathematics, 4, 121-140 (1979) · Zbl 0411.68042 |
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.
