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 twomachine flow-shop scheduling problems solvable under the sufficient conditions given in Theorems 2 – 4.

Keywords: Scheduling, flow-shop, makespan, uncertainty.

ACM Classification Keywords: F.2.2 Non-numerical algorithms and problems: Sequencing and scheduling

Link:

REALIZATION OF AN OPTIMAL SCHEDULE FOR THE TWO-MACHINE FLOW-SHOP WITH INTERVAL JOB PROCESSING TIMES

Natalja Leshchenko, Yuri Sotskov

http://www.foibg.com/ijita/vol14/ijita14-2-p12.pdf