Parallel-machine makespan with sequence-dependent setups ($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\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.