THREE-MACHINE FLOWSHOP SCHEDULING PROBLEM TO MINIMIZE MAKESPAN WITH BOUNDED SETUP AND PROCESSING TIMES

The problem of scheduling n jobs on a three-machine flowshop is addressed where setup times are considered as separate from processing times and sequence-independent. The objective is to minimize makespan. Both setup and processing times are unknown variables before the actual occurrence of these times. However, a lower bound and an upper bound are given (known) for each setup and processing time. For this problem, there may not exist a unique schedule that remains optimal for all possible realizations of setup and processing times. Hence, it is desirable to obtain a set of dominating set of schedules (which dominate all other schedules) if possible. The objective is to reduce the size of dominating set. One way of reducing the size of dominating set is to come up with dominance relations. In this paper, global and local dominance relations are developed for the problem. Moreover, the use of developed dominance relations to reduce the size of the set is illustrated by an example and computational analysis is conducted on randomly generated problems.