Makespan (Interval Scheduling)

computation scheduling

Definition

Makespan

The makespan of a schedule is the time at which all scheduled jobs have completed.
If $C_j$ is the completion time of job $j$, then the makespan is

$$C_{\max }=\underset{j\in J}{\max }{C}_j.$$

Interpretation

Makespan measures the total length of the schedule. In an interval instance with fixed intervals $I_j=[s_j,f_j)$, the completion time of job $j$ is $C_j=f_j$, so

$$C_{\max }=\underset{j\in J}{\max }{f}_j.$$

For general scheduling problems, minimising makespan means finishing the whole set of jobs as early as possible.

Makespan vs. Processing time

Makespan is elapsed time, while total processing time is total work:

$$C_{\max }=\underset{j\in J}{\max }{C}_j,P=\sum _{j\in J}{p}_j.$$

These are equal only in special cases, such as one machine with no idle time and all jobs starting at time $0$.

The left schedule has no idle time on one machine, so elapsed time equals total work. The right schedule does $10$ units of work, but two machines process the jobs simultaneously, so the elapsed time is only $5$.

Objective

Makespan objective

The scheduling objective

$$\gamma =C_{\max }$$

asks for a feasible schedule with minimum makespan.

Minimising makespan is common when all jobs must be completed and the main cost is the final completion time, not the completion time of individual jobs.

Examples

Household chores on one machine

Suppose one person must complete all chores. This is the scheduling problem

$$1\mid \varnothing \mid C_{\max }.$$

With one person, the chores must be done sequentially. If the processing times add to $12$, then the minimum makespan is $12$.

Household chores on two identical machines

Suppose two people can work in parallel on the chores. This is the scheduling problem

$$P_2\mid \varnothing \mid C_{\max }.$$

The same total work can finish earlier because two chores may run at the same time. In this schedule, both people are busy until time $6$, so the makespan is $6$.