# Adaptive Population-based Simulated Annealing for Uncertain Resource
Constrained Job Scheduling

Dhananjay Thiruvady, Su Nguyen, Yuan Sun, Fatemeh Shiri, Nayyar Zaidi,
Xiaodong Li

###### Abstract

Transporting ore from mines to ports is of significant interest in mining
supply chains. These operations are commonly associated with growing costs and
a lack of resources. Large mining companies are interested in optimally
allocating their resources to reduce operational costs. This problem has been
previously investigated in the literature as resource constrained job
scheduling (RCJS). While a number of optimisation methods have been proposed
to tackle the deterministic problem, the uncertainty associated with resource
availability, an inevitable challenge in mining operations, has received less
attention. RCJS with uncertainty is a hard combinatorial optimisation problem
that cannot be solved efficiently with existing optimisation methods. This
study proposes an adaptive population-based simulated annealing algorithm that
can overcome the limitations of existing methods for RCJS with uncertainty
including the pre-mature convergence, the excessive number of hyper-
parameters, and the inefficiency in coping with different uncertainty levels.
This new algorithm is designed to effectively balance exploration and
exploitation, by using a population, modifying the cooling schedule in the
Metropolis-Hastings algorithm, and using an adaptive mechanism to select
perturbation operators. The results show that the proposed algorithm
outperforms existing methods across a wide range of benchmark RCJS instances
and uncertainty levels. Moreover, new best known solutions are discovered for
all but one problem instance across all uncertainty levels.

###### Index Terms:

Resource Constrained Job Scheduling; Uncertainty; Simulated Annealing;
Adaptive Perturbation

##  I Introduction

The mining supply chain in Australia is one of the largest in the world, where
a significant proportion of the minerals mined are exported overseas. Mining
is major contributor to the Australian economy, with the exporting minerals
contributing around $\$$AUD 200 billion per annum to the economy, employing
240,000 individuals directly, and around 850,000 individuals indirectly [1].
Due to its role in the export of raw materials, Australia has developed a
reputation in building mining technologies and is one of the largest suppliers
of these technologies and software,
worldwide.111https://www.austrade.gov.au/ArticleDocuments/2814/Mining-
software-and-specialised-technologies-Industry-capability-report.pdf.aspx

There are numerous problems within the mining supply chain. Of significant
interest, is the transportation of ore from mines to ports. In particular,
transporting ore from multiple mining sites to a port where resources (trains
and trucks) must be shared, is a key problem. If this problem is solved
effectively, it can lead to large increases in throughput, thereby leading to
substantial gains in revenue for the mining companies. In an abstract form,
this problem can be formulated as a resource constrained job scheduling (RCJS)
problem. The transportation of ore in batches can be viewed as jobs, while
different transport modes (trains or trucks), can be viewed as resources. In
the real setting, certain batches are required to be loaded on ships before
others, and this aspect can be modelled by precedences between jobs. The
timely arrival of ore at the ports is very important, as batches of ore that
unnecessarily wait will lead to demurrage costs. This aspect is incorporated
as a weighted tardiness for each job (different batches of ore being delayed
lead to different costs), and the aim is to ensure the total weighted
tardiness across all jobs is kept at minimum.

In the literature, this problem is known as RCJS with a shared central
resource [2, 3, 4]. The complexity of RCJS makes it challenging for
optimisation algorithms, and hence, several approaches have been proposed to
tackle it. These include metaheuristics and matheuristics [4, 5, 6, 7, 8, 9,
10, 11, 12, 13]. The problem was introduced by [4], who proposed a Lagrangian
relaxation based heuristic, which was able to find good solutions and lower
bounds. Singh and Weiskircher [2], [3] consider a similar problem to RCJS that
is modelled as machine scheduling with fractional shared resources. They
propose collaborative approaches via agent-based modelling, which prove to be
effective in tackling these problems. Ernst and Singh [5] propose a Lagrangian
relaxation based matheuristic that employs particle swarm optimisation, which
showed improvements in solution quality across the RCJS benchmark dataset.
Thiruvady et al. [6] consider a variant of RCJS with hard due dates, and they
show that an ant colony optimisation (ACO) and constraint programming hybrid
can efficiently find feasible and high quality solutions. The study by
Thiruvady et al. [7] proposes a column generation approach for RCJS, which
finds excellent solutions and lower bounds. An inherent issue is the time
requirements in solving this problem, and hence, parallel implementations of
metaheuristics and matheuristics have been attempted [8, 9]. The best known
solutions for RCJS have been obtained by Nguyen et al. [11] and Blum et al.
[14]. Nguyen et al. [11] develops a hybrid of differential evolution and
column generation, and they show excellent results on small and medium sized
problems. Blum et al. [14] devise a biased random key genetic algorithm, which
produces excellent results, especially for large problem instances. In the
interest of finding good solutions quickly, studies have shown that genetic
programming can be effective for RCJS [10, 12, 15]. Finally, Thiruvady et al.
[13] propose Merge search and CMSA for RCJS.

RCJS under uncertainty (RCJSU) is a variant of RCJS that takes into
consideration different practical random sources such as job release times,
job processing times or the availability of resources. Of vital importance in
RCJS, and crucial in real-world settings, is the uncertain resource
availabilities. That is, if trains and trucks breakdown or tracks and roads
need maintenance leading to delays in the ore reaching ports, there can be
substantial losses incurred. Therefore, planners need a solution method that
can address disruptions due to random events to ensure that the solutions
obtained can ensure smooth operations either by incorporating uncertainty into
optimisation problems, reoptimisation, or reactive dispatching rules.
Thiruvady et al. [16] developed the first RCJSU formulation, and proposed a
surrogate-assisted ant colony system (SACS) to find robust solutions. The
results show that SACS outperforms solution methods based on mixed integer
programming (MIP), meta-heuristics and surrogate-assisted evolutionary
algorithms. Further analyses show that SACS finds good solutions more quickly
compared to standard ACO algorithms.

Although SACS has shown promising results, there are some key limitations.
Firstly, surrogate models help SACS address the challenge of expensive
solution evaluations, but the proposed algorithm tends to converge
prematurely, especially for large instances. Therefore, SACS (as well as other
existing algorithms in the study of Thiruvady et al. [16]) can waste a lot of
time exploring the search space without making significant progress. Secondly,
the proposed method has many pre-defined hyper-parameters such as the learning
rate of ant colony systems (ACS) and pre-selection rate for the surrogate
models. Because of this issue, the algorithm can have trouble in solving a
wide range of instances without major modifications (e.g. reoptimise hyper-
parameters). Finally, the performance of SACS is not consistent across
different uncertainty levels and different problem sizes (i.e., number of
machines). For medium problem sizes and large uncertainty levels, SACS does
not show significantly superior performance compared to standard ACS.

This paper addresses the three key limitations discussed above by developing a
new adaptive population-based simulated annealing (APSA) algorithm for RCJSU.
The main contributions of this paper are summarised as follows: (1) a new
population-based simulated annealing algorithm with a balance between
exploration and exploitation, (2) a new efficient Metropolis-Hastings
algorithm extended from the simulated annealing algorithm proposed in [4], and
(3) a new adaptive mechanism to update the probabilities for selecting
perturbation operators to avoid premature convergence. APSA is similar to
memetic algorithms, and population-based stochastic local search [17, 18] that
combines evolutionary algorithms and local search heuristics; however, APSA
adopts a much smaller population in which the population is improved mainly
via local search and adaptive perturbations rather than crossover operators.
The balance between exploration and exploitation within APSA allows the
algorithms to perform efficiently against noisy and complex problems like
RCJSU. Extensive experiments are conducted to validate the superior
performance of the proposed algorithms for RCJSU and RCJS.

The paper is organised as follows. Section II provides a review of related
work. In Section III, a formulation of the RCJSU problem is provided,
including an integer programming model. Section IV discusses the adaptive
population-based simulated annealing algorithm proposed in this study. The
experimental evaluation and associated results are presented in Section V-A.
Section VI concludes the paper and presents possibilities for future work.

##  II Related Work

A review of the literature related to RCJS is provided here, including methods
and techniques that are effective at tackling problems similar to RCJS and
RCJSU.

###  II-A Optimisation techniques for tackling RCJS

Owing to the complexity of RCJS, mathematical programming methods on their own
do not suffice in finding optimal or even feasible solutions to relatively
small problems. Hence, metahuristics and matheuristics have been popular
approaches for tackling the problem. Metaheuristics, including partical swarm
optimisation [5], ACO [8], differential evolution [11], and genetic algorithms
[14] have been known to find good solutions, albeit with large time overheads.
RCJS can be modelled with graphs, and hence, ACO lends itself well to the
problem. Nonetheless, past studies on RCJS have shown that ACO tends to
converge slowly and gets trapped in local optima. Moreover, diversification
strategies including local search (e.g., parallel implementations or niching
techniques) help ACO, but the challenges still remain. Hybrid methods,
especially those that can guarantee optimality, have also been explored [4, 7,
11], but the results show that only relatively small RCJS problem instances
(up to 30 jobs) can be solved with these methods.

###  II-B Scheduling on problems with uncertainty

Uncertainty is inherent in many real-world applications, and dealing with
uncertainty is often challenging when devising scheduling algorithms. If
uncertainty is not considered, the ensuing scheduling algorithms in the
deterministic setting are often not effective at even finding feasible
solutions (e.g. if a machine breaks down, a job will not be able to start at
its pre-determined start time). Hence, a good understanding of the setting in
which the schedules are applied is important to ensure success of the
scheduling algorithms. Often, reactive scheduling strategies can be more
effective in dealing with frequently occurring situations with uncertainties,
since the latest information can be incorporated into the decisions.
Nonetheless, if predicting the schedules is needed and knowledge of
uncertainty is available, the preference is to develop robust schedules. The
focus of this paper is on finding robust schedules for RCJSU, since
predictable schedules are necessary for mining operations to coordinate
supporting activities and to ensure that ore arrives at ports in a timely
manner. Of particular interest is the timely arrival of ore at the ports,
which relies greatly on the availability of resources. This is indeed the
focus in the RCJSU problem and presented in the formulation in Equations (1)
to (7) (see Section III).

When tackling scheduling problems with uncertainty, the aim is typically to
devise methods that are capable of identifying good solutions under any
uncertain scenario. These solutions are called robust solutions and the
research area, robust proactive scheduling under uncertainty. There are
numerous studies focusing on this area, which we summarise here. Beck and
Wilson [19] investigate job shop scheduling, focusing on a variant which
consists of stochastic processing times. Their results demonstrate that
hybrids of tabu search and constraint programming with Monte Carlo simulation
are effective in handling large-sized problems with uncertainty. The study by
Song et al. [20], proposes branch-and-bound algorithms that generate robust
schedules on a variant of resource-constrained project scheduling with
processing times that are uncertain depending on time. Identifying robust
solutions in uncertain problems introduces additional complexity, and for this
purpose metaheuristcs such as swarm intelligence algorithms and evolutionary
approaches are known to be effective. Bierwirth and Mattfield [21] study
genetic algorithms for dynamic job arrivals in classic job shop scheduling.
Their results show that their approaches are superior to priority dispatching
rules, which are popular in dynamic production scheduling. Wang et al. [22]
devise a surrogate-assisted multi-objective evolutionary method to tackle
proactive scheduling where machines are considered to have stochastic
breakdowns. To cope with the uncertainty, they propose a job compression and
rescheduling strategy [23]. Support vector regression in conjunction with
surrogate models have been proposed to enhance the speed of time-intensive
simulations. The study by Wang et al. [24] provides an in-depth analysis and
discussion of scheduling with machine breakdowns. Systematic reviews of
scheduling in problems with uncertainty have also been conducted [25, 26].

