Sage Journals: Discover world-class research

Abstract

The no-wait job shop scheduling problem (NWJSP) plays a crucial role in industrial production and is an NP-hard problem. We propose a hybrid discrete artificial bee colony (HDABC) algorithm for solving the NWJSP with the total tardiness criterion. In the proposed algorithm, we first design multiple discrete operations which combine with the basic framework of the artificial bee colony algorithm. Furthermore, we propose a new selection method that allows onlooker bee to select better food sources. To determine the start times of the jobs, we introduce and adapt the left timetabling method for the tardiness objective under consideration. Experimental results show that the HDABC algorithm has better search capability than two well-performing ABC algorithms as well as an iterated greedy algorithm in solving the NWJSP with the total tardiness criterion.

Keywords

Job shop no-wait artificial bee colony algorithm scheduling total tardiness

Introduction

With the rapid development of manufacturing industry, the productivity and optimal utilization of resources in the job shop have attracted a lot of attention. Especially in the highly competitive market environment, the no-wait job shop scheduling problem (NWJSP) has received widespread attention. The no-wait job shop model has been used in many manufacturing industries, such as steelmaking and chemical and pharmaceutical industries.¹ These industries are characterized by the fact that products need to be processed continuously during the production process, and any waiting may lead to product quality degradation or resource waste. Therefore, research on the NWJSP is of great significance.

To solve the NWJSP, many researchers have studied and proposed various metaheuristics. Hall and Sriskandarajah² provided an overview of the NWJSP and raised the importance of the problem. Macchiaroli et al.³ proposed a new decomposition method and a two-phase tabu search algorithm for solving this problem. Schuster and Framinan⁴ proposed the variable neighborhood search algorithm and the hybrid algorithm combining genetic algorithm and simulated annealing (GASA) algorithm. Framinan and Schuster⁵ proposed complete local search with memory (CLM) and verified the superiority of the proposed algorithm. Schuster⁶ studied the NWJSP and proposed a fast tabu search algorithm. Pan and Huang⁷ designed a hybrid genetic algorithm and proved that this algorithm is superior. Bozejko and Makuchowski⁸ proposed a hybrid tabu search algorithm and obtained better results. Zhu et al.⁹ introduced limited memory for the CLM algorithm and proposed a complete local search with limited memory (CLLM). They compared the CLLM with the CLM, VNS and GASA algorithms and proved that the CLLM is comparable. Bozejko and Makuchowski¹⁰ proposed a genetic algorithm with automatic adjustment. Zhu and Li¹¹ further modified the CLLM and proposed an improved CLM (MCLM). Bürgy and Grěoflin¹² investigated the optimal job insertion problem and proposed an optimal job insertion-based heuristic for solving the NWJSP. Aitzai et al.¹³ proposed an exact method and a particular swarm optimization algorithm. They demonstrated the superiority of the proposed algorithm through comparative experiments. Li et al.¹⁴ further improved the CLM by hybridizing with variable neighborhood structure and proposed an algorithm called CLMMV. Sundar et al.¹⁵ proposed a hybrid artificial bee colony (HABC) algorithm and proved the superiority of HABC in experiments. Bürgy and Grěoflin¹⁶ proposed a local search method by extending the previously proposed an optimal job insertion-based heuristic¹² and proved the effectiveness of this method. Ying and Lin¹⁷ proposed a multistart simulated annealing with bidirectional shift timetabling (MSA-BST) algorithm and analyzed the results to show that the MSA-BST outperforms the compared algorithms. Valenzuela-Alcaraz et al.¹⁸ proposed a cooperative coevolutionary genetic algorithm integrated with a shift decoding algorithm, and proved to be competitive in solving the NWJSP. Deng et al.¹⁹ proposed a simple migrating birds optimization algorithm to explore the original instance and the inverse instance. In addition to the above studies of the makespan criterion, there have been some research on the total flow time criterion. Deng et al.²⁰ developed a hybrid discrete group search optimizer to solve the problem under the total flow time criterion. Subsequently, the population-based iterated greedy (IG) algorithm was proposed for the same problem.²¹ Ying and Lin²² proposed a backtracking multistart simulated annealing (BMSA). The results show that the BMSA has certain superiority.

The above studies mainly focus on the makespan and total flow time criterions. However, studies on the total tardiness criterion already exist for other scheduling problems, such as the two-machine scheduling problem,²³ the permutation flow shop,²⁴ the job shop scheduling problem,²⁵ the flexible job shop problem (FJSP),^26,27 and the parallel blocking flow shop scheduling problem.²⁸ The tardiness criterion reflects the degree of deviation between the completion time of the jobs and the due dates, and is closely related to production efficiency. Minimizing tardiness can effectively reduce inventory costs and improve production profits for enterprises. Therefore, this goal plays an important role in actual industrial production processes. To our knowledge, there has been little study of the NWJSP with a total tardiness criterion. For this reason, we focus on presenting an effective algorithm for minimizing total tardiness for the NWJSP in this study.

As one of the more superior algorithms nowadays, the artificial bee colony (ABC) algorithm²⁹ has been widely used in the field of scheduling since it was proposed. Pan et al.³⁰ discretized the ABC algorithm for solving the lot streaming flow shop scheduling problem. Wang et al.³¹ proposed an ABC algorithm in order to solve the FJSP. Deng et al.³² proposed a discrete ABC algorithm for the blocking flow shop scheduling problem. Zhang et al.³³ applied the ABC algorithm to the job shop problem. Gao et al.³⁴ adapted the ABC algorithm and proposed a two-stage ABC algorithm for solving the FJSP. Sundar et al.³⁵ conducted a study on the NWJSP and proposed an HABC algorithm for minimizing the makespan. Inspired by beer froth phenomenon, Sharma et al.³⁶ presented the beer froth ABC algorithm (BeF_ABC) and applied this algorithm to job shop problem. To the best of our knowledge, the research of the ABC algorithm is very limited on the NWJSP, especially for the problem with total tardiness criterion. The ABC algorithm adopts the evolutionary mechanisms of three roles, thus possessing good parallel evolution and global exploration capabilities. It is easy to embed local search mechanisms in the operations of the three roles, which makes it keep good local exploitation capability. Another advantage of the algorithm is that it has a relatively simple structure, making it easy to implement. Considering these advantages, we propose a hybrid discrete ABC (HDABC) algorithm for solving the NWJSP with total tardiness criterion. There are three phases in the HDABC algorithm, the employed bee, onlooker bee and scout bee phases. In the onlooker bee phase, we propose a new food source selection strategy. In addition, we combine the algorithm with several search strategies as a way to further improve the search capability. Like most researchers, we solve the NWJSP by decomposing it into two subproblems, sequencing and timetabling subproblems. The sequencing subproblem is solved by the HDABC algorithm. For the timetabling subproblem, we introduce a left timetabling method and apply it to all phases of the proposed HDABC.

