優越集合 (スケジュールの)

【ゆうえつしゅうごう (dominant set for schedule)】

ジョブショップにおいて任意のスケジュールを考えるとき, 任意のジョブの任意の機械での処理完了(したがって, 処理開始も)がそれより遅くないスケジュールが必ず存在するようなスケジュールの集合を, スケジュールの優越集合と呼ぶ. 正則尺度を対象にする限りは, 優越集合の中で目的関数を最小にするスケジュールを見つければ最適スケジュールが得られる. すべての活性スケジュールの集合は優越集合であるが, 最小の優越集合は知られていない.