The least two decades have seen numerous studies that consider uncertainty in
scheduling problems similar to that of RCJS. There are several similarities to
project scheduling, and many studies have considered uncertainty within this
setting [27, 28, 29, 30, 31, 32, 33]. In these studies, uncertainty is
typically considered in respect to the resources, though, a few consider
processing time related uncertainty. Lambrechts et al. [29] study uncertainty
with resources, and specifically modes of execution related to the activities.
They develop the notion of “time buffering,” that efficiently generates robust
schedules. Masmoudi and Haït [30] consider resource levelling and resource
constrained project scheduling, and they propose fuzzy modelling to tackle
uncertainty. Their solution approaches are a genetic algorithm and a greedy
method to identify robust schedules. Khodakarami et al. [31] investigate
Bayesian networks to identify causal structures considering uncertainty in
sources and parameters of a project. They find that Bayesian networks are
indeed very effective at dealing with uncertainty, including aspects such as
representation, elicitation and management. Uncertainty associated with
processing times has also been investigated [32, 33]. Moradi and Shadrokh [32]
develop a problem-specific heuristic to deal with uncertainty, and the study
by Chakrabortty et al. [33] propose several Branch & Cut heuristics for
project scheduling.222Benchmark datasets obtained from the project scheduling
problem library (PSPLIB) [34].

###  II-C Hybrid optimisation methods

Local search and population-based methods [35] have been extensively
investigated in the literature to tackle challenging scheduling problems.
While local search heuristics are best known for their ability to find local
optima efficiently, population-based optimisation methods such as genetic
algorithms are better known for their exploration ability. Empirical studies
have demonstrated the need to maintain a balance between exploration and
exploitation when dealing with difficult combinatorial optimisation problems
such as job shop scheduling [36]. Such hybrid methods are commonly referred to
as memetic algorithms [17] or population-based stochastic local search
algorithms [18] in the literature. While hybrid algorithms are effective in
combinatorial optimisation, there are still a few shortcomings. Firstly,
design choices to develop competitive hybrid algorithms are difficult to make
and can be sensitive to different problem subsets. Secondly, the performance
of hybrid algorithms depend strongly on an “ideal” setting of the algorithm
parameters.

Hybrid algorithms have also been developed for RCJS. The study that introduced
the problem [4] develop a Lagrangian relaxation heuristic, which combines MIP
and simulated annealing. Following this, Thiruvady et al. [7] show that a
column generation and ACO hybrid is very effective on this problem by finding
good lower bounds. Parallel implementations of ACO [8] have also been
effective, by finding high-quality solutions quickly. [11] propose a hybrid
algorithm combining differential evolution and local search with excellent
results. The study by Thiruvady et al. [13] show that parallel matheuristics
based on MIP and ACO can effectively tackle this problem.

Thiruvady et al. [16] has developed SACS, a sophisticated algorithm combining
ACO, surrogate modelling, and local search to deal with RCJSU. The experiments
show that SACS can find excellent solutions for small problems thereby
outperforming other meta-heuristics. However, further analyses show that SACS
tends to converge prematurely and is inconsistent when working with different
problem subsets. Moreover, SACS has many hyper-parameters (for ACO, local
search, surrogate models), for which the ideal settings are difficult to find.

##  III Problem Formulation

The formal definition of RCJSU as an integer program (IP) was provided by
Thiruvady et al. [16]. Past studies have considered uncertainty in different
ways, including resource limits [29] or uncertainty in job/task processing
times [33]. However, in this study the focus is on uncertainty derived from
the variability in resources, which in turn affects the processing times of
jobs/tasks.333We refer the reader to the study by Thiruvady at al. [16] for a
detailed discussion of uncertainty in respect to this problem. The problem is
NP-hard as it is at least as hard as its deterministic counterpart, which is
indeed shown to be NP-hard [4]. This IP formulation extends the one of Singh
and Ernst [4], proposed for RCJS. Uncertainty is introduced by considering
several uncertain resource levels, that is, some proportion of the original
resource limit is used for each uncertainty sample (details in Section V-A).

We are given several jobs $\mathcal{J}$ $=\\{1,\ldots,n\\}$, which are
associated with the following information. Each job $i$ must execute on
machine $m_{i}$, ($\mathcal{M}$ $=\\{1,\ldots,l\\}$), has a a release time
$r_{i}$, processing time $p_{i}$, due time $d_{i}$, weight $w_{i}$ and
resource usage $g_{i}$. Jobs on the same machine cannot execute concurrently,
or in other words, only one job may execute at one time. A time horizon is
given, consisting of discrete points ${\mathcal{T}}=\\{0,\ldots,D\\}$, and $D$
is chosen to be sufficiently large to ensure a feasible solution will always
be found. Precendences may exist between any two jobs $i\in\mathcal{J}$ and
$j\in\mathcal{J}$ that execute on the same machine. This is represented as
$i\rightarrow j$, where job $i$ completes before job $j$ starts.

A central resource constraint exists across all machines, where the cumulative
resource usage of jobs executing at any time point must be at most
$\mathcal{G}$. When considering uncertainty, $\mathcal{G}$ is allowed to vary.
This leads to defining a sample, which has available a proportion of the
resource $\mathcal{G}$, and is an instance of the problem. As an input, the
total number of samples $u$ is provided, and the resource limit is
$\mathcal{G}_{s}$ applies to the $s^{th}$ sample ${\cal
U}=\\{1,\ldots,u_{S}\\}$.

The IP can be defined as follows. Let $z_{sjt}$ be a binary variable, which
indicates in sample $s$, job $j$ completes or has completed by time $t$, if
$z_{sjt}=1$. By this definition, a job stays complete once completed. Compared
to RCJS, the RCJSU IP formulation requires additional space complexity, which
consists of ${\mathcal{O}}(n^{3})$ variables, and each set of constraints with
an additional dimension owing to the samples. The IP formulation is:

$\displaystyle\min\quad\frac{\sum_{s\in\cal U}\sum_{j\in\cal J}\sum_{t\in\cal
T}w_{jt}\times(z_{sjt}-z_{sjt-1})}{u_{s}}$ (1) s.t. $\displaystyle
z_{sjt_{\max}}=1$ $\displaystyle\forall\ s\in{\cal U},\forall\ j\in{\cal J}$
(2) $\displaystyle z_{sjt}-z_{sjt-1}\geq 0$ $\displaystyle\forall\ j\in{\cal
J},\forall\ s\in{\cal U},$ $\displaystyle t\in\\{1,\ldots,t_{\max}\\}$ (3)
$\displaystyle z_{sjt}=0$ $\displaystyle\forall\ t\in\\{1,\ldots,e_{j}\\},$
$\displaystyle\forall\ s\in{\cal U},\ \forall\ j\in{\cal J}$ (4)
$\displaystyle z_{sbt}-z_{sa,t-p_{b}}\leq 0$ $\displaystyle\forall\
(a,b)\in{\cal C},\ \forall\ s\in{\cal U},$ $\displaystyle\forall\ t\in{\cal
T}$ (5) $\displaystyle\sum_{j\in{\cal J}^{i}}z_{sj,t+p_{j}}-z_{sjt}\leq 1$
$\displaystyle\forall\ i\in{\cal M},\ \forall\ s\in{\cal U},$
$\displaystyle\forall\ t\in{\cal T}$ (6) $\displaystyle\sum_{j\in{\cal
J}}g_{j}\cdot(z_{sj,t+p_{j}}-z_{sjt})\leq{\cal G}_{s}$ $\displaystyle\forall\
s\in{\cal U},\ \forall\ t\in{\cal T}$ (7)

Equation (1), the objective function, states that the average total weighted
tardiness (TWT) across all samples must be minimised. Constraints (2) ensure
that all jobs complete. Once a job completes it stays complete, which is
enforced by Constraints (3). Constraints (4) ensure that all jobs satisfy
release times and the precedences are imposed by Constraints (5). In this
constraint, $e_{j}=r_{j}+p_{j}-1$. Constraints (6) require that only one job
can execute on one machine at every time point. Constraints (7) ensure that
the resource limits, considering each sample, are satisfied.

For the RCJS, there are efficient scheduling heuristics that are known (see
Section IV-D). These heuristics typically depend on an alternative
formulation, where a sequence or permutation jobs are efficiently mapped to
schedules. Previous studies have used this approach for RCJS (e.g. [7]), and
it has also proved beneficial for the RCJSU [16]. In this study, $\pi$
represents a sequence of jobs while $\sigma(\pi)$ represents an efficient
mapping from $\pi$ to a feasible schedule. Therefore, $\pi$ is effectively a
solution to the problem, where given a sequence, a deterministic schedule can
be efficiently constructed.

An example RCJS problem instance is shown in Table I. This example shows how a
solution is constructed and what the optimal solution is. The problem consists
of three jobs, with the associated information in the tables. Moreover, the
resource capacity is 10 units. Considering $\pi$, there are six potential
sequences. Among the jobs, the resulting schedules from $\pi$ will be
efficient if Job 3 is scheduled early owing to an early due date and high
weight. Additionally, Job 2 should be sequenced before Job 1 due to its higher
weight. Given this information, the optimal solution is $\pi=\\{3,2,1\\}$.

TABLE I: An example with 3 jobs and 10 units of resource. Proc. is the
processing time.

Job |  | Resource |  | Weight |  | Proc. |  | Due
---|---|---|---|---|---|---|---|---
1 |  | 5 |  | 0.1 |  | 1 |  | 2
2 |  | 10 |  | 0.2 |  | 1 |  | 2
3 |  | 10 |  | 0.5 |  | 1 |  | 1

##  IV Population-based Simulated Annealing

Several metaheuristics have been able to find excellent solutions to RCJS in a
time efficient manner. One of these approaches was simulated annealing [4].
However, to tackle RCJSU, the traditional simulated annealing method has a few
shortcomings, and hence, we propose an adaptive population-based simulated
annealing (APSA). In particular, this method has three main differences from
the traditional approach: (1) a population of solutions to track and exploit
best known solutions, (2) a faster cooling schedule within the Metropolis-
Hastings algorithm, and (3) adaptive probabilistic selection of the
neighbourhood moves to perturb solutions in the population. Comparisons are
made to ACS (ant colony system) and SACS (surrogate-assisted ant colony
system) of [16], which have previously been effective on RCJSU.

###  IV-A The APSA Algorithm

Algorithm 1 shows the high-level APSA procedure for RCJSU. As input, the
algorithm takes the following: (a) $T_{0}$: an initial temperature, (b)
$t_{lim}$: time limit for the execution of the algorithm, (c) $Iter$: number
of Metropolis-Hastings iterations, (d) $s$: population size, (e) $\gamma$: a
parameter to control the cooling schedule and (f) $\rho$: a parameter that
specifies how to adapt the probabilities ($\rho=$ 0.9 for this study). In Line
2, the population $\Pi$ is initialised, where each solution consists of a
random list of all the tasks. The best known solution, $\mathcal{\pi}^{bs}$,
is initialised to be empty. In Line 3, the probability distributions
associated with three neighbourhood moves (discussed in the following) are
initialised. The main procedure takes place between Lines 4–21, and the
algorithm completes execution when the time limit is reached.

