𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Heuristics for two-machine no-wait flowshop scheduling with an availability constraint

✍ Scribed by Guoqing Wang; T.C.Edwin Cheng

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
75 KB
Volume
80
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we study the two-machine no-wait flowshop problem with an availability constraint. The problem has been shown to be NP-hard, and some heuristics with a worst-case error bound of 2 have been developed for it. We provide two improved heuristics for the problem, and show that each has a worst-case error bound of 5/3.

πŸ“œ SIMILAR VOLUMES

Complexity and algorithms for two-stage
Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints
✍ Jinxing Xie; Xijun Wang πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 519 KB

This paper considers the two-stage flexible flowshop scheduling problem with availability constraints. We discuss the complexity and the approximability of the problem, and provide some approximation algorithms with finite and tight worst case performance bounds for some special cases of the problem

An FPTAS for scheduling a two-machine fl
An FPTAS for scheduling a two-machine flowshop with one unavailability interval
✍ C.T. Ng; Mikhail Y. Kovalyov πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 87 KB

## 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. Th