Groupe d’études et de recherche en analyse des décisions


Hierarchical Control of the Two Processor Flow-shop with State Dependent Processing Times, 1. A Two Stage Approach to the Minimum Makespan Problem


Consider a flow-shop with n parts, whose processing times are state dependent. Since the state often depends on the sequence, a hierarchical approach is proposed for the scheduling problem. The method is illustrated here for the minimum makespan problem, and the number of processors is limited to two, in order to keep track of the main features of the problem. It has been shown in Sriskandarajah and Wagneur [6], that this problem is NP-hard in the strong sense. Thus the increased `simplicity' is not gained at the expense of generality. Given a sequence, we use the idle time of the first processor (P1) at stage as the control parameter of ith part, and prove an explicit formula giving the optimal launching times. Our solution shows that the makespan is minimized when P1's idle time is concentrated on some critical parts determined by the schedule. A recursive use of the formula leads to a branch and bound algorithm for the optimal schedule. Numerical results are then provided with the initial step given by the solution due to Gilmore and Gomory [2]. As an outcome, we find that the initial solution itself is fairly good for this problem.

, 19 pages