Algorithm 1 Adaptive Population-based Simulated Annealing (APSA)

1:Input: An MMALBPS instance, $T_{0}$, $t_{lim}$, $Iter$, $s$, $\gamma$,
$\rho$

2:$\Pi\leftarrow$ Initialise($s$), $\mathcal{\pi}^{bs}\leftarrow\emptyset$

3:$p^{b}\leftarrow 0.65$, $p^{j}\leftarrow 0.3$, $p^{r}\leftarrow 0.05$

4:while execution time $<t_{lim}$ do

5: for $\pi\in\Pi$ do

6: $\pi^{t}:=$ MetropolisHastings($\pi$, $T_{0}$, $Iter$, $\gamma$)

7: $\mathcal{\pi}^{bs}:=$ Update($\pi$)

8: $r\leftarrow$ $\text{{\sf rand}}()$

9: if $r<p^{b}$ then

10: $\beta-$Sampling($\mathcal{\pi}^{bs}$)

11: $p^{b}\leftarrow p^{b}\times\rho$

12: else if $r<p^{b}+p^{j}$ then

13: $\pi:=$ SwapOps($\mathcal{\pi}^{ib}$, $m$)

14: $p^{j}\leftarrow p^{j}\times\rho$

15: else

16: $\pi\leftarrow$ RandomList()

17: $p^{r}\leftarrow p^{r}\times\rho$

18: end if

19: Normalise($p^{b}$, $p^{j}$, $p^{r}$)

20: end for

21:end while

22:$\pi^{f}:=$ SwapAllJobPairs($\mathcal{\pi}^{bs}$)

23:return $\pi^{f}$

Within the main loop, the following is applied to each solution in the
population. First, in Line 6, the Metropolis-Hastings algorithm is applied
(Algorithm 2) using $\pi$ as the best solution and for $Iter$ iterations. The
resulting solution is stored in $\pi^{t}$. $\mathcal{\pi}^{bs}$ is updated to
$\pi$, if $\pi$ is an improvement, i.e., $f(\pi)<f(\mathcal{\pi}^{bs})$.
Following this, between Lines 9–19, $\pi$ is perturbed using a neighbourhood
move (details follow in Section IV-C). As part of these steps, the
probabilities associated with choosing one of the perturbation moves are
adapted or updated. That is, if a move is selected, its corresponding
probability reduced by an adaptation factor $\rho=0.9$.

Every solution obtained (by applying any neighbourhood move, etc.) requires
the computation of its objective value. As mentioned earlier, a solution is
represented by a sequence of the tasks. For each sequence of tasks $\pi$, a
feasible schedule ($\sigma(\pi)$) is obtained by constructing $u_{s}$
schedules corresponding to each uncertainty sample. Note, each schedule is
resource feasible, ensuring that at most ${\cal G}_{s}$ resources are used at
each time point for sample $s$. The result is that each sample has its own
TWT. The objective value of $\pi$ is computed as the average of the TWTs
across all samples.

###  IV-B The Metropolis-Hastings Algorithm

Algorithm 2 MetropolisHastings

1:Input: $\pi$, $T_{0}$, $Iter$, $\gamma$

2:$C\leftarrow\infty$, $T^{c}\leftarrow T_{0}$, $\pi^{ib}\leftarrow\pi$

3:for $i=1$ to $Iter$ do

4: $\pi^{b}\leftarrow$ SwapJobs($\pi^{ib}$)

5: if $f(\pi^{b})<C$ then

6: $C\leftarrow f(\pi^{b})$

7: $\pi^{ib}\leftarrow\pi^{b}$

8: $i\leftarrow 1$

9: else

10: $\Delta=f(\pi^{ib})-C$

11: if $e^{-\Delta/T^{c}}\leq\text{{\sf rand}}()$ then

12: $\pi^{ib}\leftarrow\pi^{b}$

13: end if

14: $T^{c}\leftarrow T^{c}\times\gamma$

15: end if

16:end for

17:return $\pi^{ib}$

The Metropolis-Hastings method relies on the cooling schedule to ensure a
gradual convergence to high-quality regions of the search space. However, due
to the overheads introduced by uncertainty, the traditional gradual reduction
in temperature will not suffice, and hence we propose a modified version of
the method for RCJSU.

Algorithm 2 shows the Metropolis-Hastings procedure. It takes as input: (a)
$\pi$: current best solution, (b) $T_{0}$: initial temperature, (c) $Iter$:
number of iterations that the algorithm will execute for and (d) $\gamma$: a
parameter to determine the cooling schedule. $C$ represents the best known
objective value, and is set to a large number. The temperature $T^{c}$ is set
to the initial temperature $T_{0}$, and the best solution $\mathcal{\pi}^{ib}$
is initialised to $\pi$. The algorithm executes for $Iter$ iterations between
Lines 3–16. Using $\mathcal{\pi}^{ib}$, the neighbourhood move of swapping a
pair of jobs is applied. That is, two jobs within the sequence are selected at
random and swapped (see Figure 2). If the new solution found $\pi^{b}$ is an
improvement, $C$ is updated to the objective value of $\pi^{b}$. Moreover,
$\mathcal{\pi}^{ib}$ is updated to $\pi^{b}$ and the iteration count is reset.
Otherwise, a move to the non-improving solution $\pi^{b}$ is still chosen with
probability $e^{-(f(\pi^{ib})-C)/T^{c}}$. The cooling schedule takes place in
Line 14.

###  IV-C Adaptive Perturbation

Key to the success of APSA is perturbing the best known solution, via three
neighbourhood moves. In particular, when applied carefully at different stages
of the search, the overall APSA algorithm is able to achieve excellent trade-
offs between intensification and diversification.

The first neighbourhood move is $\beta$-sampling, which was first studied in
the context of project scheduling [37]. The basic idea underlying the method
is that consecutive jobs or tasks with a sequence are inter-dependent, and
moving whole sub-sequences (maintaining certain dependencies) can lead to
significant improvements in solutions. For the purposes of the current study,
starting at a randomly selected position in the sequence, a sub-sequence of
fixed length (5 jobs) is moved to the back of the permutation.

Figure 1 provides an illustration of this method. $\pi$ consists of 11 jobs. A
position $p\in{1,\ldots,n-5}$ is chosen randomly, and this sub-sequence ($p$
to $p+5$) moves to the end (bottom part of the figure). Here, $p=4$, which
starts at Job 7, and Jobs 7, 9, 10, 3 and 11 are chosen to move to the end of
the sequence. Subsequent jobs (Jobs 8,4, and 5) move up in the sequence to
position 4. $\beta$-sampling is applied in the above manner in Line 10 of
Algorithm 1.

Figure 1: An example that demonstrates $\beta$-sampling. From the sequence
$\pi$, a subset of jobs is selected (7, 9, 10, 3, 11) and moved to the end of
the sequence.

The second neighbourhood move is Job swapping. This consists of swapping pairs
of jobs in $\pi$. Figure 2 shows an example of swapping one pair of jobs. Two
positions or indices are chosen at random in the sequence $\pi$, and the jobs
in these positions are swapped. In the example, Jobs 2 and 8 are swapped.

Figure 2: An example that demonstrates job swapping. Two indices are selected
randomly, and the corresponding jobs are swapped. In this example, indices 3
and 9 are selected, and the jobs within those indices, 2 and 9, are swapped.

The third neighbourhood move is to re-initialise the current solution to a
randomly chosen sequence. Not surprisingly, the resulting solution can belong
to vastly different areas of the search space with a very different objective
function value. Hence, this neighbourhood move is expected to produce the
largest amount of diversification.

####  IV-C1 Convergence of Probabilities

Assuming the probability values of $p_{b}$, $p_{j}$ and $p_{r}$ at time step
$t$ are $p_{b}^{t}$, $p_{j}^{t}$ and $p_{r}^{t}$, the expected probabilities
at time step $t+1$ can be calculated as

$\displaystyle p_{b}^{t+1}$
$\displaystyle=p_{b}^{t}\Bigg{(}\frac{0.9p_{b}^{t}}{1-0.1p_{b}^{t}}\Bigg{)}+p_{j}^{t}\Bigg{(}\frac{p_{b}^{t}}{1-0.1p_{j}^{t}}\Bigg{)}+p_{r}^{t}\Bigg{(}\frac{p_{b}^{t}}{1-0.1p_{r}^{t}}\Bigg{)},$
(8) $\displaystyle p_{j}^{t+1}$
$\displaystyle=p_{j}^{t}\Bigg{(}\frac{0.9p_{j}^{t}}{1-0.1p_{j}^{t}}\Bigg{)}+p_{r}^{t}\Bigg{(}\frac{p_{j}^{t}}{1-0.1p_{r}^{t}}\Bigg{)}+p_{b}^{t}\Bigg{(}\frac{p_{j}^{t}}{1-0.1p_{b}^{t}}\Bigg{)},$
(9) $\displaystyle p_{r}^{t+1}$
$\displaystyle=p_{r}^{t}\Bigg{(}\frac{0.9p_{r}^{t}}{1-0.1p_{r}^{t}}\Bigg{)}+p_{b}^{t}\Bigg{(}\frac{p_{r}^{t}}{1-0.1p_{b}^{t}}\Bigg{)}+p_{j}^{t}\Bigg{(}\frac{p_{r}^{t}}{1-0.1p_{j}^{t}}\Bigg{)}.$
(10)

Hence the governing differential equations for evolving the probabilities
$p_{b}$, $p_{j}$ and $p_{r}$ can be derived:

$\displaystyle\frac{dp_{b}}{dt}$
$\displaystyle=0.1p_{b}\Bigg{(}\frac{p_{j}^{2}}{1-0.1p_{j}}+\frac{p_{r}^{2}}{1-0.1p_{r}}-\frac{p_{b}(p_{j}+p_{r})}{1-0.1p_{b}}\Bigg{)},$
(11) $\displaystyle\frac{dp_{j}}{dt}$
$\displaystyle=0.1p_{j}\Bigg{(}\frac{p_{r}^{2}}{1-0.1p_{r}}+\frac{p_{b}^{2}}{1-0.1p_{b}}-\frac{p_{j}(p_{b}+p_{r})}{1-0.1p_{j}}\Bigg{)},$
(12) $\displaystyle\frac{dp_{r}}{dt}$
$\displaystyle=0.1p_{r}\Bigg{(}\frac{p_{b}^{2}}{1-0.1p_{b}}+\frac{p_{j}^{2}}{1-0.1p_{j}}-\frac{p_{r}(p_{b}+p_{j})}{1-0.1p_{r}}\Bigg{)}.$
(13)

######  Theorem 1.

For any initial condition of $p_{b}^{0}$, $p_{j}^{0}$, $p_{r}^{0}\in[0,1]$ and
$p_{b}^{0}+p_{j}^{0}+p_{r}^{0}=1$, the probability values converge to
$p_{b}=p_{j}=p_{r}=1/3$.

###### Proof.

At equilibrium of the differential equations (11)-(13),
$\frac{dp_{b}}{dt}=\frac{dp_{j}}{dt}=\frac{dp_{r}}{dt}=0$. Solving this system
of equations with $p_{b}+p_{j}+p_{r}=1$, we can obtain the following seven
equilibria from the differential equations:

  * •

