Two-stage flowshop earliness and tardiness machine scheduling involving a common due window

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

56 Scopus Citations
View graph of relations

Author(s)

  • W. K. Yeung
  • Ceyda Oǧuz
  • T.C. Edwin Cheng

Detail(s)

Original languageEnglish
Pages (from-to)421-434
Journal / PublicationInternational Journal of Production Economics
Volume90
Issue number3
Publication statusPublished - 18 Aug 2004
Externally publishedYes

Abstract

This paper studies a non-preemptive two-stage flowshop scheduling problem to minimize the earliness and tardiness under the environment of a common due window. The window size and the window location are considered to be given parameters. The just-in-time problem exists naturally and has many practical applications. The problem is shown to be NP-complete in the strong sense. We develop a branch and bound algorithm and a heuristic to solve the problem. We conduct the computational experiments to test the performances of the algorithms. A strong lower bound is derived for the branch and bound algorithm that can efficiently solve 15 jobs problem for about 5 minutes. The heuristic is shown to be efficient and effective, which can solve the problem of 150 jobs for about 20 seconds and provide near-optimal solution. We justify that the heuristic is an excellent solution approach for large problem instances. We also show that four special cases are either polynomial solvable or NP-complete in the ordinary sense. © 2003 Elsevier B.V. All rights reserved.

Research Area(s)

  • Branch and bound, Due window, Dynamic programming, Earliness-tardiness, Flowshop scheduling, Heuristic

Citation Format(s)

Two-stage flowshop earliness and tardiness machine scheduling involving a common due window. / Yeung, W. K.; Oǧuz, Ceyda; Cheng, T.C. Edwin.
In: International Journal of Production Economics, Vol. 90, No. 3, 18.08.2004, p. 421-434.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review