We organize the remainder of the article as follows. The NWJSP with total tardiness criterion section describes and models the NWJSP with total tardiness criterion. The timetabling method section describes the timetabling method. The HDABC for the NWJSP section describes the HDABC algorithm designed to solve the sequencing subproblem. The computations and comparisons section conducts extensive experiments and analyzes the results of the experiments. Finally, the conclusions section summarizes the current study and indicates future work.

NWJSP with total tardiness criterion

Problem description

In the NWJSP, there are n jobs $J_{1}, J_{2}, \dots, J_{n}$ and m machines $M_{1}, M_{2}, \dots, M_{m}$ . Each job $J_{i}$ has $n_{i}$ operations $o_{i, 1}, o_{i, 2}, \dots, o_{i, n_{i}}$ . Each operation is assigned to a machine for processing and has its own processing time. Due to the no-wait constraint, each job cannot be stopped once processing has begun. Each job is processed on the corresponding machine in its own order of operation. The machine for processing is given in advance for each job operation. Each job can only be processed on one machine at a time. Each machine is allowed to process only one operation at the same moment. Each job has its own due date. If its completion time is later than the due date, there will be a tardiness for this job. The sum of tardiness for all jobs is defined as total tardiness. This study aims to find a feasible scheduling sequence that has a minimum total tardiness.

Problem formulation

Assume that the processing of job $J_{i}$ starts at time $t_{i}$ , and the time required to process the uth operation $o_{i, u}$ of job $J_{i}$ is denoted by $p_{i, u}$ , then we have the completion time of job $J_{i}$ is $C_{i} = t_{i} + \sum_{u = 1}^{n_{i}} p_{i, u}$ . In addition, suppose that all jobs $J_{i} (i = 1, 2, \dots, n)$ has its own due date $d t_{i}$ . If the completion time $C_{i}$ is greater than $d t_{i}$ , there is a tardiness. The tardiness can be obtained by $T_{i} = max (0, C_{i} - d t_{i})$ . The total tardiness is computed using equation (1).

T_{t o t} = \sum_{i = 1}^{n} T_{i}

(1)

If the uth operation

o_{i, u}

of job

J_{i}

is processed at machine

M_{k}

, the cumulative processing time of job

J_{i}

on machine

M_{k}

P_{i}^{k} = \sum_{a = 1}^{u} p_{i, a}

. Let

p_{i}^{k}

denote the time to process job

J_{i}

on machine

M_{k}

, namely time of operation

o_{i, u}

. According to the Zhu and Li,¹¹ if the two jobs

J_{i}

and

J_{j}

do not conflict on machine

M_{k}

, then the start times

t_{i}

and

t_{j}

have to satisfy equation (2).

t_{j} - t_{i} \in (- \infty, P_{i}^{k} - P_{j}^{k} - p_{i}^{k}] \cup [P_{i}^{k} - P_{j}^{k} + p_{j}^{k}, + \infty)

(2)

The

t_{i}

and

t_{j}

are feasible if and only if the start times

t_{i}

and

t_{j}

of the jobs

J_{i}

and

J_{j}

satisfy equation (2) on all machines. Therefore, there are feasible time difference sets

F_{i, j}

such that

t_{j} - t_{i} \in F_{i, j}

F_{i, j}

is computed using equation (3).

F_{i, j} = ⋂_{k = 1}^{k \leq m} (- \infty, P_{i}^{k} - P_{j}^{k} - p_{i}^{k}] \cup [P_{i}^{k} - P_{j}^{k} + p_{j}^{k}, + \infty)

(3)

According to the mixed integer linear programming (MILP) model proposed by Deng et al.,¹⁹ we develop an MILP model for the NWJSP with total tardiness. As shown by equation (3),

F_{i, j}

consists of several consecutive intervals. Therefore, we have

F_{i, j} = (- \infty, e_{i, j}^{1}] \cup [s_{i, j}^{2}, e_{i, j}^{2}] \cup \dots \cup [s_{i, j}^{l_{i, j}}, + \infty)

, where the intervals are arranged in order from smallest to largest, and

l_{i, j}

is the number of intervals in

F_{i, j}

. In addition, the 0–1 variable

x_{i, j}^{n u m} \in {0, 1}, n u m \in {1, 2, \dots, l_{i, j}}

is introduced. When

t_{j} - t_{i}

is in the numth interval of

F_{i, j}

, the

x_{i, j}^{n u m} = 0

, otherwise

x_{i, j}^{n u m} = 1

. The MILP model is formulated as follows.

\begin{matrix} min T_{t o t} = \sum_{i = 1}^{n} T_{i} \end{matrix}

s . t .

T_{i} = max (0, C_{i} - d t_{i}) f o r a l l i \in {1, 2, \dots, n}

(4)

C_{i} = t_{i} + \sum_{u = 1}^{n_{i}} p_{i, u} f o r a l l i \in {1, 2, \dots, n}

(5)

t_{j} - t_{i} \leq e_{i, j}^{1} + x_{i, j}^{1} M f o r a l l i < j, i, j \in {1, 2, \dots, n}

(6)

\begin{matrix} s_{i, j}^{n u m} - x_{i, j}^{n u m} M \leq t_{j} - t_{i} \leq e_{i, j}^{n u m} + x_{i, j}^{n u m} M \\ f o r a l l i < j, i, j \in {1, 2, \dots, n}, n u m \in {1, 2, \dots, l_{i, j}} \end{matrix}

(7)

s_{i, j}^{l_{i, j}} - x_{i, j}^{l_{i, j}} M \leq t_{j} - t_{i} f o r a l l i < j, i, j \in {1, 2, \dots, n}

(8)

\sum_{n u m = 1}^{l_{i, j}} (1 - x_{i, j}^{n u m}) = 1 f o r a l l i < j, i, j \in {1, 2, \dots, n}

(9)

