A polynomial-time branching procedure for the multiprocessor scheduling problem

Abstract

In this paper, we present and analyze a branching procedure suitable for branchand-bound algorithms for solving multiprocessor scheduling problems. The originality of this branching procedure resides mainly in its ability to enumerate all feasible solutions without generating duplicated subproblems. This procedure is shown to be polynomial in time and space complexities. The main applications of such branching procedure are instances of the MSP where the costs are large because the height of the search tree is linear on the number of tasks to be scheduled. This in opposition to another branching procedure in the literature that generates a search tree whose height is porportional to the costs of the tasks.