# Order Acceptance and Scheduling with Sequence-dependent Setup Times: a New
Memetic Algorithm and Benchmark of the State of the Art

Lei He<EMAIL_ADDRESS>Arthur Guijt  Mathijs de Weerdt  Lining Xing  Neil
Yorke-Smith  College of Systems Engineering, National University of Defense
Technology, Changsha, China, 410073  Delft University of Technology, P.O. Box
5031, 2600 GA Delft, The Netherlands

###### Abstract

The Order Acceptance and Scheduling (OAS) problem describes a class of real-
world problems such as in smart manufacturing and satellite scheduling. This
problem consists of simultaneously selecting a subset of orders to be
processed as well as determining the associated schedule. A common
generalization includes sequence-dependent setup times and time windows. A
novel memetic algorithm for this problem, called Sparrow, comprises a
hybridization of biased random key genetic algorithm (BRKGA) and adaptive
large neighbourhood search (ALNS). Sparrow integrates the exploration ability
of BRKGA and the exploitation ability of ALNS. On a set of standard benchmark
instances, this algorithm obtains better-quality solutions with runtimes
comparable to state-of-the-art algorithms. To further understand the strengths
and weaknesses of these algorithms, their performance is also compared on a
set of new benchmark instances with more realistic properties. We conclude
that Sparrow is distinguished by its ability to solve difficult instances from
the OAS literature, and that the hybrid steady-state genetic algorithm (HSSGA)
performs well on large instances in terms of optimality gap, although taking
more time than Sparrow.

###### keywords:

Memetic algorithm, Biased random key genetic algorithm, Adaptive large
neighbourhood search , Order acceptance and scheduling , Sequence-dependent
setup times

††journal: Computers & Industrial Engineering

##  1 Introduction

The Order Acceptance and Scheduling (OAS) problem consists of simultaneously
selecting a subset of orders to be processed as well as determining the
associated schedule. This problem is important because it represents a class
of real-world industrial problems. For example, when a smart manufacturing
system does not have the capacity to meet the demand, it has to reject some
orders in favour of others. Other typical instances of the OAS problem are for
example satellite observation scheduling, where the number of observations
requests is usually higher than the number of observation a satellite can take
[1], and in industrial and commercial logistics, such as deciding the cities
to visit within a day to maximize the total profit [2].

Many real-world order acceptance and scheduling problems in smart
manufacturing and other domains have setup times and time windows. The setup
time is the time needed for the preparation of the next order, such as the
time to prepare batches of products in the factory domain and the observation
angle transition time in the satellite domain. The setup time is usually
sequence-dependent, which means the setup between every two orders depends on
the specific pair of orders. The time windows specify a time period for each
order when it can be processed. These problems can be generalized as a typical
type of OAS problem: the OAS problem with sequence-dependent setup times and
time windows [3]. This problem has been proven to be NP-hard [4].

The current state-of-the-art for the OAS problem with sequence-dependent setup
times and time windows limits the capability of smart industry and operations.
Currently, realistically-sized problems cannot be solved quickly enough:
instead, solution quality must be compromised to deliver timely solutions. In
addition, since current research focuses on improving the performance of
algorithms, few contributions try to understand the problem further by
studying how the problem properties correlate with its difficulty, how
different algorithms perform on problem instances with varying properties, and
how the instances in the standard benchmark set by Cesaret et al. [5]
correspond to real-life scenarios. These research gaps motivate our
contribution.

In this article we propose a novel memetic algorithm applied for the OAS
problem with sequence-dependent setup times and time windows, called
Sparrow.111This algorithm combines a population-based genetic algorithm with
adaptive large neighbourhood search. Each individual in a “swarm” thus has a
bird’s eye view of the search space – hence Sparrow.The main contributions of
this article are summarized as follows:

  1. 1.

Sparrow is a hybridization of the biased random key genetic algorithm (BRKGA)
and the adaptive large neighbourhood search algorithm (ALNS). To the best of
our knowledge, this is the first hybridization of these two algorithms. We
introduce several new strategies to make the hybridization efficient.

  2. 2.

We compare Sparrow with state-of-the-art algorithms on a set of standard
benchmark instances from the literature. The proposed algorithm obtains
better-quality solutions with comparable running time.

  3. 3.

We study the correlation of the problem properties and the algorithm
performance and find that the congestion ratio, the length of time windows,
and the correlation of processing time and revenue of orders are highly
related to the difficulty of the problem.222These terms are defined in Section
4.3.

  4. 4.

We further generate new instances that are more representative of real problem
instances in satellite scheduling (more congestion), commerce (high
correlation between revenue and processing time), and the travelling repairman
problem (short processing times and long time windows), and compare the
performance of multiple state-of-the-art algorithms on these new instances.

The remainder of this article is summarized as follows: Section 2 provides
background information; Section 3 introduces Sparrow; Section 4 provides the
empirical study of the proposed algorithm; the conclusions are summarized in
Section 5.

##  2 Background

In this section we first introduce the mathematical formation of the OAS
problem. Then we review the related works. Finally we describe the standard
BRKGA and ALNS algorithms.

###  2.1 Mathematical formulation

Consider a set of orders $O=\\{o_{1},...,o_{n}\\}$ that can be potentially
scheduled. The sequence of orders is not fixed. Each order has a revenue
$r_{i}$, a processing duration time $t_{i}$, a due time $d_{i}$, a penalty
weight of tardiness $w_{i}$ and a time window $[b_{i},e_{i}]$ indicating the
release time and deadline of the order. Let $x_{i}$ be a binary decision
variable representing whether order $o_{i}$ is selected and $p_{i}$ be a
decision variable representing the start time of $o_{i}$. Let $T_{i}$ be the
tardiness of $o_{i}$, $T_{i}=\max\\{p_{i}+t_{i}-d_{i},0\\}$. The problem can
be formulated as a mixed integer programming (MIP) model:

$\textrm{Maximize}\quad\sum_{i=1}^{n}x_{i}(r_{i}-w_{i}T_{i})$ (1)

subject to

$\begin{array}[]{c}\max\\{b_{j},p_{i}+t_{i}\\}+s_{ij}\leq p_{j}\\\ \forall
i,j\in\\{1,...,n\\}\quad\textrm{if}\quad
x_{i}=1,x_{j}=1,p_{i}<p_{j}\end{array}$ (2)
$T_{i}=\max\\{p_{i}+t_{i}-d_{i},0\\}\quad\forall i\in\\{1,...,n\\}$ (3)
$b_{i}\leq p_{i}\leq e_{i}-t_{i}\quad\forall
i\in\\{1,...,n\\}\quad\textrm{if}\quad x_{i}=1$ (4)
$x_{i}\in\\{0,1\\}\quad\forall i\in\\{1,...,n\\}$ (5)

The objective function (1) maximizes the total reward of scheduled orders. The
reward of an order equals its revenue minus the penalty of tardiness.
Constraints (2) ensure the time between every two orders should be long enough
for the setup, where $s_{ij}$ is the setup time between orders $o_{i}$ and
$o_{j}$. The value of $s_{ij}$ depends on $i$ and $j$ and is always non-
negative. Constraints (3) define the domains of the tardiness of orders.
Constraints (4) and (5) define the domains of the decision variables $p_{i}$
and $x_{i}$ respectively.

A feasible solution of this problem is a sequence of orders with scheduled
start times which meet all the constraints above. It can be represented as a
tuple $(X,P)$, where $X=\\{x_{1},...,x_{n}\\}$ and $P=\\{p_{1},...,p_{n}\\}$.

###  2.2 Related works

Due to the large number of OAS variants, we only review the articles studying
the OAS problem with sequence-dependent setup times and time windows. Readers
are referred to Slotnick [6] for a comprehensive survey of the OAS problem.

The OAS problem with sequence-dependent setup times and time windows was first
proposed by Oğuz et al. [3]. They proposed a mixed integer linear programming
(MILP) method for this problem, two simple greedy constructive heuristics, and
a heuristic algorithm called iterative sequence first-accept next (ISFAN),
which is based on the simulated annealing (SA) algorithm. Cesaret et al. [5]
proposed a tabu search (TS) algorithm to solve this problem, which achieved
better results than ISFAN. Another major contribution of this article is that
it provided the benchmark set and the upper bounds of this problem. Nguyen et
al. [7] proposed an exact branch-and-bound (B&B) with genetic programming (GP)
to discover good ordering rules. Their method could find optimal solutions for
instances with up to 20 orders. Silva et al. [8] proposed a new arc-time-
indexed formulation and two exact methods based on Lagrangian relaxation and
column generation respectively. They computed tighter upper bounds compared
with those by Cesaret et al. [5]. They also proposed an iterated local search
(ILS) method to solve the problem.

The hybridization of population-based methods with local search (LS) has been
used a lot to solve this problem. Lin and Ying [9] proposed an artificial bee
colony (ABC) algorithm to solve this problem. They used a permutation based
representation and generated new solutions through standard order crossover or
a LS algorithm (removing and inserting orders). Their methods achieved better
results than those of TS [5]. Chen et al. [10] proposed a diversity
controlling genetic algorithm (DCGA), which selects individual chromosomes not
only depending on the fitness, but also on the diversity of the whole
population. In their algorithm, they also adopted similar LS methods as in
[9]. Nguyen et al. [11] proposed a dispatching-rule-based genetic algorithm
(DRGA). The dispatching rule is a strategy to calculate some heuristic
priorities for orders and these priorities are used in the decoding process.
They also used a simple greedy LS method to improve the solutions. Following
Nguyen et al., Park et al. [12] proposed a GP method with stochastic
dispatching rules, which could generate and evolve rules to find good
solutions. They later proposed a hybrid particle swarm optimization (PSO)
method with TS using dispatching rules learned by GP [13]. Similar ideas can
also be found in [14]. Nguyen [15] proposed a hyper-heuristic algorithm, which
is a learning and optimizing system (LOS). The method trains a set of
optimizing rules in the learning phase, then the rules are used by a genetic
algorithm (GA) to find good solutions in the optimizing phase. More recently,
Chaurasia and Singh [16] proposed a hybrid steady-state genetic algorithm
(HSSGA) and an evolutionary algorithm with guided mutation (EA/G-LS). The
authors also proposed an ABC-based hyper-heuristic. However they only
published the results on small instances [17].

From the above review we can find that the hybridization of population-based
methods with LS methods is a promising method for the OAS problem with
sequence-dependent setup times and time windows. The evolutionary algorithm
(EA) is an important population-based algorithm. The hybridization of EA and
LS is called memetic algorithm (MA) [18] and has also been successfully
applied to problems where all orders are scheduled including the travelling
salesman problem [19], the flowshop scheduling problem [20] and the location
routing problem [21]. It is recognized that the superior performance of MA
comes from the integration of the exploration ability of the EA and the
exploitation ability of the LS [22]. A detailed description and comprehensive
survey of MA could be found in [23].

Next, we review the two components of Sparrow: BRKGA and ALNS.

The BRKGA algorithm is a variant of the EA method proposed by Gonçalves and De
Almeida [24]. Compared with standard GA methods, BRKGA offers more flexibility
in encoding solutions [25] and produces as good or better solutions [26].
BRKGA has shown competitive performance on a series of optimization problems
[27], including the satellite scheduling problem [28], which is very similar
to the problem studied in this article. The ALNS algorithm was first proposed
by Pisinger and Ropke [29]. It performs particularly well on problems with
order acceptance features, such as the orienteering problem [30], the
satellite scheduling problem [31] and the pickup and delivery problem with
selective requests [32].

Comparing the two approaches, the advantage of BRKGA is that it can search the
large solution space efficiently. However, the problem-independent nature of
BRKGA makes it difficult to find high-quality solutions. For the second
approach, ALNS, multiple neighbourhood operators can be defined according to
the characteristics of the problem. Therefore ALNS has a good exploitation
ability and can adapt itself according the different properties of problem
instances. However, its search efficiency can founder due to the entrapment in
a local optimum because of the single-point search. We are interested to see
if a hybridization could be made such that the advantages of the two
algorithms can be integrated and achieve better performances.

###  2.3 The standard BRKGA and ALNS algorithms

In this section we introduce the standard BRKGA [24] and ALNS [29].

In BRKGA, a population of $p$ solutions are represented as $p$ chromosomes,
consisting of genes which are encoded by real values randomly generated in the
interval [0,1], i.e., random keys. The number of genes in a chromosome equals
the number of orders. Chromosomes are then decoded to obtain solutions and
calculate fitness, which is a problem-dependent process. Example 1 shows a
simple decoding method for the problem studied in this article. The best
$p_{e}$ chromosomes are recognized as elite individuals. In the mutation
operation, $p_{m}$ chromosomes are generated randomly (i.e., same as the
initial population) to avoid the entrapment in a local optimum. In the
crossover operation, $p-p_{e}-p_{m}$ chromosomes are generated by inheriting
each gene from an elite parent with the probability $\rho_{e}$ and a non-elite
parent with the probability $1-\rho_{e}$. The encoding strategy of BRKGA
ensures that there are no duplicate orders and all solutions are feasible in
the crossover operation.

Example 1. All the orders are first sorted according to the ascending gene
values. Then the orders are started as early as possible. Any order that can
not complete before the deadline or can not achieve a positive reward, will be
rejected. Consider a set of five orders $\\{1,2,3,4,5\\}$ with the
corresponding gene values $\\{0.6,0.2,0.3,0.5,0.7\\}$. The decoder tries to
start each order as early as possible, following the sequence of
$\\{2,3,4,1,5\\}$. Assume that the end time of order 3 is larger than the
deadline of order 4, which means that order 4 cannot be inserted in the
solution, the resulting solution would be $\\{2,3,1,5\\}$.

