Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/10860
Title: An FPTAS for scheduling a two-machine flowshop with one unavailability interval
Authors: Ng, CT 
Kovalyov, MY
Keywords: Flowshop scheduling
Fully polynomial time approximation scheme
Machine availability
Issue Date: 2004
Source: Naval research logistics, 2004, v. 51, no. 3, p. 307-315 How to cite?
Journal: Naval Research Logistics 
Abstract: We study a deterministic two-machine flowshop scheduling problem with an assumption that one of the two machines is not available in a specified time period. This period can be due to a breakdown, preventive maintenance, or processing unfinished jobs from a previous planning horizon. The problem is known to be NP-hard. Pseudopolynomial dynamic programming algorithms and heuristics with worst case error bounds are given in the literature to solve the problem. They are different for the cases when the unavailability interval is for the first or second machine. The existence of a fully polynomial time approximation scheme (FPTAS) was formulated as an open conjecture in the literature. In this paper, we show that the two cases of the problem under study are equivalent to similar partition type problems. Then we derive a generic FPTAS for the latter problems with O(n5/ε4) time complexity.
URI: http://hdl.handle.net/10397/10860
ISSN: 0894-069X
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

13
Citations as of Apr 30, 2016

Page view(s)

41
Last Week
1
Last month
Checked on Apr 23, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.