Interval scheduling

Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design.

Each task is represented by an interval describing the time in which it needs to be processed by some machine (or, equivalently, scheduled on some resource).

It is equivalent to finding a maximum independent set in an interval graph.

GISDPk is a restricted version of GISDP in which the number of intervals in each group is at most k. The group interval scheduling maximization problem (GISMP) is to find a largest compatible set - a set of non-overlapping representatives of maximum size.

GISMPk is a restricted version of GISMP in which the number of intervals in each group is at most k. This problem is often called JISPk, where J stands for Job.

All these problems are special cases of single-machine scheduling, since they assume that all tasks must run on a single processor.

Several algorithms, that may look promising at first sight, actually do not find the optimal solution:[2] The following greedy algorithm, called Earliest deadline first scheduling, does find the optimal solution for unweighted single-interval scheduling: Whenever we select an interval at step 1, we may have to remove many intervals in step 2.

Here, we input our final vector (where j=9 in this example) into our schedule function from the code block above.

We perform the actions in the table below until j is set to 0, at which point, we only include into our final schedule the encountered intervals which met the

The constructed GISDP has a feasible solution (i.e. a scheduling in which each group is represented), if and only if the given set of boolean clauses has a satisfying assignment.

GISDP2 can be solved at polynomial time by the following reduction to the 2-satisfiability problem:[6] This construction contains at most O(n2) clauses (one for each intersection between intervals, plus two for each group).

The satisfiability of such formulas can be decided in time linear in the number of clauses (see 2-SAT).

[8] The following greedy algorithm finds a solution that contains at least 1/2 of the optimal number of intervals:[8] A formal explanation is given by a Charging argument.

In this representation, the interval scheduling problem is equivalent to finding the maximum independent set in this intersection graph.

A group-interval scheduling problem (GISMPk) can be described by a similar interval-intersection graph, with additional edges between each two intervals of the same group, i.e., this is the edge union of an interval graph and a graph consisting of n disjoint cliques of size k. An important class of scheduling algorithms is the class of dynamic priority algorithms.

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 interval scheduling problem is 1-dimensional – only the time dimension is relevant.

That is, all the intervals must be scheduled, but the objective is to minimize the usage of resources.