Skip to Main content Skip to Navigation

Parallel machine scheduling problem with a single server: the case of an arbitrary number of machines

Abstract : Scheduling is a discipline of combinatorial optimization. It aims to allocate a limited set of resources over time to a set of jobs to be scheduled, with the aim of optimizing one or more criteria (project duration, advances/delays, availability of machines, etc.). Scheduling on parallel machines has been widely studied in the literature because of its practical and theoretical interest. Indeed, this type of configuration is well suited to model several real problems such as scheduling in operating rooms, queue management and scheduling of requests to processors, etc. However, a great number of works consider that the jobs to be scheduled are ready without prior preprocessing or setup. Therefore, under certain conditions, this assumption can lead to non optimal results, particularly if the processing time is substantial. This may result in a shortfall and/or waste of time. To overcome this, we are interested in the scheduling problem with a single server that performs these setup operations. The problem is studied in the literature only for specific cases, namely the case of two machines and the case of equal processing times. In this thesis, we consider the problem of scheduling independent jobs on an arbitrary number of identical parallel machines with a single server. In this problem, each job requires a setup or a loading operation before its execution on a machine. This operation is performed by a single server which can be a robot or an operator. This problem has several industrial applications, namely: in semi-automatic production, container terminal and biomass logistics. Firstly, we consider the objective function of minimizing the total execution time (makespan), where all jobs are available at the beginning of the scheduling. Several mathematical models are presented for the general case of this problem, and a mathematical model is proposed for the regular case based on mathematical properties. Due to the complexity of the problem (NP-hard), a lower bound, two greedy heuristics and a metaheuristic based on variable neighborhood search are proposed. Secondly, we propose a generalization of the problem, integrating the release and due dates for all the jobs. The objective function involves the minimization of the maximum lateness. In order to solve this new extension of the problem, we suggest a mathematical model for solving small-sized instances. For large-sized instances of the problem, we design two metaheuristics based on a general variable neighborhood search and a hybrid of greedy randomized adaptive search procedure with variable neighborhood descent. Our approaches show their efficiency on benchmark instances existing in the literature.
Document type :
Complete list of metadata
Contributor : Frédéric Pruvost Connect in order to contact the contributor
Submitted on : Monday, November 15, 2021 - 4:52:10 PM
Last modification on : Monday, January 31, 2022 - 2:50:36 PM


Distributed under a Creative Commons Attribution 4.0 International License


  • HAL Id : tel-03429508, version 1


Abdelhak El Idrissi. Parallel machine scheduling problem with a single server: the case of an arbitrary number of machines. Computer Science [cs]. Université Polytechnique Hauts-de-France; Institut national des sciences appliquées Hauts-de-France; Ecole Mohammadia d'ingénieurs (Rabat, Maroc), 2020. English. ⟨NNT : 2020UPHF0034⟩. ⟨tel-03429508⟩



Record views