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

0.00 Avg rating0 Votes
Article ID: iaor20072864
Country: United States
Volume: 53
Issue: 1
Start Page Number: 16
End Page Number: 23
Publication Date: Feb 2006
Journal: Naval Research Logistics
Authors: , , ,
Keywords: combinatorial analysis
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 polynominal-time approximation schemes, one of which handles the problem with one non-availability 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.

Reviews

Required fields are marked *. Your email address will not be published.