An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem

Shunji Tanaka ()
Additional contact information
Shunji Tanaka: Kyoto University

Chapter Chapter 2 in Just-in-Time Systems, 2012, pp 21-40 from Springer

Abstract: Abstract This paper introduces our exact algorithm for the single-machine total weighted earliness–tardiness scheduling problem, which is based on the Successive Sublimation Dynamic Programming (SSDP) method. This algorithm starts from a Lagrangian relaxation of the original problem and then constraints are successively added to it until the gap between lower and upper bounds becomes zero. The relaxations are solved by dynamic programming, and unnecessary dynamic programming states are eliminated in the course of the algorithm to suppress the increase of states caused by the addition of constraints. This paper explains the methods employed in our algorithm to construct the Lagrangian relaxations, to eliminate states and to compute an upper bound together with some other improvements. Then, numerical results for known benchmark instances are given to show the effectiveness of our algorithm.

Keywords: Lagrangian Relaxation; Network Reduction; Time-indexed Formulation; Weighted Tardiness; Tight Lower Bound (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4614-1123-9_2

Ordering information: This item can be ordered from
http://www.springer.com/9781461411239

DOI: 10.1007/978-1-4614-1123-9_2

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().