文献

J-GLOBAL ID：201002278300837841   整理番号：10A1062113

1機械スケジューリング問題に対する厳密解法の研究動向

著者 (1件)： 田中俊二 (京大 大学院工学研究科)
資料名： システム/制御/情報  (システム制御情報学会誌)
巻： 54  号： 10  ページ： 385-391  発行年： 2010年10月15日 
JST資料番号： G0902A  ISSN： 0916-1600  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 生産スケジューリング問題の中で特に研究が進んでいる1機械スケジューリング問題について,厳密解法に関する最近の研究動向および筆者らの取組みを紹介した。まず,1機械スケジューリング問題の概要を述べた。次に,代表的な1機械スケジューリング問題に対する厳密解法の研究動向として,1)納期遅れ和最小化,2)重み付き納期遅れ和最小化,3)重み付き完了時刻和最小化,4)順序依存段取り時間を考慮した完了時刻和最小化,納期遅れ和最小化,5)重み付き納期ずれ和最小化を紹介した。最後に,Lagrange緩和を用いたSSDP(Successive Sublimation Dynamic Programming)法に基づく厳密解法について,時間の離散化に基づく定式化,最短経路問題への変換,Lagrange緩和問題,緩和問題への制約の付加,解法の構成,ネットワーク縮減などを示した。

シソーラス用語： *スケジューリング ,  *厳密解 ,  *納期 ,  緩和法 ,  *最短路問題 ,  制約条件 ,  数値計算
準シソーラス用語： Lagrange緩和 ,  機械スケジューリング

分類 (1件)： 工程管理  (KB03030P)

引用文献 (29件)：

• SHABTAY, D. A survey of scheduling with controllable processing times. Discrete Applied Mathematics. 2007, 155, 1643-1666
• BISKUP, D. A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research. 2008, 188, 315-329
• GRAHAM, R. L. Optimization and approximation in deterministic sequencing and scheduling : A survey. Annals of Discrete Mathematics. 1979, 5, 287-326
• EMMONS, H. One-machine sequencing to minimize certain functions of job tardiness. Operations Research. 1969, 17, 701-715
• LAWLER, E. L. A "pseudopolynomial" algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics. 1977, 1, 331-342

タイトルに関連する用語 (4件)： スケジューリング ,  厳密解法 ,  研究 ,  動向