文献

J-GLOBAL ID：201102269322327578   整理番号：11A1412322

総重み付け完了時間を最小にする単一可変リソーススケジューリング問題の強いNP困難性

Strong NP-hardness of the Single-variable-resource Scheduling Problem to Minimize the Total Weighted Completion Time

著者 (2件)： Yuan Jinjiang (Dep. of Mathematics, Zhengzhou Univ., Zhengzhou) ,  Wang Qin (Dep. of Mathematics, China Jiliang Univ., Hangzhou)
資料名： Yunchouxue Xuebao  (Yunchouxue Xuebao)
巻： 14  号： 1  ページ： 31-36  発行年： 2010年 
JST資料番号： C2545A  ISSN： 1007-6093  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 英語 (EN)

抄録/ポイント： BakerとNuttleは以下の単一可変リソーススケジューリング問題を研究した:単一リソースによる処理のため配列nジョブを,リソースの可給性が経時的に異なるときに,職務完了時間の関数を最小化する。目的関数が最小化されるとき,総重み付け完了時間であり,BakerとNuttleは,問題はNP困難であると推測した。最近,Yuan,ChengおよびNgが,この問題は二成分認識におけるNP困難であることを示したが,問題の的確な複雑性はまだ開放状態である。著者らは,本論文でこの問題が強くNP困難であることを示す。Data from the ScienceChina, LCAS. Translated by JST

シソーラス用語： 資源 ,  スケジューリング ,  *NP困難 ,  目的関数 ,  性質 ,  問題 ,  職務
準シソーラス用語： リソース ,  複雑性

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 重み付け ,  可変 ,  リソーススケジューリング ,  問題 ,  NP困難性