CP Objectives: Makespan, Tardiness, Weighted Sums

Standard objective functions used in constraint-programming scheduling models: the makespan $C_{\max}$ , total tardiness $\sum T_j$ , and weighted sums such as $\sum w_j T_j$ and $\sum w_j C_j$ . Students learn to compute each objective from a given schedule.

Step 1 of 157%

Tutorial

Makespan

A constraint-programming model for a scheduling problem needs an objective function that ranks feasible schedules. The most common one is the makespan.

The makespan is the time at which the last job in a schedule finishes. Given $n$ jobs with completion times $C_1, C_2, \ldots, C_n$ , the makespan is

C_{\max} = \max_{j=1,\ldots,n} C_j.

Minimizing $C_{\max}$ packs all the work into the shortest overall schedule.

For instance, if four jobs finish at $C_1 = 8,\ C_2 = 11,\ C_3 = 6,\ C_4 = 11$ , then

C_{\max} = \max(8,\, 11,\, 6,\, 11) = 11.

When jobs run in sequence on the same machine starting at $t = 0$ , each completion time equals the running total of processing times up to and including that job. With parallel machines, $C_{\max}$ is the latest finish across all machines.