14.2 An ILP model for the Scheduling on Identical Parallel Machines Problem¶
Part 2 · Formulations and their properties · Chapter 14 · Chapter 14: Scheduling problems · Lecture notes, volume 2 (PDF) · Slides · Exercises: Scheduling problems
The problem of this section is the scheduling on identical parallel machines (\(P\|C_{\max}\)), defined in Chapter 7 «Scheduling problems».
-
Given \(m\) identical machines and a set \(\mathscr{J}=\{1,2,\ldots,n\}\) of \(n\) jobs, with processing times \(t_j\), we denote by \(\mathscr{H}=\{1,2,\ldots,m\}\) the set of machines.
-
We introduce the following \(nm\) binary variables:
\[ x_{jh}= \begin{cases} 1 & \text{if job $j$ is assigned to machine $h$}\\[1.5ex] 0 & \text{otherwise} \end{cases} \qquad \forall j\in\mathscr{J},~\forall h\in\mathscr{H}, \]and one non-negative continuous variable:
\[ C_{\max}=\text{makespan of the schedule}. \]
Using these variables, an Integer Linear Programming (ILP) model for the Scheduling on Identical Parallel Machines Problem (\(P\|C_{\max}\)) reads as follows:
This ILP model is referred to as the \(\mathrm{ILP}_{P\|C_{\max}}\) model.
-
Description of the objective function and constraints of the \(\mathrm{ILP}_{P\|C_{\max}}\) model:
-
the linear objective function \(\eqref{obj:PCMAX}\) minimizes the makespan;
-
constraints \(\eqref{assign:PCMAX}\) ensure that each job is assigned to exactly one machine (\(n\) linear constraints);
-
constraints \(\eqref{load:PCMAX}\) link the assignment variables with the makespan variable. In particular, they ensure that the makespan is greater than or equal to the load of every machine (\(m\) linear constraints);
-
finally, constraints \(\eqref{bin:PCMAX}\) and \(\eqref{nonneg:PCMAX}\) define the variables of the ILP model.
-
Explanation of the link between the variables
-
For every machine \(h\), the makespan and its load must satisfy the direct relation
\[ C_{\max}\ge \sum_{j\in\mathscr{J}}t_jx_{jh}, \]which is imposed by constraint \(\eqref{load:PCMAX}\).
-
Since the constraint holds for every machine, it imposes
\[ C_{\max}\ge \max_{h\in\mathscr{H}}\left\{\sum_{j\in\mathscr{J}}t_jx_{jh}\right\}. \] -
In every optimal solution equality holds. Indeed, if \(C_{\max}\) were larger than the maximum load, replacing \(C_{\max}\) with the maximum load would keep all the constraints \(\eqref{load:PCMAX}\) satisfied and would decrease the objective value by a positive amount, which contradicts optimality.
-
When no job is assigned to a machine, its load is zero.
Example 14.1: \(\mathrm{ILP}_{P\|C_{\max}}\) model
We consider \(m=3\) machines (\(\mathscr{H}=\{1,2,3\}\)) and a set \(\mathscr{J}=\{1,2,\dots,7\}\) of \(7\) jobs (\(n=7\)), with the following processing times:
This is the instance of Example 7.1 of Chapter 7 «Scheduling problems»; we refer to it as Example 14.1. The \(\mathrm{ILP}_{P\|C_{\max}}\) model for this instance is:
An optimal solution \((\tilde{\vet x},\tilde C_{\max})(\mathrm{ILP}_{P\|C_{\max}})\) is:
It assigns the jobs \(\{1,3\}\) to machine \(1\), \(\{2,4\}\) to machine \(2\) and \(\{5,6,7\}\) to machine \(3\), with loads \(9\), \(9\) and \(9\). The optimal value \(z(\mathrm{ILP}_{P\|C_{\max}})\) is \(9\), since it attains the lower bound
14.3 A first Linear Programming relaxation¶
To obtain a Linear Programming (LP) relaxation of the \(\mathrm{ILP}_{P\|C_{\max}}\) model, we relax constraints \(\eqref{bin:PCMAX}\) into non-negativity constraints. The obtained LP model reads as follows:
This LP model is referred to as the \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\) model.
Example 14.2: \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\) model
The \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\) model for the instance of Example 14.1 is:
An optimal solution \((\tilde{\vet x},\tilde C_{\max})(\mathrm{LP}\text{-}0_{P\|C_{\max}})\) is:
The optimal value \(z(\mathrm{LP}\text{-}0_{P\|C_{\max}})\) is \(9\). Accordingly we have the lower bound:
Using a free dual variable \(\mu_j\) for each constraint \(\eqref{assign:LP0-PCMAX}\) and a non-negative dual variable \(\pi_h\) for each constraint \(\eqref{load:LP0-PCMAX}\), the dual model of the \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\) model is:
This LP model is referred to as the \(D(\mathrm{LP}\text{-}0_{P\|C_{\max}})\) model.
Example 14.3: \(D(\mathrm{LP}\text{-}0_{P\|C_{\max}})\) model
The dual \(D(\mathrm{LP}\text{-}0_{P\|C_{\max}})\) model for the instance of Example 14.1 is:
An optimal solution \((\tilde{\vet\mu},\tilde{\vet\pi})(D(\mathrm{LP}\text{-}0_{P\|C_{\max}}))\) is:
The optimal value \(z(D(\mathrm{LP}\text{-}0_{P\|C_{\max}}))\) is \(9\).
Proposition 14.1: Optimal value of \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\)
For every \(P\|C_{\max}\) instance,
Proof
Set \(x_{jh}=1/m\) for every job and every machine, and set
Each constraint \(\eqref{assign:LP0-PCMAX}\) is satisfied and every machine has the displayed load, hence this is a feasible primal solution. In the dual, set
Constraints \(\eqref{x:DLP0-PCMAX}\) hold at equality, \(\sum_h\pi_h=1\), and the dual objective value is
By LP Weak Duality, the two solutions are optimal, and the optimal value is the common value of the objective functions. □
14.4 A second Linear Programming relaxation¶
To obtain an LP relaxation of the \(\mathrm{ILP}_{P\|C_{\max}}\) model, we relax constraints \(\eqref{bin:PCMAX}\) into the bounds \(0\le x_{jh}\le 1\). The obtained LP model reads as follows:
This LP model is referred to as the \(\mathrm{LP}_{P\|C_{\max}}\) model.
-
Constraints \(\eqref{ub:LP-PCMAX}\) do not change the relaxation: by \(\eqref{assign:LP-PCMAX}\) and \(\eqref{nonnegx:LP-PCMAX}\), each \(x_{jh}\) is at most one. Thus
\[ z(\mathrm{LP}_{P\|C_{\max}})=z(\mathrm{LP}\text{-}0_{P\|C_{\max}})=\frac{\sum_{j\in\mathscr{J}}t_j}{m}. \]
Example 14.4: \(\mathrm{LP}_{P\|C_{\max}}\) model
The \(\mathrm{LP}_{P\|C_{\max}}\) model for the instance of Example 14.1 is:
An optimal solution \((\tilde{\vet x},\tilde C_{\max})(\mathrm{LP}_{P\|C_{\max}})\) is the solution of Example 14.2:
The optimal value \(z(\mathrm{LP}_{P\|C_{\max}})\) is \(9\). Accordingly we have the same lower bound.
Using a free dual variable \(\mu_j\) for each constraint \(\eqref{assign:LP-PCMAX}\), a non-negative dual variable \(\pi_h\) for each constraint \(\eqref{load:LP-PCMAX}\) and a non-positive dual variable \(\lambda_{jh}\) for each constraint \(\eqref{ub:LP-PCMAX}\), the dual model of the \(\mathrm{LP}_{P\|C_{\max}}\) model is:
This LP model is referred to as the \(D(\mathrm{LP}_{P\|C_{\max}})\) model.
Example 14.5: \(D(\mathrm{LP}_{P\|C_{\max}})\) model
The dual \(D(\mathrm{LP}_{P\|C_{\max}})\) model for the instance of Example 14.1 is:
An optimal solution \((\tilde{\vet\mu},\tilde{\vet\pi},\tilde{\vet\lambda})(D(\mathrm{LP}_{P\|C_{\max}}))\) is the solution of Example 14.3 with \(\tilde\lambda_{jh}=0\) for every job and every machine:
The optimal value \(z(D(\mathrm{LP}_{P\|C_{\max}}))\) is \(9\).
14.4.1 Some important theoretical properties¶
Proposition 14.2: Worst-case ratio of the LP bound
For every \(P\|C_{\max}\) instance,
Proof
Assigning every job to one machine gives a feasible schedule of makespan \(\sum_jt_j\). Hence \(z(\mathrm{ILP}_{P\|C_{\max}})\le\sum_jt_j\). By Proposition 14.1,
□
Proposition 14.3: The ratio \(1/m\) is asymptotically attained
For a fixed number \(m \ge 2\) of machines, there are instances for which
Proof
For \(M\in\Z_{\ge2}\), consider one job of processing time \(M\) and \(m\) jobs of processing time one. The long job alone forces \(z(\mathrm{ILP}_{P\|C_{\max}})\ge M\). The schedule that assigns the long job alone to machine \(1\) and the \(m\) unit jobs to the other \(m-1\) machines has loads at most \(2 \le M\), hence the makespan \(M\) is feasible. Thus \(z(\mathrm{ILP}_{P\|C_{\max}})=M\). Proposition 14.1 gives
Therefore,
□
Example 14.6: an integrality gap
Consider two machines and three jobs with processing times \((3,3,2)\). Proposition 14.1 gives \(z(\mathrm{LP}_{P\|C_{\max}})=8/2=4\). In every integer schedule one machine processes at least two of the three jobs, so its load is at least \(3+2=5\); the schedule \(\{3,2\},\{3\}\) reaches it, so \(z(\mathrm{ILP}_{P\|C_{\max}})=5\). The fractional assignment
has load four on both machines, whereas the integer optimum has loads five and three.
14.5 Additional considerations¶
-
For every job \(j\), the inequality
\[\begin{equation*} C_{\max}\ge t_j \label{valid:job-PCMAX} \tag{14.6} \end{equation*}\]is a valid inequality for model (14.1). In every integer schedule, job \(j\) is assigned to one machine, whose load and therefore makespan are at least \(t_j\) (\(n\) linear constraints);
-
The inequality
\[\begin{equation*} C_{\max}\ge\left\lceil\frac{\sum_{j\in\mathscr{J}}t_j}{m}\right\rceil \label{valid:average-PCMAX} \tag{14.7} \end{equation*}\]is also a valid inequality for model (14.1): the \(m\) machine loads sum to \(\sum_jt_j\), so their maximum is at least their average and is an integer in every integer schedule (one linear constraint);
-
The machines are identical. The constraints
\[\begin{equation*} \sum_{j\in\mathscr{J}}t_jx_{jh}\ge \sum_{j\in\mathscr{J}}t_jx_{j,h+1} \qquad \forall h\in\{1,\ldots,m-1\} \label{symmetry:PCMAX} \tag{14.8} \end{equation*}\]are optimality-preserving constraints: they are not valid for every feasible assignment, but every schedule can be relabelled so that its machine loads are non-increasing, without changing the makespan.
-
The constraints \(\eqref{symmetry:PCMAX}\) remove the equivalent relabellings of the machines only when the loads are distinct. With equal loads they remove none: in the instance of the chapter all the optimal schedules have loads \(9\), \(9\), \(9\), and all the \(12\) optimal solutions of the model satisfy them.
14.6 Typical mistakes¶
Warning
-
Using the LP bound alone. The value \(\sum_j t_j/m\) ignores the longest job: with one very long job it is much smaller than the optimal value. The valid inequality \(C_{\max}\ge t_j\) must be added.
-
Forgetting to round up. All the processing times are integer, so \(C_{\max}\) is an integer in every integer schedule: the lower bound is \(\lceil \sum_j t_j/m \rceil\).
-
Believing that the symmetry constraints remove all the equivalent solutions. They remove the relabellings of the machines only when the loads are distinct; with equal loads they remove none.
-
Forgetting the direction of the load constraints. The constraints \(\eqref{load:PCMAX}\) bound \(C_{\max}\) from below: it is the minimization that makes \(C_{\max}\) equal to the largest load.
-
Mixing the indices. The variable \(x_{jh}\) has the job \(j\) first and the machine \(h\) second.
14.7 In summary¶
In summary
-
The \(\mathrm{ILP}_{P\|C_{\max}}\) model has \(n \cdot m\) assignment variables \(x_{jh}\) and the makespan variable \(C_{\max}\), linked by one load constraint for each machine.
-
The LP relaxation has optimal value \(z(\mathrm{LP}_{P\|C_{\max}}) = \sum_j t_j / m\), attained by assigning every job with value \(1/m\) to every machine; the dual solution is \(\tilde{\pi}_h = 1/m\) and \(\tilde{\mu}_j = t_j/m\).
-
The ratio between \(z(\mathrm{LP}_{P\|C_{\max}})\) and \(z(\mathrm{ILP}_{P\|C_{\max}})\) is at least \(1/m\), and \(1/m\) is asymptotically attained.
-
The valid inequalities \(C_{\max} \ge t_j\) and \(C_{\max} \ge \lceil \sum_j t_j/m \rceil\) strengthen the model.
Dashboard of the instance of the chapter (\(m=3\), \(t=(5,5,4,4,3,3,3)\)). Lower bounds on the optimal value \(9\):
| Bound | Value | From |
|---|---|---|
| LP relaxation | \(9\) | \(\sum_j t_j / m = 27/3\) |
| Valid inequalities | \(9\) | \(\max\{5, \lceil 27/3 \rceil\}\) |
| Optimal value | \(9\) | loads \(9\), \(9\), \(9\) |
On the instance of the integrality gap (\(m=2\), \(t=(3,3,2)\)) the LP bound is \(4\) and the optimal value is \(5\).
Exercises on this chapter: Scheduling problems