It's a bit late, but last year during the Christmas break, Kaggle had a very interesting competition for the season. The story was that the toy list at Santa's workshop was long, and elves had to make all the toys, with some constraints on their productivity rating and rest intervals. This is an adaptation of the classic problem of minimizing makespan, though with additional constraints. A good leaderboard position could be achieved using offline methods since the entire list of toys was supplied in advance, but as usual I pursued online solutions for fun and speed. The problem they described can be reformulated as online makespan optimization for unrelated parallel machines with maintenance windows.

Given a set of n different jobs, each with an associated running time, and a set of k identical machines, our task is to assign each job to a machine to minimize the time to complete all jobs. In the OR literature, this is called identical parallel machine scheduling, while in AI it is called number partitioning. For eight or more machines, an OR approach based on bin packing appears best, while for fewer machines, a collection of AI search algorithms perform best. We focus here on scheduling up to seven machines, and make several new contributions. One is a new method that significantly reduces duplicate partitions for all values of k, including k = 2. Another is a new version of the Complete-Karmarkar-Karp (CKK) algorithm that minimizes the makespan. A surprising negative result is that dynamic programming is not competitive for this problem, even for k = 2. We also explore the effect of precision of values on the choice of the best algorithm. Despite the simplicity of this problem, a number of different algorithms have been proposed, and the most efficient algorithm depends on the number of jobs, the number of machines, and the precision of the running times.