Solution Approaches for the Balanced Task Planning Problem

In this paper, we introduce and solve the Balanced Task Planning Problem, which originates from real-life industrial domains. The aim of this problem is to assign tasks to machines and planning periods so that machine loads are balanced around a target value while prioritizing more critical tasks. We provide a formal problem description and use Constraint Programming and Integer Programming solvers to find optimal solutions. For large-scale instances, we propose local search variants based on Tabu Search. To evaluate the methods, we generate a large number of random problem instances and perform an experimental evaluation of the different approaches. The results show that most of the small instances can be solved using the exact approach, and, for some, optimal solutions can be obtained. Using Tabu Search, high-quality solutions could be found for the large majority of large-scale instances.