OR事典

離接グラフ

読み方：りせつぐらふ
【英】：disjunctive graph

ジョブの各作業, 処理順序の先頭と最後を示すダミーの作業0と*を節点とし, ジョブの工程順序と先行関係を示す矢線, ダミーの作業0と各ジョブの先頭作業を結ぶ矢線, 各ジョブの最後の作業と作業*を結ぶ矢線, かつ, 同じ機械の先行関係のない作業間を結ぶ両向きの矢線から成るグラフをいう. 各両向きの矢線の一方の向きを選択して全体として閉路を含まないグラフを構成すれば, これが実行可能な処理順序を与える. 選択グラフということもある.

「OR事典」の他の用語

スケジューリング：

無関連並列機械問題  資源制約付きスケジューリング  近似アルゴリズム  離接グラフ  順序付け  順序付け規則  順序付け関数