Parallel batching with multi-size jobs

Parallel batch scheduling has many applications in the industrial sector, such as material and chemical treatments, components creation through mold or additive manufacturing, and so on. The number of jobs that can be processed on a machine mostly depends on the shape and dimension of the jobs and of the machine. Literature provides many researches on the topic with several batching criteria however, to the authors knowledge, there is no study that considers batching jobs with multiple size constraints. The work investigates this problem, by considering that the batch capacity cannot exceed the sum of sizes of the jobs composing it, for each dimension (e.g., height and volume). A solution to the problem is generated by a column generation based heuristic. The heuristic first generates a set of the most promising batches through column generation by exploiting dynamic programming for the pricing procedure; then an integer optimal solution is built with the commercial solver CPLEX. The algorithm is further improved with a variable fixing procedure that speeds up the integer solution generation. Experiments are run on instances with several combinations of parameters and results show the impact of the number and type of sizes on computational times and quality of solutions. Some considerations are extended to the problem that also considers incompatible job families.