文献

J-GLOBAL ID：201802236902380879   整理番号：18A1107796

並列同一多段フローショップのメイクスパンを最小化するための近似スキーム【JST・京大機械翻訳】

An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops

著者 (5件)： Tong Weitian (Department of Computer Sciences, Georgia Southern University, Statesboro, GA 30460, USA) ,  Tong Weitian (Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada) ,  Miyano Eiji (Department of Systems Design and Informatics, Kyushu Institute of Technology, Iizuka, Fukuoka 820-8502, Japan) ,  Goebel Randy (Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada) ,  Lin Guohui (Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 734  ページ： 24-31  発行年： 2018年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 並列k-段階のFlow-ショップ問題において,著者らは,m同一のk-ステージFlow-ショップとジョブのセットを与えた。各ジョブは,Flowショップのいずれかにより処理できるが,Flowショップ間の切り替えは許されない。目的は,最後の仕事の仕上げ時間であるメークスパンを最小化することである。この問題は,古典的な並列同一マシンスケジューリング(k=1)と古典的フローショップスケジューリング(m=1)問題を一般化し,NP困難である。mとkが固定定数であるときの問題に対する多項式時間近似スキーム(PTAS)を示した。鍵となる技術は,ジョブを大きいジョブと小さなジョブに分割し,大きなジョブに対するすべての実行可能なスケジュールを列挙し,線形プログラムを解き,「スライディング」法を採用することにより,小さなジョブを扱うことである。このような技術は,いくつかのフローショップスケジューリング変種に対するPTASの設計に使用されてきた。著者らの主な貢献は,この技術の非自明な応用であり,文献における未解決の問題に対する有効な答えである。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： フローショップスケジューリング ,  NP困難 ,  線形性 ,  *近似法
準シソーラス用語： 多項式時間 ,  *メイクスパン ,  フローショップ , 【Automatic Indexing@JST】

著者キーワード (5件)： マルチプロセッサスケジューリング ,  フローショップスケジューリング ,  メイクスパン ,  線形プログラム ,  多項式時間近似スキーム

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

タイトルに関連する用語 (6件)： 多段 ,  フローショップ ,  メイクスパン ,  最小化 ,  近似 ,  スキーム