Multiprocessor Scheduling

In computer science, multiprocessor scheduling is an NP-Completeoptimization 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.

• CPU scheduling more complex when multiple CPUs are available

• Homogeneous processors within a multiprocessor

• Load sharing
  

Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing