A polynomial-time algorithm for a flow-shop batching problem with equal-length operations
Autor(en): | Brucker, Peter Shakhlevich, Natalia V. |
Stichwörter: | Batch scheduling; Engineering; Engineering, Manufacturing; Flow shop; JOBS; Operations Research & Management Science; Polynomial-time algorithm; SHOP; SINGLE-MACHINE | Erscheinungsdatum: | 2011 | Herausgeber: | SPRINGER | Journal: | JOURNAL OF SCHEDULING | Volumen: | 14 | Ausgabe: | 4 | Startseite: | 371 | Seitenende: | 389 | Zusammenfassung: | 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. Cheng et al. (Naval Research Logistics 47:128-144, 2000) provided an O(n) pseudopolynomial-time algorithm for solving the special case of the problem with two machines. Mosheiov and Oron (European Journal of Operational Research 161: 285291, 2005) developed an algorithm of the same time complexity for the general case with more than two machines. Ng and Kovalyov (Journal of Scheduling 10: 353-364, 2007) improved the pseudopolynomial complexity to O(root n). In this paper, we provide a polynomial-time algorithm of time complexity O(log(3)n). |
ISSN: | 10946136 | DOI: | 10.1007/s10951-009-0150-8 |
Show full item record