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

M.A. Kubzin, V.A. Strusevich, J. Breit and G. Schmidt

Naval Research Logistics (NRL), 2006, vol. 53, issue 1, 16-23

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 $\cal{P = NP}$. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006

Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1002/nav.20122

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:53:y:2006:i:1:p:16-23

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().