「優越集合 (スケジュールの)」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
("優越集合 (スケジュールの)" を保護しました。 [edit=sysop:move=sysop])
(相違点なし)

2007年7月20日 (金) 10:22時点における版

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

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