ALNS starts from an initial solution usually generated by a simple heuristic,
because it is less sensitive to the initial solution than general local search
[33]. ALNS proceeds to generate new solutions through destroying and
repairing. In the destroying process, $p_{d}$ orders are removed from the
current solution by removal operators. The unscheduled and removed orders are
then inserted into the destroyed solution in the repairing process by
insertion operators. There are multiple removal and insertion operators. At
each iteration, a pair of removal and insertion operators is selected by a
roulette wheel mechanism according to their weights. After a certain number of
iterations, the weight of the operator $w_{i}$ is updated adaptively according
to its accumulated score $\pi_{i}$ in the previous iterations,
$w_{i}=(1-\lambda)w_{i}+\lambda{\pi_{i}}/\sum_{j}\pi_{j}$, where
$\lambda\in[0,1]$ is a reaction factor which controls how sensitive the
weights are to changes in the performance of operators. A simulated annealing
(SA) criterion is used to control the acceptance of new solutions by a
temperature parameter $T$. Let $f(S)$ and $f(S^{\prime})$ be the reward of
current solution $S$ and new solution $S^{\prime}$ respectively. The new
solution $S^{\prime}$ is accepted if $f(S^{\prime})>f(S)$; otherwise, it is
accepted with probability:
$\rho=\exp\left(\frac{100}{T}\left(\frac{f(S^{\prime})-f(S)}{f(S)}\right)\right)$.

##  3 Sparrow

In this section, we first introduce the main framework of Sparrow. The tight
hybridization aims to avoid the possible high running time of the combination
of the two complex algorithms and aims to integrate the advantages of them.
Then we introduce the BRKGA part, where we propose a new bounded-width gene
encoding strategy for the problem with time windows, a hybrid decoding method
for the OAS problem and an intelligent crossover operator. Finally we
introduce the ALNS part, where we define several neighbourhood operators and
propose a fast insertion algorithm considering sequence-dependent setup times.

###  3.1 The main framework

The main framework of Sparrow is shown in Algorithm 1. The main structure of
this algorithm is derived from BRKGA. ALNS is used in each iteration to
improve the quality of the population. Figure 1 shows how the algorithm
evolves generations of solutions.

Figure 1: The main framework of Sparrow

A problem of integrating ALNS in BRKGA is the complexity, because ALNS itself
needs multiple iterations to improve a single solution. In order to hybridize
these two algorithms without increasing the computation time too much, we run
the destroying and repairing process of ALNS only once for each solution in
the population and only on relatively good solutions with at least $p_{f}$ of
the best fitness (i.e., the value of the objective function Eq. (1)) found so
far (Algorithm 1, Lines 6–8).

In standard ALNS, the algorithm updates the temperature in each iteration and
updates the weights of operators after a certain number of iterations
according to their performances. In this population-based ALNS, these two
processes happen in each iteration (Algorithm 1, Lines 19, 20). The weights of
operators are updated according to their performances in improving the
individuals in the population.

There are three terminal conditions of Sparrow: when the maximum iteration is
reached; when the best fitness is not improved for a maximum number of
consecutive iterations; when all orders in the instance are scheduled and
receive full revenue.

Algorithm 1 Sparrow

1:Generate an initial population $P$, consisting of $p$ chromosomes;

2:Let $S^{*}$ be the best solution and $f^{*}$ be its fitness,
$S^{*}\leftarrow\emptyset$, $f^{*}\leftarrow 0$;

3:repeat

4: for each chromosome $c$ in $P$ do

5: $S\leftarrow Decode(c)$

6: if $f(S)\geq p_{f}f^{*}$ then

7: $S\leftarrow ALNS(S,f^{*})$

8: end if

9: if $f(S)>f^{*}$ then

10: $f^{*}\leftarrow f(S)$, $S^{*}\leftarrow S$

11: end if

12: end for

13: Sort chromosomes in $P$ according to a descending order of fitness;

14: Add the top $p_{e}$ chromosomes to Elite set $E$;

15: Add the remaining chromosomes to Non-elite set $N$;

16: Generate a mutation set of $p_{m}$ chromosomes: $M\leftarrow Mutation()$;

17: Generate a crossover set of $p-p_{e}-p_{m}$ chromosomes: $C\leftarrow
Crossover(E,N)$;

18: $P\leftarrow E\cup M\cup C$;

19: Update the temperature of ALNS with the coefficient of annealing $c_{a}$:
$T\leftarrow c_{a}T$;

20: Update the weights of different operators of ALNS;

21:until Terminal condition is met;

22:return $S^{*}$, $f^{*}$;

###  3.2 The BRKGA

####  3.2.1 Encoding and decoding

In standard BRKGA, the initial random key is generated randomly in the
interval [0,1] and then decoded according to the simple decoding method in
Example 1. However, for this problem with time windows, if an order with early
time windows receives a large random key, this order may not be scheduled
because its time window is occupied by other orders with smaller random keys.
To solve this problem, we propose the bounded-width gene encoding method and
the hybrid decoding method.

Bounded-width gene encoding. When assigning the initial gene value to orders,
we calculate the proportion of the window size in the whole scheduling
horizon. For example, if an order has the time window [0,10] and the whole
scheduling horizon is [0,100], the interval for the gene value of this order
is [0,0.1]. This strategy helps to reduce the solution space, especially for
the instances with short time windows.

One problem of this strategy is that orders with earlier time windows are
preferred than those with later time windows, because those with later time
windows receive larger random keys and may not be scheduled because of the
early ones. This problem is solved by the ALNS algorithm in the removal
process. The details are shown in Section 3.3.1.

Hybrid decoding method. Our hybrid decoding method consists of the simple
decoding method as in Example 1 and a complex decoding method with order
insertion. For the complex decoding, all the orders are also sorted according
to the ascending gene values. Instead of starting each order following this
sequence, this decoder tries to insert each order into the current partial
solution at the position which increases minimum setup time. When inserting an
order, the orders in the partial solution might be postponed but will not be
canceled. The detailed insertion strategy is introduced in Section 3.3.2.

The complexity of the complex decoding is certainly higher than the simple
decoding. However, it helps to increase the probability of orders with short
time windows being successfully scheduled. We use an adaptive strategy to
hybridize these two strategies according to the instance. We calculate the
value of the average length of all orders divided by the scheduling horizon.
Let this value be $r_{d}$. For each chromosome, the algorithm chooses the
simple decoding with the probability of $r_{d}$; otherwise it uses the complex
decoding.

After a number of iterations, the random keys of different orders may squeeze
together due to the following crossover and ALNS operations. In order to avoid
this, we normalize the keys to distribute them evenly in the interval of [0,1]
in each iteration.

####  3.2.2 Intelligent crossover

In the standard BRKGA, the offspring inherits each gene from the elite parent
with the probability $\rho_{e}$; otherwise it inherits the gene from the non-
elite parent. This strategy ensures that the offspring has more genes from the
elite parent. However, in this OAS problem with sequence-dependent setup
times, the quality of a sequence of orders is important. The setup time
between any two orders can differ much. The standard crossover operation might
break good sequences when it inherits genes from different parents, thus
producing low-quality offspring.

We propose an intelligent crossover strategy to keep good order pairs together
in the offspring. Before the crossover, the algorithm identifies good order
pairs in the current elite and non-elite parents. A pair of orders is
recognized as $good$ if it has a relatively high unit reward (i.e., the total
reward of the two orders divided by the time between the start time of the
preceding order and the end time of the following order is higher than a
constant parameter $f_{g}$).

When a good pair of orders is found, the gene value of the following order
will be changed to the gene value of the preceding order plus a small enough
positive number $\epsilon$, to ensure they will have a high probability of
being together in the decoding phase. The crossover operator selects genes
from one of the parent one-by-one. Normally there is a constant $\rho_{e}$
determining the probability whether the gene comes from the elite or the non-
elite parent. For the intelligent crossover, when one gene of a good pair is
selected, the probability that the other gene in the good pair will be
selected is enhanced to be $p_{g}$, a value close to 1.

The detailed process is shown in Algorithm 2.

Algorithm 2 Intelligent crossover

1:Input: Elite set $E$; Non-elite set $N$;

2:Let $C\leftarrow\emptyset$ be the crossover offspring set;

3:repeat

4: Select an elite parent chromosome $C_{e}$ from $E$ randomly;

5: Select a non-elite parent chromosome $C_{n}$ from $N$ randomly;

6: Initialize a child chromosome $C_{c}$ with an empty gene list;

7: Identify and label $good$ pairs of orders in $C_{e}$ and $C_{n}$;

8: for $i\leftarrow 1,i\leq n,i$++ do

9: if the $i^{th}$ gene in $C_{e}$ is $good$ $\wedge$ its pair is in $C_{c}$
then

10: Generate a random value $r$ in [0,1];

11: if $r<p_{g}$ then

12: Add the $i^{th}$ gene in $C_{e}$ into $C_{c}$;

13: else

14: Add the $i^{th}$ gene in $C_{n}$ into $C_{c}$;

15: end if

16: else

17: if the $i^{th}$ gene in $C_{n}$ is $good$ $\wedge$ its pair is in $C_{c}$
then

18: Generate a random value $r$ in [0,1];

19: if $r<p_{g}$ then

20: Add the $i^{th}$ gene in $C_{n}$ into $C_{c}$;

21: else

22: Add the $i^{th}$ gene in $C_{e}$ into $C_{c}$;

23: end if

24: else

25: Generate a random value $r$ in [0,1];

26: if $r<\rho_{e}$ then

27: Add the $i^{th}$ gene in $C_{e}$ into $C_{c}$;

28: else

29: Add the $i^{th}$ gene in $C_{n}$ into $C_{c}$;

30: end if

31: end if

32: end if

33: end for

34:until $|C|=p-p_{e}-p_{m}$

35:return $C$;

###  3.3 The ALNS

As mentioned above, if a solution has a relatively good fitness, ALNS is used
to improve the solution further. In the following sections, we first introduce
the neighbourhood operators; then we introduce a fast insertion algorithm used
in the insertion operator to insert orders into the current solution. The full
ALNS algorithm is shown in Algorithm 3. In Algorithm 3,
$\sigma_{1}>\sigma_{2}>\sigma_{3}$ are three score increment parameters, used
to increase the scores of different neighbourhood operators depending on their
performances.

Algorithm 3 The ALNS algorithm

1:Input: Current solution $S_{C}$; best fitness $f^{*}$;

2:Add all unscheduled orders in order bank $B$ according to $S_{C}$;

3:Select a removal operator $O_{R}$ according to the weights;

4:Sort the scheduled orders in $S_{C}$ according to $O_{R}$;

5:$S_{N}\leftarrow$ Remove the top $p_{d}$ orders from $S_{C}$ and add them
into $B$;

6:Update the start times and time slacks of orders in $S_{N}$;

7:Select an insertion operator $O_{I}$ according to the weights;

8:Sort the unscheduled orders in $B$ according to $O_{I}$;

9:for each candidate order $o_{c}$ in $B$ do

10: $S_{N}\leftarrow$ $FastInsertionAlgorithm(S_{N},o_{c})$

11:end for

12:if $f(S_{N})>f^{*}$ then

13: $\pi_{O_{R}}\leftarrow\pi_{O_{R}}+\sigma_{1}$,
$\pi_{O_{I}}\leftarrow\pi_{O_{I}}+\sigma_{1}$, $S_{C}\leftarrow S_{N}$;

14:else

15: if $f(S_{N})>f(S_{C})$ then

16: $\pi_{O_{R}}\leftarrow\pi_{O_{R}}+\sigma_{2}$,
$\pi_{O_{I}}\leftarrow\pi_{O_{I}}+\sigma_{2}$, $S_{C}\leftarrow S_{N}$;

17: else

18: if The SA criterion accepts $S_{N}$ then

19: $\pi_{O_{R}}\leftarrow\pi_{O_{R}}+\sigma_{3}$,
$\pi_{O_{I}}\leftarrow\pi_{O_{I}}+\sigma_{3}$, $S_{C}\leftarrow S_{N}$;

20: end if

21: end if

22:end if

23:return $S_{C}$;

####  3.3.1 Neighbourhood operators

In order to ensure ALNS is suitable for a diverse range of problem instances
with varying characteristics, we use the following five removal operators and
two insertion operators. These operators are adapted from those in the
literature [29, 33] to fit our problem.

The five removal operators are: random ($p_{d}$ orders are removed randomly);
min revenue ($p_{d}$ orders with lower revenue are removed); min unit revenue
($p_{d}$ orders with lower unit revenue are removed: the unit revenue is the
revenue of the order divided by its processing time); max setup time ($p_{d}$
orders with longer setup time are removed); sequence removal (the worst
sequence of $p_{d}$ orders is removed: the quality of a sequence is evaluated
by the unit revenue).

The two insertion operators are: max revenue; max unit revenue. The insertion
operator first sorts the orders according to the descending revenue or unit
revenue, then tries to insert orders in the current solution using the fast
insertion algorithm in Section 3.3.2.

In order to make sure that the solution operated by ALNS can be encoded
correctly for the following BRKGA operations, when removing an order, the gene
of this order will be assigned a random real value larger than the largest
gene in the current solution and smaller than 1; when inserting an order, the
gene of this order will be assigned a random real value between the gene
values of its preceding and following orders. This strategy helps to solve the
problem brought by the bounded-width gene generation strategy. Although the
orders with earlier time windows have smaller gene values in the
initialization, they can be removed and get a large gene value in ALNS.

####  3.3.2 Fast insertion algorithm