\begin{matrix} x_{i, j}^{n u m} \in {0, 1} \\ f o r a l l i < j, i, j \in {1, 2, \dots, n}, n u m \in {1, 2, \dots, l_{i, j}} \end{matrix}

(10)

where M is a large enough number.

The NWJSP can be viewed as a problem consisting of sequencing and timetabling subproblems. The aim of the sequencing subproblem is to find the optimal scheduling sequence of jobs. The aim of the timetabling subproblem is to look for the set of start times that optimize the objective value of the job sequence provided by the sequence subproblem.

Timetabling method

To solve the timetabling subproblem, we introduce the left timetabling method. According to Deng et al.,²¹ the left timetabling method can be implemented using the feasible time difference set $F_{i, j}$ and the start time difference set $S_{i, j}$ . $S_{i, j}$ is calculated with equation (11).

S_{i, j} = [0, + \infty) \cap F_{i, j}

(11)

Assume that there is a sequence of jobs

π = {π_{1}, π_{2}, \dots, π_{n}}

. Let

s t_{π} = {t_{1}, t_{2}, \dots, t_{n}}

be the start timetable of the sequence π, and

t_{i}

be the start time of the job

π_{i}

. When using the left timetabling method for the job sequence π, it is important to avoid conflicts between the jobs and to schedule the jobs as far to the left as possible. Therefore, the start time difference

t_{j} - t_{i}

between job

π_{j}

and jobs

π_{i} (i = 1, 2, \dots, j - 1)

needs to satisfy equations (12) and (13).

t_{j} - t_{i} \in S_{π_{i}, π_{j}} (i = 1)

(12)

t_{j} - t_{i} \in F_{π_{i}, π_{j}} (1 < i < j)

(13)

The left timetabling method is to keep the start times of the jobs as far to the left as possible. First, set the start time

t_{1} = 0

. For the job

π_{j} (j \geq 2)

, first set the start time

t_{j}

to the left endpoint of the smallest interval in the

S_{π_{1}, π_{j}}

, and then sequentially determine whether the start time difference

t_{j} - t_{i} (i = j - 1, j - 2, \dots, 1)

between the job

π_{j}

and all the previous jobs

π_{i} (i = j - 1, j - 2, \dots, 1)

belongs to

F_{π_{i}, π_{j}}

S_{π_{1}, π_{j}}

. If the start time difference

t_{j} - t_{i}

between job

π_{j}

and job

π_{i} (i = 1, 2, \dots, j - 1)

does not belong to

F_{π_{i}, π_{j}}

S_{π_{1}, π_{j}}

, increase

t_{j}

so that

t_{j} - t_{i}

belongs to the set and restart from job

π_{j - 1}

until the start time difference between job

π_{j}

and job

π_{i} (i = 1, 2, \dots, j - 1)

satisfies

F_{π_{i}, π_{j}}

S_{π_{1}, π_{j}}

. The total tardiness

T_{t o t}

can be calculated from the generated start timetable

s t_{π} = {t_{1}, t_{2}, \dots, t_{n}}

. Algorithm 1 shows the procedure for the left method.

Algorithm 1.

Procedure for the left method.

$t_{1} = 0$ ;

for (j from 2 to n)

$t_{j} = s_{i, j}$ ; // $s_{i, j}$ is the left endpoint of the smallest interval in the $S_{π_{1}, π_{j}}$

flag = true;

while (flag)

flag = false;

for (i from j – 1 to 1)

if ( $i \neq 1$ )

if ( $t_{j} - t_{i} \notin F_{π_{i}, π_{j}}$ )

$t_{j} = s_{i, j} + t_{i}$ ; // $s_{i, j}$ is the left endpoint of the nearest interval to the left of $t_{j} - t_{i}$ in the $F_{π_{i}, π_{j}}$

flag = true;

break;

endif

else if ( $t_{j} - t_{i} \notin S_{π_{i}, π_{j}}$ )

$t_{j} = s_{i, j} + t_{i}$ ; // $s_{i, j}$ is the left endpoint of the nearest interval to the left of $t_{j} - t_{i}$ in the $S_{π_{1}, π_{j}}$

flag = true;

break;

endif

endfor

endwhile

endfor

$T_{t o t} = \sum_{i = o}^{n} m a x (0, C_{i} - d t_{i}), C_{i} = t_{i} + \sum_{u = 1}^{n_{i}} p_{i, u}$

HDABC for the NWJSP

Basic ABC algorithm

The ABC algorithm²⁹ is a metaheuristic algorithm to simulate honey bee foraging. The ABC algorithm classifies the colony into employed, onlooker and scout bees based on the foraging behavior, corresponding to the three phases of the algorithm. The employed bee seeks out good food sources and shares the information with the onlooker bee. The onlooker bee selects a food source based on a selection mechanism and further explores this food source. If the number of times the onlooker bee explores the neighborhood of a food source exceeds the maximum number of iterations limit and no better food source is found, it is considered that there is no need to explore the food source. At this point, the onlooker bee will turn into the scout bee and search for other food sources.

HDABC algorithm

Solution representation

Most researchers decompose the NWJSP into two subproblems: the sequence and the timetabling subproblems. Therefore, we divide the solution representation into two parts: job sequence and timetable. The job start times are determined by the timetabling method in the order of the job sequence and recorded in the timetable. In addition, the age_i parameter is added to each solution P_i to record the number of iterations experienced.

Initialization

For population-based algorithms, the initialization of the population is an important part. Therefore, we introduce the NEH³⁷ and NEH-WPT heuristics³⁸ for population initialization. The procedure of the NEH is to sort the jobs nonincrementally according to their total processing time, and then insert the jobs one by one into the best position according to the order. The difference between the NEH-WPT and the NEH heuristics is that the initial sequence of the NEH-WPT is a nondescending arrangement of jobs.

In the initialization phase, two initial solutions are generated by the NEH and the NEH-WPT, and the remaining solutions are generated randomly. In addition, let each solution have age_i= 0. The age of each solution will be updated at the end of each iteration. If the solution P_i is not replaced in one iteration, then age_i= age_i +1; otherwise, age_i= 0.

Employed bee phase

