Identical-machines scheduling

Identical-machines scheduling is an <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a> in <a href="/facts/Computer_science/lN3pEyPz">computer science</a> and <a href="/facts/Operations_Research/H5yJkV5n">operations research</a>. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m identical machines, such that a certain objective function is optimized, for example, the <a href="/facts/Makespan/w1HEjJaQ">makespan</a> is minimized. 
Identical machine scheduling is a special case of <a href="/facts/Uniform_machine_scheduling/LFDtRUfD">uniform machine scheduling</a>, which is itself a special case of <a href="/facts/Optimal_job_scheduling/XyUejB6y">optimal job scheduling</a>. In the general case, the processing time of each job may be different on different machines; in the case of identical machine scheduling, the processing time of each job is the same on each machine. Therefore, identical machine scheduling is equivalent to <a href="/facts/Multiway_number_partitioning/6dUsX2HI">multiway number partitioning</a>. A special case of identical machine scheduling is <a href="/facts/Single-machine_scheduling/d0jkcNrh">single-machine scheduling</a>.
In the standard <a href="/facts/Optimal_job_scheduling/XyUejB6y">three-field notation for optimal job scheduling problems</a>, the identical-machines variant is denoted by P in the first field. For example, " P||
 
 
 
 
 C
 
 max
 
 
 
 
 {\displaystyle C_{\max }}
 
" is an identical machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. 
In some variants of the problem, instead of minimizing the maximum completion time, it is desired to minimize the average completion time (averaged over all n jobs); it is denoted by P||
 
 
 
 ∑
 
 C
 
 i
 
 
 
 
 {\displaystyle \sum C_{i}}
 
. More generally, when some jobs are more important than others, it may be desired to minimize a <a href="/facts/Weighted_arithmetic_mean/VHyJfPxb">weighted average</a> of the completion time, where each job has a different weight. This is denoted by P||
 
 
 
 ∑
 
 w
 
 i
 
 
 
 C
 
 i
 
 
 
 
 {\displaystyle \sum w_{i}C_{i}}
 
.

Identical-machines scheduling open-in-new

Identical-machines scheduling