Added to Favorites

Related Searches

Definitions

Nearby Words

In computer science, multiprocessor scheduling is an NP-Complete optimization problem. The problem statement is: "Given a set J of jobs where job j_{i} has length l_{i} and a number of processors m_{i}, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?" 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 first end time. This algorithm achieves a sharp bound of 4/3 - 1/(3m) OPT.
## Similar Problems

Since multiprocessor scheduling is NP-Complete, it can be restated as any other NP-Complete problem. One of the simplest restatements of the problem is as a linear bin packing problem, where each processor is a "bin", and each job is represented by an object to pack, whose length is proportional to the job's time. Thus, the approximation algorithms used with bin packing can easily be adapted to multiprocessor scheduling.
## Sources

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Friday September 12, 2008 at 13:32:03 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Friday September 12, 2008 at 13:32:03 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.