文献

J-GLOBAL ID：201702247551708733   整理番号：17A1185838

並列段階フローショップ問題のためのFPTAS【Powered by NICT】

An FPTAS for the parallel two-stage flowshop problem

著者 (11件)： Dong Jianming (Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, Zhejiang 310018, China) ,  Tong Weitian (Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada) ,  Tong Weitian (Department of Computer Sciences, Georgia Southern University, Statesboro, GA 30458, USA) ,  Luo Taibo (Business School, Sichuan University, Chengdu, Sichuan 610065, China) ,  Luo Taibo (Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada) ,  Wang Xueshi (Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, Zhejiang 310018, China) ,  Hu Jueliang (Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, Zhejiang 310018, China) ,  Xu Yinfeng (Business School, Sichuan University, Chengdu, Sichuan 610065, China) ,  Xu Yinfeng (State Key Lab for Manufacturing Systems Engineering, Xi’an, Shaanxi 710049, China) ,  Lin Guohui (Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, Zhejiang 310018, China) ,  Lin Guohui (Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 657  号： PA  ページ： 64-72  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： NP困難m並列2段階フローショップ問題,(m , 2)-PFS問題と略記を考察し,メークスパン,すなわちmフローショップに対するすべてのジョブの最大完了時間を最小化するためにnジョブをスケジュールm並列同一2段階フローショップにする必要がある。(m , 2)-PFS問題を二つの部分問題に分解できる:nジョブを割り当てるm並列フローショップへの,各フローショップフローショップに割り当てられたジョブをスケジュールする。(m , 2)-PFS問題を最適に解決し,いかなる固定m,(2 , 2)-PFS問題を解くための以前の考えに基づくに疑似多項式時間動的計画法アルゴリズムを提案した。サブルーチンとして動的計画法アルゴリズムを用いて,(m , 2)-PFS問題のための完全多項式時間近似方式(FPTAS)を設計した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *動的計画法 ,  近似法 ,  NP困難 ,  アルゴリズム ,  フローショップスケジューリング
準シソーラス用語： サブルーチン ,  多項式時間 ,  部分問題 ,  メイクスパン ,  *フローショップ , 【Automatic Indexing@JST】

著者キーワード (5件)： 2段式フローショップスケジューリング ,  マルチプロセッサスケジューリング ,  メークスパン ,  動的計画法 ,  完全多項式時間近似スキーム

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

タイトルに関連する用語 (3件)： 段階 ,  フローショップ ,  問題