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

What is it about?

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain. 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.

Featured Image