Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm

Here we present a high-level abstraction of the common aspects of instances of the problem class. This model is proposed based on the models of different problems from Oğuz et al. (2010); He et al. (2018); Verbeeck et al. (2017). Detailed specific constraints of problems are introduced in later sections.

Consider a set of jobs \(O=\{o_0,o_1,\ldots ,o_n,o_{n+1}\}\) that can be potentially scheduled, where \(o_o\) and \(o_{n+1}\) are two dummy jobs representing the start and end job in the solution sequence respectively. The order of other jobs is not fixed. Each job has a revenue \(r_i\), a processing duration time \(d_i\), and a time window \([b_i, e_i]\). Let \(x_i\) be a binary variable representing whether job \(o_i\) is selected, \(y_{ij}\) be a binary variable representing whether job \(o_i\) directly precedes job \(o_j\), \(p_i\) be a decision variable representing the start time of \(o_i\), and M be a sufficient large constant. The problem can be formulated as a mixed integer linear programming (MILP) model:subject toThe objective function (1) maximizes the total revenue of scheduled jobs. Constraints (2) restrict the time between every two adjacent jobs should be long enough for the setup, where \(s_{ij}\) is the setup time between jobs \(o_i\) and \(o_j\). The value of \(s_{ij}\) depends on i and j for the sequence-dependent setup time case (e.g., a table of setup times for all pairs of \(o_i\) and \(o_j\)) and depends on \(p_i\) and \(p_j\) for the time-dependent setup time case (e.g., a function of \(p_i\) and \(p_j\) or a table of setup times for all pairs of \(p_i\) and \(p_j\)). Constraints (3) and (4) restrict that each accepted job is succeeded by only one job and precedes only one job. Constraints (5) and (6) define the earliest and latest start time of a job. Constraints (7) restrict that the two dummy jobs, the start and end jobs must be selected. Constraints (8) and (9) define the domains of the variables \(x_i\) and \(y_{ij}\) respectively F.

Due to the large number of problem variants and solution approaches, the reader is referred to Slotnick (2011) and Gunawan et al. (2016) for comprehensive surveys on this class of over-subscribed scheduling problems with time windows and time/sequence-dependent setup times.

The order acceptance and scheduling problem (OAS) is a typical representative of this problem class. The problem happens for instance when a manufacturing system does not have the capacity to meet demand. Oğuz et al. (2010) proposed the OAS problem with a penalty for late completion, time windows and sequence-dependent setup times. The problem was approached by MIP (Cesaret et al. 2012), TS (Cesaret et al. 2012), genetic algorithm (Nguyen et al. 2015; Chen et al. 2014; Chaurasia and Singh 2017), artificial bee colony algorithm (Lin and Ying 2013; Chaurasia and Kim 2019), hyper-heuristic based methods (Nguyen 2016) and iterated local search (Silva et al. 2018). Recently, Silva et al. (2018) used Lagrangian relaxation and column generation to find tight upper bounds of problem instances.

The Earth observation satellite scheduling (EOSS) problem is another important problem instance of this problem class. In a limited scheduling horizon, the satellite can usually observe only a subset of the user-specified jobs. Besides, the transition time for the satellite to change its observation angle between two adjacent jobs is time/sequence-dependent (Lemaître et al. 2002). The time windows in the EOSS are usually much shorter than those in the OAS problem (Liu et al. 2017). Akturk and KiliÇ (1999) studied the observation scheduling problem of Hubble Space Telescope, in which the setup times jobs are sequence-dependent. A dispatching rule considering weighted shortest processing time, setup times and nearest neighbour was proposed. Liu et al. (2017) and Peng et al. (2018) studied the agile satellite observation scheduling problem with time-dependent setup times. Liu et al. (2017) proposed a mixed integer programming (MIP) method and an ALNS algorithm, where they also integrated ALNS with an insertion algorithm considering time-dependency by introducing forward/backward time slacks. Peng et al. (2018) proposed an iterated local search (ILS) algorithm. They further calculated the minimal transition time, the neighbours and earliest/latest start time of each job to accelerate the insertion.

The selected travelling salesman problem (STSP), also referred to as the orienteering problem (OP), defines a problem where the salesman visits a subset of cities to maximize the total collected reward within a limited travel time. Compared with the above two problem variants, the travelling time (i.e., setup time) between cities is much longer, and there exists a stronger correlation among cities depending on the locations of them. Existing methods include genetic algorithms (Abbaspour and Samadzadegan 2011), iterated local search (Garcia et al. 2013), MIP (Verbeeck et al. 2017), and act colony optimization (ACO) (Verbeeck et al. 2017). Verbeeck et al. (2017) proposed the time-dependent OP with time windows (TDOPTW). In their ACO metaheuristic, they used the max shift to fast determine the feasibility of an insertion, which is similar to the ideas of Peng et al. (2018).

