Minimizing the Makespan Approximately on Two Identical Parallel Machines with a Loading--Unloading Server

Abstract

We study makespan minimisation on two identical parallel machines that share a single server for both loading and unloading. Each job must be loaded, processed without interruption on its assigned machine, and unloaded immediately after processing, with a common positive integer duration for all loading and unloading operations. We prove that the decision problem is NP-complete for every fixed server-operation duration and strongly NP-complete when this duration is part of the input. We then analyse ordinary list scheduling and the longest-processing-time rule in the non-unit setting. List scheduling has a tight supremum ratio of two. For the longest-processing-time rule, we obtain the exact worst-case ratio when all processing times are at least the server-operation duration, and derive new parameter-dependent lower and upper bounds for unrestricted instances. The results show that both processing-time granularity and blocking generated by short jobs shape the approximation behaviour of the common-server problem.