Parallel machine scheduling with tool loading

• The problem environment is parallel machine systems.
• We solve loading, tooling and scheduling problems simultaneously.
• We provide two mathematical models with the objective of minimizing makespan.
• We suggest a tabu search algorithm.

This paper presents a mixed integer programming approach that integrates the tool assignment and scheduling problems arising in parallel machine environments. There are a number of operations to be processed on parallel machines. Each operation requires a set of tools; however, the number of available tools are limited. Our objective is to minimize the makespan, i.e. the completion time of the final operation. We propose two different mathematical programming models for this problem. Since the problem is strongly NP-hard in general, finding the optimal solution requires extremely long computational times as the problem size increases. We therefore develop a tabu search algorithm in order to find near-optimal solutions within reasonable times.