文献

J-GLOBAL ID：201702236588428701   整理番号：17A1625831

ジョブ間の区間グラフ互換性を持つバッチ処理マシン上でのスケジューリングのためのオンラインアルゴリズム【Powered by NICT】

Online algorithms for scheduling on batch processing machines with interval graph compatibilities between jobs

著者 (4件)： Wang Qian (School of Mathematics, China University of Mining and Technology, Xuzhou, Jiangsu 221116, PR China) ,  Tian Ji (School of Mathematics, China University of Mining and Technology, Xuzhou, Jiangsu 221116, PR China) ,  Fu Ruyan (School of Mathematics, China University of Mining and Technology, Xuzhou, Jiangsu 221116, PR China) ,  Yao Xiangjuan (School of Mathematics, China University of Mining and Technology, Xuzhou, Jiangsu 221116, PR China)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 700  ページ： 37-44  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： m非有界並列バッチ機械のメイクスパンを最小化するオンライン(時間以上)スケジューリング問題を考察し,同じバッチ内ジョブはペアワイズ適合されなければならない。相溶性は対称二項関係,区間適合性グラフによって表現されている。バッチの処理時間は,ジョブの最大処理時間に等しいと,同じバッチにおけるすべてのジョブを同時に開始と仕上げ。この問題のために,最初に,著者らは競合比2以下のオンラインアルゴリズムは存在しないことを示した。競合比2+ 1m+1,m=1に最適化したオンラインアルゴリズムを提案した。すべてのジョブは,同じ処理時間を持っている場合,最適オンラインアルゴリズムを与えた。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *互換性 ,  適応性 ,  加工時間 ,  *バッチ処理 ,  *グラフ ,  相溶性 ,  *スケジューリング ,  対称性 ,  *ロット ,  最適化
準シソーラス用語： 競合比 ,  *オンライン ,  メイクスパン ,  *オンラインアルゴリズム ,  *区間グラフ , 【Automatic Indexing@JST】

著者キーワード (4件)： オンラインスケジューリング ,  バッチ機械 ,  適合性グラフ ,  競合比

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

タイトルに関連する用語 (6件)： 区間グラフ ,  互換性 ,  バッチ ,  マシン ,  スケジューリング ,  オンラインアルゴリズム