An FPTAS for scheduling a two‐machine flowshop with one unavailability interval

C.T. Ng and Mikhail Y. Kovalyov

Naval Research Logistics (NRL), 2004, vol. 51, issue 3, 307-315

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. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.

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

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

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:51:y:2004:i:3:p:307-315

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 ().