# Scheduling Jobs on Unrelated Machines with Job Splitting and Setup Resource Constraints for Weaving in Textile Manufacturing

Ioannis Mourtos, Stavros Vatikiotis, Georgios Zois

► To cite this version:

Ioannis Mourtos, Stavros Vatikiotis, Georgios Zois. Scheduling Jobs on Unrelated Machines with Job Splitting and Setup Resource Constraints for Weaving in Textile Manufacturing. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.424-434, 10.1007/978-3-030-85874-2_45. hal-04030387

HAL Id: hal-04030387

https://inria.hal.science/hal-04030387

Submitted on 16 Mar 2023

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.
# Scheduling jobs on unrelated machines with job splitting and setup resource constraints for weaving in textile manufacturing*

Ioannis Mourtos¹, Stavros Vatikiotis¹, and Georgios Zois¹

ELTRUN Research Lab, Department of Management Science and Technology, Athens
University of Economics and Business, Athens 104 34, Greece
{mourtos, stvatikiotis, georzois}@aueb.gr

**Abstract.** This work considers the production scheduling of the weaving process in a real-life textile industry, where a set of jobs - linked to the production of a fabric type and accompanied by a quantity - arrive over time and have to be processed (woven) by a set of parallel unrelated machines (looms) with respect to their strict deadlines (delivery dates), under the goal of makespan minimization. A number of critical job and machine properties demonstrate the challenging nature of weaving scheduling, i.e., a) job splitting: each order's quantity is allowed to be split and processed on multiple machines simultaneously, b) sequence-dependent setup times: the setup time between any two orders j and k is different than setup time between jobs k and j on the same machine and c) setup resource constraints: the number of setups that can be performed simultaneously on different machines is restricted due to a limited number of setup workers. We propose a MILP formulation that captures the entire weaving process. To handle large real instances, while also speeding up an exact solver on smaller ones, we propose two heuristics that perform job-splitting and assignment of jobs to machines either greedily or by using a relaxed version of our MILP model, respectively. We evaluate the impact of our approach on real datasets under user-imposed time limits and resources (machines, workers) availability.

**Keywords:** Textile · Weaving Scheduling · Integer Programming · Heuristics

## 1 Introduction

Increasing productivity while reducing production costs has been essential in modern textile plants in terms of business sustainability. Scheduling algorithms [3] offer a viable and effective tool to improve productivity, by optimally allocating the available resources. A typical scheduling problem in textile considers a

<footnote>* This research has been supported by the EU through the FACTLOG Horizon 2020 project, grant number 869951.</footnote>
set of articles/orders to be woven by a set of looms with respect to their delivery dates. Each order is linked to the production of a specific fabric type and is accompanied by a positive quantity, while the looms are unrelated, meaning that each loom operates on different speeds for different orders. The aim is to find a schedule with the minimum makespan, i.e., the time that the last executed order is finished.

Two properties that make weaving scheduling a challenging problem are job splitting (a job can be split in different machines) and sequence-dependent setup times (per pairs of jobs and per machine). In practice, the latter is justified by the fact that different fabric types require different warp chains for processing, thus imposing machine setup times (to replace the warp chain) from a few hours to a few days [14]. Both properties have been studied extensively under abstract models of various machine environments and optimisation criteria [1, 12, 9, 4, 13] and tackled through exact methods, approximation algorithms and metaheuristics. The weaving scheduling problem has also been well-studied and admits exact polynomial time algorithms for special cases where setup times are independent and job splitting is relaxed to preemption [14], as well as MILP models and efficient metaheuristics for the general case [5, 6, 14, 11].

Our work is focused on the weaving scheduling of PIACENZA, a textile enterprise in north Italy that manufactures woolen fabrics for luxury clothing brands. Its production environment is a parallel weaving environment composed of multiple type of looms, operating at different speeds. Weaving scheduling in PIACENZA adopts all the above-described job and machine properties, plus setup resource constraints. Specifically, the number of setups that can be performed simultaneously on different machines is restricted due to a limited number of setup workers and daily setup time is also bounded. We should note that the seminal work of [14] signifies the addition of setup resource constraints to the standard weaving scheduling as a severe challenge.

