DC Element | Wert | Sprache |
dc.contributor.author | Brucker, Peter | |
dc.contributor.author | Shakhlevich, Natalia V. | |
dc.date.accessioned | 2021-12-23T16:07:06Z | - |
dc.date.available | 2021-12-23T16:07:06Z | - |
dc.date.issued | 2011 | |
dc.identifier.issn | 10946136 | |
dc.identifier.uri | https://osnascholar.ub.uni-osnabrueck.de/handle/unios/7711 | - |
dc.description.abstract | 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). | |
dc.description.sponsorship | EPSRCUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/D059518]; EPSRCUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/D059518/1] Funding Source: UKRI; Engineering and Physical Sciences Research CouncilUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/D059518/1] Funding Source: researchfish; This research was partly supported by the EPSRC funded project EP/D059518. The authors are grateful to an anonymous referee for his/her comments that considerably improved the paper. | |
dc.language.iso | en | |
dc.publisher | SPRINGER | |
dc.relation.ispartof | JOURNAL OF SCHEDULING | |
dc.subject | Batch scheduling | |
dc.subject | Engineering | |
dc.subject | Engineering, Manufacturing | |
dc.subject | Flow shop | |
dc.subject | JOBS | |
dc.subject | Operations Research & Management Science | |
dc.subject | Polynomial-time algorithm | |
dc.subject | SHOP | |
dc.subject | SINGLE-MACHINE | |
dc.title | A polynomial-time algorithm for a flow-shop batching problem with equal-length operations | |
dc.type | journal article | |
dc.identifier.doi | 10.1007/s10951-009-0150-8 | |
dc.identifier.isi | ISI:000292276900006 | |
dc.description.volume | 14 | |
dc.description.issue | 4 | |
dc.description.startpage | 371 | |
dc.description.endpage | 389 | |
dc.contributor.orcid | 0000-0002-5225-4008 | |
dc.publisher.place | VAN GODEWIJCKSTRAAT 30, 3311 GZ DORDRECHT, NETHERLANDS | |
dcterms.isPartOf.abbreviation | J. Sched. | |
dcterms.oaStatus | Green Accepted | |
crisitem.author.dept | Universität Osnabrück | - |
crisitem.author.orcid | 0000-0002-5225-4008 | - |
crisitem.author.netid | ShNa001 | - |