Scheduling

Scheduling assigns jobs to processing resources and orders their execution subject to resource and precedence requirements. Objectives include completion time, lateness and throughput. In single-machine sequencing with all jobs mandatory, the total processing time is constant, but order-dependent setups can still change completion time. With parallel machines, machine allocation and sequencing jointly determine the parallel-machine makespan with sequence-dependent setups.

For single-machine jobs all available at time zero, order by nondecreasing deadline. Keep a tentative on-time list. Whenever appending a job makes its completion exceed its deadline, delete a job of largest processing time from that list and place it on a rejected list. Append all rejected jobs at the end. This minimizes the number of late jobs: at the first missed deadline at least one job of that prefix must be rejected, and rejecting a longest one frees at least as much processing time as any alternative. The exchange argument applies recursively to the remaining prefixes. The algorithm needs no ordering of the rejected jobs to determine the minimum count.

The time at which all work in a scheduling instance has finished, equivalently the largest completion time measured from a common start. For divisible job sizes $t_i\ge 0$ and positive machine speeds $s_j$, when each machine's completion time is its total assigned size divided by its speed, the minimum makespan is ${\sum }_i{t}_i/{\sum }_j{s}_j$. The lower bound follows from total processing capacity; assigning the fraction $s_j/{\sum }_h{s}_h$ of each job to machine $j$ attains it.

On one server with all jobs initially available, nonnegative fixed durations and no sequence-dependent setup, a nondecreasing-duration order minimizes the sum of completion times. Swapping adjacent durations $a>b$ reduces their combined contribution by $a-b$ and changes no later completion time, because their total duration is unchanged. Repeated adjacent exchanges remove every inversion. The sum of pre-service waiting times has the same optimum, differing by the fixed total duration.

Partition jobs between machines and choose an ordering on each machine. Machine $r$ has load $C_r$ equal to its processing times, initial setup and internal changeovers; the completion time of all jobs is the maximum of these loads. Minimize a variable $C_{\max }$ subject to $C_r\le C_{\max }$ for every machine. Branch and bound can combine machine-assignment decisions with route bounds; heuristic moves relocate jobs between machines, swap jobs, and reorder blocks. Minimizing the sum of route costs alone does not generally minimize the makespan.