Scheduling operations for multi-spindle and multi-machining unit machines

We address a scheduling problem which arises in the operations of multiple-spindle and multiple-machining unit machines with the objective of minimizing the makespan. These machines can process multiple workpieces simultaneously and perform multiple operations on the same workpiece simultaneously by using multiple tools. This characteristic of parallel machining tools leads to new practices which are not common in traditional scheduling literature. In addition to the precedence relationships, the inclusion/exclusion constraints determine which operations must/cannot be performed on the same spindle and machining unit. We first discuss the manufacturing environment and present the mathematical programming formulation of the problem. Since, this problem is NP-hard, we consider greedy construction algorithms based on dispatching rules. The greedy algorithms are effective in obtaining solutions fasts; however, the quality of the solutions is usually unsatisfactory. So, to improve the greedy solutions we implement scatter search approach with path relinking. We test the performance of the proposed method using synthetic and real data.