Paper Info
Title
Single-Machine Scheduling of Unit-Time Jobs with Earliness and Tardiness Penalties
Abstract
The problem of determining a schedule of jobs with unit-time lengths on a single machine that minimizes the total weighted earliness and tardiness penalties with respect to arbitrary rational due-dates is formulated as an integer programming problem. We show that if the penalties meet a certain criterion, called the Dominance Condition, then there exists an extremal optimal solution to the LP-relaxation that is integral, leading to a polynomial-time solution procedure. The general weighted symmetric penalty structure is one cost structure that satisfies the Dominance Condition; we point out other commonly found penalty structures that also fall into this category.
Year
DOI
Venue
1998
10.1287/moor.23.4.930
Math. Oper. Res.
Keywords
DocType
Volume
single-machine scheduling,cost structure,tardiness penalties,arbitrary rational due-dates,total weighted earliness,integer programming problem,general weighted symmetric penalty,unit-time jobs,polynomial-time solution procedure,dominance condition,penalty structure,extremal optimal solution,tardiness penalty
Journal
23
Issue
ISSN
Citations 
4
0364-765X
13
PageRank 
References 
Authors
1.05
7
2
Name
Order
Citations
PageRank
Sushil Verma1182.90
Maged Dessouky247939.53