文献

J-GLOBAL ID：201802277576398257   整理番号：18A0885104

機械適用性制約を持つ同一ジョブ並列機近似スケジューリングアルゴリズム【JST・京大機械翻訳】

An approximation algorithm for scheduling identical jobs on parallel machines with machine eligibility constraints

著者 (3件)： Zhan Yong (哈爾浜工程大学机電工程学院,哈爾浜,150001) ,  Xu Jianan (哈爾浜工程大学机電工程学院,哈爾浜,150001) ,  Qu Dongyue (哈爾浜工程大学机電工程学院,哈爾浜,150001)
資料名： Zhongguo Keji Lunwen  (Zhongguo Keji Lunwen)
巻： 12  号： 22  ページ： 2575-2580  発行年： 2017年 
JST資料番号： C3242A  ISSN： 2095-2783  CODEN： ZKLHAF  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： 機械の適用性を考慮した同じジョブ並列機械スケジューリング問題に対して、1種類の二段階近似スケジューリングアルゴリズムを提出した。問題の半整合モデルG=[J∪M,E,W]を構築し,元の問題を最適半マッチング探索問題に変換し,次に初期解構造と最適化により問題の近似解を得た。G=[J∪M、E、W]のトポロジー統計情報による機械の均載に対する影響を分析し、初期解構造発見式規則を設計した。さらに,欲張り原理を用いて,発見的規則に基づく初期解構造アルゴリズムを提案した。初期解の初期解を出発点とし,交差経路に基づく局所最適化法を用いて近似解を得た。交差経路木を通して,最適交差経路探索は,初期解の最適化アルゴリズムに影響する重要因子である。探索効率を改善するために,交差経路の最大長さを4に制限し,アルゴリズムの最悪ケースと時間複雑性を理論的に解析した。Data from Wanfang. Translated by JST【JST・京大機械翻訳】

シソーラス用語： *近似法 ,  最適化 ,  位相幾何学 ,  *適応性 ,  経路探索 ,  マッチング ,  *アルゴリズム ,  探索問題
準シソーラス用語： 複雑性 ,  探索効率 ,  最適アルゴリズム ,  ローカル最適化 ,  統計情報 ,  近似解 ,  *スケジューリングアルゴリズム , 【Automatic Indexing@JST】

分類 (1件)： 数値計算  (JE02000J)

タイトルに関連する用語 (4件)： 適用性 ,  制約 ,  近似 ,  スケジューリングアルゴリズム