Our last innovation is a fast insertion algorithm, which first evaluates the
feasibility and the cost of all the positions rapidly by a concept called time
slack. Then the best position is selected to insert the order. The insertion
algorithm is used in the repairing process when we insert orders back to the
solution. The detailed process of the fast insertion algorithm is shown in
Algorithm 4.

Algorithm 4 Fast insertion algorithm

1:Input: Current solution $S_{C}$, candidate order $o_{c}$;

2:for each scheduled order $o_{i}$ in $S_{C}$ do

3: if $e_{c}>b_{i}$ then

4: $t_{1}\leftarrow$ Calculate the end time of $o_{c}$ if it is inserted after
$o_{i}$;

5: $t_{Temp}\leftarrow$ Calculate the temporary start time of $o_{i+1}$ after
$o_{c}$;

6: $t_{2}\leftarrow t_{Temp}-p_{i+1}$;

7: if $t_{1}>e_{c}\vee t_{2}>$ time slack of $o_{i+1}$ then

8: Continue;

9: else

10: if $t_{1}\leq d_{c}\wedge t_{2}\leq$ due time slack of $o_{i+1}$ then

11: $Position_{i}.SetupIncrease\leftarrow s_{ic}+s_{c({i+1})}-s_{i({i+1})}$ ;

12: Add $Position_{i}$ into position list $PL1$;

13: else

14: $Position_{i}.Fitness\leftarrow$ Calculate the total fitness if $o_{c}$ is
inserted;

15: if $Position_{i}.Fitness>f(S_{C})$ then

16: Add $Position_{i}$ into position list $PL2$;

17: end if

18: end if

19: end if

20: end if

21:end for

22:if $PL1\neq\emptyset$ then

23: $BestPosition\leftarrow$ Select the position increasing minimum setup
time;

24: Insert $o_{c}$ into $S_{C}$ at $BestPosition$;

25: Update start times and time slacks;

26:else

27: if $PL2\neq\emptyset$ then

28: $BestPosition\leftarrow$ Select the position increasing maximum fitness;

29: Insert $o_{c}$ into $S_{C}$ at $BestPosition$;

30: Update start times and time slacks;

31: end if

32:end if

33:return $S_{C}$;

Time slack and due time slack. We set all the orders to start as early as
possible. Therefore when inserting one order into the current solution at a
position, it is possible to create more space for the candidate order by
postponing some orders in the solution. In order to determine how much one
order can be postponed, we adopt the time slack idea from Verbeeck et al. [2].
We further propose the due time slack heuristic for this problem with
tardiness penalty. The time slack is defined as the maximum amount of time an
order can be postponed before the solution becomes infeasible. The time slack
of each order depends on the latest start time of its succeeding order. Thus
it is calculated from the last order to the first one in a back-propagation
manner. The due time slack is the maximum amount of time an order can be
postponed without adding penalty to any order. These heuristics facilitate
determining the feasibility and the cost of one insertion only by comparing
the time needed with the corresponding slack.

Select the best position to insert. For every candidate order, we calculate
all possible insertion positions by comparing its time window with the current
solution. For each possible solution, we do the following evaluation: Suppose
we are evaluating the position between order $o_{i}$ and $o_{i+1}$ for the
candidate order $o_{c}$, we first calculate the end time of $o_{c}$ if it is
inserted after $o_{i}$ (denoted as $t_{1}$) and the time $o_{i+1}$ needed to
be postponed (denoted as $t_{2}$). If $t_{1}$ is bigger than the deadline of
$o_{c}$ or $t_{2}$ is bigger than the time slack of $o_{i+1}$, the position is
given up; if $t_{1}$ is smaller than the due time of $o_{c}$ and $t_{2}$ is
smaller than the due time slack (note that the due time slack is always
smaller than the time slack), we calculate the increase of setup time if
inserting $o_{c}$, which is $s_{ic}+s_{c({i+1})}-s_{i({i+1})}$ and add the
position to candidate position list 1, $PL_{1}$; otherwise (i.e., if $t_{1}$
is larger than the due time of $o_{c}$ or $t_{2}$ is larger than the due time
slack), we calculate the total fitness of the solution if we insert the order
at this position and if it increases the fitness, we add the position to the
candidate position list 2, $PL_{2}$. Finally, if $PL_{1}$ is not empty, the
position with the smallest value of the increase of setup time in $PL_{1}$ is
selected to insert the order; otherwise, the position with the highest total
fitness in $PL_{2}$ is selected to insert the order. If both $PL_{1}$ and
$PL_{2}$ are empty, the candidate order is given up.

We select the position according to the above strategy because when $PL_{1}$
is not empty, the candidate order can be inserted without receiving any
penalty, which means the total fitness can be increased with the revenue of
the candidate order. In this case we select the position increasing the
minimum setup time. The rationale is that it is better to use the time more
for processing orders instead of setting up. If $PL_{1}$ is empty, some orders
will receive penalty. In this case we have to compute the fitness to find the
best insertion position.

When an order is inserted, the start times of all its succeeding orders are
updated until one whose start time does not change. The time slacks of all the
orders before the candidate order and the orders whose start time is changed
are also updated.

##  4 Experiments

The goal of the experiments is to understand the strengths and weaknesses of
the different algorithms for the OAS problem with sequence-dependent setup
times and time windows. In particular, for the new algorithm, Sparrow, also to
find out good parameter settings. For this purpose we start by running Sparrow
for a range of parameter settings on a standard benchmark set. Then we compare
Sparrow with state-of-the-art algorithms. Next we study how different
properties of the problem correlate with its difficulty. Finally we generate
new problem instances with more realistic and harder properties and compare
the performances of different algorithms on the harder cases.

###  4.1 Parameter settings for Sparrow

In this section, we aim to understand how some important parameters of Sparrow
influence its performance and answer the following questions: Is this
hybridization better than the two standalone algorithms; for instances with
different properties, is it better to have a larger population size or a
larger number of iterations?

The standard benchmark set used is that by Cesaret et al. [5], which is the
most common benchmark set used by many articles [5, 7, 8, 9, 10, 11, 12, 13,
14, 15, 16, 17]. This benchmark set has $n$, $\tau$ and $r$ as parameters,
where $n$ is the number of orders $n=25,50,100$, and $\tau$ and $R$ are the
tardiness factor and the due time range factor, having the values of 0.1, 0.3,
0.5, 0.7, and 0.9. The orders are generated by random values from a discrete
random distribution [1, 20] for processing time $t_{i}$ and revenue $r_{i}$,
similarly the range [1, 10] is used for the sequence-dependent setup times
$s_{ij}$. Release times $b_{i}$ of orders are from $[0,\tau\cdot t_{T}]$,
where $t_{T}=\sum_{i=1}^{n}t_{i}$. The due time for an order is calculated by
$d_{i}=b_{i}+s_{\max}+\max\\{v,t_{i}\\}$, where $s_{\max}$ is the largest
sequence-dependent setup time over any order, and $v$ is a random value
generated from $[t_{T}(1-\tau-R/2),t_{T}(1-\tau+R/2)]$. Finally the deadlines
and weights are calculated by $e_{i}=d_{i}+Rt_{i}$ and
$w_{i}=r_{i}/(e_{i}-d_{i})$. For each set of parameters, 10 instances are
generated.

Sparrow has a lot of parameters. In this section we focus on three parameters:
the size of population $p$, the maximum number of consecutive iterations of no
improvement and the maximum iteration, because these three parameters
influence the importance of the two components in the hybridization. When the
population size is small and the number of iterations is large, solutions are
improved by more ALNS operations, hence the algorithm performance relies more
on ALNS; when the population size is large and the number of iterations is
small, the algorithm explores more solutions in the space, hence the algorithm
performance relies more on BRKGA. We compare five sets of parameters, shown in
Table 1. We change multiple parameters simultaneously and set them as in Table
1 because the Sparrow algorithm with these sets of parameters have relatively
equal CPU time. We hope to see with equal CPU time, whether we should have
larger population or more iterations for the Sparrow algorithm. In Table 1,
Set 1 refers to the case of standard ALNS and Set 5 refers to the case of
standard BRKGA.

Table 1: Five sets of experiments with different parameters Parameter name | Set 1 | Set 2 | Set 3 | Set 4 | Set 5
---|---|---|---|---|---
Size of population $p$ | 1 | 10 | 20 | 50 | 1,000
Maximum iteration of no improvement |  200$n$ |  20$n$ |  10$n$ |  4$n$ | $n$
Maximum iteration | 1,000,000 | 100,000 | 50,000 | 20,000 | 2,000
Whether ALNS is used | Yes | Yes | Yes | Yes | No

Other parameters of Sparrow are set as follows: number of elite individuals
$p_{e}=0.5p$; number of mutation individuals $p_{m}=0.1p$; probability for a
gene coming from the elite parent $\rho_{e}=0.7$; the unit reward for a good
pair $f_{g}=2$; probability of keeping the good pair $p_{g}=0.95$; number of
orders to remove by ALNS is $0.4\cdot|S|$, where $|S|$ is the number of orders
in the current solution; weight update parameter $\lambda=0.5$; coefficient of
annealing $c_{a}=0.9975$; score increment according to the performance of
operators: $\sigma_{1}=30,\sigma_{2}=20,\sigma_{3}=10$; parameter for ALNS
improvement $p_{f}=0.9$. These parameters are set empirically through some
exploratory experiments. Although these parameters are not optimal for all the
instances, they provide relatively good solutions.

In this section, we compare the gaps of the results of Sparrow with the
different parameter settings to the upper bounds provided by Silva et al. [8],
because these upper bounds are tight and more suitable for analyzing the
performance of an algorithm. We received the detailed upper bounds from the
authors of [8].

Figure 2: The gap between the upper bound and Sparrow with different parameter
settings. In Figure 2 left, each point is the average of 10 runs of all
instances with the same number of orders in the standard benchmark set. In
Figure 2 middle and right, we notice that the upper bounds from [8] are
tighter for instances with 25 orders. Therefore, to better analyze the
influence of $\tau$ and $r$, we calculate the average of 10 runs of instances
with 25 orders and the same $\tau$ and $r$. Set 5 is quite literally “off the
charts”.

The gaps of the Sparrow algorithm are calculated according to the different
numbers of orders, $\tau$ and $R$ and shown in Figure 2. We can only observe
one point of results for Set 5 with the current scale, because results for Set
5 are significantly worse (e.g., 4.04% for order size 50 and 6.00% for order
size 100). From all of the above results we conclude that the performance of
the two standalone algorithms perform much worse than the hybrid algorithm,
which proves the effectiveness of this hybridization. Comparing these three
sub-figures, we can find that the Sparrow algorithm works better when the
problem size is smaller, and when $\tau$ and $R$ are larger. We can also
conclude that when the problem grows in size, and when $\tau$ and $R$ become
smaller, the problem becomes harder for the Sparrow algorithm.

Then we compare Sets 2–4 within each sub-figure. Regarding the number of
orders, Set 2 performs better when the problem size is larger, while Set 4
performs better when the problem size is smaller. The performance of Set 3 is
between the performances of Set 2 and Set 4. It shows that the ALNS component
is more suitable for larger instances, while the BRKGA component works better
for smaller instances. Regarding the values of $\tau$ and $R$, the pattern is
not very obvious. Set 4 tends to work best when $\tau$ and $R$ are larger.

As a summary, in this section we derive the following conclusions: (1) the
hybrid Sparrow algorithm outperforms the two standalone algorithms; (2) the
problem becomes harder for Sparrow when the problem grows in size and when
$\tau$ and $R$ are smaller; (3) When the problem size is small, it is better
to have a large population, while when the problem size is large, it is better
to have a large iteration time; (4) Sparrow with a large population tends to
work better when $\tau$ and $R$ are larger.

###  4.2 Comparison with state-of-the-art algorithms

In this section, we use the same benchmark set as mentioned in Section 4.1. We
compare Sparrow to TS [5], DRGA [11], GA [15], HH [15], LOS [15], ILS [8], ABC
[9], HSSGA [16], and EA/G-LS [16]. Note that the performance of MIP solved by
ILOG CPLEX has been tested by Cesaret et al. [5] and its performance is bad
for large instances with more than 25 orders. Therefore, we do not compare
Sparrow to CPLEX in this article.

The benchmark set has instances with the number of orders ranging from 25 to
100, and $\tau$ and $R$ ranging from 0.1 to 0.9. According to the conclusions
derived in Section 4.1, we select a moderate set of parameters: population
size: $p=20$; maximum number of consecutive iterations of no improvement:
10$n$; maximum iteration: 50,000. Other parameters are set as mentioned in
Section 4.1.

Sparrow is run on Intel Core i5 3.20GHz CPU with 8GB memory, using a single
core. For other methods, we present the results from the respective articles,
which were obtained using machines with Intel Core i5, i7 and Xeon CPU,
3.00–3.40GHz, 4–16GB memory. Runtime results from such different machines are
incomparable, even unmentioned details such as cache size can have a
significant effect. However, we still include the runtime results for order
size 100 in Table 2, to be able to draw some first conclusions about runtimes
anyway.

On average, all the methods except ILS have comparable performance in terms of
CPU time. ILS is slower than others. Regarding the solution quality, the above
articles reported the gaps between their methods and the upper bounds provided
by Cesaret et al. [5]. In order to compare with these methods directly, in
this section we also use the upper bounds by Cesaret et al. [5] to calculate
the gaps of Sparrow.

