Two-machine flow-shop minimum-length scheduling with interval processing times

Chi To Ng, Natalja M. Matsveichuk, Yuri N. Sotskov, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

20 Citations (Scopus)

Abstract

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: only lower and upper bounds of the random processing times are given before scheduling, but their probability distributions are unknown. For such a problem, there may not exist a dominant schedule that remains optimal for all possible realizations of the processing times and so we look for a minimal set of schedules that are dominant. We obtain necessary and sufficient conditions for the case when it is possible to fix the order of two jobs in a minimal set of dominant schedules. The necessary and sufficient conditions are proven for the case when one schedule dominates all the others. We characterize also the case where there does not exist non-trivial schedule domination. All the conditions proven may be tested in polynomial time of n. & Operational Research Society of Singapore.
Original languageEnglish
Pages (from-to)715-734
Number of pages20
JournalAsia-Pacific Journal of Operational Research
Volume26
Issue number6
DOIs
Publication statusPublished - 1 Dec 2009

Keywords

  • Domination
  • Flow-shop
  • Makespan
  • Scheduling
  • Uncertainty

ASJC Scopus subject areas

  • Management Science and Operations Research

Cite this