Skip to content

Scheduling problems

Catalogue of combinatorial problems · Catalogue (PDF)

  • Given \(n\) jobs with processing times and \(m\) parallel machines, a solution assigns every job to one machine, where it is processed without interruption.

  • The objective is to minimize the makespan \(C_{\max}\), the completion time of the last job; in the three-field notation \(\alpha\|C_{\max}\) the field \(\alpha\) describes the machines: identical (\(P\)), a fixed number of identical machines (\(Pm\)), with different speeds (\(Q\)) or unrelated (\(R\)).

Problem Acronym Difference
Scheduling on identical parallel machines \(P\|C_{\max}\) The central problem of the family.
Scheduling on a fixed number of identical machines \(Pm\|C_{\max}\) Special case of \(P\,||\,C_{\max}\) with \(m\) fixed; with \(m=2\) it asks for a split of the jobs into two sets of loads as equal as possible.
Scheduling on parallel machines with different speeds \(Q\|C_{\max}\) Generalizes \(P\,||\,C_{\max}\), which is the case of machines with equal speeds.
Scheduling on unrelated parallel machines \(R\|C_{\max}\) Generalizes \(Q\,||\,C_{\max}\) and \(P\,||\,C_{\max}\).