1. Home
  2. Other publishers
  3. Periodicals
  4. International Journal Information Theories and Applications - IJ ITA (ITHEA)
  5. 2007
  6. Volume 14 Number 2
  7. Realization of an Optimal Schedule for the Two-machine Flow-Shop with Interval Job Processing Times

Realization of an Optimal Schedule for the Two-machine Flow-Shop with Interval Job Processing Times

View in new window
Authors: Leshchenko, NataljaSotskov, Yuri
Issue Date: 2007
ISSN: 1313-0463
URI: http://hdl.handle.net/10525/677 Copy to clipboard
Abstract: Non-preemptive two-machine flow-shop scheduling problem with uncertain processing times of n jobs is studied. In an uncertain version of a scheduling problem, there may not exist a unique schedule that remains optimal for all possible realizations of the job processing times. We find necessary and sufficient conditions (Theorem 1) when there exists a dominant permutation that is optimal for all possible realizations of the job processing times. Our computational studies show the percentage of the problems solvable under these conditions for the cases of randomly generated instances with n ≤ 100 . We also show how to use additional information about the processing times of the completed jobs during optimal realization of a schedule (Theorems 2 – 4). Computational studies for randomly generated instances with n ≤ 50 show the percentage of the two- machine flow-shop scheduling problems solvable under the sufficient conditions given in Theorems 2 – 4.
Language: en
Publisher: Institute of Information Theories and Applications FOI ITHEASubject: SchedulingFlow-ShopMakespanUncertainty
Type: Article