An exact approach to early/tardy scheduling with release dates

An exact approach to early/tardy scheduling with release dates

0.00 Avg rating0 Votes
Article ID: iaor20062606
Country: United Kingdom
Volume: 32
Issue: 11
Start Page Number: 2905
End Page Number: 2917
Publication Date: Nov 2005
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: branch and bound
Abstract:

In this paper we consider the single machine earliness/tardiness scheduling problem with different release dates and no unforced idle time. The problem is decomposed into a weighted earliness subproblem and a weighted tardiness subproblem. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is then simply the sum of the lower bounds for the two subproblems. The lower bounds and several versions of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.

Reviews

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