Skip navigation

Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints

Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints

Kubzin, Mikhail A., Strusevich, Vitaly A., Breit, J. and Schmidt, G. (2006) Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints. Naval Research Logistics, 53 (1). pp. 16-23. ISSN 0894-069X (doi:10.1002/nav.20122)

Full text not available from this repository.

Abstract

This paper addresses a two-machine open shop scheduling problem, in which the machines are not continuously available for processing. The processing of an operation affected by a non-availability interval can be interrupted and resumed later. The objective is to minimize the makespan. We present two polynomial-time approximation schemes, one of which handles the problem with one non-availability interval on each machine and the other for the problem with several non-availability intervals on one of the machines. Problems with a more general structure of the non-availability intervals are not approximable in polynomial time within a constant factor, unless P=NP.

Item Type: Article
Uncontrolled Keywords: open shop, machine availability, approximation scheme
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Department of Mathematical Sciences
Related URLs:
Last Modified: 14 Oct 2016 09:09
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/3671

Actions (login required)

View Item View Item