Improved approaches to the exact solution of the machine covering problem

For the basic problem of scheduling a set of n independent jobs on a set of m identical parallel machines with the objective of maximizing the minimum machine completion time–also referred to as machine covering–we propose a new exact branch‐and‐bound algorithm. Its most distinctive components are a different symmetry‐breaking solution representation, enhanced lower and upper bounds, and effective novel dominance criteria derived from structural patterns of optimal schedules. Results of a comprehensive computational study conducted on benchmark instances attest to the effectiveness of our approach, particularly for small ratios of n to m.