caa a22 4500 44583868X CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s10951-009-0150-8 doi (NATIONALLICENCE)springer-10.1007/s10951-009-0150-8 A polynomial-time algorithm for a flow-shop batching problem withequal-length operations [Elektronische Daten] [Peter Brucker, Natalia Shakhlevich] 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 times. 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:285-291, 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(\sqrt{n})$ . In this paper, we provide a polynomial-time algorithm of time complexity O(log 3 n). Springer Science+Business Media, LLC, 2009 Batch scheduling nationallicence Flow shop nationallicence Polynomial-time algorithm nationallicence Brucker Peter Fachbereich Mathematik/Informatik, Universität Osnabrück, 49069, Osnabrück, Germany aut Shakhlevich Natalia School of Computing, University of Leeds, LS2 9JT, Leeds, UK aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 371-389 1094-6136 14:4<371 2011 14 10951 https://doi.org/10.1007/s10951-009-0150-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-009-0150-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Brucker Peter Fachbereich Mathematik/Informatik, Universität Osnabrück, 49069, Osnabrück, Germany aut NATIONALLICENCE 700 1- Shakhlevich Natalia School of Computing, University of Leeds, LS2 9JT, Leeds, UK aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 371-389 1094-6136 14:4<371 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer