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

Abdelhak Elidrissi, Jatinder N.D. Gupta, Rachid Benmansour and Bertrand M.T. Lin

European Journal of Operational Research, 2026, vol. 328, issue 1, 15-31

Abstract: 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.

Keywords: Parallel machine scheduling; Loading server; Unloading server; NP-hardness; Mixed-integer linear programs; Problem reduction; Iterated greedy algorithm; Variable neighborhood descent (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172500414X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:328:y:2026:i:1:p:15-31

DOI: 10.1016/j.ejor.2025.05.030

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().