DSpace Kyoto University
Japanese | English 

Kyoto University Research Information Repository >
Graduate School of Engineering >
Journal Articles >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2433/160225

Full text link:

File Description SizeFormat
j.cor.2012.07.004.pdf111.35 kBAdobe PDFView/Open
Title: An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
Authors: Tanaka, Shunji
Araki, Mituhiko
Author's alias: 田中, 俊二
Keywords: Single-machine total weighted tardiness problem
Sequence-dependent setup times
Exact algorithm
Lagrangian relaxation
Dynamic programming
Issue Date: Jan-2013
Publisher: Elsevier Ltd.
Journal title: Computers & Operations Research
Volume: 40
Issue: 1
Start page: 344
End page: 352
DOI: 10.1016/j.cor.2012.07.004
Abstract: This study proposes an exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. The algorithm is an extension of the authors' previous algorithm for the single-machine scheduling problem without setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In the first stage of the algorithm, the conjugate subgradient algorithm or the column generation algorithm is applied to a Lagrangian relaxation of the original problem to adjust multipliers. Then, in the second stage, constraints are successively added to the relaxation until the gap between lower and upper bounds becomes zero. The relaxation is solved by dynamic programming and unnecessary dynamic programming states are eliminated to suppress the increase of computation time and memory space. In this study a branching scheme is integrated into the algorithm to manage to solve hard instances. The proposed algorithm is applied to benchmark instances in the literature and almost all of them are optimally solved.
Rights: © 2012 Elsevier Ltd.
URI: http://hdl.handle.net/2433/160225
Appears in Collections:Journal Articles


Export to RefWorks

Access count of this item: 165

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

DSpace Software Copyright © 2002-2007 MIT and Hewlett-Packard - Feedback - Privacy policy