Abstract:
The paper is concerned with manufacture of identical items on a conveyor line which is served by a limited number of transfer operators. The job durations can be chosen from a certain interval. A set of feasible schedules can be found on a finite set of integral matrices. An accurate branch-and-bound algorithm is developed for finding a schedule with a minimal serving period. The branching is performed so that the number of simultaneously suspended vertices is limited to the square of the problem dimension. With fixed job durations the algorithm load is polynomial.