According to our knowledge, the most relevant previous work appears in [8,9]. In [8], the authors proposed near optimal heuristics for a simplified model with identical machines, job splitting, multiple setup resources and fixed (independent) setup times per job, under the makespan minimisation objective. [9] proposes a Benders Decomposition approach and heuristics for the general case of unrelated machines, sequence-dependent setup times and multiple setup resources, again under the makespan minimisation objective. However, none of these works combine all the complex properties needed for PIACENZA's case. Interestingly, [8] referred to a case combining job-splitting, sequence-dependent setup times, unrelated machines and setup resource constraints as an open research direction.

**Our contribution.** In Section 2 we propose a formal definition of our scheduling problem, address its computational complexity and propose a mixed integer linear programming (MILP) formulation that captures the elaborate structure of the weaving process. To handle large real instances, we propose in Section 3 two combinatorial heuristics that differ on the way they perform job splitting and assignment to machines. We experiment with several weekly
instances on both MILP (using a standard solver) and heuristics to establish the computational efficiency of our approach in Section 4. As we note, although typically the trade-off between delivery dates, available machines and setup resources allows the scheduler to deliver each job on time, due to the COVID-19 pandemic a large number of jobs arrive late on the weaving department, while others become more tight in terms of deadline. To improve resource management while avoiding a further increase of tardy jobs, we propose in Section 5 a strategy that dedicates an appropriate number of machines to samples (i.e., jobs with small quantity and tight deadlines) while allocating the rest to regular jobs (i.e., jobs with large quantity and loose deadlines).

## 2 Mathematical Modeling

To present our mixed integer linear program (MILP), we employ the notation of Tables 1 and 2.

<table><caption>**Table 1:** Model Parameters</caption><thead><tr><th>Model Parameters</th><th></th></tr></thead><tbody><tr><td>J</td><td>The set of jobs (orders)</td></tr><tr><td>M</td><td>The set of machines (looms)</td></tr><tr><td>s<sub>m</sub></td><td>The fixed speed (in strokes/min) of machine m ∈ M</td></tr><tr><td>q<sub>i</sub></td><td>The quantity (in meters) of job i ∈ J</td></tr><tr><td>u<sub>i</sub></td><td>The number of strokes/meter for the fabric type of job i</td></tr><tr><td>p<sub>i,m</sub></td><td>The processing time of i ∈ J on m ∈ M, p<sub>i,m</sub> = q<sub>i</sub> · u<sub>i</sub>/s<sub>m</sub></td></tr><tr><td>S<sub>i,j,m</sub></td><td>The setup time of j ∈ J succeeding job i ∈ J on m ∈ M</td></tr><tr><td>S&#773;<sub>i</sub></td><td>The setup time of jobs processed first on each machine (1h)</td></tr><tr><td>L<sub>i</sub></td><td>A lower limit on the quantity of part of job i ∈ J allocated to any machine (50 meters)</td></tr><tr><td>d<sub>i</sub></td><td>The deadline of job i ∈ J, i.e., a strict delivery date for i</td></tr><tr><td>T<sub>max</sub></td><td>An upper bound on the makespan of an optimal schedule, e.g., T<sub>max</sub> = &sum;<sub>i&isin;J</sub> max<sub>m&isin;M</sub>(p<sub>i,m</sub> + max<sub>j&isin;J</sub>S<sub>i,j,m</sub>).</td></tr><tr><td>T</td><td>A set of equal-length intervals [&tau;<sub>i-1</sub>, &tau;<sub>i</sub>), 1 &le; i &le; T, where &tau;<sub>0</sub> = 0 and &tau;<sub>T</sub> = T<sub>max</sub></td></tr><tr><td>l<sub>i,j,m</sub></td><td>The number of intervals needed to setup job j after job i on machine m</td></tr><tr><td>l<sub>&tau;</sub></td><td>The length of every interval t &isin; T (2h, which is the least common multiple over all setup times)</td></tr><tr><td>D</td><td>A partition of T into subsets of consecutive time intervals q with total length equal to a working day</td></tr><tr><td>u<sub>q</sub></td><td>The allowed setup time per working day q &isin; D (50h)</td></tr><tr><td>R</td><td>A setup resource constraint to indicate that, at each time interval, at most R machines can be set up in parallel</td></tr></tbody></table>
(MILP) : $C_{max}$

s.t. :

$$ \sum_{i,j \in J, i \neq j} X_{i,j,m,t} \leq 1, \quad \forall t \in T, m \in M \quad (1) $$

$$ \sum_{i \in J} X'_{i,m,t} \leq 1, \quad \forall t \in T, m \in M \quad (2) $$