($p_{b}=0,p_{j}=0,p_{r}=1$),

  * •

($p_{b}=0,p_{j}=1,p_{r}=0$),

  * •

($p_{b}=1,p_{j}=0,p_{r}=0$),

  * •

($p_{b}=0,p_{j}=1/2,p_{r}=1/2$),

  * •

($p_{b}=1/2,p_{j}=0,p_{r}=1/2$),

  * •

($p_{b}=1/2,p_{j}=1/2,p_{r}=0$),

  * •

($p_{b}=1/3,p_{j}=1/3,p_{r}=1/3$).

However, the first six equilibria are unstable, in the sense that a small
disturbance will perturb the system away from those equilibria. The last
equilibrium ($p_{b}=1/3,p_{j}=1/3,p_{r}=1/3$) is the only stable equilibrium.
Hence, after a sufficient number of time steps, the probability values will
converge to this stable equilibrium. ∎

Figure 3 shows a simulation of how the probabilities associated with each
neighbourhood move (Algorithm 1) evolve across 200 simulations. We see that
three probabilities converge to almost equal levels by 125 simulations.

Figure 3: Adaptive probabilities over 200 simulations.

###  IV-D Scheduling Heuristic

The aim of the scheduling heuristic is to generate a resource feasible
schedule $\sigma(\pi)$ from the sequence $\pi$. For this purpose, the serial
scheduling scheme is employed [38], which is adapted from previous studies on
RCJS [4, 6, 7, 8]. Note, Thiruvady et al. [16] showed that this scheduling
scheme can indeed be effective for RCJSU.

(a)

(b)

Figure 4: An example of a problem with three machines and 15 jobs. From $\pi$,
jobs are selected in order (left to right) and scheduled on machines that they
belong to (e.g. orange jobs on $m_{2}$). Those jobs that have predecessors
that are not yet scheduled will be put on the waiting list $\hat{\pi}$; (a)
Job 8 requires Job 2 to be scheduled before it can be scheduled. (b) Job 8 is
scheduled once Job 2 has been scheduled, and this will be done as early as
possible considering resources.

The scheduling heuristic works as follows. Jobs in $\pi$ are selected in the
order in which they appear. Each job ($j$) is tested to see if any of its
preceding jobs have not yet been scheduled, and if so, $j$ is placed on the
waiting list. Otherwise, $j$ is scheduled as early as possible to ensure that
the resource limits are not violated. Once $j$ is scheduled, any job that
depends on $j$ (and only $j$) on the waiting list is scheduled immediately.
All such jobs on the waiting list are scheduled in order. Note, for RCJSU,
schedules using the procedure above are created for each sample.

Figure 4 shows how the scheduling heuristic works. The problem consists of 15
jobs to be scheduled on three machines. The height of a machine represents the
amount of resources available, while a job’s height represents its resource
requirement. A colour implies a job’s machine, i.e., jobs of one colour must
go on one machine (e.g. “orange” jobs should be scheduled on machine $m_{2}$).

Figure 4(a) shows a permutation $\pi$, and a solution that is partially
completed with a few jobs allocated to each machine. The waiting list also
consists of some waiting jobs $\hat{\pi}$, where for example, Job $8$ waits
for Job $2$ to be scheduled, considering Job $2$ precedes Job $8$. Figure 4(b)
shows one step in the method, where the next job in $\pi$, Job 2, is chosen
and scheduled in the first available resource feasible time slot on $m_{1}$.
Once Job 2 is scheduled, the waiting list can be examined, and it is found
that Job 8 can be released. Job 8 is scheduled as early as possible
considering the resource availability.

##  V Experimental Setting

We investigate APSA on RCJSU, and compare its performance to current state-of-
the-art approaches, including ACS and SACS. Additionally, we investigate APSA
against standard simulated annealing (SA) with the same settings, and the SA
of Singh and Ernst [4]. Finally, we examine APSA’s performance on the
deterministic problem (RCJS), and we compare APSA to ACS, SACS and a column
generation and ACO hybrid by Thiruvady et al. [7]. The experiments are
conducted on problem instances from the
literature.444https://github.com/andreas-ernst/Mathprog-
ORlib/blob/master/data/RCJS_Instances.zip consists of problem instances for
RCJS. The resource usage within these instances is modified to generate
problem instances for RCJSU. While this data was originally created for the
RCJS, each problem instance is modified to generate the data for RCJSU.
Specifically, there are 10 samples generated for each problem instance, where
each one has resource limits in the range $[U_{min},U_{l}\times G]$. $U_{min}$
is chosen to be the largest resource required by any job, i.e. $\max_{i\in\cal
J}g_{i}$, which ensures a resource feasible schedule can always be found.
Additionally, the multiplier $U_{l}\in\\{0.5,0.6,0.7,0.8,0.9,1.0\\}$ is used
to select a proportion of the resources. Typically, a smaller value (e.g. 0.5
or 0.6) means that the problem instance is tightly constrained, where the
schedules will need larger completion times, leading to a higher overall TWTs.

The parameter settings for APSA were selected through tuning by hand and by
using past studies as a guide. We refer to Algorithms 1 and 2. The time limit
$t_{l}im$ is set to 600 seconds. The initial temperature $T_{0}$ was set to
1500 [4]. Due to uncertainty and the overheads required to construct schedules
with a number of samples, the parameters within the Metropolis-Hastings
algorithm have been set to allow for much quicker cooling schedule. This is
achieved by allowing only 1000 iterations $Iter=1000$ and $\gamma=0.5$. The
population size was found through tuning by hand $s=10$. The sub-sequence size
used within $\beta$-sampling of length 5 jobs, which is obtained from [4].
Moreover, in Line 14 of Algorithm 1, there are $m=rand()*n$ applications of
job swapping, where $rand()$ is a random number between 0 and 1. The parameter
settings for ACS and SACS were obtained from [16], to which we refer the
reader for complete details.

We carry out experiments on all problem instances considering all uncertainty
levels. There are 25 repetitions of for each algorithm, with each one given 10
minutes of wall clock time. The memory limit was 2 GB, which proved to be
sufficient for all algorithms. The algorithms were implemented in C++ with
GCC-5.4.0. All experiments were carried out on Monash University’s Campus
Cluster –
MonARCH.555https://confluence.apps.monash.edu/display/monarch/MonARCH+Home

The IP was implemented in Gurobi 9.0.1 [39]. It was run for 10 minutes per
problem instance and allowed a larger amount of memory of 10GB. Across all the
runs, only one solution was found for one problem instance at the uncertainly
of 0.8. This is not surprising given the size of the model, which is
unsuitable in practical settings.

###  V-A Results

The results that follow are reported as a percentage difference from the
average solution quality over 25 runs for each algorithm to the best solution
found by any algorithm. Consider a problem instance and let $B*$ be the best
solution obtained by any algorithm for that problem instance. Let $A_{k}$ be
the best solution found by APSA for instance $k$. Then the percentage
difference for APSA is $\frac{A_{k}-B*}{A_{k}}$.

