A branch and bound method for solving scheduling problems with cumulative constraints

This paper presents a procedure for scheduling in a minimal makespan a project subject to precedence and cumulative constraints. Because of the NP-hardness of this problem, a branch and bound method is proposed. An execution interval is associated with each task. Branching consists of choosing a task and splitting its interval of execution into two intervals. Lower bounds are computed by m-machines problems, upper bounds are based on Jackson’s algorithm. Tests on classical benchmarks and randomly generated problems show the effectiveness of this method.