このアイテムのアクセス数: 375

このアイテムのファイル:
ファイル 記述 サイズフォーマット 
j.cor.2012.07.004.pdf111.35 kBAdobe PDF見る/開く
タイトル: An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
著者: Tanaka, Shunji  kyouindb  KAKEN_id
Araki, Mituhiko
著者名の別形: 田中, 俊二
キーワード: Single-machine total weighted tardiness problem
Sequence-dependent setup times
Exact algorithm
Lagrangian relaxation
Dynamic programming
発行日: Jan-2013
出版者: Elsevier Ltd.
誌名: Computers & Operations Research
巻: 40
号: 1
開始ページ: 344
終了ページ: 352
抄録: 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.
著作権等: © 2012 Elsevier Ltd.
この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。This is not the published version. Please cite only the published version.
URI: http://hdl.handle.net/2433/160225
DOI(出版社版): 10.1016/j.cor.2012.07.004
出現コレクション:学術雑誌掲載論文等

アイテムの詳細レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。