離接グラフ

【りせつぐらふ (disjunctive graph)】

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