An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems

Abstract

This paper presents the problem of batching and scheduling jobs belonging to incompatible job families on unrelated-parallel machines. More specifically, we investigate cost-efficient approaches for solving batching and scheduling problems concerning the desired lower bounds on batch sizes (${\mathit{LB}}_b$), which indirectly has a considerable impact on the production cost. Batch scheduling is a more realistic extension of the traditional group scheduling approach, in which the jobs belonging to a job family can be processed as multiple batches. The objective is to minimize the total weighted job completion time and tardiness subject to a machine- and sequence-dependent setup time, dynamic machine availability and job release times, customer segments and job priority, and different machine capability and eligibility criteria for processing. Solving this type of batch scheduling problem is a big challenge due to the high computational complexity incurred by both the sequencing assignment and batching composition. A machine learning random forest classification algorithm is used for the ${\mathit{LB}}_b$ determination. Then, an efficient mixed-integer linear programming model (MILP) is developed based on the flow conservation constraints of jobs on machines to reduce the computational complexity. By mapping the MILP model onto a network formulation, an equivalent integer set partitioning type formulation is developed for a branch-and-price optimization algorithm. Computational experiments carried out over different sets of instances, indicate the efficiency and effectiveness of the optimization algorithm, compared to the linear relaxation and relaxed MILP models. Regarding the only available benchmark in the literature, the optimization algorithm yields optimal solutions with affordable computational time.