Multiprocessor scheduling
- Multiprocessor scheduling
-
In computer science, multiprocessor scheduling is an NP-complete optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors mi, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?"[citation needed] The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment.
Algorithms
A simple, often-used algorithm is the LPT algorithm (Longest Processing Time) which sorts the jobs by its processing time and then assigns them to the machine with the earliest end time so far. This algorithm achieves an upper bound of 4/3 - 1/(3m) OPT.[1]
See also
- Job shop scheduling, a similar problem for scheduling jobs on machines. Some variants of multiprocessor scheduling and job shop scheduling are equivalent problems.
References
- ^ Graham, R. L. (1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics 17 (2): 416–429.
- A compendium of NP optimization problems. Editors: Pierluigi Crescenzi, and Viggo Kann [1]
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
Job shop scheduling — For other uses, see Scheduling. Job shop scheduling (or Job shop problem) is an optimization problem in computer science in which ideal jobs are assigned to resources at particular times. The most basic version is as follows: We are given n jobs… … 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
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
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èmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français
Liste de problemes NP-complets — 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èmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… … Wikipédia en Français
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èmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français
Jeff V. Merkey — Infobox Celebrity name = Jeffrey Vernon Merkey caption = birth date = birth place = Oklahoma City, Oklahoma residence = Lindon, Utah nationality = USA known for = Netware, Novell, Linux employer = occupation = Computer Scientist spouse = children … Wikipedia
Virgil D. Gligor — Infobox Scientist name = Virgil D. Gligor birth date = Birth date and age|1949|7|28|df=y box width = image width = 100 caption = Virgil D. Gligor, 2007 birth date = birth place = death date = death place = residence = citizenship = nationality =… … Wikipedia
Bin packing problem — In computational complexity theory, the bin packing problem is a combinatorial NP hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.There… … Wikipedia
