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

Guoqing Wang, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

25 Citations (Scopus)

Abstract

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.
Original languageEnglish
Article number2544
Pages (from-to)305-309
Number of pages5
JournalInformation Processing Letters
Volume80
Issue number6
DOIs
Publication statusPublished - 1 Jan 2001

Keywords

  • Approximation algorithms
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this