Exact and heuristic methods to solve the parallel machine scheduling problem with multi-processor tasks

Abstract

This paper studies a special parallel machine scheduling problem where some tasks require more than one machine to process, known as the Parallel Machine Scheduling Problem with Multi-processor Tasks. Two mathematical models and several theoretical properties are proposed for the studied problem. To solve this problem, this paper develops an exact branch and bound algorithm and a heuristic tabu search algorithm. A series of numerical experiments are conducted to test the performance of these solution methods. The computational results show that the solution methods are effective and efficient in solving the problem with different sizes.