Consider a flow-shop with m processors and n jobs, whose processing times are state dependent. Since the state often also depend on the sequence, a hierarchical approach is proposed for the scheduling problem. The method is illustrated here for the minimum makespan problem. It has been shown in Sriskandarajah and Wagneur , that this problem is NP-hard in the strong sense for . Given a sequence, we use the idle time of the first processor at stage as the control parameter of ith job, and prove an explicit formula giving the optimal launching times, for arbitrary monotone non decreasing processing time functions. Our solution shows that the makespan is minimized when P1's idle time is concentrated on some critical jobs 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, for linear, quadratic, and exponential processing time functions, with the initial step given by the extension of the solution due to Gilmore and Gomory , devised by Röck and Schmidt . As an outcome, we get that the initial solution itself is fairly good for this problem.
Paru en juin 1990 , 21 pages