Table 2: The CPU time (s) for instances with 100 orders by different algorithms $\tau$ | R | TS | DRGA | LOS | ILS | ABC | HSSGA | EA/G-LS | Sparrow
---|---|---|---|---|---|---|---|---|---
0.10 | 0.10 | 16.76 | 15 | 11 | 24.9 | 3.98 | 17.91 | 13.72 | 10.55
| 0.30 | 17.26 | 15 | 11 | 25.3 | 8.22 | 16.68 | 13.76 | 11.22
| 0.50 | 10.87 | 15 | 11 | 21.9 | 7.61 | 17.07 | 12.82 | 7.88
| 0.70 | 6.21 | 15 | 11 | 13.9 | 6.25 | 15.08 | 11.06 | 1.38
| 0.90 | 3.53 | 15 | 11 | 9.6 | 9.08 | 14.73 | 10.02 | 0.48
0.30 | 0.10 | 22.37 | 15 | 11 | 38.4 | 4.89 | 16.13 | 13.53 | 10.83
| 0.30 | 20.10 | 15 | 11 | 32.4 | 5.29 | 19.70 | 14.33 | 10.75
| 0.50 | 16.77 | 15 | 11 | 33.7 | 4.88 | 21.00 | 13.31 | 13.34
| 0.70 | 9.48 | 15 | 11 | 28.3 | 6.16 | 16.60 | 14.04 | 9.16
| 0.90 | 7.58 | 15 | 11 | 25.1 | 8.59 | 18.33 | 12.10 | 6.75
0.50 | 0.10 | 25.96 | 15 | 12 | 51.9 | 5.27 | 19.30 | 12.24 | 11.05
| 0.30 | 28.87 | 15 | 12 | 57.9 | 6.94 | 20.96 | 12.87 | 12.21
| 0.50 | 20.56 | 15 | 12 | 52.5 | 5.86 | 21.52 | 13.75 | 15.05
| 0.70 | 15.57 | 15 | 12 | 42.7 | 6.57 | 17.27 | 11.79 | 15.49
| 0.90 | 12.15 | 15 | 12 | 46.0 | 6.76 | 18.66 | 13.72 | 16.89
0.70 | 0.10 | 33.60 | 15 | 13 | 63.9 | 6.04 | 23.40 | 11.75 | 16.46
| 0.30 | 26.62 | 15 | 12 | 73.9 | 6.25 | 24.90 | 12.79 | 17.98
| 0.50 | 22.30 | 15 | 12 | 72.6 | 6.77 | 19.89 | 12.79 | 18.86
| 0.70 | 26.36 | 16 | 12 | 77.5 | 6.78 | 24.24 | 14.33 | 20.53
| 0.90 | 17.84 | 16 | 12 | 78.4 | 7.42 | 21.90 | 15.45 | 18.78
0.90 | 0.10 | 29.46 | 16 | 12 | 80.6 | 13.63 | 19.59 | 10.65 | 13.92
| 0.30 | 26.32 | 16 | 12 | 79.1 | 9.82 | 19.64 | 11.75 | 13.75
| 0.50 | 21.51 | 16 | 12 | 81.1 | 6.46 | 19.06 | 11.62 | 15.48
| 0.70 | 22.70 | 16 | 12 | 91.5 | 7.52 | 17.61 | 14.30 | 16.69
| 0.90 | 17.48 | 16 | 12 | 92.0 | 8.61 | 17.92 | 11.04 | 17.38
Avg. |  | 19.13 | 15 | 11 | 51.8 | 7.03 | 19.16 | 12.78 | 12.91

Table 3: Gaps (%) of various algorithms on instances with 25 orders (multiple runs for each instance) 444For the gaps of instances with 25 orders reported by Silva et al. [8], we identify some mistakes because the gaps in their table are smaller than the gaps between their tight upper bounds and the upper bounds by Cesaret et al. [5]. Therefore we decide not to include ILS in this comparison. n=25 | TS |  | DRGA |  | GA |  | HH |  | LOS |  | Sparrow
---|---|---|---|---|---|---|---|---|---|---|---
$\tau$ | R | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max
0.10 | 0.10 | 1 | 4 | 6 |  | 2 | 3 | 4 |  | 1 | 2 | 3 |  | 3 | 5 | 8 |  | 1 | 2 | 3 |  | 0.72 | 1.82 | 2.69
| 0.30 | 2 | 3 | 6 |  | 1 | 2 | 6 |  | 1 | 2 | 5 |  | 2 | 4 | 9 |  | 0 | 2 | 5 |  | 0.68 | 1.53 | 3.19
| 0.50 | 1 | 2 | 4 |  | 1 | 1 | 3 |  | 0 | 1 | 2 |  | 1 | 4 | 7 |  | 0 | 1 | 3 |  | 0.00 | 0.71 | 1.60
| 0.70 | 0 | 1 | 4 |  | 0 | 1 | 3 |  | 0 | 0 | 2 |  | 0 | 2 | 5 |  | 0 | 0 | 2 |  | 0.00 | 0.33 | 1.27
| 0.90 | 0 | 1 | 2 |  | 0 | 1 | 2 |  | 0 | 0 | 2 |  | 0 | 2 | 5 |  | 0 | 0 | 2 |  | 0.00 | 0.34 | 2.08
0.30 | 0.10 | 2 | 4 | 5 |  | 2 | 3 | 5 |  | 1 | 3 | 4 |  | 3 | 7 | 10 |  | 1 | 3 | 4 |  | 0.89 | 2.31 | 4.19
| 0.30 | 3 | 5 | 7 |  | 2 | 3 | 5 |  | 1 | 3 | 4 |  | 4 | 7 | 10 |  | 2 | 3 | 5 |  | 1.11 | 2.94 | 5.06
| 0.50 | 2 | 3 | 6 |  | 2 | 2 | 3 |  | 0 | 2 | 3 |  | 3 | 4 | 9 |  | 0 | 2 | 3 |  | 0.86 | 1.65 | 3.49
| 0.70 | 1 | 2 | 6 |  | 1 | 2 | 5 |  | 0 | 1 | 5 |  | 2 | 4 | 10 |  | 0 | 1 | 5 |  | 0.00 | 1.69 | 4.66
| 0.90 | 0 | 2 | 4 |  | 0 | 1 | 3 |  | 0 | 1 | 2 |  | 0 | 4 | 7 |  | 0 | 1 | 2 |  | 0.00 | 1.06 | 2.79
0.50 | 0.10 | 3 | 6 | 7 |  | 2 | 4 | 7 |  | 1 | 4 | 6 |  | 4 | 8 | 11 |  | 1 | 4 | 5 |  | 1.68 | 3.87 | 6.14
| 0.30 | 3 | 5 | 9 |  | 2 | 5 | 8 |  | 2 | 4 | 7 |  | 4 | 8 | 13 |  | 1 | 4 | 7 |  | 1.79 | 3.99 | 7.16
| 0.50 | 2 | 5 | 8 |  | 1 | 5 | 6 |  | 1 | 4 | 6 |  | 5 | 8 | 11 |  | 1 | 4 | 6 |  | 0.97 | 4.32 | 6.31
| 0.70 | 2 | 6 | 11 |  | 2 | 4 | 7 |  | 0 | 4 | 7 |  | 2 | 7 | 11 |  | 0 | 4 | 7 |  | 0.63 | 4.26 | 7.29
| 0.90 | 1 | 4 | 7 |  | 1 | 3 | 7 |  | 1 | 3 | 7 |  | 3 | 6 | 9 |  | 1 | 3 | 6 |  | 0.85 | 3.10 | 7.00
0.70 | 0.10 | 3 | 9 | 18 |  | 1 | 8 | 16 |  | 0 | 7 | 14 |  | 6 | 11 | 19 |  | 0 | 7 | 15 |  | 0.92 | 7.46 | 15.81
| 0.30 | 7 | 10 | 14 |  | 5 | 9 | 13 |  | 5 | 8 | 12 |  | 10 | 12 | 16 |  | 5 | 8 | 12 |  | 5.34 | 8.43 | 12.39
| 0.50 | 7 | 12 | 15 |  | 6 | 10 | 14 |  | 5 | 10 | 14 |  | 10 | 14 | 18 |  | 5 | 10 | 14 |  | 5.41 | 10.11 | 14.02
| 0.70 | 2 | 8 | 14 |  | 2 | 7 | 12 |  | 1 | 6 | 12 |  | 1 | 9 | 14 |  | 1 | 6 | 12 |  | 1.69 | 6.80 | 12.08
| 0.90 | 3 | 10 | 15 |  | 1 | 8 | 14 |  | 0 | 8 | 13 |  | 2 | 11 | 15 |  | 0 | 8 | 13 |  | 0.65 | 8.21 | 13.63
0.90 | 0.10 | 0 | 1 | 6 |  | 0 | 1 | 5 |  | 0 | 1 | 5 |  | 0 | 1 | 6 |  | 0 | 1 | 5 |  | 0.00 | 0.49 | 4.92
| 0.30 | 0 | 1 | 1 |  | 0 | 1 | 1 |  | 0 | 0 | 0 |  | 0 | 2 | 7 |  | 0 | 0 | 0 |  | 0.00 | 0.00 | 0.01
| 0.50 | 0 | 4 | 12 |  | 0 | 2 | 12 |  | 0 | 2 | 12 |  | 1 | 5 | 18 |  | 0 | 2 | 12 |  | 0.00 | 2.56 | 12.30
| 0.70 | 1 | 8 | 25 |  | 1 | 7 | 21 |  | 0 | 6 | 21 |  | 0 | 9 | 22 |  | 0 | 6 | 21 |  | 0.00 | 6.64 | 20.99
| 0.90 | 1 | 7 | 22 |  | 1 | 6 | 20 |  | 0 | 6 | 19 |  | 0 | 7 | 21 |  | 0 | 6 | 19 |  | 0.00 | 6.02 | 19.16
Avg. |  | 2 | 5 | 9 |  | 1 | 3 | 8 |  | 0 | 3 | 7 |  | 2 | 6 | 11 |  | 0 | 3 | 7 |  | 0.97 | 3.63 | 7.61

Table 4: Gaps (%) of various algorithms on instances with 50 orders (multiple runs for each instance)666For the gaps of instances with 50 orders reported by Silva et al. [8], we identify some mistakes because the gaps in their table are smaller than the gaps between their tight upper bounds and the upper bounds by Cesaret et al. [5]. Therefore we decide not to include ILS in this comparison. n=50 | TS |  | DRGA |  | GA |  | HH |  | LOS |  | Sparrow
---|---|---|---|---|---|---|---|---|---|---|---
$\tau$ | R | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max
0.10 | 0.10 | 1 | 2 | 3 |  | 1 | 2 | 3 |  | 1 | 2 | 3 |  | 3 | 4 | 5 |  | 1 | 2 | 3 |  | 0.51 | 0.79 | 1.27
| 0.30 | 1 | 2 | 4 |  | 1 | 2 | 3 |  | 1 | 2 | 4 |  | 2 | 4 | 5 |  | 1 | 2 | 3 |  | 0.60 | 1.00 | 1.53
| 0.50 | 1 | 2 | 2 |  | 1 | 1 | 2 |  | 0 | 1 | 2 |  | 1 | 2 | 4 |  | 0 | 1 | 2 |  | 0.00 | 0.42 | 0.96
| 0.70 | 0 | 2 | 16 |  | 0 | 2 | 16 |  | 0 | 2 | 16 |  | 0 | 3 | 17 |  | 0 | 2 | 16 |  | 0.00 | 1.66 | 16.38
| 0.90 | 0 | 1 | 2 |  | 0 | 0 | 0 |  | 0 | 0 | 0 |  | 0 | 0 | 1 |  | 0 | 0 | 0 |  | 0.00 | 0.00 | 0.00
0.30 | 0.10 | 2 | 3 | 3 |  | 2 | 3 | 4 |  | 1 | 2 | 4 |  | 3 | 6 | 8 |  | 1 | 2 | 3 |  | 0.63 | 1.59 | 2.86
| 0.30 | 3 | 4 | 5 |  | 2 | 3 | 4 |  | 2 | 3 | 4 |  | 5 | 6 | 9 |  | 2 | 3 | 4 |  | 1.40 | 1.81 | 2.69
| 0.50 | 1 | 3 | 5 |  | 1 | 2 | 4 |  | 1 | 2 | 4 |  | 1 | 4 | 7 |  | 1 | 2 | 3 |  | 0.18 | 1.44 | 3.64
| 0.70 | 0 | 1 | 3 |  | 0 | 1 | 2 |  | 0 | 0 | 1 |  | 1 | 3 | 5 |  | 0 | 1 | 2 |  | 0.00 | 0.39 | 1.16
| 0.90 | 1 | 1 | 3 |  | 0 | 1 | 2 |  | 0 | 0 | 1 |  | 0 | 2 | 4 |  | 0 | 0 | 1 |  | 0.00 | 0.27 | 1.32
0.50 | 0.10 | 3 | 4 | 5 |  | 3 | 4 | 5 |  | 1 | 2 | 3 |  | 4 | 6 | 8 |  | 1 | 3 | 4 |  | 1.11 | 2.01 | 2.64
| 0.30 | 3 | 6 | 8 |  | 3 | 5 | 7 |  | 2 | 3 | 6 |  | 6 | 8 | 11 |  | 2 | 4 | 6 |  | 1.97 | 3.30 | 5.44
| 0.50 | 2 | 4 | 8 |  | 2 | 4 | 8 |  | 1 | 3 | 6 |  | 3 | 7 | 12 |  | 1 | 3 | 7 |  | 1.03 | 3.00 | 6.49
| 0.70 | 2 | 3 | 5 |  | 1 | 3 | 6 |  | 0 | 2 | 4 |  | 2 | 5 | 9 |  | 0 | 2 | 4 |  | 0.37 | 1.97 | 4.14
| 0.90 | 0 | 3 | 6 |  | 0 | 2 | 5 |  | 0 | 1 | 4 |  | 0 | 5 | 7 |  | 0 | 1 | 4 |  | -4.09 | 1.53 | 4.04
0.70 | 0.10 | 4 | 7 | 9 |  | 4 | 5 | 7 |  | 2 | 4 | 5 |  | 7 | 9 | 11 |  | 2 | 4 | 5 |  | 2.24 | 3.88 | 4.74
| 0.30 | 4 | 7 | 11 |  | 4 | 7 | 10 |  | 3 | 5 | 8 |  | 8 | 10 | 14 |  | 3 | 5 | 9 |  | 2.75 | 4.82 | 8.40
| 0.50 | 7 | 9 | 13 |  | 6 | 8 | 12 |  | 4 | 6 | 11 |  | 8 | 11 | 15 |  | 5 | 6 | 11 |  | 4.74 | 6.46 | 10.91
| 0.70 | 2 | 9 | 18 |  | 3 | 8 | 15 |  | 2 | 7 | 15 |  | 6 | 11 | 20 |  | 2 | 7 | 14 |  | 1.73 | 7.13 | 15.50
| 0.90 | 4 | 10 | 18 |  | 4 | 9 | 14 |  | 3 | 7 | 13 |  | 5 | 10 | 16 |  | 3 | 7 | 13 |  | 3.26 | 7.63 | 13.02
0.90 | 0.10 | 8 | 13 | 18 |  | 8 | 12 | 19 |  | 6 | 11 | 16 |  | 10 | 14 | 21 |  | 7 | 11 | 16 |  | 6.55 | 10.98 | 16.77
| 0.30 | 12 | 16 | 21 |  | 9 | 14 | 18 |  | 9 | 13 | 17 |  | 13 | 17 | 21 |  | 9 | 13 | 17 |  | 9.28 | 13.43 | 17.80
| 0.50 | 7 | 16 | 20 |  | 4 | 13 | 19 |  | 3 | 12 | 17 |  | 5 | 16 | 20 |  | 3 | 12 | 16 |  | 3.05 | 12.31 | 16.78
| 0.70 | 8 | 14 | 21 |  | 7 | 13 | 18 |  | 5 | 11 | 17 |  | 7 | 15 | 22 |  | 6 | 11 | 17 |  | 5.62 | 11.50 | 18.42
| 0.90 | 11 | 14 | 19 |  | 10 | 13 | 17 |  | 9 | 12 | 16 |  | 12 | 16 | 20 |  | 10 | 12 | 16 |  | 9.74 | 12.49 | 16.30
Avg. |  | 3 | 6 | 10 |  | 3 | 5 | 9 |  | 2 | 5 | 8 |  | 4 | 8 | 12 |  | 2 | 5 | 8 |  | 2.11 | 4.47 | 7.73

