The one-machine problem with earliness and tardiness penalties

The one-machine problem with earliness and tardiness penalties

0.00 Avg rating0 Votes
Article ID: iaor2008173
Country: United Kingdom
Volume: 6
Issue: 6
Start Page Number: 533
End Page Number: 549
Publication Date: Nov 2003
Journal: Journal of Scheduling
Authors: ,
Keywords: programming: transportation
Abstract:

We address the one-machine problem in which the jobs have distinct due dates, earliness costs, and tardiness costs. In order to determine the minimal cost of such a problem, a new lower bound is proposed. It is based on the decomposition of each job in unary operations that are then assigned to the time slots, which gives a preemptive schedule. Assignment costs are defined so that the minimum assignment cost is a valid lower bound. A branch-and-bound algorithm based on this lower bound and on some new dominance rules is experimentally tested.

Reviews

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