In the HDABC algorithm, each employed bee searches for nectar and shares it with the onlooker bee. In this phase, we introduce the destruction and construction operator³⁹ to search for the nectar source. Firstly, randomly select d jobs, store them in a sequence RI, and remove from the original sequence. Then, the jobs in RI are inserted one by one into the best position in the original sequence to generate a new solution. Here, we introduce a bool variable imp_i. If the solution is improved imp_i= true; otherwise, imp_i= false. Finally, the employed bee will share the better of the new and old solutions with the onlooker bees. Algorithm 2 shows the procedure for the employed bee phase.

Algorithm 2.

Procedure for employed bee phase.

for (i = 1 to p)

randomly select d jobs in the job sequence of individual P_i, store them in the sequence RI, and delete them from the original sequence to generate a partial solution P*;

for (j = 1 to d)

insert the job RI_j into the best of n – d + j positions of P*;

endfor

if (P* is better than P_i)

imp_i= true;

P* replaces P_i, and if better than P_best, replace P_best;

let the number of iterations age_i= 0;

else

imp_i= false;

endif

endfor

Onlooker bee phase

During the onlooker bee phase, the onlooker bees will select the food source provided by the employed bees to explore. This selection process is usually associated with the quality of the food source. Considering that the low quality of solutions may be due to insufficient number of iterations, we propose a new selection procedure. The proposed selection process is based on whether the solution is improved or not and times the solution has been explored.

If imp_i= true, the solution is improved. This means that the neighborhood of the solution is valuable for further exploration, so the onlooker bee explores the solution further.

If imp_i= false, the solution is not improved. Here a probability of reception prob and a random number r (0 < r < 1) are introduced. If $r < p r o b$ , the solution is further explored. If $r \geq p r o b$ , nothing is done. When the age_i of the solution P_i is small, we think that the neighborhood of the solution may not be sufficiently searched, so let $p r o b = 1 - a g e_{i} / l i m i t$ , which is inversely proportional to the number of iterations age_i.

In this phase, the search is done by the NEH heuristic. To be specific, we apply the NEH heuristic to generate a new solution P* using the sequence of P_i as the initial sequence. The solution with the better objective value among the new and old solutions is retained according to the greedy selection principle. Algorithm 3 shows the procedure for the employed bee phase.

Algorithm 3.

Procedure for onlooker bee phase.

for (i = 1 to p)

if (imp_i == true)

the NEH heuristic generates a new solution P* using the sequence of P_i as the initial sequence;

the number of iterations age_i= age_i+ 1;

if (P* is better than P_i)

let the number of iterations age_i= 0;

P* replaces P_i, and if better than P_best, replace P_best;

endif

else if (r < prob)

the NEH heuristic generates a new solution P* using the sequence of P_i as the initial sequence;

the number of iterations age_i= age_i+ 1;

if (P* is better than P_i)

let the number of iterations age_i= 0;

P* replaces P_i, and if better than P_best, replace P_best;

endif

else

the number of iterations age_i= age_i+ 1;

endif

endfor

Scout bee phase

In the scout bee phase, a solution P_i is considered to be fall into a local optimum if its age_i exceeds the limit. For these solutions, we perturb them by performing ptb random swap operations on them. Here ptb is the extent of perturbation. Algorithm 4 shows the procedure for the scout bee phase.

Algorithm 4.

Procedure for scout bee phase.

for (i = 1 to p)

if (age_i> limit)

generate a new solution P* by performing ptb random swap on the individual P_i;

the number of iterations age_i= 0;

P* replaces P_i, and if better than P_best, replace P_best;

endif

endfor

Procedure of HDABC

The HDABC algorithm has the following four parameters: population size p, number of reinserted jobs d, maximum number of iterations limit and extent of perturbation ptb. Algorithm 5 shows the procedure of the HDABC algorithm.

Algorithm 5.

Procedure of HDABC algorithm.

set p, d, ptb, and limit, and initialize the population;

P_best is set to the best solution in the initial population;

while (stopping condition not met)

Algorithm 2 is performed; // employed bee phase

Algorithm 3 is performed; // onlooker bee phase

Algorithm 4 is performed; // scout bee phase

endwhile

Computations and comparisons

Experimental preparations

In this study, we implement all the algorithms in C++ and run them on a PC equipped with Intel(R) Core (TM) i5-8250U CPU 1.80 GHz processor. The benchmark instances used in the experiments of this study include the well-known instances La01-40, Abz5-9, Ft10, Ft20, Orb01-10, Yn1-4, and Swv01-20. In addition, the due date is set to $d t_{i} = f \times \sum_{k = 1}^{m} p_{i k}$ , where the tardiness factor $f = 1.6$ . The tardiness factor can be seen as a parameter that adjusts the tightness of the due dates. This parameter should be set to make the tightness of the due dates appropriate. Setting the value 1.6 can cause a tardiness for a large portion of the jobs, while it will not make the due dates too tight.

The relative percentage deviation (RPD) is used in the experiments to evaluate the performance of an algorithm. The RPD is calculated as shown in equation (14). Where the $T T_{r e f}$ is the reference solution and the $T T_{a l g m}$ represents the solution obtained by an algorithm.

R P D = \frac{T T_{a l g m} - T T_{r e f}}{T T_{r e f}} \times 100 %

(14)

Calibration of HDABC

Since the HDABC algorithm has a certain degree of stochasticity, the calibration of the parameters plays an important role. The HDABC algorithm is calibrated with the following parameters: population size p, number of re-inserted jobs d, maximum number of iterations limit, and extent of perturbation ptb.

A large design of experiments⁴⁰ is conducted for the remaining parameters: (1) population size $p \in {10, 20, 30}$ ; (2) maximum number of iterations $l i m i t \in {30, 40, 50}$ ; (3) number of reinsertion jobs $d \in {2, 4, 6}$ ; (4) the extent of perturbation $p t b \in {0.1 n, 0.2 n, 0.4 n}$ . Five instances, La01 (10 × 5), La21 (15 × 10), La26 (20 × 10), La31 (30 × 10), and Swv11 (50 × 10) are selected. For each parameter combination, the HDABC algorithm is run five times independently on each of the five instances. The stopping condition of the algorithm is running time not less than 5 mn² milliseconds. Here, the best of all the solutions of each instance is selected as the reference solution for calculating the RPD values, and the best solutions are: La01: 1712, La21: 6272, La26: 12661, La31: 32020, Swv11: 98380. In addition, we performed the multifactor analysis of variance (ANOVA) on the results. The ANOVA results are shown in Table 1. Figure 1 shows the means and 95.0% Tukey HSD intervals for all tested factors.

