Interval scheduling

Interval scheduling

Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. A list of tasks is given as a set of time intervals; for instance, one task might run from 2:00 to 5:00 and another task might run from 6:00 to 8:00. Posed as an optimization problem, the goal is to maximize the number of executed tasks. 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 greedy algorithm earliest deadline first scheduling. The general case requires dynamic programming.

ee also

*Scheduling (computing)
*Earliest deadline first scheduling


*cite book|first=Jon|last=Kleinberg|coauthors=Tardos, Eva|title=Algorithm Design|year=2006|id=ISBN 0-321-29535-8

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Scheduling (computing) — This article is about processes assignment in operating systems. For other uses, see Scheduling (disambiguation). Scheduling is a key concept in computer multitasking, multiprocessing operating system and real time operating system designs.… …   Wikipedia

  • Interval graph — In graph theory, an interval graph is the intersection graph of a set of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.Formally,… …   Wikipedia

  • Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… …   Wikipedia

  • Operating room management — An operating theatre (gynecological hospital of Medical University of Silesia in Bytom) Operating room management is the science of how to run an Operating Room Suite. Operational operating room management focuses on maximizing operational… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Web crawler — For the search engine of the same name, see WebCrawler. For the fictional robots called Skutters, see Red Dwarf characters#The Skutters. Not to be confused with offline reader. A Web crawler is a computer program that browses the World Wide Web… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Traffic Control — ➡ law enforcement * * * Introduction       supervision of the movement of people, goods, or vehicles to ensure efficiency and safety.       Traffic is the movement of people and goods from one location to another. The movement typically occurs… …   Universalium

  • Coffman–Graham algorithm — In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses… …   Wikipedia

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français