Improved Modeling and Genetic Algorithm for Job Sequencing and Tool Switching on Non-Identical Parallel Machines

Abstract

The job sequencing and tool switching problem with non-identical parallel machines (SSP-NPM) is a challenging combinatorial optimization problem that arises in flexible manufacturing systems. It jointly involves job assignment, sequencing, and tool management decisions under limited magazine capacities to minimize the makespan. In this paper, we first propose an improved position-based MILP (IPM). This model builds upon the one presented by [1], offering a more compact representation of completion times and is strengthened by static improvement mechanisms inspired by [2]. We then develop a genetic algorithm (GA) using an explicit permutation-assignment encoding and a tool-switch evaluator. Computational experiments were conducted on benchmark instances from the literature. Results show that the IPM solves 58.43% of instances to optimality, outperforming existing formulations, while on medium-size large-scale instances, the proposed GA converges about 50% faster than existing metaheuristic approaches.