Figure 1.

Means and 95.0% Tukey HSD intervals for all tested factors.

Table 1.

ANOVA results for algorithm calibration.

Source	Sum of squares	df	Mean square	F-ratio	p-value
Main effects
A:instances	20,971.0	4	5242.75	817.22	.0000
B:p	275.711	2	137.855	21.49	.0000
C:d	6233.5	2	3116.75	485.83	.0000
D:limit	1.41706	2	0.708532	0.11	.8954
E:ptb	0.0568775	2	0.0284388	0.00	.9956
Residual	12,907.6	2012	6.41533
Total (corrected)	40,389.3	2024

From the results of the ANOVA, all the parameters are statistically significant except for the limit and ptb. From Figure 1, it can be seen that 20 is significantly better than 15 and 10 for the value of parameter p. For parameter d, 6 is significantly better than 4 and 2. Furthermore, the parameter limit does not differ much for each value but 40 is slightly better than 30 and 50. The situation is similar for the parameter ptb. There are no statistical differences for the values 0.1n, 0.2n, and 0.4n. Therefore, the parameters are selected as the following combination: p = 20, limit = 40, d = 6, ptb = 0.2n.

Comparison with other metaheuristics

The discrete ABC (DABC),³⁰ HABC³⁵ and IG³⁹ algorithms are selected for comparison with the HDABC algorithm. To exclude the randomness of the algorithms, each algorithm is run 10 times on each instance. It is worth noting that the compared algorithms are adapted here to suit the problem of this study. In addition, the HDABC algorithm and all compared algorithms are run in the same environment. Here each algorithm is stopped by the running time, which is set to 20 mn². This setting allows different running times for different instance sizes, so that there is not a situation where large instances do not have enough time and small instances have too much time. In calculating the RPD value, the best result of the HDABC and all the compared algorithms after 10 runs is used as the reference value. When comparing the algorithms, the instances are divided into two groups, one group with no more than 15 and the other with more than 15 jobs. Tables 2 and 3 illustrate the results, where the best solution (best), RPD of the best solution (RPD_best) and average RPD of the 10 runs (ARPD) are recorded, and Instance, n * m and ref represent the instance name, the size of the instances and the reference value, respectively. The best results of the four algorithms are shown in bold.

Table 2.

Results of different algorithms on the instances with no more than 15 jobs.

Instance	n*m	ref	HDABC			HABC			DABC			IG
Instance	n*m	ref	best	RPD_best	ARPD	best	RPD_best	ARPD	best	RPD_best	ARPD	best	RPD_best	ARPD
la01	10*5	1712	1712	0.00	0.00	1712	0.00	0.00	1712	0.00	0.00	1712	0.00	0.00
la02	10*5	1406	1406	0.00	0.00	1406	0.00	5.48	1406	0.00	0.00	1406	0.00	9.03
la03	10*5	1456	1456	0.00	0.00	1456	0.00	0.54	1456	0.00	0.00	1456	0.00	0.00
la04	10*5	1470	1470	0.00	0.00	1470	0.00	2.72	1470	0.00	0.00	1470	0.00	3.53
la05	10*5	1582	1582	0.00	0.00	1582	0.00	0.47	1582	0.00	0.00	1582	0.00	0.00
abz5	10*10	2888	2888	0.00	0.00	2888	0.00	1.50	2888	0.00	0.00	2888	0.00	1.40
abz6	10*10	2416	2416	0.00	0.00	2416	0.00	0.18	2416	0.00	0.00	2416	0.00	1.18
ft10	10*10	2286	2286	0.00	0.00	2286	0.00	0.00	2286	0.00	0.00	2286	0.00	0.00
la16	10*10	2175	2175	0.00	0.00	2175	0.00	2.25	2175	0.00	0.00	2175	0.00	5.99
la17	10*10	1779	1779	0.00	0.00	1779	0.00	0.00	1779	0.00	0.00	1779	0.00	0.00
la18	10*10	1796	1796	0.00	0.00	1796	0.00	0.88	1796	0.00	0.00	1796	0.00	1.76
la19	10*10	2158	2158	0.00	0.00	2158	0.00	0.00	2158	0.00	0.00	2158	0.00	4.14
la20	10*10	2016	2016	0.00	0.00	2016	0.00	2.57	2016	0.00	0.00	2016	0.00	1.03
orb01	10*10	2460	2460	0.00	0.00	2460	0.00	1.45	2460	0.00	0.00	2460	0.00	0.00
orb02	10*10	1866	1866	0.00	0.00	1866	0.00	2.94	1866	0.00	0.00	1866	0.00	0.00
orb03	10*10	2448	2448	0.00	0.00	2448	0.00	1.12	2448	0.00	0.00	2448	0.00	0.00
orb04	10*10	1960	1960	0.00	0.00	1960	0.00	11.63	1960	0.00	0.00	1960	0.00	1.94
orb05	10*10	1782	1782	0.00	0.66	1782	0.00	1.75	1782	0.00	0.88	1782	0.00	3.29
orb06	10*10	2064	2064	0.00	0.00	2064	0.00	0.00	2064	0.00	0.00	2064	0.00	0.83
orb07	10*10	1011	1011	0.00	0.00	1011	0.00	0.81	1011	0.00	0.00	1011	0.00	1.33
orb08	10*10	1994	1994	0.00	0.00	1994	0.00	0.11	1994	0.00	0.00	1994	0.00	0.00
orb09	10*10	1912	1912	0.00	0.00	1912	0.00	0.00	1912	0.00	0.00	1912	0.00	0.00
orb10	10*10	2103	2103	0.00	0.00	2103	0.00	2.43	2103	0.00	0.00	2103	0.00	3.41
la06	15*5	4681	4681	0.00	0.82	4681	0.00	0.00	4681	0.00	0.82	4681	0.00	3.31
la07	15*5	4440	4440	0.00	0.25	4456	0.36	1.16	4440	0.00	1.18	4456	0.36	2.89
la08	15*5	4555	4555	0.00	0.00	4555	0.00	0.00	4555	0.00	0.36	4555	0.00	3.29
la09	15*5	4702	4702	0.00	1.27	4702	0.00	4.18	4702	0.00	0.00	4901	4.23	7.74
la10	15*5	4264	4264	0.00	0.00	4264	0.00	0.00	4264	0.00	0.00	4264	0.00	0.00
la21	15*10	6272	6272	0.00	0.62	6468	3.13	4.10	6272	0.00	0.94	6272	0.00	10.18
la22	15*10	5739	5739	0.00	0.31	5739	0.00	0.58	5739	0.00	0.31	5739	0.00	6.71
la23	15*10	6181	6181	0.00	0.29	6181	0.00	0.29	6181	0.00	0.00	6181	0.00	9.56
la24	15*10	6362	6362	0.00	0.23	6398	0.57	1.97	6362	0.00	0.51	6362	0.00	5.60
la25	15*10	5302	5302	0.00	0.18	5302	0.00	2.46	5302	0.00	1.37	5302	0.00	4.34
la36	15*15	7758	7758	0.00	1.95	7812	0.70	3.16	7758	0.00	3.11	7758	0.00	8.14
la37	15*15	8620	8620	0.00	0.35	8676	0.65	1.13	8620	0.00	0.26	8676	0.65	8.59
la38	15*15	6862	6862	0.00	0.57	6862	0.00	0.88	6862	0.00	0.94	7036	2.54	6.61
la39	15*15	7406	7406	0.00	2.90	7406	0.00	0.43	7406	0.00	3.24	8000	8.02	13.48
la40	15*15	7669	7669	0.00	2.22	7669	0.00	1.60	7669	0.00	2.80	7922	3.30	6.46
average		3567.18	3567.18	0.00	0.33	3576.61	0.14	1.60	3567.18	0.00	0.44	3601.18	0.50	3.57

