Jobs and Objective

Completion-Time Objective

Completion times are the quantities the simple objective adds.

highlighted = computed this step

Completion time

A job's completion time is when it finishes on the single machine.

completion time=finish time\text{completion time}=\text{finish time}
Single-machine sequencesThe chart recomputes completion times for both orders.original order and SPT orderimprovement 3OriginalA p=3C=3B p=1C=4C p=2C=606SPTB p=1C=1C p=2C=3A p=3C=606completion tablejoboriginal CSPT CA36B41C63totals 13 -> 10averages 13/3 -> 10/3

Total completion

The objective adds all completion times.

∑Cj\sum C_j
Single-machine sequencesThe chart recomputes completion times for both orders.original order and SPT orderimprovement 3OriginalA p=3C=3B p=1C=4C p=2C=606SPTB p=1C=1C p=2C=3A p=3C=606completion tablejoboriginal CSPT CA36B41C63totals 13 -> 10averages 13/3 -> 10/3

Average flow

Average flow time divides the total by the number of jobs.

average=∑Cj/n\text{average}=\sum C_j/n
Single-machine sequencesThe chart recomputes completion times for both orders.original order and SPT orderimprovement 3OriginalA p=3C=3B p=1C=4C p=2C=606SPTB p=1C=1C p=2C=3A p=3C=606completion tablejoboriginal CSPT CA36B41C63totals 13 -> 10averages 13/3 -> 10/3

Objective note

This book optimizes total completion time and average flow time, not due-date lateness.

objective: total completion time\text{objective: total completion time}
Single-machine sequencesThe chart recomputes completion times for both orders.original order and SPT orderimprovement 3OriginalA p=3C=3B p=1C=4C p=2C=606SPTB p=1C=1C p=2C=3A p=3C=606completion tablejoboriginal CSPT CA36B41C63totals 13 -> 10averages 13/3 -> 10/3