Scheduling on identical parallel machines (\(P\|C_{\max}\))¶
Definition 1: Scheduling on identical parallel machines
Given:
-
a set of \(m\) identical machines,
-
a set \(\mathscr{J} = \{1,2,\dots,n\}\) of \(n\) jobs,
-
for each job \(j \in \mathscr{J}\), a processing time \(t_j \in \Z_{\ge 1}\),
the problem \(P\,||\,C_{\max}\) asks to assign each job to a machine, so that the time needed to complete all the jobs, i.e., the largest total processing time assigned to a machine, is minimized.
Assumptions
-
We make the following assumption:
-
There are more jobs than machines (otherwise each job gets a machine of its own, and the optimal makespan is \(\max_j t_j\)). Formally:
\[ n > m \]
-
What the course does on this problem¶
Properties¶
-
Strongly NP-hard when \(m\) is part of the input; weakly NP-hard for a fixed number of machines (Ch. 1).
-
Lower bound \(\max\{\max_j t_j, \lceil \sum_j t_j/m \rceil\}\); it is not always attained: \((4,3,3)\) on two machines gives \(5\), the optimum is \(6\) (Ch. 7).
-
A makespan at most \(T\) exists if and only if the jobs fit into \(m\) bins of capacity \(T\) (Ch. 7).
Formulations¶
-
The model \(\ILP_{\PCmax}\) has \(nm\) binary variables \(x_{jh}\) and the continuous variable \(C_{\max}\) (Ch. 14).
-
The LP bound is \(\sum_j t_j/m\); its ratio to the optimum is at least \(1/m\), and \(1/m\) is approached (Ch. 14).
-
Valid inequalities strengthen the model; load ordering breaks the symmetry only when the loads are distinct (Ch. 14).
Heuristics¶
-
On the instance of Ch. 7 (three machines, optimum \(9\)) LIST with the shortest jobs first gives \(12\) and LPT gives \(11\) (Ch. 30).
-
The LPT solution is a local optimum for move, while two swaps reach \(9\); the auxiliary objective \(\sum_h L_h^2\) gives a slope to the plateaus (Ch. 31).
-
Tabu search and VNS reach \(9\) on the same instance (Ch. 32).
MIP heuristics¶
-
On the instance of Ch. 7 fractional diving ends at \(10\), guided diving from LPT finds \(9\), the feasibility pump returns \(11\) (Ch. 33).
-
RINS, local branching and proximity search, started from LPT, reach \(9\); proximity search also proves it optimal (Ch. 33).