×

Transporting jobs through a processing center with two parallel machines. (English) Zbl 1311.90048

Wu, Weili (ed.) et al., Combinatorial optimization and applications. 4th international conference, COCOA 2010, Kailua-Kona, HI, USA, December 18–20, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-17457-5/pbk). Lecture Notes in Computer Science 6508, 408-422 (2010).
Summary: In this paper, we consider a processing system that consists of two identical parallel machines such that the jobs are delivered to the system by a single transporter and moved between the machines by the same transporter. The objective is to minimize the length of a schedule, i.e., the time by which the completed jobs are collected together on board the transporter. The jobs can be processed with preemption, provided that the portions of jobs are properly transported to the corresponding machines. We establish properties of feasible schedule, define lower bounds on the optimal length and describe an algorithm that behaves like a fully polynomial-time approximation scheme (FPTAS).
For the entire collection see [Zbl 1203.68018].

MSC:

90B35 Deterministic scheduling theory in operations research

Software:

Knapsack
PDFBibTeX XMLCite
Full Text: DOI