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

W. K. Yeung, Ceyda Oǧuz, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

53 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)421-434
Number of pages14
JournalInternational Journal of Production Economics
Volume90
Issue number3
DOIs
Publication statusPublished - 18 Aug 2004

Keywords

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

ASJC Scopus subject areas

  • Business, Management and Accounting(all)
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this