Transporting jobs through a processing center with two parallel machines
Tools
Tools
Kellerer, Hans, Soper, Alan J. 
ORCID: 0000-0002-0901-9803 and Strusevich, Vitaly A.
(2010)
Transporting jobs through a processing center with two parallel machines.
In: Wu, Weili and Daescu, Ovidiu, (eds.)
Combinatorial Optimization and Applications: 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part I.
Lecture Notes in Computer Science
(6508).
Springer Berlin Heidelberg, Berlin, Germany, pp. 408-422.
ISBN 978364274575
ISSN 0302-9743
(doi:https://doi.org/10.1007/978-3-642-17458-2_33)
Abstract
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).
| Item Type: | Book Section |
|---|---|
| Additional Information: | [1] Paper published in series: Lecture Notes in Computer Science. Volume 6508, 2010, DOI: 10.1007/978-3-642-17458-2. Book titled Combinatorial Optimization and Applications: 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part I. Editors: Weili Wu, Ovidiu Daescu. [2] Also allocated ISBN 978364217458(Online) and series ISSN 0302-9743. [2] ISSN: 0302-9743 (Print), 1611-3349 (Online) |
| Uncontrolled Keywords: | scheduling with transportation, parallel machines, FPTAS, |
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| Pre-2014 Departments: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Computer Science School of Computing & Mathematical Sciences > Department of Mathematical Sciences |
| Related URLs: | |
| Last Modified: | 14 Oct 2016 09:11 |
| URI: | http://gala.gre.ac.uk/id/eprint/4316 |
Actions (login required)
 |
View Item |