A branch-and-bound algorithm for single-machine earliness–tardiness scheduling with idle time

A branch-and-bound algorithm for single-machine earliness–tardiness scheduling with idle time

0.00 Avg rating0 Votes
Article ID: iaor19982702
Country: United States
Volume: 8
Issue: 4
Start Page Number: 402
End Page Number: 412
Publication Date: Sep 1996
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: programming: branch and bound
Abstract:

We address the NP-hard single-machine problem of scheduling n independent jobs so as to minimize the sum of α times total completion and β times total earliness with β > α, which can be written as an earliness–tardiness problem. Postponing jobs by leaving the machine idle may then be advantageous. The allowance of machine idle time between the execution of jobs singles out our problem from most concurrent research on problems with earliness penalties. Solving the problem to optimality poses a computational challenge, since the possiblity of leaving the machine idle has a major effect on designing a branch-and-bound algorithm in general, and on computing lower bounds in particular. We present a branch-and-bound algorithm which is based upon many dominance rules and various lower bound approaches, including relaxation of the machine capacity, data manipulation, and Lagrangian relaxation. The algorithm is shown to solve small instances with up to 20 jobs.

Reviews

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