An Arc-Flow Model for the Makespan Minimization Problem on Identical Parallel Machines

Abstract

In this paper, we consider the basic makespan minimization problem on identical parallel machines. The aim of this study is to solve, to optimality the hard instances of the literature. We present an integer linear program based on an innovative arc-flow model inspired from the duality between the bin packing problem and the parallel-machine scheduling problem. The proposed mathematical model is tested on a large set of hard instances. The results of computational experiments attest the efficiency of the new approach and prove that it outperforms the existing ones. In addition to its efficiency, the proposed method is simple and easy to use.

Keywords

• Arc-flow model
• integer programming
• parallel machines
• scheduling