文献

J-GLOBAL ID：202002253979804726   整理番号：20A0146812

リリース日による非関連並列機械スケジューリングのための新しい近似アルゴリズム【JST・京大機械翻訳】

A new approximation algorithm for unrelated parallel machine scheduling with release dates

著者 (4件)： Pei Zhi (Department of Industrial Engineering, Zhejiang University of Technology, Hangzhou, China) ,  Wan Mingzhong (Department of Industrial Engineering, Zhejiang University of Technology, Hangzhou, China) ,  Wan Mingzhong (Department of Industrial and Systems Engineering, Northern Illinois University, DeKalb, USA) ,  Wang Ziteng (Department of Industrial and Systems Engineering, Northern Illinois University, DeKalb, USA)
資料名： Annals of Operations Research  (Annals of Operations Research)
巻： 285  号： 1-2  ページ： 397-425  発行年： 2020年 
JST資料番号： T0444A  ISSN： 0254-5330  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 本研究では,重み付き完了時間の最小和によるジョブ割当を得るために,リリース日付を有する非関連並列マシンスケジューリング問題を考察した。この問題は強い意味でNP困難であるが,多項式時間内で形式可能なタスクを探索する最適性を与える,一定最悪ケース境界に基づく4近似アルゴリズムを考案し,既存の16/3近似と比較して証明した。新しく提案したアルゴリズムにおいて,元のスケジューリング問題を,リリース日付に基づいていくつかのサブ問題に分割した。各サブ問題に対して,凸二次整数計画法モデルを,特定の問題構造に従って構築した。次に,各サブ問題の半正定緩和を介して下限を生成するために,半定値プログラミング手法を実装した。さらに,二値制約を考慮することによって,分岐と結合ベースの方法と局所探索戦略を別々に適用して,各サブ問題の最適解を位置決めした。次に,元のスケジューリング問題の解を,提案した近似アルゴリズムを通してサブ問題の結果を統合することによって引き出した。数値解析において,提案方法が常に最適解の[数式:原文を参照]の中でスケジューリング結果を得ることができることを発見した。そして,スケジューリング問題のスケールが増加するにつれて,解の品質がさらに改善される漸近的傾向を観察することができた。Copyright 2019 Springer Science+Business Media, LLC, part of Springer Nature Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  整数計画法 ,  並列計算機 ,  近傍探索法 ,  *近似法 ,  緩和現象 ,  品質 ,  凸形 ,  NP困難 ,  *スケジューリング ,  数値解析
準シソーラス用語： 半正定値計画法 ,  最適解 ,  最適性 ,  *近似アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (5件)： 非関連並列機械スケジューリング ,  放出日 ,  半正定値プログラミング ,  近似アルゴリズム ,  分岐と限界

分類 (4件)： 数理計画法  (KA03030M) ,  オペレーションズリサーチ一般  (KA03010Q) ,  林業一般  (FF01010M) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (3件)： リリース日 ,  並列機械スケジューリング ,  近似アルゴリズム