Two-machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs

Wing Kwan Yeung, Ceyda Oǧuz, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

26 Citations (Scopus)

Abstract

This article studies two due window scheduling problems to minimize the weighted number of early and tardy jobs in a two-machine flow shop, where the window size is externally determined. These new scheduling models have many practical applications in real life. However, results on these problems have rarely appeared in the literature because of a lack of structural and optimality properties for solving them. In this article, we derive several dominance properties and theorems, including elimination rules and sequencing rules based on Johnson's order, lower bounds on the penalty, and upper bounds on the window location, which help to significantly trim the search space for the problems. We further show that the problems are NP-hard in the ordinary sense only. We finally develop efficient pseudopolynomial dynamic programming algorithms for solving the problems.
Original languageEnglish
Pages (from-to)593-599
Number of pages7
JournalNaval Research Logistics
Volume56
Issue number7
DOIs
Publication statusPublished - 1 Oct 2009

Keywords

  • Due window
  • Dynamic programming
  • Early and tardy jobs
  • Flow shop scheduling
  • NP-hardness

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Cite this