Skip navigation

Preemptive scheduling on two identical parallel machines with a single transporter

Preemptive scheduling on two identical parallel machines with a single transporter

Kellerer, Hans, Soper, Alan J. ORCID: 0000-0002-0901-9803 and Strusevich, Vitaly A. (2012) Preemptive scheduling on two identical parallel machines with a single transporter. Journal of Combinatorial Optimization, 25 (2). pp. 279-307. ISSN 1382-6905 (Print), 1573-2886 (Online) (doi:https://doi.org/10.1007/s10878-012-9511-x)

[img]
Preview
PDF (AAM)
8516_SOPER_STRUSEVICH_(AAM)_(2013).pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (525kB)

Abstract

We consider a scheduling problem on two identical parallel machines, in which the jobs are moved between the machines by an uncapacitated transporter. In the processing preemption is allowed. The objective is to minimize the time by which all completed jobs are collected together on board the transporter. We identify the structural patterns of an optimal schedule and design an algorithm that either solves the problem to optimality or in the worst case behaves as a fully polynomial-time approximation scheme.

Item Type: Article
Additional Information: [1] This is the Authors’ Accepted Manuscript version. The final publication is available at Springer via http://dx.doi.org/10.1007/s10878-012-9511-x.
Uncontrolled Keywords: scheduling with transportation, parallel machines, approximation scheme,
Subjects: Q Science > QA Mathematics
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Department of Mathematical Sciences
Related URLs:
Last Modified: 14 Oct 2016 20:00
URI: http://gala.gre.ac.uk/id/eprint/8516

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics