# Rescheduling Problem for Heavy Cargo Logistics with Transporters

Kyungduk Moon, Myungho Lee, Kangbok Lee

► To cite this version:

Kyungduk Moon, Myungho Lee, Kangbok Lee. Rescheduling Problem for Heavy Cargo Logistics with Transporters. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2022, Gyeongju, South Korea. pp.485-493, 10.1007/978-3-031-16407-1_57 . hal-05386129

HAL Id: hal-05386129

https://inria.hal.science/hal-05386129v1

Submitted on 27 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
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Rescheduling Problem for Heavy Cargo Logistics with Transporters

Kyungduk Moon✉, Myungho Lee✉, and Kangbok Lee✉,✉

Pohang University of Science and Technology, Pohang, South Korea

kblee@postech.ac.kr

**Abstract.** We consider a flexible flow shop rescheduling problem with transporters that carry heavy cargoes from a manufacturing site to loading docks. If a transporter is occupied by a heavy cargo, it cannot transport other heavy cargo until the operation at the last stage of the dedicated heavy cargo is completed. This imposes resource constraints for transporters that are practically relevant in heavy cargo logistics. We also consider stage skipping, resource eligibility constraints, sequence-dependent relocation time on transporters, and available time intervals of resources. Assuming that an initial schedule is given, we propose a mixed-integer (linear) programming model for a scheduling problem with multiple objectives including makespan and several rescheduling objectives.

**Keywords:** Scheduling · Transporter · Resource constraint · MIP

## 1 Introduction

Heavy cargoes produced in South Korea are transported by specialized cargo ships and transporters from suppliers to domestic customers. For example, steel plates and coils produced by a steel-making company are transported by elevation transporters (E/T cars) to specialized ships called Roll-on/Roll-off (RoRo) ships, and then delivered by those ships to final destinations. In this paper, we demonstrate how practical scheduling problems happening in heavy cargo logistics can be managed by using Mixed-Integer (linear) Programming (MIP) formulation.

Each job representing a delivery batch consists of multiple operations including loading cargoes to a transporter, inspection, and unloading cargoes at a yard. According to operation types, we can assume that there is a list of stages, and each job is processed through a predefined sub-sequence of stages on the given list. The first/last stage is always loading/unloading cargoes, while some stages in the middle (e.g., inspection) may be skipped depending on the job. Processing each operation requires a machine and a transporter as resource. The numbers
<figure><img src="image_3.png" /><figcaption>Fig. 1. An illustrative example of heavy cargo transportation schedule</figcaption></figure>

of machines in each stage and transporters could be more than one, and each job
has eligibility to machines and transporters. The processing time of each opera-
tion depends on its assigned machine and between two consecutive operations is
a transportation time. Once a heavy cargo is loaded to a dedicated transporter
at the first stage, it cannot be unloaded until the final operation is completed.
Between two consecutive jobs assigned to the same transporter is a sequence-
dependent relocation time mainly caused by moving from one site to the next.
Machines and transporters have specified available time intervals in a scheduling
horizon. Given an initial schedule, the objective is to minimize makespan and
rescheduling objectives, including machine assignment deviation, transportation
assignment deviation, and completion time deviation. Figure 1 shows an illustra-
tive example with three stages (Loading → Inspection → Unloading) and three
transporters. Among six jobs (labeled by 1–6 with distinct colors), only Job 4
skipped the second stage.

We deal with the flexible (hybrid) flow shop problem explained in [4], a well-
known and practical problem that many authors have studied. Comprehensive
survey paper such as [5] exists. Practical requirements such as machine environ-
ment, stage skipping, resource eligibility constraints, etc., are listed in those sur-
veys. For another practical requirement beyond surveys, some flexible flow shop
problems consider resources for transportation between stages and such resources
could be robots [1] or transporters [3]. While most previous papers regard trans-
porters would be released after one transportation between stages, we consider
that each transporter is occupied from the first to the last stage since the frequent
movement of heavy cargo on transporters is not desired. Moreover, we also con-
sider multiple unavailable periods, which were never considered in this context.
Due to the problem’s hardness, most previous papers use various metaheuris-
tics as NSGA-III [2]. However, unavailable time intervals within transporters
are likely to degrade the performance of existing metaheuristic methodologies
because efficiently finding a feasible and reasonably good neighbor solution is
hard. Furthermore, slight modification of the incumbent solution significantly
may affect the objective value. Thus, we focus more on formulating the problem
to efficient MIP formulation that finds a reasonable solution without sticking to
local optima.
## 2 Mathematical Model

<table><thead><tr><th colspan="2">Sets</th></tr></thead><tbody><tr><td>G</td><td>Set of stages (:= {1, ..., H})</td></tr><tr><td>J</td><td>Set of jobs to be scheduled</td></tr><tr><td>R</td><td>Set of transporters (:= {1, ..., R})</td></tr><tr><td>G<sub>j</sub></td><td>The sequence of stages of job j (:= {G<sub>j</sub>[1], G<sub>j</sub>[2], ..., G<sub>j</sub>[H<sub>j</sub>]} where H<sub>j</sub> is the number of stages that job j is processed through, G<sub>j</sub>[1] is fixed to be 1, and G<sub>j</sub>[H<sub>j</sub>] is fixed to be H (∀j ∈ J)</td></tr><tr><td>J<sup>init</sup></td><td>Set of jobs that belong to an initial schedule (J<sup>init</sup> ⊆ J)</td></tr><tr><td>J<sub>r</sub></td><td>Set of jobs that are eligible to transporter r (∀r ∈ R)</td></tr><tr><td>M<sub>h</sub></td><td>Set of machines of stage h where i-th machine is denoted as (i, h) (M<sub>h</sub>'s are mutually exclusive ∀h ∈ G)</td></tr><tr><td>E<sup>M</sup><sub>ih</sub></td><td>Set of machines eligible with job j at stage h (∀j ∈ J, h ∈ G<sub>j</sub>)</td></tr><tr><td>E<sup>T</sup><sub>j</sub></td><td>Set of transporters eligible with job j (∀j ∈ J)</td></tr></tbody></table>

<table><thead><tr><th colspan="2">Simplifying notation for sets</th></tr></thead><tbody><tr><td>J<sup>2</sup><sub>‡</sub></td><td>{(j, j') : (j, j') ∈ J × J, j ≠ j'}</td></tr><tr><td>G<sub>{j,j'}</sub></td><td>G<sub>j</sub> ∩ G<sub>j'</sub> (∀(j, j') ∈ J<sup>2</sup><sub>‡</sub>)</td></tr><tr><td>E<sup>M</sup><sub>jh</sub></td><td>E<sup>M</sup><sub>jh</sub> ∩ E<sup>M</sup><sub>h</sub> (∀(j, j') ∈ J<sup>2</sup><sub>‡</sub>, h ∈ G<sub>{j,j'}</sub>)</td></tr><tr><td>E<sup>T</sup><sub>j</sub></td><td>E<sup>T</sup><sub>j</sub> ∩ E<sup>T</sup><sub>j'</sub> (∀(j, j') ∈ J<sup>2</sup><sub>‡</sub>)</td></tr></tbody></table>

