Skip to content

Formulations of scheduling problems

Part 2 · Formulations and their properties · Chapter 14 · Lecture notes, volume 2 (PDF) · Slides · Exercises: Scheduling problems

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • write the ILP model of \(P\|C_{\max}\) and explain how the makespan variable is linked to the machine loads;

  • write the LP relaxations and their duals, and prove that their optimal value is \(\sum_j t_j / m\);

  • prove that the LP bound is at least \(1/m\) of the optimal value, and that the factor is tight;

  • use the valid inequalities and the symmetry-breaking constraints of the model.

14.1 Overview of the family

  • The ILP models of the parallel machine scheduling problems use the set \(\mathscr{H}=\{1,2,\ldots,m\}\) of the machines and one binary assignment variable \(x_{jh}\) for each job \(j \in \mathscr{J}\) and each machine \(h \in \mathscr{H}\).

  • One continuous variable \(C_{\max}\) represents the makespan: one constraint for each machine imposes that \(C_{\max}\) is at least the load of the machine.

  • The objective function minimizes \(C_{\max}\), so at the optimum it is equal to the largest load.

The scheduling models are assignment models of the jobs to the machines, as the packing models assign items to bins; the min-max objective is linearized with the makespan variable \(C_{\max}\).

  • The table lists the members of the family, with the name of their ILP model and the section that writes it.
Problem Model Variables Section
\(P\|C_{\max}\) \(\mathrm{ILP}_{P\|C_{\max}}\) binary \(x_{jh}\) and continuous \(C_{\max}\) 14.2

  • Overview

    Overview of the family

    Open

  • 14.2 An ILP model for the Scheduling on Identical Parallel Machines Problem

    Some important theoretical properties

    Open

Next: 14.2 An ILP model for the Scheduling on Identical Parallel Machines Problem

Exercises on this chapter: Scheduling problems