An Almost Exact Multi-Machine Scheduling Solution for Homogeneous Processing

In the context of job scheduling in parallel machines, we present a class of asymptotically exact binary programs for the minimization of the $\tau$-norm of completion time variances. Building on overlooked properties of the min completion time variance in a single machine and on an equivalent bilevel formulation, our approach provides an asymptotic approximation (with quadratic convergence) that can be computed much more efficiently than the original problem. Dominance properties are enforced as linear constraints to improve the characterization of the exact solution by these bounds. Our numerical study reveals that the lower bound problem can be solved in less than one third of computation time, in comparison to the exact problem, while resulting in an almost identical solution.

Article

Download

View An Almost Exact Multi-Machine Scheduling Solution for Homogeneous Processing