<table><thead><tr><th colspan="2">Parameters</th></tr></thead><tbody><tr><td>C<sup>init</sup><sub>jh</sub></td><td>The completion time of job j of stage h in a given initial schedule (j ∈ J<sup>init</sup>, ∀h ∈ G<sub>j</sub>)</td></tr><tr><td>Q</td><td>A sufficiently large number</td></tr><tr><td>[a<sup>M</sup><sub>ihu</sub>, b<sup>M</sup><sub>ihu</sub>]</td><td>The u-th available interval of machine (i, h) (�forall u ∈ {1, ..., μ<sub>ih</sub>}, h ∈ G, i ∈ M<sub>h</sub> where μ<sub>ih</sub> is the number of mutually exclusive available intervals)</td></tr><tr><td>[a<sup>T</sup><sub>rv</sub>, b<sup>T</sup><sub>rv</sub>]</td><td>The v-th available interval of transporter r (�forall v ∈ {1, ..., ν<sub>r</sub>}, r ∈ R where ν<sub>r</sub> is the number of mutually exclusive available intervals)</td></tr><tr><td>l<sub>jj'<sub>r</sub></sub></td><td>Relocation time between the end of job j and the beginning of job j' if processed by transporter r (�forall (j, j') ∈ J<sup>2</sup><sub>‡</sub>, r ∈ E<sup>T</sup><sub>{j,j'}</sub>)</td></tr><tr><td>p<sub>ijh</sub></td><td>Processing time of job j on machine (i, h) (�forall j ∈ J, h ∈ G<sub>j</sub>, i ∈ E<sup>M</sup><sub>jh</sub>)</td></tr><tr><td>γ<sup>M</sup><sub>ijh</sub></td><td>1 if assigning job j to machine (i, h) incurs deviation penalty; 0 otherwise (�forall j ∈ J<sup>init</sup>, h ∈ G<sub>j</sub>, i ∈ E<sup>M</sup><sub>jh</sub>)</td></tr><tr><td>γ<sup>T</sup><sub>jr</sub></td><td>1 if assigning job j to transporter r incurs deviation penalty; 0 otherwise (�forall j ∈ J<sup>init</sup>, r ∈ E<sup>T</sup><sub>j</sub>)</td></tr><tr><td>π<sub>1</sub>-π<sub>4</sub></td><td>Coefficients of penalty for (makespan/machine assignment deviation/transporter assignment deviation/completion time deviation)</td></tr><tr><td>τ<sub>jh</sub></td><td>Transportation time of job j between stage h and its next (�forall j ∈ J, h ∈ G<sub>j</sub> \ {H})</td></tr><tr><td>q̂<sub>min</sub></td><td>a lower bound of the total processing time of transporters ∑<sub>j∈J</sub> ∑<sub>h∈G<sub>j</sub></sub> min<sub>i∈E<sup>M</sup><sub>jh</sub></sub> {p<sub>ijh</sub>} + ∑<sub>j∈J</sub> ∑<sub>h∈G<sub>j</sub>\{H}</sub> τ<sub>jh</sub></td></tr><tr><td>l̂<sub>min</sub></td><td>a lower bound of the total relocation time of transporters; the sum of (|J| - R)-smallest elements in {min<sub>r∈R</sub>, j'∈J<sub>r</sub>\{j}</sub> {l<sub>j'jr</sub>} : j ∈ J</td></tr></tbody></table>

continued
Binary variables

$X_{jj'h}$ 1 if job j precedes job j' on the same machine at stage h; 0 otherwise ($\forall(j, j') \in \mathcal{J}_{\neq}^2, h \in \mathcal{G}_{\{j,j'\}}$)

$Y_{ijh}$ 1 if job j is assigned to machine (i, h); 0 otherwise ($\forall j \in \mathcal{J}, h \in \mathcal{G}_j, i \in \mathcal{E}_{jh}^M$)

$y_{ijhu}^M$ 1 if job j is processed by machine (i, h) within the u-th available interval; 0 otherwise ($\forall j \in \mathcal{J}, h \in \mathcal{G}_j, i \in \mathcal{E}_{jh}^M, u \in \{1, \dots, \mu_{ih}\}$)

$y_{jrv}^T$ 1 if job j is processed by transporter r within the v-th available interval; 0 otherwise ($\forall j \in \mathcal{J}, r \in \mathcal{E}_j^T, v \in \{1, \dots, \nu_r\}$)