Table 5: Gaps (%) of various algorithms on instances with 100 orders (multiple runs for each instance) n=100 | TS |  | DRGA |  | GA |  | HH |  | LOS |  | ILS-Avg |  | Sparrow
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\tau$ | R | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max
0.10 | 0.10 | 1 | 2 | 3 |  | 1 | 1 | 2 |  | 1 | 2 | 3 |  | 2 | 3 | 5 |  | 2 | 2 | 3 |  | 0.74 | 0.95 | 1.35 |  | 0.39 | 0.57 | 0.80
| 0.30 | 2 | 2 | 3 |  | 1 | 1 | 2 |  | 2 | 2 | 3 |  | 1 | 3 | 4 |  | 1 | 2 | 3 |  | 0.44 | 0.74 | 1.09 |  | 0.34 | 0.61 | 0.88
| 0.50 | 1 | 1 | 3 |  | 1 | 1 | 1 |  | 1 | 1 | 2 |  | 1 | 1 | 2 |  | 1 | 1 | 2 |  | 0.20 | 0.37 | 0.58 |  | 0.00 | 0.13 | 0.28
| 0.70 | 0 | 1 | 1 |  | 0 | 1 | 1 |  | 0 | 0 | 0 |  | 0 | 0 | 2 |  | 0 | 0 | 1 |  | 0.00 | 0.04 | 0.12 |  | 0.00 | 0.00 | 0.00
| 0.90 | 0 | 1 | 1 |  | 0 | 0 | 0 |  | 0 | 0 | 0 |  | 0 | 0 | 0 |  | 0 | 0 | 0 |  | 0.00 | 0.01 | 0.10 |  | 0.00 | 0.00 | 0.00
0.30 | 0.10 | 1 | 3 | 4 |  | 2 | 3 | 4 |  | 2 | 3 | 4 |  | 4 | 6 | 7 |  | 2 | 2 | 3 |  | 1.00 | 1.40 | 1.82 |  | 0.53 | 0.99 | 1.44
| 0.30 | 2 | 3 | 5 |  | 1 | 3 | 4 |  | 1 | 2 | 4 |  | 2 | 5 | 7 |  | 1 | 3 | 4 |  | 0.73 | 1.38 | 2.67 |  | 0.57 | 1.24 | 2.49
| 0.50 | 1 | 2 | 4 |  | 2 | 2 | 3 |  | 1 | 2 | 3 |  | 3 | 4 | 6 |  | 1 | 2 | 3 |  | 0.73 | 1.17 | 1.65 |  | 0.65 | 1.07 | 1.75
| 0.70 | 1 | 2 | 3 |  | 1 | 1 | 1 |  | 0 | 1 | 2 |  | 1 | 2 | 4 |  | 0 | 1 | 2 |  | 0.27 | 0.44 | 0.74 |  | 0.00 | 0.30 | 0.79
| 0.90 | 1 | 1 | 2 |  | 0 | 1 | 1 |  | 0 | 0 | 1 |  | 0 | 1 | 3 |  | 0 | 0 | 1 |  | 0.00 | 0.25 | 0.73 |  | 0.00 | 0.11 | 0.42
0.50 | 0.10 | 2 | 4 | 5 |  | 3 | 5 | 7 |  | 3 | 4 | 6 |  | 7 | 8 | 11 |  | 2 | 4 | 5 |  | 1.46 | 2.26 | 3.11 |  | 1.07 | 1.79 | 2.71
| 0.30 | 3 | 4 | 6 |  | 4 | 4 | 6 |  | 3 | 4 | 5 |  | 6 | 7 | 9 |  | 2 | 3 | 5 |  | 1.72 | 2.32 | 3.08 |  | 1.49 | 2.16 | 2.63
| 0.50 | 3 | 4 | 5 |  | 3 | 4 | 6 |  | 2 | 4 | 5 |  | 5 | 7 | 10 |  | 2 | 3 | 4 |  | 1.58 | 2.40 | 3.36 |  | 1.31 | 2.33 | 3.35
| 0.70 | 2 | 3 | 4 |  | 1 | 3 | 4 |  | 0 | 2 | 3 |  | 2 | 5 | 7 |  | 0 | 2 | 3 |  | 0.49 | 1.61 | 2.80 |  | 0.35 | 1.49 | 2.38
| 0.90 | 1 | 2 | 5 |  | 1 | 2 | 4 |  | 0 | 1 | 3 |  | 2 | 3 | 6 |  | 0 | 1 | 4 |  | 0.39 | 1.16 | 2.76 |  | 0.19 | 0.92 | 2.40
0.70 | 0.10 | 3 | 5 | 6 |  | 4 | 6 | 8 |  | 4 | 5 | 6 |  | 7 | 9 | 11 |  | 3 | 4 | 7 |  | 2.28 | 3.13 | 3.77 |  | 1.69 | 2.47 | 3.21
| 0.30 | 4 | 7 | 11 |  | 4 | 6 | 9 |  | 3 | 5 | 8 |  | 6 | 9 | 13 |  | 2 | 5 | 7 |  | 1.89 | 3.86 | 5.82 |  | 1.35 | 3.66 | 5.80
| 0.50 | 4 | 6 | 13 |  | 4 | 7 | 15 |  | 3 | 6 | 12 |  | 6 | 10 | 18 |  | 2 | 5 | 12 |  | 2.63 | 4.25 | 8.69777For this value reported by Silva et al. [8], we find it smaller than the gaps between their tight upper bounds and the upper bounds by Cesaret et al. [5]. |  | 2.23 | 4.34 | 10.65
| 0.70 | 3 | 7 | 13 |  | 5 | 8 | 12 |  | 4 | 6 | 9 |  | 6 | 9 | 13 |  | 2 | 5 | 8 |  | 2.66 | 6.17 | 9.32 |  | 1.92 | 4.81 | 7.33
| 0.90 | 5 | 8 | 13 |  | 4 | 7 | 10 |  | 4 | 6 | 9 |  | 5 | 9 | 12 |  | 3 | 5 | 8 |  | 3.92 | 6.60 | 8.27 |  | 2.97 | 5.07 | 6.55
0.90 | 0.10 | 7 | 9 | 12 |  | 6 | 9 | 12 |  | 5 | 7 | 9 |  | 8 | 11 | 14 |  | 4 | 6 | 9 |  | 4.40 | 7.02 | 9.07 |  | 3.44 | 5.46 | 8.47
| 0.30 | 7 | 14 | 17 |  | 8 | 12 | 16 |  | 6 | 10 | 13 |  | 11 | 14 | 18 |  | 6 | 9 | 12 |  | 8.91 | 11.83 | 13.59 |  | 4.90 | 8.65 | 11.20
| 0.50 | 11 | 16 | 18 |  | 11 | 14 | 19 |  | 8 | 12 | 17 |  | 12 | 16 | 20 |  | 8 | 11 | 16 |  | 10.12 | 14.06 | 18.40 |  | 7.90 | 10.76 | 15.67
| 0.70 | 11 | 15 | 20 |  | 10 | 14 | 16 |  | 9 | 12 | 15 |  | 11 | 16 | 19 |  | 8 | 11 | 14 |  | 9.67 | 12.75 | 15.95 |  | 7.38 | 10.73 | 13.02
| 0.90 | 11 | 16 | 22 |  | 8 | 13 | 19 |  | 6 | 12 | 17 |  | 8 | 15 | 22 |  | 4 | 11 | 18 |  | 7.21 | 13.23 | 18.43 |  | 3.32 | 10.67 | 16.53
Avg. |  | 3 | 6 | 8 |  | 3 | 5 | 7 |  | 3 | 4 | 6 |  | 5 | 7 | 10 |  | 2 | 4 | 6 |  | 2.54 | 3.98 | 5.49 |  | 1.76 | 3.21 | 4.83

