Skip to content

Scheduling problems

Part 1 · Combinatorial optimization problems · Chapter 7 · Lecture notes, volume 1 (PDF) · Slides · Exercises: Scheduling problems

Prerequisites

Objectives

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

  • classify a scheduling problem with the three-field notation, and state the problem \(P\,||\,C_{\max}\);

  • describe a schedule by the sets of jobs of the machines, and compute loads and makespan;

  • count the assignments and the distinct schedules of an instance;

  • build a first schedule by hand, assigning every job to the least loaded machine;

  • compute a lower bound on the optimal makespan and use it to prove that a schedule is optimal.

7.1 Overview of the family

  • The scheduling problems of this chapter share the same data: a set \(\mathscr{J} = \{1,2,\dots,n\}\) of \(n\) jobs, \(m\) parallel machines and, for each job, a processing time.

  • A solution assigns every job to a machine: the jobs \(J_h\) of machine \(h\) are processed one after the other, and the machine completes them at the time \(L_h\), its load.

  • The objective is to minimize the makespan \(C_{\max} = \max_h L_h\), the completion time of the last job.

A parallel machine scheduling problem partitions the jobs among the machines so that the last machine finishes as early as possible. The members of the family differ in the machine environment, described by the three-field notation.

  • The table lists the members of the family, with the section that defines each of them.
Problem Notation Machines Section
identical parallel machines \(P\,||\,C_{\max}\) every job takes \(t_j\) on every machine 7.2
machines with different speeds \(Q\,||\,C_{\max}\) machine \(h\) has its own speed 7.1.1
unrelated parallel machines \(R\,||\,C_{\max}\) job \(j\) takes \(t_{jh}\) on machine \(h\) 7.1.1

7.1.1 The three-field notation

  • Scheduling problems are classified with the three-field notation \(\alpha\,|\,\beta\,|\,\gamma\) of Graham, Lawler, Lenstra and Rinnooy Kan, where:

    1. \(\alpha\) describes the machine environment: \(1\) for a single machine, \(P\) for identical parallel machines, \(Q\) for parallel machines with different speeds, \(R\) for unrelated parallel machines;

    2. \(\beta\) describes the job characteristics, such as release dates \(r_j\) or precedence constraints prec; an empty field means that there are none;

    3. \(\gamma\) describes the objective function, such as the makespan \(C_{\max}\) or the total completion time \(\sum_j C_j\).

  • In this notation, \(P\,||\,C_{\max}\) is the problem of scheduling jobs without additional characteristics on identical parallel machines, minimizing the makespan.

  • Overview

    Overview of the family · The three-field notation

    Open

  • 7.2 Scheduling on identical parallel machines

    Counting the solutions · A first schedule by hand · A combinatorial lower bound · Relation with the bin packing problem · Remarks

    Open

Next: 7.2 Scheduling on identical parallel machines

Exercises on this chapter: Scheduling problems

In depth: what the course does on this problem