$\beta_{jr}$ 1 if job j is assigned to transporter r; 0 otherwise ($\forall j \in \mathcal{J}, r \in \mathcal{E}_j^T$)

$\theta_{jj'r}$ 1 if job j immediately precedes job j' on transporter r; 0 otherwise ($\forall(j, j') \in \mathcal{J}_{\neq}^2, r \in \mathcal{E}_{\{j,j'\}}^T$)

$\theta_{*jr}$ 1 if job j is the first job of transporter r; 0 otherwise ($\forall r \in \mathcal{R}, j \in \mathcal{J}_r$)

$\theta_{j*r}$ 1 if job j is the last job of transporter r; 0 otherwise ($\forall r \in \mathcal{R}, j \in \mathcal{J}_r$)

Continuous variables (non-negative)

$C_{ijh}^M$ The completion time of job j at stage h if it is assigned to machine i; 0 otherwise ($\forall j \in \mathcal{J}, h \in \mathcal{G}_j, i \in \mathcal{E}_{jh}^M$)

$C_{jh}$ The completion time of job j at stage h ($\forall j \in \mathcal{J}, h \in \mathcal{G}_j$)

$C_{max}$ The makespan at the last stage

$S_{jj'h}^M$ The starting time of job j at stage h if it is assigned to machine i; 0 otherwise ($\forall j \in \mathcal{J}, h \in \mathcal{G}_j, i \in \mathcal{E}_{jh}^M$)

$S_{jh}$ The starting time of job j at stage h ($\forall j \in \mathcal{J}, h \in \mathcal{G}_j$)

$\Delta_{jh}^+$ The positive and negative deviation of completion time of job j at stage h ($\forall j \in \mathcal{J}_{\text{init}}, h \in \mathcal{G}_j$)

$$ \text{Min } \pi_1 C_{\text{max}} + \pi_2 \sum_{j \in \mathcal{J}^{\text{init}}} \sum_{h \in \mathcal{G}_j} \sum_{i \in \mathcal{E}_{jh}^M} \gamma_{ijh}^M Y_{ijh} + \pi_3 \sum_{j \in \mathcal{J}^{\text{init}}} \sum_{r \in \mathcal{E}_j^T} \gamma_{jr}^T \beta_{jr} + \pi_4 \sum_{j \in \mathcal{J}^{\text{init}}} \sum_{h \in \mathcal{G}_j} (\Delta_{jh}^+ + \Delta_{jh}^-) \quad (1) $$

$$ \text{s.t.} \quad \sum_{i \in \mathcal{E}_{jh}^M} Y_{ijh} = 1 \qquad \forall j \in \mathcal{J}, h \in \mathcal{G}_j \quad (2) $$

$$ X_{jj'h} + X_{j'jh} \geq Y_{ijh} + Y_{ij'h} - 1 \quad \forall (j, j') \in \mathcal{J}_{\neq}^2, h \in \mathcal{G}_{\{j,j'\}}, i \in \mathcal{E}_{\{j,j'\}}^M h \quad (3) $$

$$ X_{jj'h} + X_{j'jh} \leq 1 - Y_{ijh} + Y_{ij'h} \quad \forall (j, j') \in \mathcal{J}_{\neq}^2, h \in \mathcal{G}_{\{j,j'\}}, i \in \mathcal{E}_{\{j,j'\}}^M h \quad (4) $$

$$ \sum_{j' \in \mathcal{J}_r \setminus \{j\}} \theta_{jj'r} + \theta_{j*r} = \beta_{jr} \quad \forall r \in \mathcal{R}, j \in \mathcal{J}_r \quad (5) $$

$$ \sum_{j' \in \mathcal{J}_r \setminus \{j\}} \theta_{j'jr} + \theta_{*jr} = \beta_{jr} \quad \forall r \in \mathcal{R}, j \in \mathcal{J}_r \quad (6) $$

$$ \sum_{j \in \mathcal{J}_r} \theta_{*jr} \leq 1 \quad \forall r \in \mathcal{R} \quad (7) $$

$$ \sum_{r \in \mathcal{E}_j^T} \beta_{jr} = 1 \quad \forall j \in \mathcal{J} \quad (8) $$

$$ S_{j'h} \geq C_{jh} - Q(1 - X_{jj'h}) \quad \forall (j, j') \in \mathcal{J}_{\neq}^2, h \in \mathcal{G}_{\{j,j'\}} \quad (9) $$