Table 6: Gaps (%) of various algorithms on instances with 25 orders (single run for each instance) n=25 | ABC |  | HSSGA |  | EA/G-LS |  | Sparrow-Average |  | Sparrow-Best |  | Sparrow-Worst
---|---|---|---|---|---|---|---|---|---|---|---
$\tau$ | R | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max
0.10 | 0.10 | 1.45 | 2.70 | 3.85 |  | 1.09 | 2.08 | 3.16 |  | 1.09 | 2.16 | 3.16 |  | 0.72 | 1.82 | 2.69 |  | 0.72 | 1.67 | 2.69 |  | 0.72 | 2.07 | 3.15
| 0.30 | 0.69 | 2.18 | 5.78 |  | 0.69 | 1.66 | 3.20 |  | 0.69 | 1.58 | 3.20 |  | 0.68 | 1.53 | 3.19 |  | 0.00 | 1.32 | 2.72 |  | 0.68 | 1.61 | 3.40
| 0.50 | 0.00 | 1.38 | 2.45 |  | 0.00 | 0.90 | 1.90 |  | 0.00 | 0.91 | 1.77 |  | 0.00 | 0.71 | 1.60 |  | 0.00 | 0.64 | 1.41 |  | 0.00 | 0.84 | 1.84
| 0.70 | 0.00 | 0.63 | 2.68 |  | 0.00 | 0.39 | 1.67 |  | 0.00 | 0.39 | 1.67 |  | 0.00 | 0.33 | 1.27 |  | 0.00 | 0.18 | 1.00 |  | 0.00 | 0.38 | 1.67
| 0.90 | 0.00 | 0.35 | 2.09 |  | 0.00 | 0.35 | 2.09 |  | 0.00 | 0.35 | 2.09 |  | 0.00 | 0.34 | 2.08 |  | 0.00 | 0.26 | 2.03 |  | 0.00 | 0.37 | 2.09
0.30 | 0.10 | 1.21 | 3.11 | 5.24 |  | 1.21 | 2.48 | 4.55 |  | 1.21 | 2.44 | 4.55 |  | 0.89 | 2.31 | 4.19 |  | 0.68 | 2.17 | 3.84 |  | 1.71 | 2.55 | 4.54
| 0.30 | 1.12 | 3.37 | 6.04 |  | 1.12 | 3.12 | 4.62 |  | 2.15 | 3.46 | 6.04 |  | 1.11 | 2.94 | 5.06 |  | 1.11 | 2.55 | 4.33 |  | 1.11 | 3.18 | 5.28
| 0.50 | 1.12 | 2.40 | 5.24 |  | 1.12 | 1.52 | 3.50 |  | 2.15 | 1.85 | 3.50 |  | 0.86 | 1.65 | 3.49 |  | 0.66 | 1.48 | 3.49 |  | 0.86 | 1.87 | 3.49
| 0.70 | 0.88 | 1.97 | 5.32 |  | 0.00 | 1.61 | 4.61 |  | 0.00 | 1.90 | 5.32 |  | 0.00 | 1.69 | 4.66 |  | 0.00 | 1.32 | 4.10 |  | 0.00 | 1.94 | 5.31
| 0.90 | 0.00 | 1.27 | 3.38 |  | 0.00 | 1.05 | 2.82 |  | 0.00 | 1.10 | 2.82 |  | 0.00 | 1.06 | 2.79 |  | 0.00 | 0.84 | 2.73 |  | 0.00 | 1.23 | 2.82
0.50 | 0.10 | 2.80 | 4.88 | 6.76 |  | 1.68 | 4.17 | 6.76 |  | 1.68 | 4.11 | 6.76 |  | 1.68 | 3.87 | 6.14 |  | 1.60 | 3.59 | 5.61 |  | 1.68 | 4.38 | 6.75
| 0.30 | 2.85 | 4.49 | 7.29 |  | 1.82 | 4.22 | 7.29 |  | 1.82 | 4.12 | 7.29 |  | 1.79 | 3.99 | 7.16 |  | 1.68 | 3.85 | 7.08 |  | 1.81 | 4.25 | 7.29
| 0.50 | 1.94 | 4.48 | 6.02 |  | 0.97 | 4.28 | 6.08 |  | 0.97 | 4.25 | 6.08 |  | 0.97 | 4.32 | 6.31 |  | 0.97 | 4.08 | 6.01 |  | 0.97 | 4.67 | 7.14
| 0.70 | 0.64 | 4.20 | 7.17 |  | 0.64 | 4.16 | 7.17 |  | 0.64 | 4.19 | 7.17 |  | 0.63 | 4.26 | 7.29 |  | 0.63 | 4.16 | 7.17 |  | 0.63 | 4.74 | 8.36
| 0.90 | 1.03 | 3.37 | 7.00 |  | 1.03 | 3.05 | 7.00 |  | 1.03 | 3.13 | 6.79 |  | 0.85 | 3.10 | 7.00 |  | 0.68 | 2.97 | 7.00 |  | 1.02 | 3.42 | 7.00
0.70 | 0.10 | 0.93 | 7.72 | 15.88 |  | 0.93 | 7.43 | 14.86 |  | 0.93 | 7.53 | 16.22 |  | 0.92 | 7.46 | 15.81 |  | 0.92 | 7.35 | 14.86 |  | 0.92 | 7.56 | 16.55
| 0.30 | 5.05 | 8.64 | 12.40 |  | 5.78 | 8.49 | 12.40 |  | 5.78 | 8.53 | 12.50 |  | 5.34 | 8.43 | 12.39 |  | 5.05 | 8.33 | 12.39 |  | 5.77 | 8.61 | 13.30
| 0.50 | 5.37 | 10.45 | 14.03 |  | 5.37 | 10.05 | 14.03 |  | 5.37 | 10.17 | 14.03 |  | 5.41 | 10.11 | 14.02 |  | 5.37 | 10.01 | 14.02 |  | 5.78 | 10.55 | 14.14
| 0.70 | 1.69 | 6.90 | 12.08 |  | 1.58 | 6.56 | 12.08 |  | 1.58 | 6.47 | 12.08 |  | 1.69 | 6.80 | 12.08 |  | 1.69 | 6.69 | 12.08 |  | 1.69 | 7.18 | 12.08
| 0.90 | 0.01 | 8.12 | 13.64 |  | 0.01 | 8.12 | 13.64 |  | 0.01 | 8.27 | 13.64 |  | 0.65 | 8.21 | 13.63 |  | 0.00 | 8.06 | 13.63 |  | 1.19 | 8.51 | 13.63
0.90 | 0.10 | 0.00 | 0.59 | 4.93 |  | 0.00 | 0.49 | 4.93 |  | 0.00 | 0.49 | 4.93 |  | 0.00 | 0.49 | 4.92 |  | 0.00 | 0.49 | 4.92 |  | 0.00 | 0.49 | 4.92
| 0.30 | 0.00 | 0.16 | 1.48 |  | 0.00 | 0.00 | 0.01 |  | 0.00 | 0.00 | 0.01 |  | 0.00 | 0.00 | 0.01 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.01 | 0.10
| 0.50 | 0.00 | 2.58 | 12.30 |  | 0.00 | 2.49 | 12.30 |  | 0.00 | 2.49 | 12.30 |  | 0.00 | 2.56 | 12.30 |  | 0.00 | 2.49 | 12.30 |  | 0.00 | 2.72 | 12.30
| 0.70 | 0.00 | 6.81 | 20.99 |  | 0.00 | 6.67 | 20.99 |  | 0.00 | 6.67 | 20.99 |  | 0.00 | 6.64 | 20.99 |  | 0.00 | 6.61 | 20.99 |  | 0.00 | 6.75 | 20.99
| 0.90 | 0.00 | 6.09 | 19.33 |  | 0.00 | 5.99 | 19.10 |  | 0.00 | 5.99 | 19.10 |  | 0.00 | 6.02 | 19.16 |  | 0.00 | 5.99 | 19.09 |  | 0.00 | 6.05 | 19.33
Avg. |  | 1.15 | 3.95 | 8.13 |  | 1.00 | 3.65 | 7.63 |  | 1.08 | 3.70 | 7.76 |  | 0.97 | 3.63 | 7.61 |  | 0.87 | 3.48 | 7.42 |  | 1.06 | 3.84 | 7.90

Table 7: Gaps (%) of various algorithms on instances with 50 orders (single run for each instance) n=50 | ABC |  | HSSGA |  | EA/G-LS |  | Sparrow-Average |  | Sparrow-Best |  | Sparrow-Worst
---|---|---|---|---|---|---|---|---|---|---|---
$\tau$ | R | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max
0.10 | 0.10 | 1.20 | 1.89 | 2.81 |  | 0.51 | 1.18 | 1.69 |  | 0.51 | 1.08 | 1.47 |  | 0.51 | 0.79 | 1.27 |  | 0.37 | 0.64 | 0.99 |  | 0.51 | 0.94 | 1.59
| 0.30 | 1.06 | 1.77 | 2.33 |  | 0.71 | 1.12 | 1.57 |  | 0.71 | 1.10 | 1.57 |  | 0.60 | 1.00 | 1.53 |  | 0.45 | 0.90 | 1.53 |  | 0.70 | 1.08 | 1.53
| 0.50 | 0.34 | 0.96 | 2.03 |  | 0.00 | 0.43 | 0.84 |  | 0.00 | 0.45 | 0.95 |  | 0.00 | 0.42 | 0.96 |  | 0.00 | 0.33 | 0.83 |  | 0.00 | 0.56 | 1.25
| 0.70 | 0.00 | 1.90 | 16.39 |  | 0.00 | 1.73 | 16.39 |  | 0.00 | 1.66 | 16.39 |  | 0.00 | 1.66 | 16.38 |  | 0.00 | 1.63 | 16.38 |  | 0.00 | 1.78 | 16.38
| 0.90 | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00
0.30 | 0.10 | 1.63 | 2.59 | 3.77 |  | 1.02 | 1.80 | 2.79 |  | 1.22 | 1.93 | 2.86 |  | 0.63 | 1.59 | 2.86 |  | 0.60 | 1.30 | 2.48 |  | 0.81 | 1.85 | 3.24
| 0.30 | 1.94 | 2.98 | 4.49 |  | 1.55 | 2.06 | 2.66 |  | 1.54 | 2.18 | 3.05 |  | 1.40 | 1.81 | 2.69 |  | 1.15 | 1.63 | 2.51 |  | 1.54 | 2.13 | 3.23
| 0.50 | 1.94 | 1.88 | 3.88 |  | 1.55 | 1.51 | 3.88 |  | 1.54 | 1.53 | 3.68 |  | 0.18 | 1.44 | 3.64 |  | 0.00 | 1.23 | 3.10 |  | 0.37 | 1.63 | 4.26
| 0.70 | 0.00 | 0.75 | 1.56 |  | 0.00 | 0.39 | 1.03 |  | 0.00 | 0.35 | 1.04 |  | 0.00 | 0.39 | 1.16 |  | 0.00 | 0.24 | 1.03 |  | 0.00 | 0.66 | 1.55
| 0.90 | 0.00 | 0.50 | 1.83 |  | 0.00 | 0.29 | 1.21 |  | 0.00 | 0.23 | 1.02 |  | 0.00 | 0.27 | 1.32 |  | 0.00 | 0.16 | 1.01 |  | 0.00 | 0.35 | 1.62
0.50 | 0.10 | 1.71 | 3.07 | 4.17 |  | 1.11 | 2.20 | 3.20 |  | 1.11 | 2.23 | 3.38 |  | 1.11 | 2.01 | 2.64 |  | 0.76 | 1.78 | 2.43 |  | 1.11 | 2.15 | 3.05
| 0.30 | 3.08 | 4.45 | 6.11 |  | 2.26 | 3.43 | 5.15 |  | 2.26 | 3.53 | 5.73 |  | 1.97 | 3.30 | 5.44 |  | 1.64 | 3.01 | 5.15 |  | 2.25 | 3.78 | 5.72
| 0.50 | 2.07 | 3.78 | 6.82 |  | 1.03 | 3.04 | 6.33 |  | 1.03 | 3.17 | 7.14 |  | 1.03 | 3.00 | 6.49 |  | 0.83 | 2.77 | 6.16 |  | 1.03 | 3.39 | 7.14
| 0.70 | 0.76 | 2.28 | 4.24 |  | 0.36 | 2.00 | 3.87 |  | 0.38 | 2.03 | 4.24 |  | 0.37 | 1.97 | 4.14 |  | 0.36 | 1.67 | 3.86 |  | 0.37 | 2.22 | 4.41
| 0.90 | 3.61 | 1.71 | 4.04 |  | 0.00 | 1.54 | 4.31 |  | -4.02 | 1.57 | 4.04 |  | -4.09 | 1.53 | 4.04 |  | -4.41 | 1.17 | 4.04 |  | -4.01 | 1.91 | 4.04
0.70 | 0.10 | 3.16 | 4.57 | 5.79 |  | 2.42 | 4.17 | 5.20 |  | 2.42 | 4.18 | 5.39 |  | 2.24 | 3.88 | 4.74 |  | 1.85 | 3.58 | 4.45 |  | 2.41 | 4.13 | 5.19
| 0.30 | 3.51 | 5.74 | 9.36 |  | 3.01 | 5.02 | 8.30 |  | 3.17 | 5.05 | 8.30 |  | 2.75 | 4.82 | 8.40 |  | 2.47 | 4.46 | 8.12 |  | 3.00 | 5.12 | 9.18
| 0.50 | 5.30 | 7.09 | 11.39 |  | 5.08 | 6.71 | 11.03 |  | 5.17 | 6.70 | 11.03 |  | 4.74 | 6.46 | 10.91 |  | 4.42 | 6.10 | 10.32 |  | 5.08 | 6.88 | 11.28
| 0.70 | 1.89 | 7.56 | 15.26 |  | 1.72 | 7.18 | 15.38 |  | 1.37 | 7.09 | 14.31 |  | 1.73 | 7.13 | 15.50 |  | 1.37 | 6.69 | 15.38 |  | 2.40 | 7.63 | 15.81
| 0.90 | 3.69 | 8.02 | 13.67 |  | 2.91 | 7.69 | 13.38 |  | 3.30 | 7.62 | 13.00 |  | 3.26 | 7.63 | 13.02 |  | 2.91 | 7.28 | 13.00 |  | 3.68 | 7.95 | 13.10
0.90 | 0.10 | 7.30 | 11.33 | 16.77 |  | 6.55 | 10.97 | 16.77 |  | 7.30 | 11.15 | 16.77 |  | 6.55 | 10.98 | 16.77 |  | 6.55 | 10.87 | 16.77 |  | 6.55 | 11.23 | 16.77
| 0.30 | 9.28 | 13.77 | 17.80 |  | 9.28 | 13.49 | 17.60 |  | 9.28 | 13.47 | 17.40 |  | 9.28 | 13.43 | 17.80 |  | 9.28 | 13.27 | 17.60 |  | 9.28 | 13.57 | 18.00
| 0.50 | 3.28 | 12.77 | 17.29 |  | 3.28 | 12.33 | 16.88 |  | 3.46 | 12.45 | 16.73 |  | 3.05 | 12.31 | 16.78 |  | 2.62 | 12.16 | 16.51 |  | 3.64 | 12.67 | 17.65
| 0.70 | 5.81 | 11.53 | 17.85 |  | 5.62 | 11.48 | 17.85 |  | 5.62 | 11.39 | 17.85 |  | 5.62 | 11.50 | 18.42 |  | 5.62 | 11.26 | 17.84 |  | 5.62 | 11.74 | 19.03
| 0.90 | 10.02 | 12.38 | 16.27 |  | 9.57 | 12.37 | 15.92 |  | 9.58 | 12.30 | 16.09 |  | 9.74 | 12.49 | 16.30 |  | 9.40 | 12.22 | 16.10 |  | 10.01 | 12.81 | 16.46
Avg. |  | 2.90 | 5.01 | 8.24 |  | 2.38 | 4.57 | 7.73 |  | 2.28 | 4.58 | 7.74 |  | 2.11 | 4.47 | 7.73 |  | 1.93 | 4.25 | 7.50 |  | 2.25 | 4.73 | 8.06

