TWO-MACHINE FLOW-SHOP MINIMUM-LENGTH SCHEDULING WITH INTERVAL PROCESSING TIMES

C. T. Ng (), Natalja M. Matsveichuk, Yuri N. Sotskov () and T. C. Edwin Cheng ()
Additional contact information
C. T. Ng: Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
Natalja M. Matsveichuk: United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street, 6, Minsk 220012, Belarus
Yuri N. Sotskov: United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street, 6, Minsk 220012, Belarus
T. C. Edwin Cheng: Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

Asia-Pacific Journal of Operational Research (APJOR), 2009, vol. 26, issue 06, 715-734

Abstract: The flow-shop minimum-length scheduling problem withnjobs 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 ofn.

Keywords: Scheduling; flow-shop; makespan; uncertainty; domination (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595909002432
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:26:y:2009:i:06:n:s0217595909002432

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595909002432

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().