# Job-Shop Scheduling with Cooperative Transportation Resources

Amine Oussama, Jean-Philippe Gayon, Philippe Lacomme

► To cite this version:

Amine Oussama, Jean-Philippe Gayon, Philippe Lacomme. Job-Shop Scheduling with Cooperative Transportation Resources. 26ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, École Nationale des Ponts et Chaussées, Feb 2025, Champs-Sur-Marne, France. hal-05361856

HAL Id: hal-05361856

https://hal.science/hal-05361856v1

Submitted on 13 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Job-Shop Scheduling with Cooperative Transportation
Ressources

Amine Oussama¹, Jean-Philippe Gayon¹, Philippe Lacomme¹

Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS,
63000 Clermont-Ferrand, France

{amine.oussama, j-philippe.gayon, philippe.lacomme}@uca.fr

**Keywords** : Job-Shop scheduling, Transportation, Reconfigurable and cooperative robots,
Synchronization, Disjunctive graph, Metaheuristic, Mixed integer linear programming

# 1 Introduction

The Job-Shop scheduling Problem (JSP) is one of the most known problems in the domain of the production task scheduling [1]. The Job-Shop scheduling Problem with Transportation resources (JSPT) is a generalization of the classical JSP and consists of jointly scheduling production operations and transport operations which are performed by automated vehicles also called mobile robots [2, 3]. The context of this work is to address the increasing robotization of manufacturing and logistics processes taking into account the new-generation mobile robots that can be operated to handle or transport a heavy or large object by cooperation [4, 5].

In this work, we examine the JSPT from a more general perspective, where each transport
operation can require the simultaneous use of several specialized robots due to the unique
characteristics and handling requirements of each job, encompassing factors like size, weight
and fragility. The originality of our work lies in considering the JSPT environment with
the assumption that a transport operation may require the intervention of several robots to
cooperate in carrying a job from a machine to another which requires proper synchronization
between robots over time. We call this new variant the Job-Shop scheduling Problem with
Cooperative Transportation resources (JSPT-C). To the best of our knowledge this problem
has never been studied before. Note that synchronization issues appear in other problems
including the Vehicle Routing Problem [6] where the synchronization can involve, for instance,
vehicles, drivers or medical staff. The primary goal of this presentation is to introduce the
JSPT-C problem, and establish a disjunctive graph model for the problem. We also propose
an exact resolution using a MILP approach, and an approximate resolution by a metaheuristic.
Moreover, We showcase how to use the model to solve classical JSPT instances from the
literature, and we propose a comparative experimental study between the exact and heuristic
approaches on newly generated instances specifically designed for the JSPT-C.

# 2 Problem description

We consider a set of *N* jobs *J*={*J*₁,..., *J*ₙ} that have to be processed on a set of *M* machines. Each job *J*ᵢ consists of *n*ᵢ ≤ *M* production operations, and is processed exactly once on a specific machine. The *j*-th production operation of job *J*ᵢ has an uninterrupted processing time *P*ᵢⱼ. A machine can process only one job at once. Jobs are transported between machines using a set of *NR* robots *R*. These robots have identical (loaded or unloaded) transportation times from a source machine to a destination machine but may differ in their ability to handle specific jobs. Initially, all jobs and robots are located at a depot. The process of transferring a job from one machine (or depot) to another is referred to as a transport operation. Each
production operation is preceded by a transport operation, hence each job has $n_i$ transport operations. The first transport operation of a job consists of transferring the job from the depot to the machine performing its initial production operation. The j-th transport operation of job $J_i$ requires a subset of $R_{ij}$ robots selected from the subset $C_{ij} \subseteq \mathcal{R}$ of robots that can handle this specific transport operation. The objective is to determine an assignment of transport operations to the required number of robots, a sequence of production operations on the machines, and a sequence of transport operations on the robots, in order to minimize the Makespan, which is the time at which all jobs have been processed.

# 3 Formulations and Results

A disjunctive graph model for the JSPT-C will be presented : this model is an extension of the disjunctive graph model originally proposed for the JSP and later adapted for the JSPT, incorporating the cooperation and synchronization of multiple robots to perform a transport operation. We will also present a MILP formulation and a GRASPxELS metaheuristic with a local search procedure that leverages Bierwith's sequence method for solution evaluation. In a first experimental study, we validate the correctness of our model by solving a set of 40 instances of the classical JSPT from the literature. We demonstrate that our model, dedicated to a more general problem, has some merit in effectively solving the JSPT compared to the best-published methods specifically designed for that problem. With a time limit set to 1 hour, our MILP finds optimal solutions for all the instances except for 3, with an average computational time of 95 seconds to find an optimal solution, while our metaheuristic converges in an average of 22 seconds providing high-quality solutions with an average GAP of 3.73%. In a second experimental study, we adapted some of the previously used 40 classical JSPT instances to our problem for which we added cooperation and synchronization issues. These instances are relatively small: $N \in [5, 8]$, $M = 4$ and $NR = 2$ but the number of disjunctive graphs is strongly high due to the robot assignment problem. We also generated new instances for the JSPT-C problem by adapting some known JSP instances from the literature. We compared our metaheuristic with the exact approach, and we demonstrate that our metaheuristic provides high-quality solutions in a reduced computational time. This leads us to conclude that both our modeling and local search strategies are effective.

To favor future research, all the solutions computed by our approach and the used and newly generated instances are available online at

<https://perso.isima.fr/~amoussam/index_files/pages/Research/JSPT-C.html>

# References

[1] Hegen Xiong et al. "A survey of job shop scheduling problem: The types and models". In: *Computers & Operations Research* 142 (2022), p. 105731.

[2] Johann Hurink and Sigrid Knust. "Tabu search algorithms for job-shop problems with a single transport robot". In: *European journal of operational research* 162.1 (2005), pp. 99–111.

[3] Ümit Bilge and Gündüz Ulusoy. "A time window approach to simultaneous scheduling of machines and material handling system in an FMS". In: *Operations Research* 43.6 (1995), pp. 1058–1070.

[4] Jungwon Seo, Jamie Paik, and Mark Yim. "Modular reconfigurable robotics". In: *Annual Review of Control, Robotics, and Autonomous Systems* 2.1 (2019), pp. 63–88.

[5] MecaBotiX. https://www.mecabotix.com/. Accessed: 2023.

[6] Michael Drexl. "Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints". In: *Transportation Science* 46.3 (2012), pp. 297–316.