Arc Flow Formulation for Efficient Uniform Parallel Machine Scheduling

This paper considers the scheduling problem of uniform parallel machines. The objective is to minimize the makespan. This problem holds practical significance and is inherently NP-hard. Therefore, solutions of the exact formulation are limited to small-sized instances. As the problem size increases, the exact formulation struggles to find optimal solutions within a reasonable time. To address this challenge, an arc flow formulation is proposed, aiming to solve larger instances. The arc flow formulation creates a pseudo-polynomial number of variables, with its size being significantly influenced by the problem’s bounds. Therefore, bounds from the literature are utilized, and symmetry-breaking rules are applied to reduce the size of the arc flow graph. To test the effectiveness of the proposed arc flow formulation, it was compared with a mathematical formulation from the literature on small instances with up to 30 jobs. Computational results showed that the arc flow formulation outperforms the mathematical formulation from the literature, solving all cases within a few seconds. Additionally, on larger benchmark instances, the arc flow formulation solved 84.27% of the cases to optimality. The maximum optimality gap does not exceed 0.072% for the instances not solved to optimality.