HDABC: hybrid discrete artificial bee colony; HABC: hybrid artificial bee colony; DABC discrete artificial bee colony; IG: iterated greedy; RPD: relative percentage deviation; ARPD: average RPD.

Table 3.

Results of different algorithms on the instances with more than 15 jobs.

Instance	n*m	ref	HDABC			HABC			DABC			IG
Instance	n*m	ref	best	RPD_best	ARPD	best	RPD_best	ARPD	best	RPD_best	ARPD	best	RPD_best	ARPD
ft20	20*5	8539	8539	0.00	0.71	8701	1.90	3.51	8539	0.00	0.45	8539	0.00	2.04
la11	20*5	8828	8828	0.00	1.41	8828	0.00	0.92	8828	0.00	1.80	9146	3.60	10.23
la12	20*5	7744	7744	0.00	0.32	7744	0.00	1.44	7744	0.00	0.29	7779	0.45	4.79
la13	20*5	8864	8884	0.23	1.62	8864	0.00	1.17	8884	0.23	2.85	9178	3.54	5.79
la14	20*5	9404	9411	0.07	2.36	9563	1.69	3.82	9508	1.11	2.93	9404	0.00	4.44
la15	20*5	9756	9756	0.00	1.50	9858	1.05	2.02	9809	0.54	2.36	9915	1.63	4.94
la26	20*10	12,789	12,789	0.00	4.64	12,895	0.83	4.02	12,835	0.36	5.04	13,618	6.48	12.18
la27	20*10	13,859	13,859	0.00	3.57	13,859	0.00	4.35	13,910	0.37	3.04	14,286	3.08	7.49
la28	20*10	13,295	13,295	0.00	2.00	13,295	0.00	3.41	13,295	0.00	3.07	14,551	9.45	11.87
la29	20*10	11,732	11,975	2.07	3.39	11,732	0.00	3.85	12,200	3.99	5.79	12,018	2.44	8.09
la30	20*10	11,731	11,731	0.00	1.47	11,731	0.00	2.16	11,731	0.00	1.10	11,731	0.00	7.63
swv01	20*10	10,944	10,944	0.00	0.00	10,944	0.00	2.98	10,944	0.00	0.00	11,297	3.23	3.25
swv02	20*10	11,840	11,840	0.00	1.14	11,840	0.00	1.06	11,840	0.00	1.29	12,368	4.46	9.36
swv03	20*10	12,188	12,188	0.00	0.66	12,188	0.00	2.31	12,288	0.82	0.83	12,293	0.86	6.16
swv04	20*10	12,317	12,317	0.00	0.37	12,317	0.00	1.02	12,317	0.00	1.46	12,317	0.00	4.91
swv05	20*10	11,946	11,946	0.00	1.05	12,033	0.73	1.62	11,946	0.00	0.82	12,162	1.81	3.57
abz7	20*15	7388	7388	0.00	5.25	7388	0.00	4.39	7388	0.00	6.64	7528	1.89	12.78
abz8	20*15	7269	7398	1.77	8.22	7586	4.36	10.03	7269	0.00	7.86	7690	5.79	15.32
abz9	20*15	7355	7460	1.43	4.49	7516	2.19	6.02	7355	0.00	4.16	7430	1.02	10.07
swv06	20*15	15,033	15,033	0.00	2.56	15,855	5.47	7.32	15,033	0.00	2.54	15,033	0.00	10.45
swv07	20*15	15,159	15,159	0.00	0.53	15,159	0.00	1.69	15,159	0.00	0.29	15,802	4.24	6.68
swv08	20*15	15,453	15,453	0.00	4.73	17,077	10.51	12.57	15,453	0.00	7.89	17,327	12.13	16.43
swv09	20*15	15,755	15,755	0.00	0.73	15,833	0.50	1.35	15,755	0.00	0.67	15,755	0.00	5.23
swv10	20*15	16,419	16,419	0.00	0.22	16,419	0.00	0.00	16,419	0.00	0.63	16,419	0.00	7.93
yn1	20*20	10,218	10,238	0.20	3.40	10,238	0.20	4.03	10,218	0.00	3.82	10,586	3.60	10.13
yn2	20*20	10,060	10,716	6.52	12.11	10,611	5.48	11.73	10,060	0.00	10.94	10,799	7.35	19.90
yn3	20*20	9749	9763	0.14	13.23	9749	0.00	11.22	10,494	7.64	12.79	10,892	11.72	20.89
yn4	20*20	10,908	10,910	0.02	3.56	10,910	0.02	2.61	10,908	0.00	3.71	11,099	1.75	11.03
la31	30*10	32,500	33,732	3.79	6.97	32,500	0.00	4.29	32,558	0.18	5.50	34,108	4.95	8.20
la32	30*10	34,709	34,709	0.00	7.27	35,492	2.26	6.31	35,890	3.40	6.85	38,803	11.80	15.88
la33	30*10	32,302	32,302	0.00	6.01	32,809	1.57	4.27	33,093	2.45	6.08	33,755	4.50	7.61
la34	30*10	34,107	34,232	0.37	3.97	34,562	1.33	4.39	34,107	0.00	3.89	35,656	4.54	10.30
la35	30*10	33,101	33,101	0.00	7.11	34,436	4.03	6.80	34,128	3.10	6.95	36,302	9.67	16.43
swv11	50*10	97,974	97,974	0.00	3.60	101,134	3.23	4.75	99,834	1.90	3.44	100,310	2.38	4.65
swv12	50*10	98,630	98,716	0.09	2.72	98,630	0.00	4.60	99,867	1.25	4.12	100,595	1.99	5.57
swv13	50*10	101,448	101,448	0.00	1.96	103,926	2.44	3.70	102,136	0.68	3.24	102,774	1.31	3.99
swv14	50*10	95,860	97,779	2.00	4.17	95,860	0.00	3.87	96,743	0.92	3.57	98,054	2.29	7.49
swv15	50*10	97,623	99,864	2.30	2.96	99,882	2.31	4.59	97,623	0.00	2.63	98,388	0.78	5.27
swv16	50*10	105,279	110,139	4.62	6.97	105,279	0.00	4.49	111,197	5.62	6.97	111,710	6.11	10.97
swv17	50*10	102,478	104,116	1.60	4.84	102,478	0.00	2.38	104,917	2.38	5.77	109,970	7.31	11.44
swv18	50*10	103,138	104,246	1.07	5.78	103,138	0.00	4.41	104,838	1.65	5.41	110,757	7.39	11.16
swv19	50*10	105,887	105,887	0.00	6.32	108,168	2.15	5.69	110,645	4.49	8.46	111,543	5.34	10.91
swv20	50*10	103,116	106,167	2.96	5.87	103,116	0.00	3.77	106,616	3.39	6.00	106,024	2.82	7.76
average		34,760.33	35,166.28	0.73	3.76	35,166.12	1.26	4.21	35,402.81	1.08	4.04	36,179.33	3.81	9.10

