Partial job order for solving the two-machine flow-shop minimum-length problem with uncertain processing times

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 for the random processing time are given, while the probability distribution between these bounds is unknown). For such a problem, there often does not exist a dominant schedule that remains optimal for all possible realizations of the job processing times, and so we look for a minimal dominant set of schedules, which may be represented by a partial job order. We investigate properties of this partial job order and show how to construct this order in polynomial time. The approach based on a set of dominant schedules allows us to find special cases of the problem when it is possible to find an optimal schedule in spite of the uncertainty of the numerical data.