Despite all this work, there is no method capable of finding good solutions to diverse real life instances within the available solving time. In this paper, we propose a general method which performs well on all above problem instances in terms of solution quality and running time.

Adaptive large neighbourhood search (ALNS) is one of the most promising approaches for scheduling problems (Ropke and Pisinger 2006). Since ALNS is less sensitive to the initial solution than general local search (Demir et al. 2012), the initial solution is usually generated by a simple greedy heuristic. The solution is updated by removing some jobs from the current solution with the removal operators and inserting some jobs back to the solution with the insertion operators. Multiple removal and insertion operators can be defined according to the problem characteristics. In each iteration, an adaptive mechanism based on a roulette wheel is used to select a pair of removal and insertion operators according to their weights. The weight of the operator \(w_i\) is updated 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 \) is a constant weight update parameter in [0, 1]. When a new solution is generated, it is accepted if it is better than the current solution, otherwise its acceptance is determined by a simulated annealing (SA) criterion with probability: \(\rho =\exp \left( \frac{100}{T}\left( \frac{f(S')-f(S)}{f(S)} \right) \right) \), where f(S) and \(f(S')\) are the reward of current solution S and new solution \(S'\) respectively, and T is the temperature.

Tabu search (TS) was first proposed by Glover (1986). In TS, some simple local search moves are defined to update the solutions. To prevent short-term cycling, recently visited solutions or recently used local search moves are stored in a tabu list, and may not be tried again while in the list. The forbidden solutions or moves lose their tabu status after a certain short time.

Žulj et al. (2018) proposed the first hybridization of ALNS and TS and found that a simple hybridization of these two metaheuristics outperformed both the standalone methods for the order batching problem. Their method combines the diversification capabilities of ALNS and the intensification capabilities of TS. It uses ALNS to search for better solutions and, if a certain number of ALNS iterations have passed, invokes TS. Thus ALNS and TS are alternated in a simple two-stage manner.

Although ALNS has been widely successful (Thomas and Schaus 2018), a main drawback is that its search efficiency can founder due to re-visiting recent solutions. Although in standard ALNS, large portions of the solution are destroyed and rebuilt, and it would seem less likely a previous solution would be visited than other local search algorithms with simpler moves, the probability of short cycling still exists and could be higher when ‘good’ jobs are identified and selected a lot by the algorithm. Sometimes although jobs are inserted in different orders by different insertion operators, the resulting solutions are the same. This motivates us to propose the hybrid algorithm of ALNS and TS.

As noted earlier, Žulj et al. (2018) proposed the first hybridization of ALNS and TS. However, since ALNS and TS are used in separate stages, this hybridization does not change the short-term cycling nature of ALNS. In contrast, we propose a tight integration of ALNS with TS, which includes three types of tabu heuristics: the removal tabu, the insertion tabu and the instant tabu.

Removal tabu For each job, we declare a removal tabu attribute. If a new solution is accepted, the removal of newly-inserted jobs is forbidden for the following \(\theta \) iterations; otherwise, the removal of the jobs removed in this iteration is forbidden for the following \(\theta \) iterations.

Insert tabu For each job, we declare an insertion tabu attribute. If a new solution is accepted, the reinsertion of newly-removed jobs is forbidden for the following \(\theta \) iterations. Here we do not forbid the reinsertion of the jobs inserted in this iteration if the new solution is rejected as we do in the removal tabu, because in this case the removal tabu is enough to prevent visiting a recent solution. Preventing the reinsertion of jobs can lead to a lower solution quality, because this problem attempts to schedule as many jobs as possible.

²

All the three heuristics are used in the solution update process (Algorithm 1, line 6). The removal and tabu attributes are updated in Algorithm 1, line 14. For the values of the tabu attribute \(\theta \), we follow Cordeau and Laporte (2005) and set it to a random value in \([0,\sqrt{n/2}]\), where n is the number of jobs. Since the instant tabu is used only once in one iteration, it does not have a tabu attribute.

We compare the three tabu types and the two ALNS–TS hybridizations in “Tabu search” section.

ALNS uses multiple neighbourhood operators to update solutions (Algorithm 1, lines 5–6). To make sure that the algorithm is efficient for a diverse range of problem instances with varying properties, we use the following ten generic removal operators and seven generic insertion operators, and introduce a simple but effective randomization strategy to diverse the search. These operators are adapted from Pisinger and Ropke (2007) and Demir et al. (2012) to fit our problem, while the randomization strategy is new. The randomization strategy is similar to the idea of adding noise to the insertion operators by Pisinger and Ropke (2007). However, we extend this idea to both removal and insertion operators.

The ten removal operators are:

All the jobs removed by the above removal operators and other unscheduled operators are stored in a candidate job bank. Seven insertion operators are used to sort the jobs in the job bank and insert them one by one from the top of the list back to the solution. The insertion method is introduced in “Fast insertion algorithm” section. The insertion stops until no jobs can be inserted, or the total revenue of the repaired solution plus the total revenue in the job bank (i.e., the upper bound of the new solution in this iteration) is lower than the current solution.

The seven insertion operators are:

After selecting the removal/insertion operators by the roulette wheel mentioned in “Standard ALNS and TS” section, standard ALNS ranks the jobs according to the heuristic values of the operators: e.g., for the min revenue removal operator, the revenue is regarded as the heuristic value h, the jobs are ranked in an ascending order of h, and the jobs on the top of the list are removed. In order to diverse the search, we add randomness to the heuristic values of selected certain operators: \(h \leftarrow h\times (1+r)\), where r is a random value in [0, 1]. Here we differ from the common approach of selecting jobs randomly according to a probability that depends on h, because we want to add limited randomness and while keeping emphasis on following h. Our approach here thus introduces a random component without neglecting the heuristic.

When removing and inserting a job, if the job is forbidden to be removed or inserted, the operator skips it and check the next one. However, through an aspiration criterion, the tabu status of a job can be revoked if the number of removed jobs is smaller than \(p_d\) for the removal tabu, and all other jobs that are not forbidden by tabu have been tested for insertion and there is still open space in the solution for the candidate job for the insertion tabu. This aspiration criterion ensures that there are enough jobs to remove and insert.

Besides solution cycling, a further drawback of ALNS is that it evaluates a new solution depending on the quality of the whole solution sequence. Hence, during the search process, solutions with some good parts (i.e., parts of the solution might have higher objective value while consume less time) are rejected due to the low quality of the whole sequence—thus neglecting potentially valuable in-process information. Due to the time-dependency and sequence-dependency, the quality of a solution is influenced significantly by these small parts.

Inspired by genetic algorithms, we propose the partial sequence dominance (PSD) heuristic (Algorithm 1, lines 7–9): we construct a compound solution which keeps better partial sequences from the new solution and the current solution. The partial sequence is defined in Definition 1. An example of the definition of the partial sequence is shown in Fig. 1. The quality of the partial sequence is evaluated by unit revenue: the objective function value divided by the total period of the partial sequence. If the compound solution is better than the new solution and different from the current solution, it replaces the new solution. Figure 2 shows one example of PSD. In standard ALNS, the new solution is given up. However, partial sequence 1 and partial sequence 2 of the new solution are better than the current solution. So according to PSD, we keep partial sequence 1 and partial sequence 2 of the new solution and partial sequence 3 of the current solution, and we get the compound solution, which is better than the current solution.

The detailed process of constructing a compound solution from two solutions is shown in Algorithm 2. When a new solution is produced, we partition it into multiple partial sequences. We compare each partial sequence of the new solution with the corresponding partial sequence of the current solution. The partial sequence with higher unit revenue is stored in the compound solution.

A challenge for the PSD heuristic is that one job can appear in different partial sequences of the current solution and the new solution. Thus one job might be processed twice in the compound solution. To maintain the feasibility, all the repetitive jobs in the compound solution are removed. Then the start times of jobs in the solution are updated so that all jobs in the compound solution start as early as possible.

The last algorithmic feature of the algorithm is a fast insertion algorithm, which is used to insert jobs back to the solution by the insertion operators. We first proposed this method for a scheduling problem with sequence-dependent setup times in a previous paper (He et al 2019). To make sure the algorithm is complete and clear to the reader, we give a short description of the basic ideas of the insertion algorithm, and then we generalize the fast insertion algorithm to the time-dependent case.

The fast insertion algorithm uses the following two steps to insert a candidate job. First, the feasibility of the insertion at all positions of the solution is evaluated rapidly by a concept called time slack. The time slack is the time a job can be postponed before the solution becomes infeasible. Because all the jobs in the current solution are started as early as possible, the candidate job can be inserted before a job if the time that the following job needs to be postponed is smaller than its time slack. Note that in this step, all positions at which if the candidate job is inserted and the resulting solution is the same as the current solution are also forbidden because of the new instant tabu. Then in the second step, the best possible position is selected to insert the task. We select the position which increases the least setup time and adds the least penalty to the postponed jobs in the current solution. More details of the fast insertion algorithm are given in Appendix A.

For the problems put forward in this paper, which have time-dependent setup times, there are two challenges for the above insertion algorithm: (1) how to calculate the latest start time of a job so that we can calculate its time slack? This is more complicated than the sequence-dependent case because the setup time changes with the start time; (2) how to calculate the increased setup time? We cannot know the exact increased setup time unless we calculate the start times of all the postponed jobs and the changed setup times, which is too complex. For challenge 1, we can calculate the latest start time of job \(o_i\) by solving the equation: \(p_i^{Late}=p_j^{Late}-Setup(p_i^{Late},p_j^{Late})\), where \(p_j^{Late}\) is the latest start time of the following job \(o_j\) and \(Setup(time_1,time_2)\) is a function to calculate the time-dependent setup times. However, for the problem where such an analytic function does not exist, such as the agile Earth observation satellite scheduling problem where the setup time is given by a table, the dichotomy method by Liu et al. (2017) can be used to find the latest start time of a job given the latest start time of its successor. For challenge 2, we use the increased setup time of the insertion position (e.g., if we insert candidate job \(o_c\) between \(o_i\) and \(o_j\), the increased setup time of the insertion position is \(s_{ic}+s_{cj}-s_{ij}\)) to approximate the actual increased setup time. On a time-dependent agile Earth observation satellites scheduling problem benchmark (Liu et al. 2017) and a time-dependent orienteering problem benchmark (Verbeeck et al. 2017), the average error of this approximation of the setup time is 12.43% and 16.12% respectively.

We choose three representative problem domains, the order acceptance and scheduling (OAS) problem with time windows and sequence-dependent setup times, the agile Earth observation satellite scheduling problem (AEOSS), and the time-dependent orienteering problem with time windows (TDOPTW).

We consider the OAS problem from Cesaret et al. (2012). In this problem, the setup time between two jobs is sequence-dependent. Besides, the setup of a job can only start after its release, which makes the setup constraint become: \(\max \{b_j,p_i+d_i\}+s_{ij}+(y_{ij}-1)M\le p_j\). This problem is also special because of the tardiness penalty: if a job \(o_i\) starts after its due time \(\bar{e_i}\), it receives penalty \(\omega _iT_i\) on its revenue, where \(\omega _i\) is the penalty weight and \(T_i\) is the tardiness, \(T_i=\max \{p_i-\bar{e_i},0\}\). Therefore, the objective function becomes \(\max \sum _{i=1}^n x_i(r_i-\omega _iT_i)\). We use the benchmark dataset published by Cesaret et al. (2012). Three main parameters were used to generate these instances. The first parameter is the number of jobs \(n=10,15,20,25,50,100\) and we only test the larger instances with 25, 50 and 100 jobs; the second parameter, \(\tau \), influences the length of time windows: when \(\tau \) is larger, the time windows are smaller; the third parameter, R, influences the range of the end time and the due time of time windows: when R is larger, the deadlines spread broadly, so the overlap of time windows gets smaller. Both \(\tau \) and R have five values: 0.1, 0.3, 0.5, 0.7, 0.9. Ten random instances are generated for each parameter setting, giving 750 instances in total.

We consider the AEOSS problem from Liu et al. (2017). The transition time between two adjacent jobs \(o_i\) and \(o_j\) is calculated by: \(s_{ij}=t+|A_i(p_i)-A_j(p_j)|/v\), where t is constant time for stabilizing the satellite, function \(A_i\) is represented by a table returning the angle of the satellite for observing \(o_i\) at the start time of the observation, and v is the satellite transition velocity. The scheduling horizon is 24 hours, which means there are multiple time windows for each observation job. Let \(w_i\) be the total number of time windows for job i, and k be the k-th time window of job i. The objective function becomes \(\max \sum _{i=1}^n\sum _{k=1}^{w_i} x_{ik}r_i \), where \(x_{ik}\in \{0,1\}\) is a decision variable, meaning whether the k-th time window is selected. Since each job can only be processed once, an additional constraint should be considered: \(\sum _{k=1}^{w_i}x_{ik}\le 1 \text { }\forall i \). The original dataset of AEOSS problem was not published, we generate the dataset following the configuration from Liu et al. (2017). The jobs are generated according to a uniform random distribution over two geographical regions: China and the whole world. For the Chinese area distribution mode, fifteen instances are designed and the number of jobs contained in these instances changes from 50 to 400 with an increment of 25. For the worldwide distribution mode, twelve instances are designed and the number of jobs contained in these instances changes from 50 to 600 with an increment of 50.

We consider the TDOPTW problem from Verbeeck et al. (2017). In this problem, the scheduling horizon is divided into several 15-minute time slots and for each time slot, a travelling velocity starting in this time slot is given. Therefore, the travelling time (i.e., setup time) is given by a piecewise linear function, dependent on the end time of the preceding job: \(s_{ij}=\mu (p_i+d_i) + \upsilon \), where \(\mu \) and \(\upsilon \) are two parameters, and the values of them depend on the time slot of the end time. This dataset was generated by Verbeeck et al. (2017). It has instances with job number 20, 50 and 100. For each set of instances with the same number of jobs, there are four variations in scheduling horizon \(t_{max}\) (8, 10, 12 and 14h) and three random variations in the lengths of time windows (small, medium and large). Therefore, in total there are 36 instances.

Although these are sequence/time-dependent scheduling problems with time windows, there are in fact some differences. Table 1 compares all the differences of the three problem domains we have noticed.

In this section we aim to answer the following questions: how the three tabu types perform on problem domains with varying properties; whether TS helps to avoid recent solutions; whether TS can improve the performance of ALNS on the three problem domains; whether our tight hybridization is better than the two-stage hybridization? These studies help us to understand the performance of the tabu search heuristics so that we can use them efficiently.

In the proposed algorithm, we use ten removal operators and seven insertion operators to update solutions.

We test the performance of PSD by comparing the algorithm without PSD (ALNS/TF) with ALNS/TPF. According to Fig. 10, PSD shows obvious improvements on AEOSS problems, while it does not improve the performance of the algorithm much on the OAS problem and the TDOPTW problem. There are two reasons for this. For the OAS problem and the TDOPTW problem, the solution sequences are relatively short. PSD works well when the solution sequence gets long, because more partial sequences can be ignored in the long solution sequence. The second reason is that the time windows of the OAS problem and the TDOPTW problem are relatively long. If the time window is long, one order can exist in different partial sequences in the current solution and in the new solution respectively, reducing the quality of the compound solution. This can be further proved in Fig. 11, where for the OAS problem, PSD works better when \(\tau \) is larger (i.e., when the time window is shorter).

The fast insertion algorithm contains two ideas: the time slack strategy and the best position selection strategy. We study each in turn.

First, we provide the parameter setting of the algorithm for the three problems. The use of TS, the randomized operators, PSD, and FI is set according to the conclusions of the algorithmic analysis reported in “Algorithmic analysis” section. Other parameters such as the number of jobs to remove are set empirically through some exploratory experiments. Although these parameters are not optimal for all the instances, they provide relatively good solutions. The parameters are listed in Table 3. In Table 3, \(c_a\) is the coefficient of annealing to update the temperature. The temperature at the \(i^{th}\) iteration is \(T_i=c_aT_{i-1}\). The three score increments are used for different performances of the selected operators: \(\sigma _3\) is added to the score if a new best solution is found; \(\sigma _2\) is added to the score if a new solution which is better than the current solution is found; \(\sigma _1\) is added to the score if a new solution which is worse than the current solution is found, but it is accepted by the SA criterion.

Note that among all these parameters, only the maximum iteration and the use of the instant tabu are different on the three domains, which shows the robust performance of our algorithm on diverse problem instances.

The algorithm has two terminal conditions: when the maximum iteration is reached or when all the jobs are scheduled and get the full revenue (i.e., when the upper bound is reached). The maximum iteration is set so that the algorithm has similar runtime as its competing algorithms on the three domains. For the AEOSS problem, we set another terminal condition, when the solution is not improved for continuous 1000 iterations, because the algorithm converges fast on the AEOSS domain.

The ALNS/TPF algorithm is compared with state-of-the-art algorithms including DRGA (Nguyen et al. 2015), LOS (Nguyen 2016), ABC (Lin and Ying 2013), HSSGA (Chaurasia and Singh 2017), EG/G-LS (Chaurasia and Singh 2017), and ILS (Silva et al. 2018). A MILP formulation by the CPLEX solver has been tested by Cesaret et al. (2012), which shows bad performance for large instances with more than 15 instances. Therefore we do not compare ALNS/TPF against CPLEX in this section.

Our ALNS/TPF is run on Intel Core i5 3.20 GHz CPU with 8GB memory, using a single core. The results of other methods are from the respective articles, which were obtained using different machines with Intel Core i5, i7 and Xeon CPU, 3.00–3.40 GHz, 4–16 GB memory. Besides, unmentioned details such as cache size can have a significant effect on the runtime. Hence we do not report detailed CPU time. On average, all the methods have comparable performance in terms of CPU time. According to the data reported in the references, ILS uses most time and ABC the least.

The solution quality of instances with 25–100 jobs are shown in Tables 4, 5 and 6.⁵ Regarding the solution quality, we compare the gaps of these algorithms to the upper bounds by Cesaret et al. (2012). ALNS/TPF, TDRGA, 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 other three algorithms, ABC, HSSGA and EA/G-LS are run only once for each instance. Due to this, these methods can sometimes reach the optimal solution, resulting in a lower solution gap. DRGA and LOS only reported rounded-down integer values. But it is still obvious that ALNS/TPF produces the best solutions on nearly all the instances.

We compare the proposed ALNS/TPF with our previous algorithm called ALNS/TPI (He et al. 2018), the standard ALNS (Liu et al. 2017), the ILS algorithm (Peng et al. 2018), and an MIP model from He et al. (2018). We have obtained the source codes for the standard ALNS and the ILS algorithm from the corresponding authors. All algorithms are run on an Intel Core i5 3.20 GHz CPU, 8 GB memory, running Windows 7; only a single core is used. IBM ILOG CPLEX version 12.8 is used for MIP solving. A time limit of 3600 s is set for MIP solving, which uses more than 100x as much running time as ALNS/TPF does. The results for metaheuristics are the average of ten runs.

We compare the solution quality and the CPU time. The solution quality is the percentage of the total revenue of scheduled jobs (i.e., the objective value) divided by the total revenue of all the jobs. Table 7 shows the comparison of the five different algorithms. It shows that the CPU time of the ALNS/TPF increases slowly with the increasing number of jobs, and is about ten times faster than ILS, which is the fastest one among other algorithms. The solution quality is consistently higher than that of ILS, ALNS/TPI and ALNS. As expected, MIP by CPLEX can only find optimal solutions for small-size instances but performs badly when the instance size gets large. For the four small instances with optimal solutions by CPLEX, ALNS/TPF, ALNS/TPI and ILS also find the same optimal solution. Among all the methods, the standard ALNS performs the worst, consuming a long time to produce solutions with the lowest quality. Finally, Fig. 17 shows the anytime quality of different algorithms for the instance with 600 jobs distributed worldwide (CPLEX found no feasible solution within the time limit).

Then we study how the performance gaps between ALNS/TPF and other algorithms change with the increasing number of jobs. We evaluate the performance gap between an algorithm A and ALNS/TPF by the following formula:

From Fig. 18 we can find that gaps between the performance of ALNS/TPF and those of other algorithms tend to grow when there are more jobs and when jobs are distributed densely (i.e., when the conflict among jobs is higher). The performance of the standard ALNS decreases quickly when the problem grows in size and our proposed ALNS/TPF performs well for large and difficult instances.

The ALNS/TPF algorithm is compared with the ACS algorithm by Verbeeck et al. (2017). A MILP formulation by the CPLEX solver has been tested by Verbeeck et al. (2017), which shows bad performance for large instances with more than 20 instances. Therefore we do not compare ALNS/TPF against CPLEX in this section.

Our ALNS/TPF is run on Intel Core i5-3470 3.20 GHz CPU with 8GB memory, using a single core. For the ACS method, we present the results from the respective article. Since ACS was run on a high performance computing system (48 Intel Xeon processors and 384 GB memory), the runtime of the two algorithms cannot be compared directly. We do not report detailed CPU time here.

The solution quality of this problem is evaluated by the total revenue of the solution (i.e., the value of the objective function). The total revenue of instances with 25–100 jobs is shown in Table 8. ALNS/TPF produces the best solutions on all the instances. Besides, ALNS/TPF performs much better than ACS when the instances grow in size (i.e., more jobs and longer scheduling horizon).