Interval scheduling: Difference between revisions

Revision as of 04:19, 24 June 2021

Revision as of 04:21, 24 June 2021

Line 22:

=== Greedy polynomial solution ===

The following [[greedy algorithm]], called [[Earliest deadline first scheduling]], does find the optimal solution:

# Select the interval, ''x'', with the earliest '''finishing time'''.

# Remove ''x'', and all intervals intersecting ''x'', from the set of candidate intervals.

Line 103:

==Variations==

An important class of scheduling algorithms is the class of dynamic priority algorithms. When none of the intervals overlap the optimum solution is trivial. The optimum for the non-weighted version can found with the [[earliest deadline first scheduling]]. Weighted interval scheduling is a generalization where a value is assigned to each executed task and the goal is to maximize the total value. The solution need not be unique.

When none of the intervals overlap the optimum solution is trivial. The optimum for the non-weighted version can found with the [[earliest deadline first scheduling]]. Weighted interval scheduling is a generalization where a value is assigned to each executed task and the goal is to maximize the total value. The solution need not be unique.

The interval scheduling problem is 1-dimensional – only the time dimension is relevant. The [[Maximum disjoint set]] problem is a generalization to 2 or more dimensions. This generalization, too, is NP-complete.

Another variation is resource allocation, in which a set of intervals s are scheduled using resources ''k'' such that ''k'' is minimized. That is, all the intervals must be scheduled, but the objective is to reduceminimize the numberusage of resources as much as possible.

Another variation is when there are ''m'' processors instead of a single processor. I.e., ''m'' different tasks can run in parallel.<ref name=NakajimaHakimiSee />[[identical-machines scheduling]].

==See also==

*[[Scheduling (computing)]]

*[[Earliest deadline first scheduling]]

==Sources==