Table 8: Gaps (%) of various algorithms on instances with 100 orders (single run for each instance) n=100 | ABC |  | HSSGA |  | EA/G-LS |  | Sparrow-Average |  | Sparrow-Best |  | Sparrow-Worst
---|---|---|---|---|---|---|---|---|---|---|---
$\tau$ | R | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max |  | Min | Avg | Max
0.10 | 0.10 | 1.11 | 1.75 | 2.21 |  | 0.40 | 0.77 | 1.32 |  | 0.72 | 0.94 | 1.22 |  | 0.39 | 0.57 | 0.80 |  | 0.19 | 0.46 | 0.65 |  | 0.54 | 0.69 | 0.85
| 0.30 | 0.90 | 1.35 | 1.71 |  | 0.45 | 0.71 | 0.98 |  | 0.44 | 0.74 | 1.06 |  | 0.34 | 0.61 | 0.88 |  | 0.18 | 0.50 | 0.81 |  | 0.45 | 0.75 | 1.01
| 0.50 | 0.36 | 0.70 | 1.23 |  | 0.00 | 0.19 | 0.38 |  | 0.00 | 0.20 | 0.37 |  | 0.00 | 0.13 | 0.28 |  | 0.00 | 0.07 | 0.18 |  | 0.00 | 0.20 | 0.37
| 0.70 | 0.00 | 0.09 | 0.35 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00
| 0.90 | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00 |  | 0.00 | 0.00 | 0.00
0.30 | 0.10 | 1.27 | 2.11 | 2.71 |  | 0.50 | 1.18 | 1.71 |  | 0.69 | 1.25 | 1.71 |  | 0.53 | 0.99 | 1.44 |  | 0.39 | 0.83 | 1.35 |  | 0.58 | 1.09 | 1.53
| 0.30 | 1.40 | 2.12 | 3.97 |  | 0.66 | 1.27 | 2.64 |  | 0.66 | 1.41 | 2.64 |  | 0.57 | 1.24 | 2.49 |  | 0.56 | 1.06 | 2.23 |  | 0.74 | 1.38 | 2.64
| 0.50 | 1.40 | 1.67 | 2.45 |  | 0.66 | 1.07 | 1.52 |  | 0.66 | 1.11 | 1.69 |  | 0.65 | 1.07 | 1.75 |  | 0.45 | 0.91 | 1.52 |  | 0.81 | 1.22 | 2.03
| 0.70 | 0.00 | 0.63 | 1.16 |  | 0.00 | 0.35 | 0.85 |  | 0.00 | 0.24 | 0.63 |  | 0.00 | 0.30 | 0.79 |  | 0.00 | 0.17 | 0.62 |  | 0.00 | 0.38 | 0.96
| 0.90 | 0.00 | 0.26 | 0.82 |  | 0.00 | 0.10 | 0.56 |  | 0.00 | 0.14 | 0.47 |  | 0.00 | 0.11 | 0.42 |  | 0.00 | 0.05 | 0.28 |  | 0.00 | 0.20 | 0.64
0.50 | 0.10 | 2.50 | 3.37 | 4.33 |  | 1.22 | 2.09 | 2.99 |  | 1.69 | 2.31 | 3.27 |  | 1.07 | 1.79 | 2.71 |  | 0.81 | 1.57 | 2.47 |  | 1.26 | 2.03 | 2.91
| 0.30 | 2.46 | 3.01 | 4.00 |  | 1.54 | 2.29 | 2.95 |  | 1.67 | 2.43 | 2.96 |  | 1.49 | 2.16 | 2.63 |  | 1.14 | 1.94 | 2.51 |  | 1.53 | 2.45 | 3.15
| 0.50 | 2.26 | 3.13 | 4.21 |  | 1.22 | 2.36 | 3.35 |  | 1.48 | 2.51 | 3.61 |  | 1.31 | 2.33 | 3.35 |  | 1.13 | 2.12 | 3.17 |  | 1.39 | 2.66 | 3.69
| 0.70 | 0.77 | 1.82 | 2.99 |  | 0.51 | 1.49 | 2.33 |  | 0.51 | 1.32 | 2.24 |  | 0.35 | 1.49 | 2.38 |  | 0.34 | 1.26 | 2.06 |  | 0.51 | 1.70 | 2.78
| 0.90 | 0.53 | 1.42 | 3.13 |  | 0.18 | 1.04 | 2.15 |  | 0.18 | 0.90 | 2.15 |  | 0.19 | 0.92 | 2.40 |  | 0.00 | 0.73 | 2.23 |  | 0.35 | 1.11 | 2.77
0.70 | 0.10 | 3.20 | 3.99 | 4.84 |  | 2.09 | 2.84 | 3.53 |  | 2.27 | 2.98 | 3.82 |  | 1.69 | 2.47 | 3.21 |  | 1.45 | 2.25 | 3.13 |  | 1.90 | 2.73 | 3.52
| 0.30 | 2.37 | 4.72 | 7.16 |  | 1.71 | 3.88 | 6.07 |  | 1.67 | 4.09 | 6.26 |  | 1.35 | 3.66 | 5.80 |  | 1.14 | 3.35 | 5.43 |  | 1.66 | 3.95 | 6.07
| 0.50 | 3.27 | 5.27 | 11.94 |  | 2.25 | 4.62 | 10.95 |  | 2.62 | 4.69 | 10.95 |  | 2.23 | 4.34 | 10.65 |  | 1.97 | 4.06 | 10.44 |  | 2.44 | 4.60 | 11.02
| 0.70 | 2.77 | 5.37 | 7.37 |  | 2.18 | 5.16 | 7.78 |  | 2.77 | 5.39 | 7.65 |  | 1.92 | 4.81 | 7.33 |  | 1.76 | 4.46 | 7.00 |  | 2.35 | 5.19 | 7.74
| 0.90 | 3.57 | 5.90 | 8.33 |  | 3.73 | 5.48 | 7.49 |  | 3.15 | 5.34 | 6.88 |  | 2.97 | 5.07 | 6.55 |  | 2.75 | 4.72 | 6.16 |  | 3.26 | 5.49 | 6.95
0.90 | 0.10 | 4.70 | 6.62 | 9.44 |  | 4.57 | 6.27 | 9.06 |  | 4.75 | 6.45 | 9.34 |  | 3.44 | 5.46 | 8.47 |  | 3.26 | 5.21 | 8.28 |  | 3.63 | 5.72 | 8.76
| 0.30 | 5.39 | 9.40 | 11.86 |  | 5.11 | 9.03 | 11.25 |  | 5.39 | 9.09 | 12.35 |  | 4.90 | 8.65 | 11.20 |  | 4.60 | 8.40 | 10.96 |  | 5.29 | 8.98 | 11.82
| 0.50 | 8.82 | 11.88 | 17.25 |  | 8.60 | 11.26 | 16.29 |  | 8.28 | 11.20 | 15.84 |  | 7.90 | 10.76 | 15.67 |  | 7.52 | 10.47 | 15.52 |  | 8.32 | 11.01 | 15.86
| 0.70 | 7.96 | 11.19 | 12.85 |  | 8.07 | 11.23 | 13.07 |  | 8.05 | 11.07 | 13.06 |  | 7.38 | 10.73 | 13.02 |  | 7.10 | 10.41 | 12.54 |  | 7.71 | 11.14 | 13.43
| 0.90 | 4.11 | 11.31 | 16.83 |  | 3.57 | 11.07 | 16.60 |  | 4.07 | 11.02 | 16.73 |  | 3.32 | 10.67 | 16.53 |  | 3.17 | 10.41 | 16.17 |  | 3.47 | 10.92 | 16.93
Avg. |  | 2.44 | 3.96 | 5.73 |  | 1.97 | 3.43 | 5.03 |  | 2.07 | 3.47 | 5.08 |  | 1.76 | 3.21 | 4.83 |  | 1.60 | 3.02 | 4.63 |  | 1.93 | 3.42 | 5.10

Sparrow, TS, DRGA, GA, HH, LOS and ILS are run ten times on each of the
instances. The average gaps of the ten runs for each instance are calculated
first. Then for each group of instances with the same parameters, we calculate
the minimum, average and maximum gaps of the ten instances in this group. The
results of instances with 25–100 orders are shown in Tables 3–5. The other
three algorithms, ABC, HSSGA and EA/G-LS are run only once for each instance.
In order to compare with these three algorithms, we calculate the minimum,
average and maximum results of the best, the average, and the worst of the ten
runs (denoted as Sparrow-Best, Sparrow-Average and Sparrow-Worst respectively)
as a reference of the performance of our algorithm. The results are shown in
Tables 6–8. Note that in Tables 6–8, we only highlight the best results among
ABC, HSSGA, EA/G-LS and Sparrow-Average.

In Tables 3–5, TS, DRGA, GA, HH and LOS only reported rounded-down integer
values. But it is still obvious that Sparrow produces the best solutions on
nearly all the instances. In Tables 6–8, the average results of Sparrow are
better than those of ABC, HSSGA and EA/G-LS on most of the instances. Even the
worst results of the ten runs of Sparrow are better than those of ABC, HSSGA
and EA/G-LS on around half of the instances. Therefore we can conclude that on
average Sparrow produces the best solutions among all the algorithms.

Then we study how the performance gaps between Sparrow and other algorithms
change with the different parameters of the instances. We evaluate the
performance gap between an algorithm $A$ and Sparrow by the following formula:

$GapToSparrow_{A}=\frac{Gap_{A}-Gap_{Sparrow}}{Gap_{Sparrow}}$ (6)

where $Gap_{A}$ is the gap between the algorithm $A$ and the upper bound and
$Gap_{Sparrow}$ is the gap between Sparrow and the upper bound.

Figure 3: The gaps of different algorithms to Sparrow.999We do not plot the
results of ILS in this figure because we find that some gaps reported by Silva
et al. [8] are smaller than the gaps between their tight upper bounds and the
upper bounds by Cesaret et al. [5].

The performance gaps of different algorithms are calculated according to the
different numbers of orders, $\tau$ and $R$ and shown in Figure 9. Note that
in Figure 9 some performance gaps of LOS are smaller than 0, because LOS only
reported rounded-down integer values. In general, from Figure 9 we can find
that gaps between the performance of Sparrow and those of other algorithms
tend to grow when there are more orders, and when $\tau$ and $R$ are smaller.
These are the cases found to be hard for Sparrow, but these cases are even
harder for the other algorithms. Among other algorithms, HSSGA and EA/G-LS
have the steadiest performance for instances with different parameters. Like
Sparrow, HSSGA and EA/G-LS also work better than others when there are more
orders, and when $\tau$ and $R$ are smaller. On the contrary, GA and LOS work
better when there are fewer orders, and when $\tau$ and $R$ are larger.

###  4.3 Problem properties

In this section, we aim to understand the problem further by studying how
different properties (other than $n$, $\tau$ and $R$) of the problem correlate
with its difficulty. To achieve this, we evaluate the performance of Sparrow
on instances with different properties, because according to the comparison
with other algorithms above, we find that Sparrow is the new state of the art
for this problem. In this section, we use the same benchmark as in Section 4.1
and 4.2, and the tight upper bounds provided by Silva et al. [8]. As in Figure
2, we select the instances with 25 orders in order to decrease the influence
from the upper bounds, because the upper bounds for instances with 25 orders
are tighter than those for instances with 50 and 100 orders.

In this section, we calculate the following properties of each problem
instance: standard deviation of setup times; standard deviation of window
length; standard deviation of revenue of orders; the length of horizon;
average window length; congestion ratio (this value is calculated by adding up
the processing time and the smallest setup time of each order, divided by the
horizon, to evaluate how congested the instance is); standard deviation of
order processing time; average conflict ratio (the conflict ratio of an order
is calculated by adding up the overlap time between its time window and the
time windows of all other orders, divided by the length of its time window);
standard deviation of conflict ratio; setup window ratio (this value is the
average setup time divided by the average length of window); process window
ratio (this value is the average processing time divided by the average length
of window); correlation coefficient between processing time and revenue of
orders.

In Figure 4 we show how the performance of Sparrow changes with six
properties. We do not plot the performance with other properties because the
correlations are weak, which shows that Sparrow adapts it well for these
properties. According to Figure 4, the problem becomes harder for Sparrow
when: (1) the average conflict ratio is larger; (2) the average window length
is larger. This is consistent with the observation in Figure 2, because when
$\tau$ is smaller, the average window length is larger; (3) the congestion
ratio is larger; (4) the process window ratio is smaller. This case is harder
because the space where an order can be shifted within a window is larger. The
solution space becomes larger; (5) the setup window ratio is smaller; (6) the
correlation coefficient between processing time and revenue is larger. The
reason is that when the correlation is larger, the difference among order
values is smaller, therefore it is more difficult to select orders.

Figure 4: The correlation of the performance of Sparrow and different
properties of the problem. Each point is the average of 10 runs of each
instance with 25 orders.

According to the observations above, it can be concluded that the following
properties make the problem harder:

  1. 1.

Congestion-related properties: larger congestion ratio; larger conflict ratio.

  2. 2.

Order-related properties: larger correlation between processing time and
revenue of orders.

  3. 3.

Window-related properties: longer time windows; smaller process/setup window
ratio.

It is interesting to see that each of the three hard cases corresponds to a
real-life situation. The satellite scheduling problem usually has the problem
of the scheduling horizon being heavily contested; many real-life situations
such as commerce cause longer orders to be more expensive, where the
processing time and revenue of an order are more correlated; cases such as the
travelling repairman problem involve mostly short processing times, while
having relatively longer time windows.

Although the benchmark set by Cesaret et al. [5] is known to contain difficult
instances, the three real-life and difficult scenarios above do not correspond
to the instances generated with this methodology. Therefore in the next
section, we generate three new sets of instances, each corresponding to one of
the scenarios, to compare the performances of different algorithms.

###  4.4 The performances of different algorithms on new instances

