We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m different machines.
The goal is to minimize the makespan - the total time required to execute the schedule.
The time that machine i needs in order to process job j is denoted by pi,j.
In the standard three-field notation for optimal job scheduling problems, the uniform-machine variant is denoted by Q in the first field.
" is a uniform 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 Q||
[1] It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the partition problem.
Horowitz and Sahni[1] presented: Minimizing the maximum completion time is NP-hard even for identical machines, by reduction from the partition problem.
A constant-factor approximation is attained by the Longest-processing-time-first algorithm (LPT).
Similarly, one can minimize the objective function sum(f(Ci)).
Then, by definition, the set of tasks constitute a lattice structure.