HDABC: hybrid discrete artificial bee colony; HABC: hybrid artificial bee colony; DABC discrete artificial bee colony; IG: iterated greedy; RPD: relative percentage deviation; ARPD: average RPD.

For the instances with no more than 15 jobs, the average values of the RPD_best for both the HDABC and DABC algorithms are 0, whereas those for the HABC and IG algorithms are 0.14 and 0.50, respectively. In terms of the average values of the ARPD, the HDABC, DABC, HABC and IG have 0.33, 1.60, 0.44, and 3.57, respectively. From the above results, the HDABC and DABC algorithms are better than the HABC and IG algorithms. Although the HDABC and DABC algorithms have the same average value of the RPD_best, the average ARPD of the HDABC is superior to that of the DABC.

For the instances with more than 15 jobs, the average RPD_best values of the HDABC, DABC, HABC, and IG algorithms are 0.73, 1.26, 1.08, and 3.81, respectively. The average ARPD values of the HDABC, DABC, HABC, and IG algorithms are 3.76, 4.21, 4.04, and 9.10, respectively. From the results, the conclusions are similar to those of the instances with no more than 15 jobs. In other words, the HDABC and DABC outperform the HABC and IG, while the HDABC is slightly better than the DABC.

In addition to the above comparisons, we also perform an ANOVA on the RPD values of the results of 10 runs of each algorithm. In the ANOVA, the RPD values are the dependent variables, and the algorithms and instances are the factors. The corresponding results are shown in Table 4, where the p-value for both algorithms and instances are less than .05, suggesting that both are statistically significant. The means and 95.0% Tukey HSD intervals for different algorithms are provided in Figure 2. Figure 2 shows that the HDABC and DABC are significantly better than the HABC and IG. The confidence intervals of the HDABC and DABC have some overlap, demonstrating that the difference is not significant.

Figure 2.

Means and 95.0% Tukey HSD intervals for different algorithms.

Table 4.

ANOVA results for comparing different algorithms.

Source	Sum of squares	df	Mean square	F-ratio	p-value
Main effects
A:alg	10,070.5	3	3356.82	378.10	.0000
B:instance	30,345.4	80	379.318	42.73	.0000
Residual	28,019.2	3156	8.87809
Total (corrected)	68,435.1	3239

ANOVA: analysis of variance.

Conclusions

This study considers NWJSP with the total tardiness criterion. For the NWJSP, we decompose it into the sequencing and timetabling subproblems, and develop an MILP model. For the timetabling subproblem, we introduce the left timetabling method for determining the start timetable of the solution. For the sequencing subproblem, we propose the HDABC algorithm for finding possible sequences of jobs. The HDABC algorithm uses the framework of the basic ABC algorithm and redefines its three phases using some discrete operations. In the onlooker bee phase, we propose a new selection mechanism with an acceptance probability. For the solutions with improvements, the search is performed directly; otherwise, the search is judged according to the acceptance probability.

In the computational experiments, we calibrate the parameters of the HDABC algorithm and compare it with the DABC, HABC, and IG algorithms. The results demonstrate that the HDABC algorithm is slightly superior to the DABC and significantly outperforms the HABC and IG algorithms.

This study aims to develop an HDABC algorithm for the NWJSP with the total tardiness criterion. It can be seen from the results of this study that the proposed algorithm has great potential for application to other complicated scheduling problems. In the future, we will consider applying the HDABC to other scheduling problems or objectives, such as distributed flow shop scheduling problem, and multiobjective scheduling problems with energy consumption related objectives.

Footnotes

Author contributions

Conceptualization: Xuemei Huang; formal analysis: Jie Yin; investigation: Guanlong Deng; methodology: Xuemei Huang; software: Jie Yin; supervision: Guanlong Deng; validation: Guanlong Deng; writing—original draft: Jie Yin.

Data availability

The data presented in this study are openly available in at Mendeley Data.

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Xuemei Huang

Jie Yin

Guanlong Deng

References

Tang

Liu

Rong

, et al. A mathematical programming model for scheduling steelmaking-continuous casting production. Eur J Oper Res 2000; 120: 423–435.

Hall

Sriskandarajah

. A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 1996; 44: 510–525.

Macchiaroli

Mole

Riemma

. Modelling and optimization of industrial manufacturing processes subject to no-wait constraints. Int J Prod Res 1999; 37: 2585–2607.

