Consider the optimal control problem for the two processor flow-shop when processing times for n tasks are (linear) functions of the state. Since the latter also depends on the sequence, a hierarchical approach is proposed. We solve here, for any given sequence, the problem of optimally launching the tasks using the idle time of the first processor (P1) at stage as the control parameter if ith task. In particular, we show that makespan associated to a given sequence is minimized when P1's idle time is concentrated on some critical parts determined by the schedule. Also, our results suggest how to devise a fast heutistic algorithm, and propose interesting bounds for a branch-and-bound approach to the scheduling problem.
Published May 1989 , 16 pages