ダウンロード数: 316
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.ejor.2013.02.048.pdf | 135.12 kB | Adobe PDF | 見る/開く |
タイトル: | An exact algorithm for the precedence-constrained single-machine scheduling problem |
著者: | Tanaka, Shunji https://orcid.org/0000-0002-0181-743X (unconfirmed) Sato, Shun |
著者名の別形: | 田中, 俊二 |
キーワード: | Scheduling Single-machine Precedence constraints Exact algorithm Lagrangian relaxation Dynamic programming |
発行日: | Sep-2013 |
出版者: | Elsevier B.V. |
誌名: | European Journal of Operational Research |
巻: | 229 |
号: | 2 |
開始ページ: | 345 |
終了ページ: | 352 |
抄録: | This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors’ previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness–tardiness problems, and most instances with 100 jobs of the former problem. |
著作権等: | © 2013 Elsevier B.V. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
URI: | http://hdl.handle.net/2433/174100 |
DOI(出版社版): | 10.1016/j.ejor.2013.02.048 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。