A reduction approach for the parallel machine scheduling problem with a separate server for loading and unloading operations

This paper addresses the non-preemptive identical parallel machine scheduling problem with a dedicated loading server and a dedicated unloading server. Each job has to be loaded by the dedicated loading server immediately before being processed on one of the identical parallel machines, and unloaded immediately by the dedicated unloading server after its processing. The objective function involves the minimization of the makespan. This problem arises in the semiconductor industry, plastic injection industry, kitchen production systems, healthcare, container terminals, and many other industrial fields. We prove the problem to be strongly NP-hard, analyze a special case with identical loading, processing, and unloading times, and establish a tight lower bound. In addition, we propose two novel mixed-integer linear programming formulations: one utilizing time-indexed variables with an iterative strengthening algorithm, and the other employing linear-ordering variables along with two enhanced valid inequalities. Given the complexity of the problem, we introduce a reduction approach that simplifies the problem by modifying certain constraints, enabling the determination of a feasible solution much more quickly. Building on this reduction, we provide a linear-time reduction algorithm and a fast formulation based on assignment-and-positional date variables. Furthermore, we study a special case involving regular jobs. To solve large-scale instances of the problem with up to 250 jobs and up to 5 machines, we design a hybrid approach combining an iterated greedy algorithm with variable neighborhood descent. As shown in the computational experiments on two sets of benchmark instances, the reduction approach significantly outperforms all previous methods existing in the literature.