文献

J-GLOBAL ID：201802273535017846   整理番号：18A0280573

コンフリクトグラフを用いたオープンショップスケジューリング問題【Powered by NICT】

Open shop scheduling problems with conflict graphs

著者 (2件)： Tellache Nour El Houda (RECITS Laboratory, Faculty of Mathematics, USTHB University, BP 32 El-Alia, Bab-Ezzouar, Algiers, Algeria) ,  Boudhar Mourad (RECITS Laboratory, Faculty of Mathematics, USTHB University, BP 32 El-Alia, Bab-Ezzouar, Algiers, Algeria)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 227  ページ： 103-120  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,いくつかの矛盾するジョブは,さまざまなマシンに同時に処理できないという制約を受けるオープンショップを扱った。本研究との関連で,これらの衝突は無向グラフ,コンフリクトグラフと呼ばれるにより与えられる。最大完了時間(メークスパン)を最小にするスケジュールを求める。最初に,この問題の異なるバージョンのNP困難性を証明した。,多項式時間可解な例のための,簡単で効率的なアルゴリズムを考案を提示した。一方,発見的方法と一般的な場合に対する下限を示した。発見的方法は二部グラフにおけるマッチングの構築だけでなくビーム探索と組み合わせた特異的挿入法に基づいている。最後に,発見的方法の効率を試験し,満足すべき結果を示すことを著者らの計算実験を報告した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： アルゴリズム ,  NP困難 ,  *発見的方法 ,  無向グラフ
準シソーラス用語： ビーム探索 ,  二部グラフ ,  多項式時間 ,  メイクスパン ,  *オープンショップ , 【Automatic Indexing@JST】

著者キーワード (6件)： オープンショップスケジューリング ,  コンフリクトグラフ ,  複雑性 ,  発見的方法 ,  下限 ,  メークスパン

分類 (2件)： 工程管理  (KB03030P) ,  計算理論  (JB02000A)

タイトルに関連する用語 (2件)： オープンショップ ,  スケジューリング