= Parallel-machine makespan with sequence-dependent setups
{title2=$C_{\max}=\max_r C_r$}
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\leq 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.
Back to article page
