Exact approaches for parallel machine scheduling with loading and unloading servers

We study the non-preemptive scheduling of general jobs on identical parallel machines, where loading and unloading operations are performed by either a single shared server or by two dedicated servers. The objective is to minimise the makespan. In the literature, exact solution approaches are scarce, and limited to the two-machine case with a single server, or to regular job sets processed on any number of machines with two dedicated servers. We propose three exact solution approaches, each of which is adapted to both problem variants for any number of machines. We adapt two existing models, the time-indexed formulation (TIF) and the arc-flow formulation (FFF), and we propose a constraint programming model (CP). The performance of the models is assessed on benchmark instances with up to 100 jobs and 7 machines. Computational results showed that the FFF and CP models outperformed TIF for instances with more than 10 jobs. CP showed an outstanding performance, solving the majority of problems with 100 jobs to optimality in a short computational time. When non optimal, CP provided feasible solutions with an extremely low gap to best bound.