Efficient symmetry breaking formulations for the job grouping problem

The job grouping problem consists of assigning a set of jobs, each with a specific set of tool requirements, to machines with a limited tool capacity in order to minimize the number of machines needed. Traditionally, a formulation has been used that assigns jobs to machines. However, such a formulation contains a lot of symmetry since the machines are identical and they can be permuted in any feasible solution. We propose a new formulation for this problem, based on the asymmetric representatives formulation (ARF) idea. This formulation eliminates the symmetry between the identical machines. We further propose various symmetry breaking constraints, including variable reduction and lexicographic ordering constraints, which can be added to the traditional formulation. These formulations are tested on a data set from the literature and newly generated data sets using a state-of-the-art commercial solver, which includes symmetry breaking features.