$$ \sum_{t \in T} X_{i,j,m,t} \leq 1, \quad \forall i, j \in J, i \neq j, m \in M \quad (3) $$

$$ \sum_{j \in J, t \in T} X_{0,j,m,t} \leq 1, \quad \forall m \in M \quad (4) $$

$$ \sum_{m \in M} Q_{i,m} = q_i, \quad \forall i \in J \quad (5) $$

$$ L_i \cdot Y_{i,m} \leq Q_{i,m} \leq q_i \cdot Y_{i,m}, \quad \forall i \in J, m \in M \quad (6) $$

$$ Y_{i,m} = \sum_{t \in T, j \in J, j \neq i} X_{i,j,m,t}, \quad \forall i \in J, m \in M \quad (7) $$

$$ Y_{j,m} = \sum_{t \in T, i \in J, i \neq j} X_{i,j,m,t}, \quad \forall j \in J, m \in M \quad (8) $$

$$ \sum_{t \in T} X_{i,j,m,t} + \sum_{t \in T} X_{j,i,m,t} \leq 1, \quad \forall i, j \in J, i, j \neq 0, i \neq j, m \in M \quad (9) $$

$$ \sum_{i,j \in J, i \neq j, t \in T} X_{i,j,m,t} = \sum_{i \in J} Y_{i,m} - 1, \quad \forall m \in M \quad (10) $$

$$ X_{i,j,m,t} + \sum_{\substack{i' \in J, i' \neq i, \\ t' \in T, t' \leq t}} X_{j,i',m,t'} \leq 1, \quad \forall i \in J, j \in J, i \neq j, m \in M, t \in T \quad (11) $$

