Abstract: The parallel machines scheduling problem with job-splitting property and family setups is common in engineering practice such as drilling task scheduling of printed circuit boards. Until now, there is still a lack of efficient optimization model and method. To address this issue, a mathematical model with the objective to minimize the total tardiness is first constructed, and then two existing dominance rules are embedded in the form of constraints. In order to solve a practical size problem efficiently, the simulated annealing algorithms with embedded dominance rules are proposed. Finally, computational experiments based on randomly generated instances are designed to validate the effectiveness of the constructed models and algorithms. Experimental results show that the proposed mathematical model with embedded dominance rules is superior to the existing model in terms of the size of the problem that can be solved and the computational efficiency. In addition, the proposed simulated annealing algorithm with embedded dominance rules are also superior to the existing simulated annealing algorithm.

Key words: parallel machines scheduling, job splitting, family setups, dominance rules, integer programming, simulated annealing algorithm