Schuster

Framinan

. Approximative procedures for no-wait job shop scheduling. Oper Res Lett 2003; 31: 308–318.

Framinan

Schuster

. An enhanced timetabling procedure for the no-wait job shop problem: a complete local search approach. Comput Oper Res 2006; 331: 1200–1213.

Schuster

. No-wait job shop scheduling: tabu search and complexity of subproblems. Math Methods Oper Res 2006; 63: 473–491.

Pan

JCH

Huang

. A hybrid genetic algorithm for no-wait job shop scheduling problems. Expert Syst Appl 2009; 36: 5800–5806.

Bożejko

Makuchowski

. A fast hybrid tabu search algorithm for the no-wait job shop problem. Comput Ind Eng 2009; 56: 1502–1509.

Zhu

Wang

. Complete local search with limited memory algorithm for no-wait job shops to minimize makespan. Eur J Oper Res 2009; 198: 378–386.

10.

Bozejko

Makuchowski

. Solving the no-wait job-shop problem by using genetic algorithm with automatic adjustment. Int J Adv Manuf Technol 2011; 57: 735–752.

11.

Zhu

. An effective meta-heuristic for no-wait job shops to minimize makespan. IEEE Trans Autom Sci Eng 2012; 9: 189–198.

12.

Bürgy

Gröflin

. Optimal job insertion in the no-wait job shop. J Comb Optim 2013; 26: 345–371.

13.

Aitzai

Benmedjdoub

Boudhar

. Branch-and-bound and PSO algorithms for no-wait job shop scheduling. J Intell Manuf 2016; 27: 679–688.

14.

. A memory-based complete local search method with variable neighborhood structures for no-wait job shops. Int J Adv Manuf Technol 2016; 87: 1401–1408.

15.

Sundar

Suganthan

Jin

, et al. A hybrid artificial bee colony algorithm for the job-shop scheduling problem with no-wait constraint. Soft Comput 2017; 21: 1193–1202.

16.

Bürgy

Gröflin

. The no-wait job shop with regular objective: a method based on optimal job insertion. J Comb Optim 2017; 33: 977–1010.

17.

Ying

Lin

. Solving no-wait job-shop scheduling problems using a multi-start simulated annealing with bi-directional shift timetabling algorithm. Comput Ind Eng 2020; 146: 106615.

18.

Valenzuela-Alcaraz

Cosío-León

Romero-Ocaño

, et al. A cooperative coevolutionary algorithm approach to the no-wait job shop scheduling problem. Expert Syst Appl 2022; 194: 116498.

19.

Deng

Wei

Zhang

, et al. A simple migrating birds optimization algorithm with two search modes to solve the no-wait job shop problem. Expert Syst Appl 2024; 238: 122112.

20.

Deng

Zhang

Jiang

, et al. Total flow time minimization in no-wait job shop using a hybrid discrete group search optimizer. Appl Soft Comput 2019; 81: 105480.

21.

Deng

Zhang

, et al. A population-based iterated greedy algorithm for no-wait job shop scheduling with total flow time criterion. Eng Appl Artif Intell 2020; 88: 103369.

22.

Ying

Lin

. Minimizing total completion time in the no-wait jobshop scheduling problem using a backtracking metaheuristic. Comput Ind Eng 2022; 169: 108238.

23.

Bank

Ghomi

Jolai

, et al. Two-machine flow shop total tardiness scheduling problem with deteriorating jobs. Appl Math Model 2012; 36: 5418–5426.

24.

Schaller

Valente

. A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness. Int J Prod Res 2013; 51: 772–779.

25.

Zhang

Song

. A hybrid differential evolution algorithm for job shop scheduling problems with expected total tardiness criterion. Appl Soft Comput 2013a; 13: 1448–1458.

26.

Mousakhani

. Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness. Int J Prod Res 2013; 51: 3476–3487.

27.

Türkyilmaz

Bulkan

. A hybrid algorithm for total tardiness minimisation in flexible job shop: genetic algorithm with parallel VNS execution. Int J Prod Res 2015; 53: 1832–1848.

28.

Ribas

Companys

Tort-Martorell

. An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem. Expert Syst Appl 2019; 121: 347–361.

29.

Karaboga

. An idea based on honey bee swarm for numerical optimization (Vol. 200, pp. 1–10). Technical report-tr06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

30.

Pan

Tasgetiren

Suganthan

, et al. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Inf Sci (Ny) 2011; 181: 2455–2468.

31.

Wang

Zhou

, et al. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Technol 2012; 60: 303–315.

32.

Deng

. A discrete artificial bee colony algorithm for minimizing the total flow time in the blocking flow shop scheduling. Chin J Chem Eng 2012; 20: 1067–1073.

33.

Zhang

Song

. A hybrid artificial bee colony algorithm for the job shop scheduling problem. Int J Prod Econ 2013b; 141: 167–178.

34.

Gao

Suganthan

Chua

, et al. A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion. Expert Syst Appl 2015; 42: 7652–7663.

35.

Sundar

Suganthan

Jin

, et al. A hybrid artificial bee colony algorithm for the job-shop scheduling problem with no-wait constraint. Soft COmput 2017; 21: 1193–1202.

36.

Sharma

. Beer froth artificial bee colony algorithm for job-shop scheduling problem. Appl Soft Comput 2018; 68: 507–524.

37.

Nawaz

Enscore

Ham

. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega (Westport) 1983; 11: 91–95.

38.

Wang

Pan

Tasgetiren

. A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem. Comput Ind Eng 2011; 61: 76–83.

39.

Ruiz

Stützle

. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 2007; 177: 2033–2049.

40.

Montgomery

. Design and analysis of experiments. 9th ed. New York: Wiley, 2017.

A hybrid discrete artificial bee colony optimization algorithm for the no-wait job shop problem with tardiness criterion

Abstract

Keywords

Introduction

NWJSP with total tardiness criterion

Problem description

Problem formulation

Timetabling method

HDABC for the NWJSP

Basic ABC algorithm

HDABC algorithm

Solution representation

Initialization

Employed bee phase

Onlooker bee phase

Scout bee phase

Procedure of HDABC

Computations and comparisons

Experimental preparations

Calibration of HDABC

Comparison with other metaheuristics

Conclusions

Footnotes

Author contributions

Data availability

Declaration of conflicting interests

Funding

ORCID iD

References