In this section, we describe an evaluation of the state-of-the-art algorithms
on three new sets of instances: the _satellite scheduling_ set is more
congested by setting the parameters as follows: $n=\\{100,150,200,250,300\\}$,
$\tau=0.1$, and $R=0.1$. The _commerce_ set has a more correlated processing
time and revenue by generating a random value $\gamma$ in [1,20] and
calculating the final revenue of order $o_{i}$ by $((1-q)\gamma+2q\cdot
t_{i})$, and setting $q=\\{0.0,0.2,0.4,0.6,0.8,1.0\\}$, $n=100$, $\tau=0.1$,
and $R=0.1$. Finally, the _travelling repairman_ set has long time windows
whereas the processing times are short, by multiplying $t_{T}$ with a constant
$c=\\{1.0,1.2,1.4,1.6,1.8,2.0\\}$, and $n=100$, $\tau=0.1$, and $R=0.1$. Since
multiplying $t_{T}$ by $c$ makes the instance less congested, we generate
$n\cdot c$ orders to the keep the congestion ratio at a similar level. For
each set we generate ten instances with the same parameters. Therefore we have
$5\cdot 10+6\cdot 10+6\cdot 10=170$ new instances in total.

Besides Sparrow, we include two other algorithms which correspond to the state
of the art: ILS by Silva et al. [8] and HSSGA by Chaurasia and Singh [16]. As
obtaining the original implementations of these algorithms proved to be
infeasible, we reimplemented the algorithms according to their descriptions
with varying degrees of success. For our implementation of ILS the gaps are
too dissimilar to the gaps reported for the benchmark instances provided by
Cesaret et al. [5] to argue reproduction of their algorithm. Therefore we
refer to our implementation as ILS*. For HSSGA using proposed parameters our
gap was found to be at most 1% larger than the values reported by Chaurasia
and Singh [16], with a similar count of instances solved to optimality for the
same set of benchmark instances. We argue that in the latter case the
implementation is at least globally representative of the performance of HSSGA
as described in the article.

All the three algorithms are run on Intel Core i5 3.20GHz CPU with 8GB memory,
using a single core. Sparrow uses the same parameters as mentioned in Section
4.2 and the other two algorithms use the same parameters as mentioned in
articles [16, 8].

We do not have the upper bounds of the new instances. Therefore we calculate
the gaps between the results of HSSGA and ILS* and the results of Sparrow. The
gaps of HSSGA and ILS*, as well as the CPU times of the three algorithms on
the three new instance sets are shown in Figures 5-7. Each point is the
average result of 10 runs. Since the runtime of ILS* turned out to be too long
for large instances, we set a time limit of 3600s.

On the satellite scheduling set, the gap between Sparrow and ILS* increases
when there are more orders, which shows that ILS* cannot handle larger
instances well. The gap between Sparrow and HSSGA does not change much. This
shows that both Sparrow and HSSGA have a stronger ability to solve instances
with larger congestion ratio efficiently. For instances with 150 and 300
orders, HSSGA performs better than Sparrow (with the gap smaller than 0).
Regarding CPU times, ILS* shows a weak scalability. There is decline at order
size 300, because many instances in order size 300 were stopped by the time
limit, resulting in a lower average CPU time. Sparrow uses the least time.
Both HSSGA and Sparrow algorithm are based on a hybridization of a population-
based method and a local search method. The two algorithms integrate the
exploration ability of the population-based method and the exploitation
ability of the local search method well, making them adapt well for instances
with varying sizes.

Figure 5: The gaps of HSSGA and ILS* to Sparrow (Left), and the CPU times of
three algorithms on the satellite scheduling set (right).

Figure 6: The gaps of HSSGA and ILS* to Sparrow (Left), and the CPU times of
three algorithms on the commerce set (right).

Figure 7: The gaps of HSSGA and ILS* to Sparrow (Left), and the CPU times of
three algorithms on the travelling repairman set (right).

On the commerce set, the gaps of ILS* and HSSGA both increases when $q$ is
larger (i.e., when revenue and processing time are more correlated), which
shows that Sparrow can solve instances with correlated processing time and
revenue well. Sparrow uses the least time and produces the best solutions.
Sparrow performs well on this set of instance mainly because of the self-
adaption ability of the ALNS component: ALNS uses multiple neighbourhood
operators and can choose the most efficient one according to the instances.
When the processing time and revenue of orders are more correlated, the
operators based on the unit revenue would become less efficient to select
orders. In this case Sparrow chooses other operators and the correlation
between processing time and revenue does not influence the performance of
Sparrow much.

Last, on the travelling repairman set, the changes of the gaps of the two
algorithms are not clear. However it is obvious that Sparrow uses the least
time and produces the best solutions. We believe this is because of the fast
insertion algorithm with the time slack strategy, which provides a good
flexibility for the orders to shift in the long time windows.

As a summary, Sparrow has a relatively high ability to handle harder and real-
life cases, especially when revenue and processing time are more correlated,
and the time window is very long. The HSSGA algorithm performs well on large
instances in terms of optimality gap, although taking more time than Sparrow.
The ILS* algorithm performs worst on these harder instances, and has the worst
scalability.

##  5 Conclusions

This article studied the Order Acceptance and Scheduling (OAS) problem with
sequence-dependent setup times and time windows. We proposed a novel memetic
algorithm called Sparrow, a hybridization of the biased random key genetic
algorithm (BRKGA) and adaptive large neighbourhood search (ALNS). We
introduced a new bounded-width gene encoding strategy, a hybrid decoding
method, an intelligent crossover operator, several neighbourhood operators,
and a fast insertion algorithm, making Sparrow suitable for problems with
varying properties.

Sparrow is tested on a set of standard benchmark with 750 instances with
25–100 orders. Compared with state-of-the-art algorithms, Sparrow obtains
better-quality solutions with comparable running time. The gaps between
Sparrow and other algorithms tend to increase when the problem instances get
more difficult. We further study this problem by analyzing the correlation
between problem properties and the algorithm performance and find that the
congestion ratio of the instance, the length of time windows and the
correlation between revenue and processing time are the key properties
influencing the difficulty of the problem. Finally, we generate new instances
with up to 300 orders, longer time windows and more correlated processing time
and revenue, and compare the performances of different algorithms on these new
realistic instances to understand their strengths and weaknesses. We find that
Sparrow has a good ability to solve these difficult instances and the HSSGA
algorithm from [16] performs well on large instances in terms of optimality
gap, although taking more time than Sparrow. We believe that the integration
of the exploration ability of population-based methods and the exploitation
ability of local search methods in Sparrow and HSSGA, and the varying
neighbourhood operators and the fast insertion strategy in Sparrow make them
successful on the difficult instances.

Our next steps are to further improve the performance of Sparrow on large
instances, and apply it to other real-world problem domains such as the agile
satellite observation scheduling problem which has time-dependent revenue,
time-dependent setup times and multiple machines and time windows.

## Acknowledgements

We gratefully thank Dr. Yuri Laio T.V. Silva and Dr. Anand Subramanian for
providing the tight upper bound of each instance. This work is supported by
China Scholarship Council for Lei He’s visit at Delft University of
Technology, the Netherlands (Grant No. 201703170269), and China Hunan
Postgraduate Research Innovating Project (Grant No. CX2018B020).

## References

## References

  * [1] P. Wang, G. Reinelt, P. Gao, Y. Tan, A model, a heuristic and a decision support system to solve the Earth observing satellites fleet scheduling problem, Computers & Industrial Engineering 61 (2) (2011) 322–335.
  * [2] C. Verbeeck, P. Vansteenwegen, E.-H. Aghezzaf, The time-dependent orienteering problem with time windows: a fast ant colony system, Annals of Operations Research 254 (1-2) (2017) 481–505.
  * [3] C. Oğuz, F. S. Salman, Z. B. Yalçın, et al., Order acceptance and scheduling decisions in make-to-order systems, International Journal of Production Economics 125 (1) (2010) 200–211.
  * [4] J. B. Ghosh, Job selection in heavily loaded shop, Computers and Operations Research 24 (2) (1997) 141–145.
  * [5] B. Cesaret, C. Oğuz, F. S. Salman, A tabu search algorithm for order acceptance and scheduling, Computers & Operations Research 39 (6) (2012) 1197–1205.
  * [6] S. A. Slotnick, Order acceptance and scheduling: A taxonomy and review, European Journal of Operational Research 212 (1) (2011) 1–11.
  * [7] S. Nguyen, M. Zhang, M. Johnston, Enhancing branch-and-bound algorithms for order acceptance and scheduling with genetic programming, in: European Conference on Genetic Programming, Springer, 2014, pp. 124–136.
  * [8] Y. L. T. Silva, A. Subramanian, A. A. Pessoa, Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times, Computers & Operations Research 90 (2018) 142–160.
  * [9] S.-W. Lin, K. Ying, Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm, Journal of the Operational Research Society 64 (2) (2013) 293–311.
  * [10] C. Chen, Z. Yang, Y. Tan, R. He, Diversity controlling genetic algorithm for order acceptance and scheduling problem, Mathematical Problems in Engineering 2014 (2014) Article ID 367152.
  * [11] S. Nguyen, M. Zhang, K. C. Tan, A dispatching rule based genetic algorithm for order acceptance and scheduling, in: Proceedings of the 16th Annual Conference on Genetic and Evolutionary Computation (GECCO 2015), ACM, 2015, pp. 433–440.
  * [12] J. Park, S. Nguyen, M. Johnston, M. Zhang, Evolving stochastic dispatching rules for order acceptance and scheduling via genetic programming, in: Australasian Joint Conference on Artificial Intelligence, Springer, 2013, pp. 478–489.
  * [13] J. Park, S. Nguyen, M. Zhang, M. Johnston, Enhancing heuristics for order acceptance and scheduling using genetic programming, in: Asia-Pacific Conference on Simulated Evolution and Learning, Springer, 2014, pp. 723–734.
  * [14] S. Nguyen, M. Zhang, M. Johnston, A sequential genetic programming method to learn forward construction heuristics for order acceptance and scheduling, in: Evolutionary Computation (CEC), 2014 IEEE Congress on, IEEE, 2014, pp. 1824–1831.
  * [15] S. Nguyen, A learning and optimizing system for order acceptance and scheduling, The International Journal of Advanced Manufacturing Technology 86 (5-8) (2016) 2021–2036.
  * [16] S. N. Chaurasia, A. Singh, Hybrid evolutionary approaches for the single machine order acceptance and scheduling problem, Applied Soft Computing 52 (2017) 725–747.
  * [17] S. N. Chaurasia, J. H. Kim, An artificial bee colony based hyper-heuristic for the single machine order acceptance and scheduling problem, in: Decision Science in Action, Springer, 2019, pp. 51–63.
  * [18] P. Moscato, On evolution, search, optimization, gas and martial arts: toward memetic algorithms, Tech. rep., California Institue Technology, Pasadena, CA. Caltech Concurrent Comput. Prog. Rep. 826 (1989).
  * [19] B. Bontoux, C. Artigues, D. Feillet, A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem, Computers & Operations Research 37 (11) (2010) 1844–1852.
  * [20] H. Wang, Y. Fu, M. Huang, G. Q. Huang, J. Wang, A nsga-ii based memetic algorithm for multiobjective parallel flowshop scheduling problem, Computers & Industrial Engineering 113 (2017) 185–194.
  * [21] N. Asgari, M. Rajabi, M. Jamshidi, M. Khatami, R. Z. Farahani, A memetic algorithm for a multi-objective obnoxious waste location-routing problem: a case study, Annals of Operations Research 250 (2) (2017) 279–308.
  * [22] N. Krasnogor, J. Smith, A tutorial for competent memetic algorithms: model, taxonomy and design issues, IEEE Transactions on Evolutionary Computation 9 (5) (2005) 474–488.
  * [23] F. Neri, C. Cotta, Memetic algorithms and memetic computing optimization: A literature review, Swarm and Evolutionary Computation 2 (2012) 1–14.
  * [24] J. F. Gonçalves, J. R. De Almeida, A hybrid genetic algorithm for assembly line balancing, Journal of Heuristics 8 (6) (2002) 629–642.
  * [25] A. A. Chaves, J. F. Gonçalves, L. A. N. Lorena, Adaptive biased random-key genetic algorithm with local search for the capacitated centered clustering problem, Computers & Industrial Engineering 124 (2018) 331–346.
  * [26] J. F. Gonçalves, M. G. Resende, Biased random-key genetic algorithms for combinatorial optimization, Journal of Heuristics 17 (5) (2011) 487–525.
  * [27] H. Prasetyo, G. Fauza, Y. Amer, S. H. Lee, Survey on applications of biased-random key genetic algorithms for solving optimization problems, in: Industrial Engineering and Engineering Management (IEEM), 2015 IEEE International Conference on, IEEE, 2015, pp. 863–870.
  * [28] P. Tangpattanakul, N. Jozefowiez, P. Lopez, Biased random key genetic algorithm for multi-user earth observation scheduling, in: Recent Advances in Computational Optimization, Springer, 2015, pp. 143–160.
  * [29] D. Pisinger, S. Ropke, A general heuristic for vehicle routing problems, Computers & Operations Research 34 (8) (2007) 2403–2435.
  * [30] P. J. Palomo-Martínez, M. A. Salazar-Aguilar, G. Laporte, Planning a selective delivery schedule through adaptive large neighborhood search, Computers & Industrial Engineering 112 (2017) 368–378.
  * [31] X. Liu, G. Laporte, Y. Chen, R. He, An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time, Computers & Operations Research 86 (2017) 41–53.
  * [32] Y. Li, H. Chen, C. Prins, Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests, European Journal of Operational Research 252 (1) (2016) 27–38.
  * [33] E. Demir, T. Bektaş, G. Laporte, An adaptive large neighborhood search heuristic for the pollution-routing problem, European Journal of Operational Research 223 (2) (2012) 346–359.