The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times

Abstract

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: lower and upper bounds for the random processing time are given before scheduling, but its 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 we look for a minimal set of schedules that is dominant. Such a minimal dominant set of schedules may be represented by a dominance digraph. We investigate useful properties of such a digraph.

Keywords:

• scheduling
• makespan
• uncertainty
• dominance relation

AMS Subject Classifications::

• 90B35
• 90C15
• 90C31

Acknowledgements

The research of the second and third authors was supported by Belarusian Republican Foundation for Fundamental Research (grant M08MC-027). The authors would like to thank the anonymous referees for useful suggestions and comments on an earlier draft of this article.