$$ X_{i,j,m,t} \cdot l_{i,j,m} \leq \sum_{t'=t}^{t+l_{i,j,m}-1} X'_{j,m,t'} \quad \forall i,j \in J, i \neq j, m \in M, t \in T \setminus \{T-r|1 \leq r \leq l_{i,j,m}\} \quad (12) $$

$$ \sum_{t \in T} X'_{j,m,t} \leq \sum_{i \in J, i \neq j, t \in T} l_{i,j,m} \cdot X_{i,j,m,t}, \quad \forall j \in J, m \in M \quad (13) $$

$$ \sum_{i \in J, m \in M} X'_{i,m,t} \leq R, \quad \forall t \in T \quad (14) $$

$$ \sum_{i \in J, m \in M, t \in q} l_{\tau} \cdot X'_{i,m,t} \leq u_q, \quad \forall q \in D \quad (15) $$

$$ C_{j,m} - C_{i,m} + V(1 - \sum_{t \in T} X_{i,j,m,t}) \geq Q_{j,m} \cdot \frac{u_j}{s_m} + S_{i,j,m} \cdot \sum_{t \in T} X_{i,j,m,t}, \quad \forall i, j \in J, j \neq i, m \in M \quad (16) $$

$$ C_{j,m} \geq \sum_{i \in J, i \neq j, t \in T} X_{i,j,m,t}(\tau_{t-1} + S_{i,j,m}) + Q_{j,m} \cdot \frac{u_j}{s_m}, \quad \forall j \in J, m \in M \quad (17) $$

$$ \bar{S}_i \cdot Y_{i,m} + Q_{i,m} \cdot \frac{u_i}{s_m} \leq C_{i,m} \leq C_{max}, \quad \forall i \in J, m \in M \quad (18) $$

$$ \sum_{j \in J, t \in T, t > \lfloor \frac{R}{M} \rfloor} X_{0,j,m,t} = 0, \quad \forall m \in M \quad (19) $$

$$ Y_{i,m}, X'_{i,m,t}, X_{i,j,m,t} \in \{0,1\}, C_{i,m}, Q_{i,m} \in \mathbb{R}^{+}, \quad \forall i, j \in J, m \in M, t \in T $$

The overall goal is to minimise the makespan of the schedule, denoted as $C_{max}$. Since setup times are strictly positive, it is easy to prove that each machine
processes at most one part of each split job. We refer to the above problem as the *Weaving Scheduling* problem, which is *NP-hard* even if machines are identical, job setup times are fixed (and independent) and $R = 1$ [7].

<table><caption>**Table 2:** Decision Variables</caption><thead><tr><th colspan="2">Variables</th></tr></thead><tbody><tr><td>X<sub>i,j,m,t</sub></td><td>1 if j ∈ J is the successor of i ∈ J on machine m ∈ M, which is set up right after i at time t ∈ T and there are no other jobs processed between them on m, 0 otherwise</td></tr><tr><td>X'<sub>i,m,t</sub></td><td>1 if i ∈ J is under setup on machine m ∈ M at t ∈ T, 0 otherwise</td></tr><tr><td>Y<sub>i,m</sub></td><td>1 if i ∈ J is assigned on machine m ∈ M, 0 otherwise</td></tr><tr><td>Q<sub>i,m</sub> ∈ ℝ<sup>+</sup></td><td>The quantity of job i ∈ J to be processed by m ∈ M</td></tr><tr><td>C<sub>i,m</sub> ∈ ℝ<sup>+</sup></td><td>The completion time of the part of job i ∈ J processed on m ∈ M</td></tr><tr><td>C<sub>max</sub> ∈ ℝ<sup>+</sup></td><td>The makespan of the schedule</td></tr></tbody></table>

(MILP) is partly inspired by formulations on special cases [8,13], extending them to capture the elaborate structure of *Weaving Scheduling*. More specifically, Constraints (1)-(4), (7)-(11), (19), are used to ensure the feasibility of job assignment, respecting that each machine processes at most one single part of each split job. Constraints (5)-(6) allow for job splitting wrt to the quantity limits. Constraints (12), (13), (16) ensure that the setup of each job part precedes its execution on the corresponding machine and calculate its completion time. Constraints (14), (15) are setup resource constraints, and Constraints (17), (18) provide tight lower bounds.

## 3 Combinatorial Heuristics

Using an exact commercial solver (Gurobi 9.1) on (MILP), we can solve many daily instances (i.e., ones with orders arriving at the same date) in a few minutes either optimally or by a small gap. Hence (MILP) could be used to support short-term goals like scheduling jobs in a daily manner. However, to fully support the business needs of a weaving enterprise, including mid and long-term goals, it is important to efficiently tackle larger real instances. In this direction, we propose two combinatorial heuristics, GH1 and GH2, which differ in the way they handle job splitting and assignment of each part of a job to a machine, while handling the sequence-dependent setup times and setup resources in the same way. Table 3 summarizes the notation used in the present and the following sections.

GH1, performs an iterative exact splitting and assignment of jobs (parts) to machines using a MILP formulation (which is a subproblem of *Weaving Scheduling* where setup resource constraints are not taken into account) that minimises makespan subject to Constraints (5), (6) (to ensure that quantity limits are satisfied), (20) that calculates a lower bound on the time needed to process the assigned part of each job on each machine and (21) that limits the number of
<table><caption>**Table 3:** Algorithms and experiment parameters and abbreviations</caption><thead><tr><th>Notation</th><th></th></tr></thead><tbody><tr><td>GH1</td><td>The first greedy heuristic</td></tr><tr><td>max _assgn</td><td>Upper limit on job assignments in each iteration of GH1</td></tr><tr><td>GH2</td><td>The second greedy heuristic</td></tr><tr><td>LPT</td><td>Longest Processing Time first rule used in GH2</td></tr><tr><td>λ</td><td>A positive constant chosen on the assignment step of GH2</td></tr><tr><td>ld<sub>m</sub></td><td>The load of m ∈ M on the assignment step of GH2</td></tr><tr><td>aTSP</td><td>The Asymmetric Traveling Salesman Problem</td></tr><tr><td>LB</td><td>A lower bound derived by the solution of the MILP in GH1</td></tr><tr><td>% Gap</td><td>The percentage gap of GH1 or GH2 wrt LB: <sup>{GH1,GH2}-LB</sup>&frasl;<sub>LB</sub> . 100</td></tr><tr><td>Tardiness</td><td>For each job j in a schedule it is equal to {max<sub>m∈M</sub> C<sub>j,m</sub> - d<sub>j</sub>, 0}</td></tr><tr><td>Tardy job</td><td>A job j ∈ J with positive tardiness, i.e., max<sub>m∈M</sub> C<sub>j,m</sub> > d<sub>j</sub></td></tr></tbody></table>

possible job assignments to max _assgn. GH1 starts by setting the maximum possible value of max _assgn = |J| × |M| and after each iteration decreases it by 1, in order to exploit all possible exact solutions (of increased or decreased job splitting potential) choosing the best among them. It terminates when the number of jobs exceeds the possible assignments i.e., max _assgn = |J| - 1, as there is no possibility to assign all jobs.

$$ \sum_{i \in J} (Q_{i,m} \frac{u_i}{s_m} + Y_{i,m} \cdot \min_{j \in J} S_{i,j,m}) \leq C_{max} \quad \forall m \in M \quad (20) $$

$$ \sum_{i \in J} \sum_{m \in M} Y_{i,m} \leq \max _{\text {assgn }} \quad \forall m \in M \quad (21) $$

On the other hand, GH2 performs a greedy job splitting dividing job quantities into parts based on the lower bound $L_i$: For each job i with $q_i \geq 2L_i$ we create $\alpha = \lceil \frac{q_i}{L_i} \rceil$ job parts of quantity equal to $\frac{q_i}{\alpha}$. Then, the job parts are ordered according to the LPT rule, in order to prevent the resulted schedule from unbalanced machine loads (i.e., when a job with large processing time is scheduled last). Then assignment process is similar to the one proposed in [2] for makespan minimisation on unrelated processors: For the LPT order of job parts, it assigns each part i to the machine $k = \arg \min_{m \in M} \{\lambda^{ld_m} + S_{j,i,m} + Q_{i,m} \frac{u_i}{s_m} - \lambda^{ld_m}\}$, where j is the last job executed on m before i.

Both GH1 and GH2 are then following the next two stages. **STAGE A:** For each machine, the assigned job parts are scheduled optimally by reducing the problem to aTSP, where nodes correspond to jobs' parts and the distance between nodes to sequence-dependent setup time plus processing time of the corresponding job part; the exact approach of [12] is proved quite efficient for our instances. **STAGE B:** For each machine in decreasing order of load and each available group of workers, we compute the earliest time that a job part can start its setup, respecting the order of job parts from **STAGE A**. Note that, in **STAGE B**, by starting from the most loaded machine, we significantly reduce the effect of
idle intervals between consecutive job executions on the final makespan. Moreover, in the case of GH2, we do not violate the assumption that each machine processes at most one single part of each split job, as the setup time between parts of the same job is equal to zero, and thus in the aTSP solution they will be consequently ordered.

Summarising, GH1 performs an exhaustive job splitting and assignment supported by an exact solver, while GH2 computes a fast greedy assignment of all possible job parts to machines.

# 4 Computational experiments

The experiments are performed on 27 weekly instances, from 01/2020 - 07/2020. The number of jobs per instance ranges from 7-69, the available groups of workers and number of machines per week are $R = 3$ and 12 respectively, while setup times receive values from the set $\{2h, 4h, 6h\}$. The experiments ran on a 64-bit Windows PC (Intel i5, 2.5GHz CPU speed, 8GB RAM) using Python 3.7.2 for GH1, GH2 and GUROBI 9.1 (Python API for (MILP) and MILP of GH1).

We tested (MILP) on the above dataset, with a 2-hour limit, on 4, 6, 8 and 10 machines and it was able to solve optimally one weekly instance (7 orders) on 10 and 8 machines in 10 sec and 25 sec respectively, while the other two instances were solved with Gaps 8.62 % after 262 sec for 6 machines and 5.14% after 1735 sec for 4 machines. The difficulty of (MILP) to deal with job splitting property lies on the fact that the time horizon (thus, the number of time intervals and the number of variables) increases exponentially as the quantity of the job increases. Interestingly, the above results refer to the solution of Gurobi when using as upper bound the best among GH1 and GH2 solutions (normalizing processing times and setup times as multiples of $l_T$), otherwise we could only handle some daily instances. So we proceed by applying GH1 and GH2 to solve our weekly instances. To better evaluate the performance of GH1 and GH2 we divide our dataset into five subsets of increasing number of jobs, each consisting of 5-6 weekly instances and we test each subset for different number of available machines (4,6,8,10,12).

<table><caption>**Table 4:** Results over all weekly instances on 4, 6, 8, 10 and 12 machines</caption><thead><tr><th rowspan="2"># Orders</th><th colspan="5">% Gaps of GH1</th><th rowspan="2">Mean Gap (%)</th><th rowspan="2">Mean t(s)</th><th colspan="5">% Gaps of GH2</th><th rowspan="2">Mean Gap (%)</th><th rowspan="2">Mean t(s)</th></tr><tr><th>4</th><th>6</th><th>8</th><th>10</th><th>12</th><th>4</th><th>6</th><th>8</th><th>10</th><th>12</th></tr></thead><tbody><tr><td>[7, 26]</td><td>3.2</td><td>4.92</td><td>6.99</td><td>10.45</td><td>10.39</td><td>7.19</td><td>38.7</td><td>13.03</td><td>22.46</td><td>30.21</td><td>38.43</td><td>42.15</td><td>29.25</td><td>3.9</td></tr><tr><td>[35, 40]</td><td>2.2</td><td>3.21</td><td>4.2</td><td>5.67</td><td>5.99</td><td>4.25</td><td>34.9</td><td>11.07</td><td>16.94</td><td>22.91</td><td>36.8</td><td>29.82</td><td>23.51</td><td>25.3</td></tr><tr><td>[43, 45]</td><td>2.14</td><td>2.77</td><td>4.17</td><td>5.59</td><td>7.05</td><td>4.34</td><td>38.6</td><td>10.87</td><td>14.88</td><td>23.78</td><td>35.5</td><td>38.63</td><td>24.73</td><td>8.7</td></tr><tr><td>[46.51]</td><td>1.97</td><td>2.86</td><td>3.7</td><td>4.82</td><td>6.09</td><td>3.89</td><td>33.8</td><td>11.16</td><td>15.95</td><td>23.02</td><td>33.86</td><td>30.72</td><td>22.94</td><td>6.5</td></tr><tr><td>[57, 69]</td><td>1.76</td><td>2.54</td><td>3.37</td><td>4.39</td><td>5.62</td><td>3.54</td><td>36.1</td><td>12.98</td><td>17.96</td><td>22.7</td><td>31.22</td><td>24.05</td><td>21.78</td><td>15.9</td></tr><tr><td>Mean Gap</td><td>2.28</td><td>3.3</td><td>4.55</td><td>6.29</td><td>7.1</td><td>4.71</td><td>-</td><td>11.84</td><td>17.75</td><td>24.68</td><td>35.23</td><td>33.32</td><td>24.57</td><td>-</td></tr><tr><td>Mean t(s)</td><td>6.3</td><td>35.4</td><td>33.5</td><td>46.5</td><td>59.8</td><td>-</td><td>35</td><td>26.9</td><td>7</td><td>5.3</td><td>4</td><td>14.6</td><td>-</td><td>11.6</td></tr></tbody></table>

As we show in Table 4, GH1 outperforms GH2, achieving results of 4.2 times smaller gap, but being 3 times slower on average, over different numbers of
available machines. Notably, GH1 achieves almost optimal solutions of Gap less than 7.1% (4.7% on average) for all instances, in less than a minute (35 sec on average). Note that instances with a few orders on many machines seem to demonstrate larger Gaps, compared to smaller number of machines mainly due to the total setup time constraint and the limited number of groups of workers. Additionally, running times may seem inconsistent regarding the size of the instances, but this is justified due to the small number of instances of each subset. As a result, instances that are time-consuming within a subset have a huge impact on the average running time.

## 5 Enhancements

It is important to note that, due to the COVID-19 situation, 22.13% of orders were tardy. Even though the solutions in Section 4 achieve small gaps, they cause a significant increase on the number of tardy jobs which therefore rise to 27.4% of the total orders (an increase of 24% compared to the ones initially tardy).

Moreover, observing that small jobs (unsplittable with $q_i < 100$ meters) have tight deadlines, while larger ones have looser, it appeared reasonable to dedicate a set of machines to small jobs and the rest to the large ones. To this direction, we perform a comparison of GH1 and GH2 on small and large jobs separately, to decide which is the best choice in every case. We divide each weekly instance to small and large jobs and, as before, we divide our dataset into subsets of increasing number of (either small or large) jobs. Subsets with small jobs consist of 4-6 weekly instances each, while subsets of large jobs of 5-7; note that on the latter we have excluded two instances, since they included only 1 and 2 jobs respectively. The size of small job instances ranges from 6 to 41, while for large from 5 to 34.

<table><thead><tr><th rowspan="2"># Orders</th><th colspan="4">% Gaps of GH1</th><th colspan="4">% Gaps of GH2</th></tr><tr><th>4</th><th>6</th><th>8</th><th>10</th><th>4</th><th>6</th><th>8</th><th>10</th></tr></thead><tbody><tr><td>[6, 12]</td><td>3.78</td><td>8.53</td><td>5.36</td><td>4.37</td><td>27.11</td><td>26.67</td><td>20.13</td><td>15.36</td></tr><tr><td>[14, 22]</td><td>6.64</td><td>9.55</td><td>16.69</td><td>19.84</td><td>22.66</td><td>41.52</td><td>44.42</td><td>52.07</td></tr><tr><td>[25, 29]</td><td>8.26</td><td>20.53</td><td>48.24</td><td>58.43</td><td>16.35</td><td>32.03</td><td>55.16</td><td>68.08</td></tr><tr><td>[30, 31]</td><td>6.69</td><td>25.8</td><td>60.75</td><td>77.98</td><td>26.49</td><td>53.8</td><td>64.05</td><td>102.75</td></tr><tr><td>[33, 41]</td><td>6.41</td><td>16.33</td><td>45.5</td><td>65.08</td><td>15.13</td><td>23.86</td><td>51.83</td><td>56.02</td></tr><tr><td>Mean Gap</td><td>6.54</td><td>16.35</td><td>36.6</td><td>46.94</td><td>20.95</td><td>35.56</td><td>48.49</td><td>60.45</td></tr><tr><td>Mean t(s)</td><td>9</td><td>2.7</td><td>5.7</td><td>30.6</td><td>1.1</td><td>1.5</td><td>2</td><td>2.4</td></tr></tbody></table>

<table><caption>**Table 5:** Results on small (left) and large (right) job instances for 4, 6, 8, 10 machines</caption><thead><tr><th rowspan="2"># Orders</th><th colspan="4">% Gaps on GH1</th><th colspan="4">% Gaps on GH2</th></tr><tr><th>4</th><th>6</th><th>8</th><th>10</th><th>4</th><th>6</th><th>8</th><th>10</th></tr></thead><tbody><tr><td>[5, 12]</td><td>2.96</td><td>4.23</td><td>6.04</td><td>7.82</td><td>17.45</td><td>38.01</td><td>30.82</td><td>64.14</td></tr><tr><td>[13, 16]</td><td>1.66</td><td>2.46</td><td>3.4</td><td>4.71</td><td>10.14</td><td>20.66</td><td>24.61</td><td>46.55</td></tr><tr><td>[18, 19]</td><td>1.58</td><td>2.29</td><td>3.46</td><td>4.19</td><td>8.88</td><td>13.43</td><td>21.61</td><td>29.36</td></tr><tr><td>[20, 34]</td><td>1.02</td><td>1.53</td><td>2.27</td><td>3.21</td><td>7.89</td><td>14.34</td><td>19.7</td><td>25.27</td></tr><tr><td>Mean Gap</td><td>1.78</td><td>2.59</td><td>3.73</td><td>4.93</td><td>11.01</td><td>21.61</td><td>24.12</td><td>41.38</td></tr><tr><td>Mean t(s)</td><td>9.9</td><td>358.1</td><td>208.6</td><td>300.1</td><td>125.8</td><td>51.7</td><td>13.8</td><td>11.5</td></tr></tbody></table>

We tested (MILP) on small jobs, using a simplified version (where in constraints (16)-(18) we substituted $Q_{i,m} \cdot \frac{u_i}{s_m}$ by $Y_{i,m} \cdot p_{i,m}$ while Constraints (5)-(6) were removed) on 4, 6, 8 and 10 machines, for 8 out of 27 weekly instances (from 6 to 18 orders). Notably the exact solver was able to solve optimally 20 instances in 98.03 sec on average, 10 instances were solved with mean Gap 7.36% and for 2 it was not able to obtain a solution under 1-hour limit. However, since the solutions obtained were of similar Gap with the ones of GH1, we do not present
them in more detail. Table 5 presents the comparison between GH1 and GH2 on small and large job instances, respectively. GH1 achieves solutions of better quality, with 26.6% and 4.8% Gap for small and large jobs respectively, however GH2 is much faster (4 times on large and almost 6 times on small jobs). Interestingly, for small jobs the difference on their gap is significantly decreasing (from 410% on large jobs to 55%). Note that Gap values on small jobs instances are quite large, but this is due to the strict daily total setup time constraint.

Since GH1 performs better on both small and large job instances, we run it once to schedule first all small jobs to an appropriate number of machines, and re-run it consequently to schedule the large jobs on the remaining machines or (if possible) after the small jobs on their dedicated machines. More precisely, we run GH1 for each weekly instance, for 12 candidate numbers of dedicated machines ($|M| \in \{1, 2, \dots, 12\}$) on small jobs. The aim of this approach is to examine the effect of dedicated machines on three optimisation criteria: makespan, number of tardy jobs and total tardiness.

<figure><img src="image_3.png" /><figcaption>**Fig. 1:** Best policies to balance makespan, number of tardy jobs and total tardiness, over weekly instances.</figcaption></figure>

We consider as baseline the makespan, number of tardy jobs and total tardiness over all weekly instances computed by GH1 in Section 4 and highlight the smallest average change on each criterion over the same instances, over all runs under different number of dedicated machines: For makespan, the smallest average increase is 1.55%, while for the same instances tardiness and the number of tardy jobs decrease by 16.68% and 10% respectively. For the number of tardy jobs, the largest average decrease is 16%, while for the same instances the makespan increases by 4.07%, and tardiness decreases by 19.1%. For total tardiness, the largest average decrease is 22.62%, while for the same instances makespan increases by 6.35% and number of tardy jobs decreases by 12.12%.

Fig. 1 presents a proposed policy for weekly instances, in order to achieve better trade offs between makespan increase and number of tardy jobs, tardiness decrease. We conclude that dedicating machines on small jobs positively affects 17 out of 27 instances (in Fig. 1), trading a small increase on makespan for
large reductions on the number of tardy jobs and total tardiness. Notably all improvements occurred when the number of dedicated machines ranges from 2-7, while in 76% of the instances the range is from 2-4. It is also encouraging that on 15 of those 17 instances there were various alternative policies that could be chosen demonstrating also positive effects.

Additional experimentation, on both real and random or modified literature instances, could yield more insights. Although already competitive within a quite challenging setting, our optimisation approach could be further strengthened by examining tighter formulations in a combination with a Benders-like decomposition, to accomplish provably near-optimal solutions on even larger instances.

## References

1. Allahverdi, A., Ng, C-T., Cheng, T. E. and Kovalyov, Y. A survey of scheduling problems with setup times or costs. *EJOR*, 187: 985-1032, 2008.

2. Aspnes, Y., Azar, Y. Fiat, A., Plotkin, S., and Waarts, O. On-line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling. *JACM* 44(3):486-504, 1997.

3. Brucker, P. Scheduling Algorithms. Springer, 1999.

4. Correa, J., Verdugo, V., Verschae, J. Splitting versus setup trade-offs for scheduling to minimize weighted completion time. *ORL*, 44: 469-473, 2016.

5. Eroglu, D. Y. and Ozmutlu, H. C. Solution method for a large-scale loom scheduling problem with machine eligibility and splitting property. *TJTI*, 108(12): 2154-2165, 2017.

6. Eroglu, D. Y., Ozmutlu, H. C. and Ozmutlu, S. Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times. *IJPR*, 52(19):5841-5856, 2014.

7. Letsios, D., Bradley, J. T., Suraj, G., Misener, R. and Page, N. Approximate and robust bounded job start scheduling for Royal Mail delivery offices. *JOS*, 1-22, 2021.

8. Lee, J-H., Hoon Jang, H. and Kim, H-J. Iterative job splitting algorithms for parallel machine scheduling with job splitting and setup resource constraints. *JORS*, 2020.

9. Peyro, L. F. Models and an exact method for the Unrelated Parallel Machine scheduling problem with setups and resources. *ESWA*, 2020.

10. Peyro, L.F., Ruiz, R. and Perea, F. Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times. *COR*, 81: 173-182, 2019.

11. Pimentel, C., Alvelos, F., Duarte, A. and Carvalho, J. Exact and heuristic approaches for lot splitting and scheduling on identical parallel machine. *IJMTM*, 22(1): 39-57, 2011.

12. Roberti, R., and Toth P. Models and algorithms for the Asymmetric Traveling Salesman Problem: an experimental comparison. *EJTL*, 1:113-133, 2012.

13. Rosales, O.A., Bello, F. A. and Alvarez, A. Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. *IJAMT*, 76:1705-1718, 2015.

14. Serafini, P. Scheduling jobs on several machines with job splitting property. *INFORMS J. Comp.*, 44:531-659 1996.

15. Wang, J-B. and Wang, J-J. Research on scheduling with job-dependent learning effect and convex resource-dependent processing times. *IJPR*, 53 (19): 5826-5836, 2015.