Tables II and III show the results of ACS, SACS and APSA for low and high
uncertainty levels $UL$, respectively. The tables show the best result
obtained by any algorithm (which is highlighted in bold if it is found by
APSA) for each uncertainty level, followed by the percentage differences of
each algorithm to the corresponding best solution. The best result found by
any algorithm is highlighted in bold, and those results that are statistically
significant (determined using a Wilcoxon ranked-sum test) are marked with a
“*”. To summarise the performance of the algorithms across the problem
instances, the last row of the tables report the number of times (# best) the
algorithm finds the best solution.

TABLE II: Results of ACS, SACS and APSA shown as the percentage difference to
the best solution for uncertainty levels 0.5, 0.6 and 0.7; Results in column
“Best” are highlighted in bold if APSA finds the best solution; Results for
each algorithm are highlighted in bold when they achieve best average results,
while statistically significant results (pair-wise Wilcoxon ranked-sum test)
at a 95$\%$ confidence interval are marked with a *.

|  | 0.5 |  | 0.6 |  | 0.7
---|---|---|---|---|---|---
|  | Best | ACS | SACS | APSA |  | Best | ACS | SACS | APSA |  | Best | ACS | SACS | APSA
3-5 |  | 971.7 | 1.034 | 1.043 | *0.142 |  | 942.6 | 0.494 | 0.404 | *0.048 |  | 988.8 | 1.177 | 1.092 | *0.260
3-23 |  | 224.9 | 0.934 | 0.791 | *0.000 |  | 232.5 | 2.314 | 2.052 | *0.138 |  | 240.5 | 2.374 | 2.345 | *0.162
3-53 |  | 221.5 | 0.474 | 0.366 | *0.000 |  | 213.4 | 0.066 | 0.028 | -0.005 |  | 231.7 | 0.319 | 0.211 | *0.000
4-28 |  | 150.6 | 6.754 | 6.768 | *0.671 |  | 128.1 | 6.409 | 6.300 | *1.046 |  | 116.1 | 6.763 | 6.720 | *0.164
4-42 |  | 401.7 | 1.327 | 1.279 | *0.144 |  | 361.1 | 1.603 | 1.606 | *0.219 |  | 323.9 | 0.540 | 0.509 | *0.034
4-61 |  | 248.3 | 5.578 | 5.324 | *0.209 |  | 213.2 | 4.877 | 4.192 | *0.225 |  | 196.6 | 8.246 | 7.519 | *1.073
5-7 |  | 801.3 | 3.582 | 3.590 | *0.604 |  | 673.3 | 4.496 | 4.147 | *0.371 |  | 656.6 | 3.925 | 3.932 | *0.801
5-21 |  | 683.6 | 4.640 | 4.353 | *1.066 |  | 535.8 | 6.148 | 5.088 | *0.649 |  | 577.4 | 5.504 | 4.342 | *1.320
5-62 |  | 816.7 | 4.660 | 4.450 | *0.579 |  | 688.0 | 5.712 | 5.436 | *1.145 |  | 676.5 | 5.117 | 5.175 | *1.042
6-10 |  | 1971.2 | 4.115 | 3.230 | *0.859 |  | 2026.3 | 4.708 | 3.944 | *1.610 |  | 1583.3 | 5.018 | 4.215 | *1.520
6-28 |  | 739.3 | 5.201 | 5.212 | *0.587 |  | 762.4 | 5.105 | 4.963 | *1.229 |  | 574.8 | 6.738 | 6.692 | *1.541
6-58 |  | 763.9 | 4.778 | 4.590 | *1.468 |  | 799.0 | 4.781 | 4.303 | *1.055 |  | 587.2 | 6.391 | 6.214 | *0.823
7-5 |  | 1235.3 | 2.203 | 2.054 | *0.131 |  | 1025.5 | 3.745 | 3.631 | *0.725 |  | 1213.8 | 2.963 | 2.833 | *0.386
7-23 |  | 1426.7 | 6.619 | 5.917 | *1.641 |  | 1194.3 | 6.363 | 6.007 | *1.776 |  | 1391.4 | 6.034 | 5.365 | *1.286
7-47 |  | 1442.1 | 6.778 | 5.901 | *1.540 |  | 1191.5 | 6.496 | 5.815 | *1.461 |  | 1410.3 | 6.524 | 5.664 | *1.529
8-3 |  | 1856.4 | 10.401 | 7.545 | *1.670 |  | 1995.5 | 10.389 | 8.257 | *2.845 |  | 1640.1 | 11.968 | 9.434 | *3.054
8-53 |  | 1154.1 | 6.363 | 6.101 | *1.623 |  | 1250.5 | 5.754 | 5.576 | *1.181 |  | 1053.8 | 6.512 | 6.794 | *1.839
8-77 |  | 2799.0 | 5.864 | 4.565 | *1.612 |  | 2971.5 | 5.134 | 4.193 | *1.135 |  | 2570.1 | 5.883 | 5.522 | *2.000
9-20 |  | 2462.6 | 5.900 | 5.301 | *1.648 |  | 2086.1 | 5.375 | 5.114 | *1.227 |  | 2125.4 | 5.644 | 5.402 | *1.836
9-47 |  | 3185.0 | 6.684 | 5.270 | *2.029 |  | 2640.4 | 7.618 | 5.934 | *1.993 |  | 3333.7 | 6.529 | 5.134 | *2.123
9-62 |  | 3485.6 | 4.678 | 4.103 | *1.154 |  | 2969.1 | 4.414 | 3.864 | *0.869 |  | 3656.7 | 4.199 | 3.589 | *1.060
10-7 |  | 5854.2 | 4.066 | 3.749 | *0.875 |  | 5603.8 | 4.764 | 4.108 | *1.387 |  | 5126.2 | 4.792 | 4.332 | *1.198
10-13 |  | 5246.0 | 3.092 | 2.783 | *0.769 |  | 4932.8 | 4.675 | 4.018 | *1.607 |  | 4517.0 | 4.719 | 4.497 | *1.694
10-31 |  | 1603.1 | 6.196 | 6.914 | *1.724 |  | 1525.3 | 6.018 | 6.445 | *1.210 |  | 1369.6 | 6.959 | 7.841 | *1.608
11-21 |  | 2359.0 | 4.747 | 5.053 | *1.167 |  | 2402.8 | 4.731 | 4.919 | *0.990 |  | 2502.8 | 5.099 | 4.934 | *1.247
11-56 |  | 3991.0 | 4.836 | 4.420 | *1.185 |  | 4047.3 | 5.072 | 4.196 | *1.177 |  | 4156.7 | 5.714 | 5.204 | *2.094
11-63 |  | 4354.2 | 3.885 | 3.518 | *0.863 |  | 4196.9 | 5.211 | 4.887 | *1.682 |  | 4561.3 | 3.580 | 3.516 | *0.636
12-14 |  | 4405.2 | 4.136 | 4.295 | *1.429 |  | 4378.3 | 4.937 | 4.890 | *1.944 |  | 3636.3 | 4.592 | 4.533 | *1.352
12-36 |  | 6825.5 | 2.979 | 3.217 | *1.484 |  | 6844.5 | 3.762 | 3.376 | *1.435 |  | 5710.1 | 3.732 | 3.504 | *1.429
12-80 |  | 5234.4 | 6.105 | 5.769 | *2.985 |  | 5310.1 | 4.949 | 4.875 | *2.004 |  | 4460.8 | 5.080 | 4.653 | *2.376
15-2 |  | 8105.5 | 3.879 | 4.319 | *3.304 |  | 7577.1 | 3.058 | 3.153 | *2.565 |  | 7737.2 | 2.834 | 2.843 | *2.015
15-3 |  | 9206.1 | 4.375 | 4.181 | *2.511 |  | 8585.2 | 3.669 | 3.626 | *2.008 |  | 8820.9 | 2.820 | 2.663 | *0.972
15-5 |  | 7548.8 | 5.099 | 5.345 | *2.547 |  | 7021.0 | 4.965 | 4.958 | *2.430 |  | 7186.8 | 3.964 | 3.968 | *1.876
20-2 |  | 15042.1 | 2.994 | 3.320 | *1.635 |  | 14021.9 | 2.747 | 2.957 | *1.928 |  | 15724.6 | 2.889 | 2.738 | *1.793
20-5 |  | 25172.0 | 3.239 | 2.917 | *1.693 |  | 23175.3 | 3.832 | 4.185 | *2.425 |  | 26028.0 | 3.782 | 4.010 | *2.558
20-6 |  | 13733.3 | 2.596 | 2.678 | *1.614 |  | 12713.5 | 2.707 | 2.725 | *1.900 |  | 14329.1 | 2.554 | 2.630 | *1.713
$\\#$ best |  | 36 | 0 | 0 | 36 |  | 36 | 0 | 0 | 36 |  | 36 | 0 | 0 | 36

The results in both tables show that APSA finds best known solutions for all
problem instances and uncertainty levels (except instance 15–2 at uncertainty
level 0.9), and the best average results across all problem instances for all
uncertainty levels. Looking closely, we see that the differences between the
algorithms are smallest for the smallest problems (3 machines) and largest
problems (20 machines). Everywhere else, APSA has significant advantages. For
the problem instances with 3 machines, this is not surprising, because it is
expected that all algorithms find solutions that are close to optimal.
However, APSA has the advantage that, for every run, it finds a solution close
to the best. On investigating the individual runs on the large problem
instances, we find that there are relatively few iterations conducted ($<$
10). This leads to APSA not converging sufficiently well, thereby not finding
as large improvements are seen on other smaller problem instances.

TABLE III: Results of ACS, SACS and APSA shown as the percentage difference to
the best solution for uncertainty levels 0.8, 0.9 and 1.0; Results in column
“Best” are highlighted in bold if APSA finds the best solution; Results for
each algorithm are highlighted in bold when they achieve best average results,
while statistically significant results (pair-wise Wilcoxon ranked-sum test)
at a 95$\%$ confidence interval are marked with a *.

|  | 0.8 |  | 0.9 |  | 1.0
---|---|---|---|---|---|---
|  | Best | ACS | SACS | APSA |  | Best | ACS | SACS | APSA |  | Best | ACS | SACS | APSA
3-5 |  | 861.9 | 0.972 | 0.773 | *0.031 |  | 949.2 | 0.165 | 0.162 | *0.000 |  | 786.3 | 0.424 | 0.439 | *0.050
3-23 |  | 214.6 | 1.981 | 1.631 | *0.084 |  | 232.2 | 1.636 | 1.666 | *0.000 |  | 200.9 | 2.787 | 2.568 | *0.244
3-53 |  | 186.0 | 0.016 | 0.016 | *0.000 |  | 212.5 | 0.085 | 0.047 | *0.000 |  | 145.5 | 0.069 | 0.041 | *0.000
4-28 |  | 101.5 | 7.224 | 6.800 | *0.857 |  | 113.3 | 4.556 | 4.830 | *0.618 |  | 64.5 | 8.632 | 8.368 | *1.364
4-42 |  | 279.3 | 1.891 | 1.457 | *0.329 |  | 300.6 | 0.935 | 0.975 | *0.116 |  | 212.4 | 2.241 | 1.973 | *0.009
4-61 |  | 168.7 | 7.753 | 7.327 | *0.854 |  | 186.6 | 6.062 | 5.729 | *1.388 |  | 114.9 | 6.922 | 6.983 | *1.654
5-7 |  | 573.2 | 4.079 | 3.704 | *0.406 |  | 632.9 | 4.775 | 4.399 | *0.242 |  | 589.9 | 4.582 | 3.841 | *0.071
5-21 |  | 445.1 | 5.687 | 5.028 | *1.654 |  | 488.2 | 5.930 | 4.931 | *1.540 |  | 505.9 | 5.582 | 4.556 | *1.044
5-62 |  | 575.7 | 6.429 | 5.659 | *1.553 |  | 645.9 | 6.114 | 5.526 | *1.118 |  | 592.3 | 5.185 | 4.788 | *1.047
6-10 |  | 1880.3 | 4.587 | 3.369 | *0.899 |  | 1404.6 | 5.327 | 4.447 | *1.101 |  | 1674.6 | 3.967 | 3.259 | *0.809
6-28 |  | 702.7 | 6.215 | 5.974 | *1.083 |  | 502.2 | 6.283 | 6.263 | *1.296 |  | 598.6 | 5.578 | 5.366 | *0.984
6-58 |  | 736.0 | 4.356 | 3.806 | *1.067 |  | 517.5 | 6.059 | 5.606 | *1.015 |  | 794.9 | 4.651 | 3.495 | *0.742
7-5 |  | 992.0 | 3.793 | 3.876 | *0.812 |  | 1277.6 | 2.216 | 2.062 | *0.272 |  | 919.6 | 4.071 | 3.771 | *1.075
7-23 |  | 1163.8 | 6.092 | 5.997 | *1.662 |  | 1466.6 | 5.974 | 5.281 | *1.206 |  | 1058.8 | 7.126 | 6.215 | *1.327
7-47 |  | 1135.7 | 7.691 | 6.703 | *2.246 |  | 1493.3 | 6.067 | 5.524 | *1.051 |  | 1031.0 | 8.798 | 7.950 | *2.866
8-3 |  | 1594.1 | 10.686 | 8.116 | *2.517 |  | 1740.7 | 9.527 | 7.545 | *1.922 |  | 1077.0 | 13.622 | 10.734 | *2.893
8-53 |  | 1041.5 | 6.370 | 5.954 | *1.625 |  | 1107.4 | 5.501 | 5.821 | *1.518 |  | 752.1 | 7.790 | 7.627 | *2.153
8-77 |  | 2499.8 | 5.215 | 4.627 | *1.302 |  | 2669.8 | 4.973 | 4.097 | *1.163 |  | 1861.2 | 6.300 | 4.572 | *1.253
9-20 |  | 2277.7 | 5.016 | 4.463 | *1.343 |  | 1964.0 | 5.258 | 5.149 | *1.170 |  | 1959.1 | 6.745 | 6.119 | *2.360
9-47 |  | 2868.8 | 6.328 | 4.602 | *1.956 |  | 2048.5 | 6.802 | 5.562 | *1.512 |  | 2312.4 | 6.872 | 5.587 | *1.624
9-62 |  | 3189.2 | 4.428 | 4.091 | *1.275 |  | 2316.4 | 5.602 | 4.744 | *1.526 |  | 2609.0 | 4.345 | 3.926 | *0.947
10-7 |  | 4216.6 | 5.468 | 5.133 | *2.104 |  | 4675.7 | 4.641 | 4.449 | *1.545 |  | 4010.0 | 5.551 | 5.095 | *1.859
10-13 |  | 3721.5 | 4.347 | 4.032 | *1.152 |  | 4107.9 | 4.741 | 4.474 | *1.548 |  | 3522.7 | 4.906 | 4.490 | *1.417
10-31 |  | 1100.6 | 8.086 | 8.739 | *1.873 |  | 1249.2 | 5.754 | 6.423 | *1.094 |  | 1041.7 | 6.940 | 7.985 | *1.382
11-21 |  | 1948.8 | 5.689 | 5.640 | *1.829 |  | 1940.4 | 5.596 | 5.714 | *1.757 |  | 2050.3 | 5.098 | 4.992 | *1.648
11-56 |  | 3322.7 | 5.332 | 4.479 | *1.307 |  | 3291.5 | 5.616 | 5.364 | *1.741 |  | 3452.8 | 4.922 | 4.790 | *1.473
11-63 |  | 3504.1 | 4.215 | 4.112 | *1.296 |  | 3312.6 | 4.210 | 4.106 | *1.008 |  | 3670.2 | 3.747 | 3.788 | *0.900
12-14 |  | 3625.5 | 4.608 | 4.575 | *1.365 |  | 2998.5 | 4.821 | 5.534 | *1.807 |  | 2781.7 | 6.100 | 5.753 | *2.273
12-36 |  | 5705.1 | 3.695 | 3.216 | *1.549 |  | 4798.6 | 4.066 | 3.667 | *1.820 |  | 5923.6 | 3.240 | 3.124 | *1.236
12-80 |  | 4447.2 | 5.204 | 4.647 | *2.377 |  | 3754.3 | 5.471 | 5.201 | *2.299 |  | 3534.2 | 5.557 | 5.138 | *2.620
15-2 |  | 6311.7 | 2.411 | 2.192 | *1.555 |  | 7051.6 | 3.569 | 3.568 | *3.032 |  | 5905.5 | 2.888 | 2.977 | *2.104
15-3 |  | 7074.2 | 3.101 | 3.040 | *1.102 |  | 8037.3 | 2.679 | 2.814 | *1.449 |  | 6630.9 | 3.497 | 3.397 | *1.511
15-5 |  | 5753.9 | 4.440 | 4.115 | *1.766 |  | 6473.3 | 6.295 | 5.637 | *3.051 |  | 5431.4 | 4.227 | 4.047 | *1.682
20-2 |  | 13838.7 | 3.476 | 3.375 | *2.390 |  | 13081.1 | 2.433 | 2.402 | *1.347 |  | 12956.3 | 3.272 | 3.372 | *2.110
20-5 |  | 22944.5 | 4.050 | 3.861 | *2.593 |  | 21584.8 | 3.658 | 3.912 | *2.586 |  | 21684.4 | 2.997 | 2.975 | *1.512
20-6 |  | 12518.9 | 3.399 | 3.142 | *2.205 |  | 11895.5 | 1.884 | 2.172 | *1.169 |  | 11880.4 | 1.851 | 1.780 | *1.014
$\\#$ best |  | 36 | 0 | 0 | 36 |  | 35 | 0 | 0 | 36 |  | 36 | 0 | 0 | 36

The results in Tables II and III are summarised in Figure 6. The figure shows
the performance of each algorithm (ACS, SACS and APSA) by uncertainty levels.
The bars represent the average of percentage difference to best across all
instances in an uncertainty level. As expected, APSA clearly outperforms the
other two methods, with a slight advantage with increasing uncertainty levels.

Figure 5: Comparison of ACS, SACS and APSA by uncertainty levels.

###  V-B Convergence Characteristics of APSA

APSA outperforms SACS and ACS across all problem instances for all uncertainty
levels, due to its ability to diversify well. In particular, APSA’s ability to
stop getting stuck in local optima leads to substantial gains.

In the following, we examine the convergence of APSA, and compare it to ACS
and SACS. We choose four problem instances, which are sufficiently diverse in
size to allow making somewhat general inferences about APSA. The results are
shown in Figure 6, where each sub-figure corresponds to one problem instance.
The plots show time in seconds on the x-axis and TWT (logarithmic scale) on
the y-axis.

Figure 6: Convergence profiles of ACS, SACS and APSA on four RCJSU problem
instances of different sizes. The instances chosen are 3–53, 6–28, 9–47 and
12–14. The TWTs on the y-axes are presented on a logarithmic scale.

Again, APSA is clearly the best performing method across all four problem
instances. There are two main advantages of the algorithm, especially related
to the population and diversification. Firstly, the starting solution,
irrespective of the problem instance, is better than ACS or SACS. This can be
attributed to the population, where at the beginning of the search process,
there is a substantial amount of diversity in the starting solutions.
Secondly, and more importantly, there is continuous improvement in APSA over-
time. This can be clearly seen for medium to large problem instances (6–28,
9–47 and 12–14). The increased diversity allowed by the re-initialisation of
the solutions in the population ensures that the population does not get stuck
in local optima.

###  V-C Comparisons of APSA to the original SA ([4])

The original SA (OSA) algorithm [4] can be adapted to tackle the RCJSU
problem.666Full details of the algorithm can be found in [4], and due to space
limitations, we do not provide the full algorithm or its description here. The
main difference is that every time a new solution is created, a new objective
needs to be computed, which involves creating multiple schedules corresponding
to the samples. Otherwise, all the settings for the algorithm remain the same.

TABLE IV: A comparison of PSA and the original SA [4] (SAO) for the
uncertainty levels of 0.6 and 0.9.

|  | 0.6 |  | 0.9
---|---|---|---|---
|  | Best | APSA | SAO |  | Best | APSA | SAO
3-5 |  | 942.64 | 0.05 | 0.03 |  | 949.18 | 0.00 | 0.00
3-23 |  | 232.48 | 0.14 | 0.62 |  | 232.24 | 0.00 | 0.09
3-53 |  | 213.37 | 0.00 | 0.00 |  | 212.45 | 0.00 | 0.00
4-28 |  | 127.92 | 1.19 | 2.19 |  | 113.26 | 0.62 | 1.28
4-42 |  | 361.12 | 0.22 | 0.47 |  | 300.61 | 0.12 | 0.10
4-61 |  | 213.24 | 0.23 | 1.02 |  | 186.58 | 1.39 | 2.69
5-7 |  | 673.31 | 0.37 | 1.15 |  | 632.89 | 0.24 | 0.68
5-21 |  | 535.80 | 0.65 | 2.87 |  | 488.18 | 1.54 | 3.14
5-62 |  | 688.01 | 1.15 | 3.25 |  | 645.89 | 1.12 | 3.79
6-10 |  | 2026.29 | 1.61 | 2.65 |  | 1404.63 | 1.10 | 2.96
6-28 |  | 762.44 | 1.23 | 2.33 |  | 502.18 | 1.30 | 2.53
6-58 |  | 798.97 | 1.06 | 2.30 |  | 517.45 | 1.01 | 3.37
7-5 |  | 1025.49 | 0.72 | 1.82 |  | 1277.61 | 0.27 | 0.81
7-23 |  | 1194.27 | 1.78 | 4.06 |  | 1466.58 | 1.21 | 2.60
7-47 |  | 1191.50 | 1.46 | 4.30 |  | 1493.28 | 1.05 | 4.49
8-3 |  | 1995.45 | 2.84 | 6.84 |  | 1740.71 | 1.92 | 5.11
8-53 |  | 1250.50 | 1.18 | 3.11 |  | 1107.35 | 1.52 | 3.26
8-77 |  | 2971.52 | 1.13 | 2.74 |  | 2669.8 | 1.16 | 2.52
9-20 |  | 2086.08 | 1.23 | 3.23 |  | 1964.04 | 1.17 | 3.13
9-47 |  | 2640.36 | 1.99 | 3.98 |  | 2048.54 | 1.51 | 3.95
9-62 |  | 2969.09 | 0.87 | 2.42 |  | 2316.43 | 1.53 | 3.47
10-7 |  | 5602.57 | 1.41 | 2.59 |  | 4675.71 | 1.55 | 3.14
10-13 |  | 4932.81 | 1.61 | 2.56 |  | 4107.91 | 1.55 | 3.15
10-31 |  | 1525.30 | 1.21 | 2.42 |  | 1249.17 | 1.09 | 3.05
11-21 |  | 2402.84 | 0.99 | 2.69 |  | 1940.39 | 1.76 | 3.46
11-56 |  | 4046.64 | 1.19 | 2.54 |  | 3291.52 | 1.74 | 3.09
11-63 |  | 4196.87 | 1.68 | 2.69 |  | 3312.59 | 1.01 | 1.94
12-14 |  | 4378.29 | 1.94 | 2.56 |  | 2998.54 | 1.81 | 3.21
12-36 |  | 6821.22 | 1.78 | 2.23 |  | 4798.61 | 1.82 | 2.52
12-80 |  | 5310.08 | 2.00 | 2.11 |  | 3754.28 | 2.30 | 3.13
15-2 |  | 7554.56 | 2.87 | 2.27 |  | 7144.34 | 1.69 | 2.04
15-3 |  | 8585.22 | 2.01 | 2.20 |  | 8037.26 | 1.45 | 1.41
15-5 |  | 7021.04 | 2.43 | 2.71 |  | 6473.33 | 3.05 | 3.68
20-2 |  | 13813.10 | 3.47 | 3.42 |  | 13081.1 | 1.35 | 2.21
20-5 |  | 23175.30 | 2.42 | 3.53 |  | 21584.8 | 2.59 | 2.98
20-6 |  | 12713.50 | 1.90 | 2.13 |  | 11895.5 | 1.17 | 1.03
$\\#$ best |  |  | 32 | 2 |  |  | 31 | 3

Table IV shows the results for APSA and OSA considering the uncertainty levels
0.6 and 0.9. Other than the smallest problem instances (3 machines), APSA
clearly is superior, finding better average solutions ($>$ 85$\%$) across both
uncertainty levels.

###  V-D Comparison of APSA with SA

The novel components of APSA including the population of solutions, adaptive
probabilistic selection and quicker cooling schedule clearly lead to
significant gains over traditional OSA. In this section, we aim to understand
the impacts of the population on APSA. This essentially involves an
implementation of APSA with a population size of 1.

TABLE V: A comparison of PSA and SA for the uncertainty levels of 0.6 and 0.9.

|  | 0.6 |  | 0.9
---|---|---|---|---
|  | Best | PSA | SA |  | Best | PSA | SA
3-5 |  | 942.64 | 0.05 | 0.02 |  | 949.18 | 0.00 | 0.00
3-23 |  | 232.48 | 0.14 | 0.19 |  | 232.24 | 0.00 | 0.00
3-53 |  | 213.37 | 0.00 | 0.00 |  | 212.45 | 0.00 | 0.00
4-28 |  | 127.92 | 1.19 | 0.85 |  | 113.26 | 0.62 | 0.68
4-42 |  | 361.12 | 0.22 | 0.14 |  | 300.61 | 0.12 | 0.10
4-61 |  | 213.24 | 0.23 | 0.24 |  | 186.15 | 1.62 | 1.58
5-7 |  | 673.31 | 0.37 | 0.40 |  | 632.89 | 0.24 | 0.27
5-21 |  | 534.38 | 0.92 | 1.31 |  | 487.22 | 1.74 | 1.70
5-62 |  | 688.01 | 1.15 | 1.53 |  | 645.89 | 1.12 | 1.69
6-10 |  | 2026.29 | 1.61 | 1.52 |  | 1401.94 | 1.29 | 1.35
6-28 |  | 762.44 | 1.23 | 1.28 |  | 501.61 | 1.41 | 1.24
6-58 |  | 798.94 | 1.06 | 1.23 |  | 514.92 | 1.51 | 1.44
7-5 |  | 1025.15 | 0.76 | 0.93 |  | 1277.4 | 0.29 | 0.29
7-23 |  | 1194.27 | 1.78 | 2.08 |  | 1463.78 | 1.40 | 1.62
7-47 |  | 1184.72 | 2.04 | 2.21 |  | 1482.06 | 1.82 | 2.62
8-3 |  | 1995.45 | 2.84 | 3.88 |  | 1740.22 | 1.95 | 2.12
8-53 |  | 1245.14 | 1.62 | 1.81 |  | 1107.35 | 1.52 | 1.70
8-77 |  | 2971.52 | 1.13 | 1.14 |  | 2669.8 | 1.16 | 1.48
9-20 |  | 2081.38 | 1.46 | 1.58 |  | 1957.18 | 1.52 | 1.67
9-47 |  | 2634.12 | 2.23 | 2.57 |  | 2042.29 | 1.82 | 2.92
9-62 |  | 2960.89 | 1.15 | 1.37 |  | 2316.43 | 1.53 | 1.72
10-7 |  | 5578.66 | 1.84 | 1.74 |  | 4675.71 | 1.55 | 2.03
10-13 |  | 4911.50 | 2.05 | 1.89 |  | 4107.3 | 1.56 | 2.06
10-31 |  | 1516.59 | 1.79 | 1.35 |  | 1249.17 | 1.09 | 1.36
11-21 |  | 2370.51 | 2.37 | 2.28 |  | 1940.39 | 1.76 | 2.01
11-56 |  | 4010.97 | 2.09 | 2.01 |  | 3291.52 | 1.74 | 2.09
11-63 |  | 4196.87 | 1.68 | 1.48 |  | 3300.36 | 1.38 | 1.23
12-14 |  | 4375.23 | 2.01 | 1.69 |  | 2998.54 | 1.81 | 2.01
12-36 |  | 6782.42 | 2.36 | 2.27 |  | 4777.3 | 2.27 | 2.25
12-80 |  | 5224.42 | 3.68 | 3.13 |  | 3719.45 | 3.26 | 3.75
15-2 |  | 7538.83 | 3.09 | 3.39 |  | 7038.4 | 3.23 | 2.90
15-3 |  | 8514.53 | 2.85 | 2.48 |  | 7929.08 | 2.83 | 2.43
15-5 |  | 7020.24 | 2.44 | 2.25 |  | 6473.33 | 3.05 | 3.09
20-2 |  | 13893.20 | 2.87 | 3.46 |  | 13081.1 | 1.35 | 1.64
20-5 |  | 23173.90 | 2.43 | 3.50 |  | 21584.8 | 2.59 | 2.81
20-6 |  | 12617.80 | 2.67 | 2.93 |  | 11707.5 | 2.79 | 2.84
$\\#$ best |  |  | 21 | 15 |  |  | 27 | 9

The results can be seen in Table V, where comparisons are made for the
uncertainty levels 0.6 and 0.9. We see that there is a clear advantage of the
population, and the advantage increases with the higher uncertainty levels.

###  V-E Comparisons on the Deterministic Problem

APSA’s advantages obtained from the population, a quicker cooling schedule and
adaptive probabilistic selection for the perturbation of solutions, make for
an effective algorithm in the uncertain setting. Its performance on the
deterministic problem or RCJS is worth investigating, to see if any of the
novelties proposed in the algorithm can be beneficial for the deterministic
problem. The results are shown in table VI, where APSA to ACS, SACS, and a
column generation and ACO hybrid (CGACO) are compared.

TABLE VI: A comparison of CGACO [7], ACS, SACS and PSA on RCJS. Statistical
significance was obtained using a pair-wise Wilcoxon ranked-sum test, with
significant results at a 95$\%$ confidence interval highlighted in bold.

|  | CGACO |  | ACS |  | SACS |  | PSA
---|---|---|---|---|---|---|---|---
Instance |  | Best | Mean | SD |  | Best | Mean | SD |  | Best | Mean | SD |  | Best | Mean | SD
Instance |  | Best | Mean | SD |  | Best | Mean | SD |  | Best | Mean | SD |  | Best | Mean | SD
3 - 5 |  | 515.68 | 520.30 | 6.16 |  | 505.00 | 505.00 | 0.00 |  | 505.00 | 505.00 | 0.00 |  | 505.00 | 505.00 | 0.00
3 - 23 |  | 149.07 | 150.04 | 1.09 |  | 149.07 | 149.09 | 0.08 |  | 149.07 | 149.11 | 0.12 |  | 149.07 | 149.07 | 0.00
3 - 53 |  | 69.36 | 69.36 | 0.00 |  | 69.36 | 69.36 | 0.00 |  | 69.36 | 69.36 | 0.00 |  | 69.36 | 69.36 | 0.00
4 - 28 |  | 23.90 | 23.90 | 0.00 |  | 23.94 | 24.04 | 0.09 |  | 23.94 | 24.00 | 0.06 |  | 23.81 | 23.81 | 0.00
4 - 42 |  | 68.59 | 71.26 | 3.01 |  | 66.73 | 66.73 | 0.00 |  | 66.73 | 66.73 | 0.00 |  | 66.07 | 66.36 | 0.33
4 - 61 |  | 47.69 | 47.98 | 0.23 |  | 45.96 | 45.96 | 0.00 |  | 45.96 | 45.96 | 0.00 |  | 45.96 | 45.96 | 0.00
5 - 7 |  | 260.15 | 275.00 | 17.65 |  | 256.76 | 267.40 | 5.43 |  | 256.69 | 262.81 | 4.29 |  | 252.90 | 253.37 | 0.18
5 - 21 |  | 177.27 | 177.27 | 0.00 |  | 168.63 | 169.21 | 0.92 |  | 168.63 | 168.79 | 0.39 |  | 168.63 | 168.63 | 0.00
5 - 62 |  | 264.99 | 276.22 | 13.75 |  | 259.15 | 266.35 | 5.17 |  | 259.12 | 266.37 | 5.43 |  | 250.51 | 252.63 | 2.62
6 - 10 |  | 1031.40 | 1031.40 | 0.00 |  | 874.90 | 891.58 | 9.87 |  | 870.83 | 887.66 | 8.29 |  | 831.23 | 843.86 | 6.11
6 - 28 |  | 241.28 | 241.28 | 0.00 |  | 230.04 | 239.48 | 5.35 |  | 225.53 | 236.04 | 5.87 |  | 218.37 | 222.03 | 1.91
6 - 58 |  | 264.33 | 268.87 | 4.72 |  | 248.01 | 255.63 | 3.34 |  | 241.04 | 251.53 | 4.52 |  | 238.84 | 240.65 | 0.60
7 - 5 |  | 488.17 | 502.07 | 20.37 |  | 445.18 | 460.07 | 6.51 |  | 445.82 | 459.88 | 5.91 |  | 418.06 | 429.25 | 7.87
7 - 23 |  | 655.52 | 658.40 | 2.55 |  | 587.96 | 604.99 | 10.14 |  | 577.88 | 595.26 | 8.20 |  | 553.91 | 570.05 | 8.24
7 - 47 |  | 543.82 | 547.21 | 11.49 |  | 472.24 | 502.76 | 12.45 |  | 470.42 | 497.73 | 11.80 |  | 428.51 | 453.82 | 12.17
8 - 3 |  | 911.22 | 1010.67 | 111.72 |  | 725.49 | 768.23 | 15.77 |  | 721.80 | 746.00 | 14.32 |  | 622.92 | 669.74 | 17.23
8 - 53 |  | 522.59 | 522.58 | 0.00 |  | 494.32 | 507.07 | 6.56 |  | 487.27 | 501.04 | 6.56 |  | 455.45 | 470.12 | 7.38
8 - 77 |  | 1610.28 | 1648.35 | 67.75 |  | 1281.98 | 1311.84 | 14.88 |  | 1265.41 | 1298.44 | 14.54 |  | 1208.54 | 1235.36 | 14.73
9 - 20 |  | 1017.43 | 1023.07 | 5.42 |  | 999.95 | 1026.94 | 13.00 |  | 991.70 | 1014.82 | 12.15 |  | 932.37 | 953.10 | 13.71
9 - 47 |  | 1564.69 | 1715.26 | 178.01 |  | 1290.84 | 1382.97 | 31.23 |  | 1325.49 | 1362.21 | 14.96 |  | 1226.35 | 1284.73 | 22.42
9 - 62 |  | 1730.74 | 1804.20 | 95.07 |  | 1549.98 | 1578.38 | 15.15 |  | 1546.42 | 1572.67 | 11.82 |  | 1449.69 | 1490.92 | 20.10
10 - 7 |  | 2979.79 | 3108.48 | 125.12 |  | 2731.54 | 2806.54 | 32.56 |  | 2709.76 | 2782.76 | 27.75 |  | 2567.60 | 2657.63 | 37.67
10 - 13 |  | 2573.10 | 2649.91 | 94.07 |  | 2337.86 | 2389.39 | 26.48 |  | 2304.22 | 2353.62 | 23.97 |  | 2210.89 | 2264.51 | 29.62
10 - 31 |  | 674.48 | 674.48 | 0.00 |  | 665.47 | 700.52 | 13.95 |  | 663.87 | 702.88 | 15.53 |  | 620.08 | 639.33 | 8.39
11 - 21 |  | 1100.04 | 1130.03 | 24.62 |  | 1075.88 | 1132.02 | 22.93 |  | 1075.24 | 1119.88 | 18.19 |  | 1032.07 | 1057.54 | 15.66
11 - 56 |  | 2072.37 | 2216.39 | 192.02 |  | 2009.59 | 2077.04 | 26.14 |  | 1979.92 | 2044.09 | 29.91 |  | 1872.61 | 1946.54 | 35.84
11 - 63 |  | 2360.96 | 2362.08 | 0.70 |  | 2135.00 | 2193.68 | 28.26 |  | 2132.93 | 2182.86 | 23.47 |  | 2029.50 | 2077.91 | 23.15
12 - 14 |  | 2257.65 | 2345.85 | 55.65 |  | 1922.26 | 1983.88 | 35.70 |  | 1851.20 | 1944.55 | 29.38 |  | 1771.49 | 1879.07 | 31.24
12 - 36 |  | 3781.18 | 3966.80 | 209.41 |  | 3192.39 | 3293.29 | 41.24 |  | 3179.14 | 3250.00 | 36.68 |  | 2992.22 | 3110.58 | 44.50
12 - 80 |  | 3116.71 | 3286.07 | 138.28 |  | 2625.59 | 2697.86 | 35.31 |  | 2557.22 | 2633.16 | 40.96 |  | 2408.84 | 2520.89 | 52.05
15 - 2 |  | 5207.54 | 5353.60 | 266.67 |  | 4220.06 | 4369.19 | 68.77 |  | 4166.11 | 4276.08 | 58.83 |  | 4041.59 | 4209.96 | 86.57
15 - 3 |  | 5538.80 | 6477.89 | 800.76 |  | 4834.72 | 4967.70 | 65.56 |  | 4694.78 | 4827.35 | 50.00 |  | 4481.04 | 4629.03 | 89.13
15 - 5 |  | 4560.35 | 4942.42 | 649.77 |  | 3794.91 | 3901.78 | 55.80 |  | 3729.25 | 3825.77 | 56.47 |  | 3496.33 | 3612.27 | 61.85
20 - 2 |  | 10959.00 | 10959.00 | 0.00 |  | 9301.75 | 9536.87 | 104.95 |  | 9076.52 | 9317.65 | 108.35 |  | 8832.93 | 9214.97 | 171.43
20 - 5 |  | 20813.00 | 20813.00 | 0.00 |  | 15595.70 | 16020.42 | 296.60 |  | 15226.80 | 15664.50 | 244.66 |  | 14590.60 | 15304.66 | 281.96
20 - 6 |  | 8789.68 | 9658.98 | 542.10 |  | 8176.13 | 8371.80 | 100.00 |  | 8057.20 | 8245.80 | 92.95 |  | 7905.06 | 8212.50 | 159.31

CGACO is also run 25 times on each problem instance. A single sample was used
for ACS, SACS and APSA, leading to the original resource limit (effectively
RCJS). We see in Table VI that beyond small problem instances ($>$ 4
machines), APSA has a clear advantage. It generally performs best, but without
the same large gains seen on RCJSU.

##  VI Conclusion

This study investigates an optimisation problem that originates in the mining
industry, specifically transporting ore from mines to ports. Past studies have
considered the problem as deterministic, however, in real settings, the
resources needed to transport the ore are subject to uncertainty. The problem
is also called resource constrained job scheduling with uncertainty, where for
this study, we consider multiple uncertain scenarios. To tackle this problem,
we propose an adaptive population-based simulated approach, which has
significant advantages over previously proposed ACO based approaches. We find
that using a population, increasing the rate of the cooling schedule within
the Metropolis-Hastings algorithm and adaptively selecting intensification and
diversification via the neighbourhood moves, proves advantageous. These
modifications, compared to traditional simulated annealing, lead to finding
robust solutions, and hence, best results on a benchmark dataset for RCJSU.

Despite the success of APSA on RCJSU, investigating how the approach performs
on other optimisation problems with uncertainty will be of interest in future
work. In particular, it is expected an adaptation of APSA is likely to be
effective for problems that consist of highly constrained disjoint feasible
regions, such as RCJSU.

The MIP model in Section III is clearly too complex and large for existing
solvers, but decomposition approaches such as column generation or Benders’
decomposition may prove effective. The advantage of such methods is that they
can provide guarantees of solution quality (via lower bounds to RCJSU), which
can help to measure the quality of the solutions found by APSA.

## References

  * [1] M. C. of Australia, “Mining is the Largest Contributor to Australian Economy in 2019-20,” 2020, available from: https://www.minerals.org.au/news/mining-largest-contributor-australian-economy-2019-20.
  * [2] G. Singh and R. Weiskircher, “Collaborative resource constraint scheduling with a fractional shared resource,” in _IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology_ , vol. 2. IEEE, 2008, pp. 359–365.
  * [3] ——, “A Multi-Agent System for Decentralised Fractional Shared Resource Constraint Scheduling,” _Web Intelligence and Agent Systems_ , vol. 9, no. 2, pp. 99–108, 2011.
  * [4] G. Singh and A. T. Ernst, “Resource Constraint Scheduling with a Fractional Shared Resource,” _Operations Research Letters_ , vol. 39, no. 5, pp. 363 – 368, 2011.
  * [5] A. T. Ernst and G. Singh, “Lagrangian particle swarm optimization for a resource constrained machine scheduling problem,” in _2012 IEEE Congress on Evolutionary Computation_ , June 2012, pp. 1–8.
  * [6] D. Thiruvady, G. Singh, A. T. Ernst, and B. Meyer, “Constraint-based ACO for a Shared Resource Constrained Scheduling Problem,” _International Journal of Production Economics_ , vol. 141, no. 1, pp. 230–242, 2012.
  * [7] D. Thiruvady, G. Singh, and A. T. Ernst, “Hybrids of integer programming and aco for resource constrained job scheduling,” in _Hybrid Metaheuristics: 9th International Workshop, HM 2014_ , M. J. Blesa, C. Blum, and S. Voß, Eds., vol. 8457. Hamburg: LNCS, 2014, pp. 130–144.
  * [8] D. Thiruvady, A. T. Ernst, and G. Singh, “Parallel ant colony optimization for resource constrained job scheduling,” _Annals of Operations Research_ , vol. 242, no. 2, pp. 355–372, July 2016.
  * [9] D. Cohen, A. Gómez-Iglesias, D. Thiruvady, and A. T. Ernst, “Resource constrained job scheduling with parallel constraint-based aco,” in _Artificial Life and Computational Intelligence_ , M. Wagner, X. Li, and T. Hendtlass, Eds. Cham: Springer International Publishing, 2017, pp. 266–278.
  * [10] S. Nguyen, M. Zhang, and K. C. Tan, “Adaptive charting genetic programming for dynamic flexible job shop scheduling,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , ser. GECCO ’18. New York, NY, USA: ACM, 2018, pp. 1159–1166.
  * [11] S. Nguyen, D. Thiruvady, A. T. Ernst, and D. Alahakoon, “A Hybrid Differential Evolution Algorithm with Column Generation for Resource Constrained Job Scheduling,” _Computers & Operations Research_, vol. 109, pp. 273–287, 2019.
  * [12] S. Nguyen and D. Thiruvady, “Evolving Large Reusable Multi-pass Heuristics for Resource Constrained Job Scheduling,” in _2020 IEEE Congress on Evolutionary Computation (CEC)_ , 2020, pp. 1–8.
  * [13] D. Thiruvady, C. Blum, and A. T. Ernst, “Solution Merging in Matheuristics for Resource Constrained Job Scheduling,” _Algorithms_ , vol. 13, no. 10, pp. 256–287, Oct 2020.
  * [14] C. Blum, D. Thiruvady, A. T. Ernst, M. Horn, and G. Raidl, “A Biased Random Key Genetic Algorithm with Rollout Evaluations for the Resource Constraint Job Scheduling Problem,” in _AI 2019: Advances in Artificial Intelligence_ , J. Liu and J. Bailey, Eds. Cham: Springer International Publishing, 2019, pp. 549–560.
  * [15] S. Nguyen, D. Thiruvady, M. Zhang, and D. Alahakoon, “Automated design of multipass heuristics for resource-constrained job scheduling with self-competitive genetic programming,” _IEEE Transactions on Cybernetics_ , pp. 1–14, 2021.
  * [16] D. Thiruvady, S. Nguyen, F. Shiri, N. Zaidi, and X. Li, “Surrogate-assisted Population Based ACO for Resource Constrained Job Scheduling with Uncertainty,” _Swarm and Evolutionary Computation_ , vol. 69, p. 101029, 2022.
  * [17] Y.-S. Ong, M. H. Lim, and X. Chen, “Memetic computation-past, present & future,” _IEEE Computational Intelligence Magazine_ , vol. 5, no. 2, pp. 24–31, 2010.
  * [18] H. H. Hoos and T. Stützle, _Stochastic Local Search Algorithms: An Overview_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, pp. 1085–1105.
  * [19] J. C. Beck and N. Wilson, “Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations,” _Journal of Artificial Intelligence Research_ , vol. 28, p. 183–232, 2007.
  * [20] W. Song, D. Kang, J. Zhang, Z. Cao, and H. Xi, “A sampling approach for proactive project scheduling under generalized time-dependent workability uncertainty,” _Journal of Artificial Intelligence Research_ , vol. 64, no. 1, p. 385–427, Jan. 2019.
  * [21] C. Bierwirth and D. C. Mattfeld, “Production scheduling and rescheduling with genetic algorithms,” _Evolutionary Computation_ , vol. 7, no. 1, pp. 1–17, Mar. 1999.
  * [22] D.-J. Wang, F. Liu, Y.-Z. Wang, and Y. Jin, “A knowledge-based evolutionary proactive scheduling approach in the presence of machine breakdown and deterioration effect,” _Knowledge-Based Systems_ , vol. 90, pp. 70 – 80, 2015.
  * [23] K. Gao, F. Yang, M. Zhou, Q. Pan, and P. N. Suganthan, “Flexible Job-Shop Rescheduling for New Job Insertion by Using Discrete Jaya Algorithm,” _IEEE Transactions on Cybernetics_ , vol. 49, no. 5, pp. 1944–1955, 2019\.
  * [24] D. Wang, Y. Yin, and Y. Jin, _Rescheduling Under Disruptions in Manufacturing Systems: Models and Algorithms_. Springer, 2020.
  * [25] T. Chaari, S. Chaabane, N. Aissani, and D. Trentesaux, “Scheduling Under Uncertainty: Survey and Research Directions,” in _2014 International conference on advanced logistics and transport (ICALT)_. IEEE, 2014, pp. 229–234.
  * [26] D. Ouelhadj and S. Petrovic, “A survey of dynamic scheduling in manufacturing systems,” _Journal of Scheduling_ , vol. 12, no. 4, p. 417–431, 2008.
  * [27] W. Herroelen and R. Leus, “Project Scheduling Under Uncertainty: Survey and Research Potentials,” _European journal of operational research_ , vol. 165, no. 2, pp. 289–306, 2005.
  * [28] E. Demeulemeester and W. Herroelen, _Robust Project Scheduling_. Now Publishers Inc, 2011, vol. 9.
  * [29] O. Lambrechts, E. Demeulemeester, and W. Herroelen, “Time Slack-based Techniques for Robust Project Scheduling Subject to Resource Uncertainty,” _Annals of operations Research_ , vol. 186, no. 1, pp. 443–464, 2011.
  * [30] M. Masmoudi and A. Haït, “Project Scheduling Under Uncertainty Using Fuzzy Modelling and Solving Techniques,” _Engineering Applications of Artificial Intelligence_ , vol. 26, no. 1, pp. 135–149, 2013.
  * [31] V. Khodakarami, N. Fenton, and M. Neil, “Project Scheduling: Improved Approach to Incorporate Uncertainty Using Bayesian Networks,” _Project Management Journal_ , vol. 38, no. 2, pp. 39–49, 2007.
  * [32] H. Moradi and S. Shadrokh, “A Robust Scheduling for the Multi-mode Project Scheduling Problem with a Given Deadline Under Uncertainty of Activity Duration,” _International Journal of Production Research_ , vol. 57, no. 10, pp. 3138–3167, 2019.
  * [33] R. K. Chakrabortty, R. A. Sarker, and D. L. Essam, “Resource constrained project scheduling with uncertain activity durations,” _Computers & Industrial Engineering_, vol. 112, pp. 537–550, 2017.
  * [34] R. Kolisch and A. Sprecher, “Psplib - a project scheduling problem library: Or software - orsep operations research software exchange program,” _European Journal of Operational Research_ , vol. 96, no. 1, pp. 205–216, 1997.
  * [35] S. Luke, _Essentials of Metaheuristics_ , 2nd ed. Lulu, 2013, available for free at http://cs.gmu.edu/$\sim$sean/book/metaheuristics/.
  * [36] R. Cheng, M. Gen, and Y. Tsujimura, “A tutorial survey of job-shop scheduling problems using genetic algorithms, part ii: hybrid genetic search strategies,” _Computers & Industrial Engineering_, vol. 36, no. 2, pp. 343–364, 1999.
  * [37] V. Valls, S. Quintanilla, and F. Ballestin, “Resource-constrained Project Scheduling: A Critical Activity Reordering Heuristic,” _European Journal of Operational Research_ , vol. 149, pp. 282–301, 2003\.
  * [38] R. Kolisch, “Serial and Parallel Resource-constrained Project Scheduling Methods Revisited: Theory and Computation,” _European Journal of Operational Research_ , vol. 90, no. 2, pp. 320 – 333, 1996.
  * [39] G. Optimization, “Gurobi optimizer version 5.0,” 2010, available from: http://www.gurobi.com/.