$$ S_{j, \mathcal{G}_j[\rho+1]} \geq C_{j, \mathcal{G}_j[\rho]} + \tau_{j, \mathcal{G}_j[\rho]} \quad \forall j \in \mathcal{J}, \rho \in \{1, \dots, (H_j - 1)\} \quad (10) $$

$$ S_{j'1} \geq C_{jH} + l_{jj'r} - Q(1 - \theta_{jj'r}) \quad \forall (j, j') \in \mathcal{J}_{\neq}^2, r \in \mathcal{E}_{\{j,j'\}}^T \quad (11) $$

$$ C_{ijh}^M \leq \sum_{u=1}^{\mu_{ih}} b_{ihu}^M y_{ijhu}^M \quad \forall j \in \mathcal{J}, h \in \mathcal{G}_j, i \in \mathcal{E}_{jh}^M \quad (12) $$

$$ S_{ijh}^M \geq \sum_{u=1}^{\mu_{ih}} a_{ihu}^M y_{ijhu}^M \quad \forall j \in \mathcal{J}, h \in \mathcal{G}_j, i \in \mathcal{E}_{jh}^M \quad (13) $$
$$ \sum_{u=1}^{\mu_{ih}} y_{ijh u}^{M} = Y_{ijh} \qquad \forall j \in \mathcal{J}, h \in \mathcal{G}_j, i \in \mathcal{E}_{jh}^{M} \qquad (14) $$

$$ C_{ijh}^{M} = S_{ijh}^{M} + p_{ijh} Y_{ijh} \qquad \forall j \in \mathcal{J}, h \in \mathcal{G}_j, i \in \mathcal{E}_{jh}^{M} \qquad (15) $$

$$ S_{jh} = \sum_{i \in \mathcal{E}_{jh}^{M}} S_{ijh}^{M} \qquad \forall j \in \mathcal{J}, h \in \mathcal{G}_j \qquad (16) $$

$$ C_{jh} = \sum_{i \in \mathcal{E}_{jh}^{M}} C_{ijh}^{M} \qquad \forall j \in \mathcal{J}, h \in \mathcal{G}_j \qquad (17) $$

$$ C_{jH} \le \sum_{r \in \mathcal{E}_j^T} \sum_{v=1}^{\nu_r} b_{rv}^T y_{jrv}^T \qquad \forall j \in \mathcal{J} \qquad (18) $$

$$ S_{j1} \ge \sum_{r \in \mathcal{E}_j^T} \left( \sum_{v=1}^{\nu_r} a_{rv}^T y_{jrv}^T + \sum_{j' \in \mathcal{J}_r \setminus \{j\}} l_{j'jr} \theta_{j'jr} \right) \quad \forall j \in \mathcal{J} \qquad (19) $$

$$ \sum_{v=1}^{\nu_r} y_{jrv}^T = \beta_{jr} \qquad \forall r \in \mathcal{R}, j \in \mathcal{J}_r \qquad (20) $$

$$ C_{jh} - C_{jh}^{\text{init}} = \Delta_{jh}^{+} - \Delta_{jh}^{-} \qquad \forall j \in \mathcal{J}^{\text{init}}, h \in \mathcal{G}_j \qquad (21) $$

$$ C_{\max} \ge C_{ijH}^{M} \qquad \forall j \in \mathcal{J}, i \in \mathcal{E}_{jh}^{M} \qquad (22) $$

The objective function (1) is a linear combination of (i) the makespan at the last stage, (ii) machine assignment deviation penalty, (iii) transporter deviation penalty, and (iv) completion time deviation penalty from the given initial schedule. Constraints (2) are for assigning each job to only one eligible machine at each stage that the job is processed on. Constraints (3) and (4) impose a precedence relationship for two jobs assigned to the same machine. Constraints (5)–(7) establish immediate precedence relationships among the jobs assigned to the same transporter. Constraints (8) are for assigning each job to only one eligible transporter. Constraints (9) restrict a job on the same machine to start later than preceding jobs. Constraints (10) tell that a job’s starting time at the next stage is greater than the completion time of the previous stage plus the transportation time. Constraints (11) imply that if two jobs are assigned to the same transporter, the succeeding job’s starting time is greater than the completion time of preceding job plus the sequence-dependent relocation time. Constraints (12)–(14) restrict a job to be processed within the assigned machine’s available interval for each stage. Constraints (15)–(17) define the completion time and starting time of each job at the stages it is processed by. Constraints (18)–(20) imply that the transportation of each job should be processed within the selected transporter’s available interval. Constraints (21) define the completion time deviation of previously existing jobs. Constraints (22) define makespan.
# 3 Results

To evaluate the performance of the proposed MIP, we design an experiment on randomly created instances: small and large. Details for each instance are summarized by Table 1.

<table><caption>**Table 1.** Experiment parameters</caption><thead><tr><th>Parameters</th><th>Small</th><th>Large</th></tr></thead><tbody><tr><td>The number of stages (<i>H</i>)</td><td>3</td><td>5</td></tr><tr><td>The number of jobs (|<i>J</i>|)</td><td><i>U</i>(5, 10)</td><td><i>U</i>(15, 20)</td></tr><tr><td>The number of transporters (|<i>R</i>|)</td><td>3</td><td>5</td></tr><tr><td>The number of machines in each stage (|<i>M</i><sub>h</sub>|)</td><td>[1,2,1]</td><td>[2,3,3,2,2]</td></tr><tr><td>The number of available intervals (<i>μ</i><sub>ih</sub>, <i>ν</i><sub>r</sub>)</td><td><i>U</i>(1, 3), <i>U</i>(1, 2)</td><td><i>U</i>(1, 4), <i>U</i>(1, 3)</td></tr><tr><td>The probability that a job skips a stage<sup>†</sup></td><td>20%</td><td>30%</td></tr><tr><td>The probability that a job is eligible (<i>M</i>, <i>T</i>)<sup>††</sup></td><td>80%, 70%</td><td>70%, 65%</td></tr><tr><td>Processing time at an eligible machine (<i>p</i><sub>ijh</sub>)</td><td><i>Ũ</i>(3, 8)</td><td><i>Ũ</i>(3, 8)</td></tr><tr><td>Transportation time between two stages (<i>τ</i><sub>jh</sub>)</td><td><i>Ũ</i>(5, 10)</td><td><i>Ũ</i>(5, 10)</td></tr><tr><td>Relocation time between two jobs (<i>l</i><sub>jj'</sub><sub>r</sub>)<sup>*</sup></td><td><i>Ũ</i>(10, 20)</td><td><i>Ũ</i>(10, 20)</td></tr><tr><td>Length of an available interval (<i>M</i>, <i>T</i>)</td><td><i>Ũ</i>(18, 48), <i>Ũ</i>(50, 100)</td><td><i>Ũ</i>(30, 80), <i>Ũ</i>(70, 140)</td></tr><tr><td>Length between two available intervals (<i>M</i>, <i>T</i>)</td><td><i>Ũ</i>(9, 24), <i>Ũ</i>(25, 50)</td><td><i>Ũ</i>(15, 40), <i>Ũ</i>(35, 70)</td></tr></tbody></table>

(Abbreviation) *M*: related to machines, *T*: related to transporters

(Note) *U* is a discrete uniform distribution and *Ũ* ~ 10 · *U*

† Jobs do not skip the first and the last stage

†† Jobs forcefully have eligibility to one random machine at each stage they pass through and one random transporter; eligibility to the others is determined with probability

* Relocation time is symmetric (i.e., $l_{jj'}r = l_{j'jr} \forall j, j' \in \mathcal{J}_{\neq}^2, r \in \mathcal{E}_{\{j,j'\}}^T$)

Experiments code is implemented by Python MIP package, and we use Gurobi solver ver.9.5.1. We use a desktop computer with Windows 10 OS, AMD Ryzen 9 3900X CPU, and 64GB RAM.

Since our MIP is a rescheduling model, an initial schedule is required. We set $J^{\text{init}} = \emptyset$ and apply the same MIP. We set 3600 s seconds as a time limit of an MIP and find initial schedules of instances with objective coefficients $\pi = (1, 0, 0, 0)$ so that only the makespan objective is considered in those initial schedules.

We also provide a lower bound to the makespan. Recall that $\hat{q}_{\text{min}}$ and $\hat{l}_{\text{min}}$ are the lower bounds of the total processing time and of the total relocation time of transporters, respectively. Thus, the makespan of multiprocessing transporters preemptively dealing with the minimum required total working time ($\hat{q}_{\text{min}} + \hat{l}_{\text{min}}$) can be a lower bound to the true makespan. We considered transporter availability while computing the lower bound but disregarded detailed operations of machines and transporter eligibility.

Since all small instances (instance 1–10) could be optimally solved within 6 s, we focus on the results of large instances as presented in Table 2. We examine the objective values at three timestamps (60, 600, and 3600 s seconds) and compare the optimality gap to the final lower bound improved from the initial preemptive
<table><caption>**Table 2.** Computational results of initial scheduling for large instances</caption><thead><tr><th rowspan="2">Instance</th><th colspan="2">60 s</th><th colspan="2">600 s</th><th colspan="2">3,600 s</th><th colspan="2">LB</th></tr><tr><th>C<sub>max</sub></th><th>Gap</th><th>C<sub>max</sub></th><th>Gap</th><th>C<sub>max</sub></th><th>Gap</th><th>Init</th><th>Final</th></tr></thead><tbody><tr><td>11</td><td>201</td><td>11.7%</td><td>199</td><td>10.6%</td><td>195</td><td>8.3%</td><td>167.5</td><td>180.0</td></tr><tr><td>12</td><td>200</td><td>17.9%</td><td>200</td><td>17.9%</td><td>199</td><td>17.3%</td><td>169.6</td><td>169.6</td></tr><tr><td>13</td><td>344</td><td>36.0%</td><td>288</td><td>13.8%</td><td>272</td><td>7.5%</td><td>226.2</td><td>253.0</td></tr><tr><td>14<sup>†</sup></td><td>291</td><td>0.0%</td><td>291</td><td>0.0%</td><td>291</td><td>0.0%</td><td>173.6</td><td>291.0</td></tr><tr><td>15</td><td>289</td><td>30.2%</td><td>284</td><td>27.9%</td><td>268</td><td>20.7%</td><td>219.6</td><td>222.0</td></tr><tr><td>16</td><td>295</td><td>23.9%</td><td>288</td><td>21.0%</td><td>281</td><td>18.1%</td><td>226.8</td><td>238.0</td></tr><tr><td>17<sup>†</sup></td><td>236</td><td>0.0%</td><td>236</td><td>0.0%</td><td>236</td><td>0.0%</td><td>197.6</td><td>236.0</td></tr><tr><td>18</td><td>252</td><td>29.6%</td><td>237</td><td>21.9%</td><td>237</td><td>21.9%</td><td>194.4</td><td>194.4</td></tr><tr><td>19</td><td>268</td><td>27.3%</td><td>252</td><td>19.7%</td><td>243</td><td>15.4%</td><td>210.6</td><td>210.6</td></tr><tr><td>20</td><td>358</td><td>43.0%</td><td>331</td><td>32.2%</td><td>323</td><td>29.0%</td><td>250.4</td><td>250.4</td></tr></tbody><tfoot><tr><td>Avg.</td><td>273</td><td>22.0%</td><td>261</td><td>16.5%</td><td>254</td><td>13.8%</td><td>203.6</td><td>224.5</td></tr></tfoot></table>

lower bound. The average optimality gap at 60 s is 22.0%, which is acceptably good for an initial solution, and it could be further improved to be 13.8% at 3600 s.

<figure><img src="image_4.png" /><figcaption>(a) Extended unavailable interval at the last stage (drawn as the black box)</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) Extended processing time of Job 2 at the last stage</figcaption></figure>

<caption>**Fig. 2.** Rescheduling examples (processing of jobs is labeled by distinct ids and colors)</caption>

<footnote>†The optimality for instance 14(17) was proven within 182(91) seconds.</footnote>
We demonstrate rescheduling scenarios applied to instance 1 of which the optimal solution from initial scheduling is illustrated in Fig. 1. We consider two scenarios that may happen in practice: (a) extended unavailable intervals of a machine, and (b) extended processing time of an operation. For both scenarios, we set objective coefficients of $\pi = (1, 60, 60, 1)$. All rescheduling problems could be solved within 0.5 s under the same experimental settings to initial scheduling. In Fig. 2(a), due to the extended machine unavailability of 2 h at the last stage, all jobs except Job 1 and 2 are delayed. Nevertheless, every job could be processed without changing resource assignment, which is a desired outcome. In Fig. 2(b), due to the extended processing time of Job 2 by 80 min at the last stage, Job 2 and Job 3 are swapped in machine allocation. All other jobs need not change the resource assignment and could be rescheduled with slight modification of completion times. This is a satisfying result and demonstrates how MIP can effectively handle complicated rescheduling problems.

## 4 Conclusion

We consider a flexible flow shop rescheduling problem motivated by heavy cargo logistics from manufacturing sites to loading docks. We construct an MIP formulation of the problem, and it finds optimal initial solutions in 6 s for the small problems. Moreover, it finds reasonable initial solutions within 60, 600, and 3600 s with a gap of 22%, 16.5%, and 13.8%, respectively. Moreover, it performs rescheduling in a much shorter amount of time well. We could further develop a model to reduce the current gap for future work. For example, we could propose a heuristic that could work as an initial solution to the MIP. On the other hand, using our problem structure, we could apply parallel machine scheduling techniques to the transporters to build a tighter lower bound. We expect a more practical result by applying these techniques.

**Acknowledgements.** This paper was supported by the National IT Industry Promotion Agency of Korea (NIPA) funded by the Ministry of Science and Information and Communications Technology of Korea (MSIT). (Grants: S1510-22-1001(001))

## References

1. Elmi, A., Topaloglu, S.: A scheduling problem in blocking hybrid flow shop robotic cells with multiple robots. Comput. Oper. Res. **40**(10), 2543–2555 (2013)

2. He, X., Dong, S., Zhao, N.: Research on rush order insertion rescheduling problem under hybrid flow shop based on NSGA-III. Int. J. Prod. Res. **58**(4), 1161–1177 (2020)

3. Lei, C., Zhao, N., Ye, S., Wu, X.: Memetic algorithm for solving flexible flow-shop scheduling problems with dynamic transport waiting times. Comput. Ind. Eng. **139**, 105984 (2020)
4. Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems, 5th edn. Springer, Cham (2016). https://doi.org/10.1007/978-3-642-46773-8_5

5. Ruiz, R., Vázquez-Rodríguez, J.A.: The hybrid flow shop scheduling problem. Eur. J. Oper. Res. **205**(1), 1–18 (2010)