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

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

0.00 Avg rating0 Votes
Article ID: iaor19921890
Country: France
Volume: 25
Start Page Number: 311
End Page Number: 340
Publication Date: Apr 1991
Journal: RAIRO Operations Research
Authors: ,
Keywords: programming: branch and bound
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.