1 Introduction

The scheduling problem is one of the most commonly encountered problems in the management of production systems. It involves the allocation of a number of jobs to machines taking into consideration a set of constraints. Scheduling problems occur in all economic domains, from computer engineering to manufacturing techniques. Most scheduling problems are complex combinatorial optimization problems and very difficult to solve. The job shop scheduling problem (JSP) is a branch of production scheduling which is among the hardest combinatorial optimization problems. It is a well-known optimization problem often used in practical scheduling applications in the manufacturing sector. The JSP consists of a set of n jobs that have to be processed on a set of m machines. Each job is fully defined by an ordered sequence of operations that are associated with a particular machine while respecting certain constraints, such as:

  1. (i)

    No more than one operation of any job can be executed simultaneously.

  2. (ii)

    No machine can process more than one operation at the same time.

  3. (iii)

    The job operations must be executed in a predefined sequence, and once an operation is started, no preemption is permitted.

The objective is to schedule each operation on the machines, taking the precedence constraints into account such that a number of optimization criteria are attained, including cost, run time, and makespan (\(C_\mathrm{max}\): total completion time) minimization.

In this paper we are interested in the job shop scheduling problem including time lag constraints, which is a special case of resource-constrained project scheduling problems with minimum and maximum time lags between operations of different jobs (González et al. 2015).

The job shop problem including minimum and maximum time lag constraints is a generalization of the job shop scheduling problem, in which there are time relations between the starting times of operations. The job shop scheduling problem including time lag constraints involves two kinds of time lag constraints: either time lags between two successive operations of the same job (job shop scheduling problem with time lags, denoted as JSPTL) or generic time lags between pairs of operations, denoted as JSPGTL. A job shop scheduling problem including minimum and maximum time lag constraints is NP-hard (Lacomme and Tchernev 2012).

The addition of time lag constraints between operations makes even the usually simple task of finding a feasible schedule difficult, and few articles have tackled time lag constraints. In this paper we propose solving the JSPTL-JSPGTL problem with a biogeography-based optimization (BBO) algorithm combined with a greedy constructive algorithm and Tabu search metaheuristic. BBO was introduced in 2008 to solve global optimization problems. It is an evolutionary algorithm that is inspired by the migration of species between habitats. BBO has been demonstrated to be a powerful search technique because it includes both exploration and exploitation strategies based on migration. It is one of the fastest-growing nature-inspired algorithms for solving practical optimization problems. This is a result of its advantages in terms of simplicity, flexibility, and computational efficiency, as well as its stochastic nature, which does not require derivatives of the objective function. Motivated by the effectiveness of this newly emerging evolutionary algorithm in solving different kinds of optimization problems, this study represents the first reported work using the BBO for solving the JSPTL-JSPGTL problem. Our intention is to provide an adaptation of the different parameters of BBO to suit the problem characteristics. We also extend the classic BBO algorithm by adding a constructive greedy algorithm to create the initial population and using the Tabu search algorithm for the mutation step. This hybridization allows us to obtain the best results for the job shop with time lags, which is a very challenging problem for local search metaheuristics, because the classical neighborhood structures for the standard job shop lead to unfeasible schedules most of the time. We conducted an experimental study in which we compared it with the state-of-the-art approach in both the JSPTL and JSPGTL. The experimental results prove that our method is very competitive and that the proposed HBBO algorithm is both effective and efficient. The remainder of the paper is organized as follows. The next section provides related works. In Sect. 3, we give an overview of the job shop scheduling problem with minimum and maximum time lag constraints. In Sect. 4 we explain the concept and structure of the basic BBO algorithm, and we present the adaptation of the HBBO algorithm for our problem in Sect. 5. Section 6 analyzes the performance results of HBBO when applied to solve instances of benchmark problems in the literature. In Sect. 7, we summarize our contributions and propose some avenues for future research.

2 Related works

Time lag describes the waiting-time constraints between two consecutive operations in the same job or between two operations of different jobs. Two kinds of time lag constraints can be used in several fields of industrial job shop applications, either minimum or maximum time lags. Minimum time lag constraints can correspond to overlap time, storage time, transit time, or communication time between processes of a computer system. Minimum time lags may be used when waiting time between operations is required for processing, such as cooling (Fondrevelle et al. 2006), material handling (Soukhal et al. 2005), and chemical reactions (Chu and Proth 1996). The minimum time lag between operations (i, j) and \((i', j')\) of different jobs is denoted as \(TL^\mathrm{min}_{(i, j), (i', j')}\), see Fig. 1. Maximum time lags can be used to demand that the waiting time between operations not be overly long in order to avoid deterioration of products (Hodson et al. 1985). Maximum time lag constraints can be used in the chemical sector. For example, filtration of a product must respond quickly to the formulation to prevent the precipitation of the product. In the agribusiness sector, for example, freezing of meals must occur no later than 30 minutes after cooking; otherwise the meal is declared unfit for human consumption. Similar scenarios can be found in the pharmaceutical and other sectors. The maximum generic time lag between operations (i, j) and \((i', j')\) of different jobs is denoted as \(TL^\mathrm{max}_{(i, j), (i', j')}\), see Fig. 2.

Fig. 1
figure 1

Minimum time lags

Full size image
Fig. 2
figure 2

Maximum time lags

Full size image

Minimum and maximum time lag constraints arise in many real-life scheduling applications. For example, in the steel industry, the time lag between the heating of a piece of steel and its molding should be small (Wismer 1972). Similarly when scheduling chemical reactions, the reactive component usually cannot be stored for a long period between two stages of a process, so as to avoid interactions with external elements (Rajendran 1994). Many other industrial applications can be found, such as fabrication of printed circuits (Kim et al. 1996), hoist-scheduling problems (Manier and Bloch 2003), perishable product production (Johnson 1954), biotechnology, and chemistry (Nawaz et al. 1983).

Time lag constraints have been introduced in numerous scheduling problems. Mitten (1958) employed time lag constraints for the first time in a problem with parallel machines using a polynomial algorithm to minimize the makespan for the flow shop problem with two machines. Wikum et al. (1994) studied problems with a single machine considering minimum and maximum distances between jobs and proved that these problems are NP-hard, although some particular cases are polynomially solvable. Brucker et al. (1999) showed many examples of scheduling problems that can be modeled as single-machine problems with time lags, including multiprocessor tasks, multipurpose machines, or problems with changeover costs. They also proposed a branch-and-bound method to solve the problem. Hurink and Keuchel (2001) proposed a local search approach for the single-machine problem with positive and negative time lags. Fondrevelle et al. (2006) solved permutation flow shop scheduling problems with maximum and minimum time lags. Botta-Genoulaz (2000) tackled maximum lateness minimization in hybrid flow shop scheduling with precedence constraints and time lags. Another example was presented in the thesis of Zhang (2010), where several variants of online and offline problems with time lags are studied. Time lag constraints have been introduced in many works concerned with solving the resource-constrained project scheduling problem (RCPSP). Bartusch et al. (1988) proposed a scheduling project network with resource constraints and time windows, and Brinkmann and Neumann (1996) proposed heuristic procedures for resource-constrained project scheduling with minimum and maximum time lags. Neumann et al. (2002) studied the project scheduling problem with time windows and scare resources. Heilmann (2003) proposed an exact procedure for a general RCPSP where multiple modes are available for the performance of the individual activities, as well as both minimum and maximum time lags between the different activities. The objective is to determine a mode and a start time for each activity such that all constraints are observed while minimizing the project duration. Hamdi and Loukil (2011) proposed a permutation flow shop problem with maximum and minimum time lags and makespan minimization. Nikbakhsh et al. (2012) proposed an immune algorithm for a hybrid flow shop scheduling problem with time lags and sequence-dependent setup times.

Dhouib et al. (2013) proposed a combination of a simulated annealing algorithm and a mixed-integer mathematical program for solving a permutation flow shop scheduling problem with time lag constraints. Sheikh (2013) investigated a genetic algorithm for solving a multi-objective flexible flow line problem with due window, time lag, and job rejection. Zhao et al. (2017) proposed a universal approach to resolve flow shop scheduling problems with time lags. Ye et al. (2017) studied a non-permutation flow shop scheduling problem with time lags to minimize the makespan.

Different methods have been proposed in the literature for solving the job shop scheduling problem with time lags in the literature. Caumond et al. (2005a) introduced a genetic algorithm based on an operation insertion heuristic. Caumond et al. (2004) proposed a Tabu search metaheuristic, and Caumond et al. (2005b) proposed a constructive heuristic based on Giffer and Thompson’s heuristic. Deppner (2004) investigated an approach based on a construction method. Caumond et al. (2008) introduced a memetic algorithm based on a disjunctive graph that is suitable for various industrial situations. Karoui et al. (2010) investigated a climbing discrepancy search method. Artigues et al. (2011) proposed an insertion heuristic and generalized resource constraint propagation approach for the job shop problem. González et al. (2015) proposed a scatter search procedure combining path relinking and the Tabu search metaheuristic of Nowicki and Smutnicki (2005). Afsar et al. (2016) proposed a disjunctive graph model for the job shop problem with time lags and transport. Other methods have been proposed for solving the job shop scheduling problem with generic time lags. Lacomme et al. (2011) proposed a dedicated constraint propagation technique using the Bierwirth vector for presenting a solution, and Lacomme and Tchernev (2012) proposed a set of greedy randomized propagation rules. Harrabi and Belkahla Driss (2016) proposed a Tabu search metaheuristic, while Harrabi et al. (2017a, 2017b, 2017c) proposed a combination of a genetic algorithm and Tabu search metaheuristic. Multi-agent systems have recently been widely used for the resolution of job shop problems. Harrabi and Belkahla Driss (2015) proposed a Tabu search metaheuristic in a multi-agent model. Harrabi et al. (2017a, 2017b, 2017c) proposed the use of parallel Tabu searches in a multi-agent system composed of competitive agents. Harrabi et al. (2017a, 2017b, 2017c) proposed a multi-agent model based on a hybrid genetic algorithm. Harrabi et al. (2018) proposed a BBO combined with a greedy algorithm for the job shop scheduling problem with time lags between successive operations of the same job. Harrabi et al. (2020) proposed a modified BBO algorithm with an improved mutation operator for the job shop scheduling problem with generic time lags. In this paper, we propose a hybrid BBO algorithm for the job shop scheduling problem with additional minimum and maximum time lag constraints with makespan minimization. Indeed, the popularity of hybrid optimization approaches is rapidly growing as an effective strategy to improve the performance of classical algorithms by combining components from various optimization methods. Population-based optimization algorithms like BBO often have good global exploration ability. However, they are generally not very efficient at local exploitation. In contrast, local search algorithms are efficient at local exploitation but are not effective at exploring the entire search space. Therefore, hybridization of a local search with population-based optimization is a promising way to synergize the advantages of both approaches in a single algorithm. The aim of this type of hybridization is to find the right trade-off between global exploration and local exploitation of the problem search space. Studies have shown that BBO performance can be enhanced through the incorporation of techniques from other metaheuristics (Ma and Simon 2017). Many works in the literature have investigated the hybridization of BBO with other algorithms. Al-Roomi and El-Hawary (2016) presented a combination of BBO and simulated annealing (SA), and Wee et al. (2016) introduced a Tabu search in the mutation step of BBO for the quadratic assignment problem. BBO is also often hybridized with other population-based algorithms. Foe example, many authors have used a hybridization of BBO and differential evolution (DE) to solve various optimization problems. Bhattacharya and Chattopadhyay (2010) and Bhattacharya and Chattopadhyay (2011) investigated an application of BBO and DE for economic emission load dispatch. Wireless sensor network power allocation was solved with BBO/DE in Boussaïd et al. (2011). In Du et al. (2009), BBO was hybridized with an evolutionary strategy (ES). Sinha et al. (2012) proposed a hybridization between BBO and ant colony optimization (ACO). The combination of BBO and particle swarm optimization (PSO) was proposed in Guo et al. (2013). Zheng et al. (2014a, 2014b) introduced a new variation of BBO, called ecogeography-based optimization (EBO), which regards the population of islands (solutions) as an ecological system with a local topology. Two novel migration operators are designed to perform effective exploration and exploitation in the solution space, mimicking the species dispersal under ecogeographic barriers and differentiations. Lu et al. (2018) proposed a biogeography-based memetic algorithm, or BBMA, which redefines the migration and mutation operators of the BBO. They employed a local population topology to suppress premature convergence and used a critical-path-based local search operator to enhance the exploitation ability. Rifai et al. (2018) investigated a non-dominated sorting BBO for a scheduling problem of a flexible manufacturing system (FMS) having multi-loading/unloading and shortcuts infused in the reentrant characteristics. This model is formulated to identify the near optimal trade-off solutions capable of addressing the two objectives of makespan minimization and total earliness. Wu et al. (2019) used a water optimization metaheuristic for the flow shop scheduling problem using a self-adaptive local search procedure to improve the basic algorithm. Zhao et al. (2019) proposed a hybrid BBO with a variable neighborhood search for solving the no-wait flow shop scheduling problem.

3 Job shop scheduling problem with time lags: description and mathematical modeling

3.1 Problem description

The job shop problem with generic minimum and maximum time lags (JSPGTL) is a generalization of the job shop problem in which there are time constraints restricting the minimum and/or the maximum distance between two operations. The JSPGTL involves a set of jobs that should be processed on a set of machines. Each job i consists of a sequence of operations; (i, j) denotes the jth operation of job i. Machines cannot process more than one job simultaneously. Each operation should be allocated to one machine. Every machine and every job is ready at time 0. Each job has a fixed processing sequence; if the process of an operation is started, it should be finished without any interruption. For some pairs of operations (i, j) and \((i',j')\), there are minimum and maximum time lag constraints, respectively, denoted by TL\(^\mathrm{min}_{(i, j), (i', j')}\) and TL\(^\mathrm{max}_{(i,j), (i',j')}\), restricting the distance between the end of (i, j) and the start of \((i',j')\) to the interval \([\mathrm{TL}^\mathrm{min} _{(i,j), (i',j')}, \mathrm{TL}^\mathrm{max} _{(i,j), (i',j')}]\). Solving the JSPGTL consists in sequencing all operations on the machines subject to a set of constraints. There are precedence constraints for operations of the same job, so each job consists of a set of operations that should be sequentially scheduled. Also, there are capacity constraints such that each machine processes at most one operation at a time, and each operation requires the uninterrupted and exclusive use of a given machine during \(p_{ij}\) time units. Finally, we consider the addition of minimum and maximum time lags constraints between operations which present the minimum and maximum waiting time between the ending time and the starting time of two operations. The objective is to find an optimal solution according to some criterion, most commonly the makespan, which is the completion time of the last operation.

Table 1 Example of instance job shop J
Full size table

Example: Table 1 illustrates an example of instance J for a job shop with three jobs and three machines.

The minimum and maximum time lags between operations of different jobs are:

$$\begin{aligned} \begin{array}{l} TL^\mathrm{min} _{(O11), (O13)} = 36 \quad TL^\mathrm{max} _{(O11), (O13)} = 45 \\ TL^\mathrm{min} _{(O11), (O22)} = 20 \quad TL^\mathrm{max} _{(O11), (O22)} = 30 \\ TL^\mathrm{min} _{(O21), (O31)} = 5 \quad TL^\mathrm{max} _{(O21), (O31)} = 20 \end{array} \end{aligned}$$

Figure 3 presents an example of a feasible solution in a Gantt chart model for the instance of a job shop with generic time lags given in Table 1.

Fig. 3
figure 3

Example of a Gantt chart solution

Full size image

3.2 Mathematical modeling

The mathematic model of the job shop scheduling problem with generic time lags is formulated as follows:

Input variables

  • M = the set of machines;

  • J = the set of jobs;

  • \(\Omega \) = the set of operations;

  • \(\Omega _{\mu }\) = the set of operations processed on machine \(\mu \).

Decision variables

  • \(p_{ij}\) = the duration of operation (i, j);

  • \(t_{ij}\) = the start times of operations (i, j);

  • TL\(^\mathrm{min}_{(i, j), (i', j')}\) = minimum time lags between operations (i, j) and \((i', j')\);

  • TL\(^\mathrm{max}_{(i,j), (i',j')}\) = maximum time lags between operations (i, j) and \((i', j')\);

  • \(x_{(ij),(i'j')}\) = corresponds to the sequencing variables;

    $$\begin{aligned} x_{(ij),(i'j')} = \left\{ \begin{array}{ll} 1 &{} \quad \hbox {if}\,\,(ij)\,\,\hbox {is before}\,\,(i'j') \\ 0 &{} \quad \hbox {Otherwise.} \end{array} \right. \end{aligned}$$

  • H is a large positive number.

Linear programming equations

The problem of linear formulation of a job shop with generic time lags was given by Lacomme et al. (2011) and was inspired by the linear programming formulation for job shop scheduling proposed by (Manne 1960).

$$\begin{aligned} \mathrm{Min} C_\mathrm{max} \end{aligned}$$
(1)

such that

$$\begin{aligned}&C_\mathrm{max} \ge t_{ij} + p_{ij} , \forall (i, j) \in \Omega \end{aligned}$$
(2)
$$\begin{aligned}&t_{i'j'} \le t_{ij} + p_{ij} + H.( x_{(ij),(i'j')} - 1 ),\nonumber \\&\quad \forall (i,j), (i', j') \in \Omega _{\mu }, \forall \mu \in M \end{aligned}$$
(3)
$$\begin{aligned}&t_{ij} \le t_{i'j'} + p_{i'j'} + H . x_{(ij),(i'j')} ,\nonumber \\&\quad \forall (i,j), (i', j') \in \Omega _{\mu }, \forall \mu \in M \end{aligned}$$
(4)
$$\begin{aligned}&t_{i'j'} \ge t_{ij} + p_{ij} + TL^\mathrm{min}_{(i, j), (i', j')}, \forall (i,j), (i', j') \in \Omega \end{aligned}$$
(5)
$$\begin{aligned}&t_{i'j'} \le t_{ij} + p_{ij} + TL^\mathrm{max}_{(i, j), (i', j')}, \forall (i,j), (i', j') \in \Omega \end{aligned}$$
(6)
$$\begin{aligned}&t_{ij} \ge 0, \forall (i,j) \in \Omega \end{aligned}$$
(7)
$$\begin{aligned}&x_{(ij),(i'j')} \in \{0,1\}, \forall (i,j), (i', j') \in \Omega _{\mu }, \forall \mu \in M \end{aligned}$$
(8)

Constraint (2) states that the makespan is greater than or equal to the finish time of each operation. Constraints (3) and (4) represent the machine disjunctions. Constraints (5) and (6) correspond to the time lags constraints.

When there is a classical precedence constraint between two operations, the value of the minimum time lag is set to 0, and the value of the maximum time lag is set to \(\infty \).

When there is no constraint between two operations, both the minimum and the maximum time lags are set to \(\infty \).

3.3 Disjunctive graph model

In the disjunctive graph introduced by Roy and Sussmann (1964), each operation is modeled by a node and an arc from operation (i, j) to operation \((i',j')\), and represents the minimum distance between the start time of these two operations. It corresponds to the binary constraint:

\(t_{i'j'} - t_{ij} \ge l_{(i j),(i' j')}\), where \(l_{(i j),(i' j')}\) is the length of the arc. The maximum time lag from an operation (i, j) to an operation \((i',j')\) is represented by an arc with negative length which corresponds to the duration of (i, j) plus the maximum time lag value. Minimum time lag constraints are modeled by an extra arc from operation (i, j) to operation \((i',j')\) and weighted with the processing time of (i, j) plus the minimum time lag value. When no time lags are specified (for example, between one operation and the dummy operation of the graph), it is possible to assume, without loss of generality, that we have null minimum time lags and infinite maximum time lags. Since there is no interest in considering infinite maximum time lags, negative arcs representing infinite maximum time lags are ignored in the graphic representation. To model time lag constraints on the conjunctive/disjunctive graph, we use the formulation based only on the start times of operations \(st_{Oi,j}\) (and the processing times of operations). Then, the time lag constraints given in Sect. 3.1 are modeled by:

  • 46 \(\le st_{O1,3} - st_{O1,1} \le \) 55

  • 30 \(\le st_{O2,2} - st_{O1,1} \le \) 40

  • 20 \(\le st_{O3,1} - st_{O2,1} \le \) 35

Figure 4 presents the disjunctive graph of the job shop scheduling problem with generic time lags given in Table 1. Maximum time lag constraints are represented by negative arc cost in the disjunctive graph from one operation to the previous one. The negative cost of the arc is equal to the duration of the previous operation plus the maximum time lag value.

Fig. 4
figure 4

Disjunctive graph

Full size image

4 Biogeography-based optimization

4.1 Basic concepts of the BBO algorithm

The BBO algorithm, proposed by Simon (2008), is inspired by the mathematics of biogeography, mainly from the work of MacArthur and Wilson (1967). A large number of theoretical, methodological, and practical studies on BBO have since arisen. The two main concepts of BBO are habitat suitability index (HSI) and suitability index variables (SIVs). Features that correlate with the HSI include rainfall, diversity of topographic features, land area, and temperature. SIVs are considered the independent variables of the habitat. Geographical areas that are well suited for species are said to possess a high HSI. Considering the optimization algorithm, a population of candidate solutions can be represented as vectors. Each integer in the solution vector is considered a SIV. In assessing the performance of the solutions, habitats with a high HSI are considered to be good solutions, and habitats with a low HSI are considered to be poor solutions. Therefore, the HSI is analogous to fitness in other population-based optimization algorithms. The two main operators of the BBO are migration and mutation. The main algorithm of the BBO is shown in Algorithm 1.

figure a

4.2 Adaptation of the BBO algorithm in scheduling problems

The BBO algorithm has been successfully used for solving many scheduling problems. Ma et al. (2015) proposed a multi-objective BBO for automated warehouse scheduling, in which a real-world scheduling problem was presented as a constrained multi-objective optimization problem. A railway scheduling application using BBO was presented by Zheng et al. (2014a, 2014b), which derived a mathematical model that considered multiple stations requiring supplies, source stations for storing supplies, and allocation stations for providing wagons. Rabiee et al. (2016) developed a modified BBO algorithm for hybrid flow shop scheduling to minimize mean tardiness under various assumptions, including machine eligibility, unrelated parallel machines, different ready times, and sequence-dependent setup times. Habib et al. (2011) introduced a new BBO algorithm for solving the flexible job shop scheduling problem. Wang and Duan (2014) proposed a HBBO algorithm for the job shop scheduling problem in which the proposed HBBO algorithm combines chaos theory and a “searching around the optimum” strategy with the basic BBO, which makes it converge to global optimum solution faster and more stably. Yang (2015) investigated a modified BBO algorithm with a machine-based shifting decoding strategy for solving the flexible job shop scheduling problem. Lin (2016) introduced a hybrid discrete BBO algorithm, or HDBBO, which combined the Nawaz, Enscore, and Ham (NEH) heuristic with opposition-based learning and BBO for the flow shop scheduling problem. The literature reports numerous applications of BBO to benchmarks and practical optimization problems and compares the performance against different well-known algorithms. The results confirm that BBO outperforms the existing algorithms and can efficiently solve most of the benchmark functions. In this work, we use the hybridization of BBO for the job shop scheduling problem with time lags and makespan minimization.

Fig. 5
figure 5

Habitat representation

Full size image

5 Hybrid biogeography-based optimization for the job shop scheduling problem with time lag constraints

In this section, we present the hybridization steps for the BBO algorithm with a Tabu search metaheuristic for solving the job shop scheduling problem with minimum and maximum time lags constraints.

5.1 Representing habitat

We represent a solution with a real number vector containing the total number of operations and the processing order of operations for each machine. Each vector presents a solution. Figure 5 presents an example of the representation of a solution from the problem instance given in Table 1. In Fig. 5, (\(O_{11}\), \(O_{21}\), \(O_{32}\), \(O_{33}\), \(O_{12}\), \(O_{23}\), \(O_{31}\), \(O_{22}\), \(O_{31}\)) is a possible habitat for an instance of a job shop scheduling problem with time lag constraints with problem size of \(3 \times 3\). We have a vector V containing the operations sequence with length \(L = (n \times m)\), equal to the total number of operations \((3 \times 3 = 9)\). For each machine, the processing order of operations is given. For example, the processing order of operations for machine 1 is (\(O_{21}\), \(O_{11}\), \(O_{32}\)). Each index represents the selected operation to be processed on the machine indicated at position p. For example, \(p=4, V(4)\) is the selected operation \(O_{21}\) to be executed on machine m2.

5.2 Initialization of population

The BBO algorithm starts with population habitats. According to the chosen parameter population size PS, an initial population containing PS individuals is generated using the greedy algorithm. This heuristic is a popular method for solving combinatorial optimization and operations research problems (i.e., generally NP-hard). Greedy heuristics are used because they are fast, produce solutions with good quality, are easy to implement, and can easily be expanded. They are commonly used to speed up research. Indeed, in most cases, greedy algorithms have a reduced polynomial time complexity, and their use often leads to better-quality local optima (Talbi 2009). The greedy algorithm starts building the solution from one operation to another. After inserting the operation to a defined position of the current solution, the different constraints are checked. If all constraints are satisfied, we proceed to the next operation. Otherwise this operation is deleted in the current position and added to another position that respects the different constraints, see Algorithm 2.

figure b

5.3 Selecting strategies

This step is one of the distinctive steps of BBO with other algorithms, and is executed through two different strategies, one for migration and one for mutation.

5.3.1 Selecting migration strategies

Solutions are selected for immigrating or emigrating according to the immigration rate \(\lambda _{i}\) and the emigration rate \(\mu _{j}\). According to the concept of the BBO algorithm, during the migration process, we face two types of selection. Firstly, we should determine whether or not a special habitat \(H_{i}\) should immigrate. To do so, a simple comparison of \(\lambda _{i}\) with a random number is done. Secondly, we should select habitat \(H_{i}\) for emigrating to \(H_{j}\). Details of the selection algorithm for migration are shown in Algorithm 3.

figure c

5.3.2 Selecting mutation strategies

According to the concept of the BBO algorithm, during the mutation process, a habitat \(H_{i}\) should or should not be mutated. For this, a simple comparison of the mutation probability with a random number is done. Algorithm 4 explains how the mutation selection strategy is performed in the BBO algorithm.

figure d

5.4 Migration operator

Migration is a probabilistic operator that is used for modifying each solution \(H_{i}\) by sharing features among different solutions. The idea of a migration operator is based on the migration in biogeography which shows the movement of species among different habitats. Solution \(H_{i}\) is selected as immigrating habitat with respect to its immigration rate \(\lambda _{i}\), and solution \(H_{j}\) is selected as emigrating habitat with respect to its emigration rate \(\mu _{j}\). This means that a solution is selected for immigrating or emigrating depending on its immigration rate \(\lambda _{i}\) or emigration rate \(\mu _{j}\); the migration process can be shown as:

\(H_{i}\)(SIV)\(\leftarrow H_{j}\)(SIV) After calculating the HSI for each solution \(H_{i}\), the immigration rate \(\lambda _{i}\) and the emigration rate \(\mu _{j}\) can be evaluated as follows:

$$\begin{aligned} \lambda _{i}= & {} I\left( 1 - \frac{k_{i}}{n} \right) \end{aligned}$$
(9)
$$\begin{aligned} \mu _{j} = E\left( \frac{k_{i}}{n} \right) \end{aligned}$$
(10)

In Eqs. (9) and (10), \(k_{i}\) represents the rank of the ith habitat after sorting all habitats according to their HSIs, and n represents the size of the population. It is clear that since higher HSI indicates a better solution, higher \(k_{i}\) represents the better solution. Therefore, the first solution is the worst, and the nth solution is the best. In the equations, n is the number of habitats in the population, while I represents the maximum immigration rate and E the maximum emigration rate, which are both usually set to 1. The two rates \(\lambda _{i}\) and \(\mu _{j}\) are the functions of fitness or HSI of the solution. Since, according to the biogeography, the SIVs of a high-HSI solution tend to emigrate to low-HSI solutions, a high-HSI solution has a relatively high \(\mu _{j}\) and low \(\lambda _{i}\), while in a poor solution, a relatively low \(\mu _{j}\) and a high \(\lambda _{i}\) are expected. The migration process can be presented as Algorithm 5 (Wang and Duan 2014).

figure e

Figure 6 illustrates an example of migration operator application for our problem, see Fig. 6.

Fig. 6
figure 6

Migration operator of the BBO algorithm

Full size image
Fig. 7
figure 7

Gantt charts of migration process solutions

Full size image

As mentioned earlier, the SIVs from a good habitat tend to migrate into a poor habitat. This migration operator is performed probabilistically based on immigration and emigration rates. In this example, we will explain how the migration is implemented in our BBO algorithm. Consider dealing with an instance of a job shop scheduling problem with time lags with three jobs, three operations, and three machines. Suppose, based on immigration and emigration rates, that an immigrating habitat \(H_{i} = (O_{21}, O_{11}, O_{32},O_{12},O_{23},O_{33},O_{31},O_{22},O_{31}) \)and an emigrating habitat \(H_{e} = (O_{11}, O_{21}, O_{32},O_{12},O_{33},O_{23},O_{31},O_{22},O_{31})\). The migration process is: \(H_{e}\) (SIV) \(\leftarrow \,H_{i}\) (SIV)

SIVs of \(H_{i}\) will be randomly selected and replace randomly selected SIVs of \(H_{e}\). Assuming that SIVs of \(H_{i}\) (\(O_{12}\), \(O_{23}\), \(O_{33}\)) are selected to replace SIVs of \(H_{e}\) (\(O_{12}\), \(O_{33}\), \(O_{23}\)), the migration process consists of the following steps:

  1. (1)

    SIVs of machine 2 from \(H_{i}\) (\(O_{12}\), \(O_{23}\), \(O_{33}\)) migrate into \(H_{e}\) to replace SIVs of \(H_{e}\) (\(O_{12}\), \(O_{33}\), \(O_{23}\)).

  2. (2)

    SIVs (\(O_{12}\), \(O_{23}\), \(O_{33}\)) replace SIVs (\(O_{12}\), \(O_{33}\), \(O_{23}\)).

  3. (3)

    SIVs (\(O_{11}\), \(O_{21}\), \(O_{32}\)) and (\(O_{31}\), \(O_{22}\), \(O_{31}\)) of machine 1 and machine 3 from \(H_{e}\) remain at original places.

  4. (4)

    Therefore, the new habitat, \(H_{n}\) = (\(O_{11}\), \(O_{21}\), \(O_{32}\), \(O_{12}\),\(O_{23}\), \(O_{33}\), \(O_{31}\), \(O_{22}\), \(O_{31}\)) is produced, see Fig. 7.

5.5 Mutation operator

Mutation is used to enhance the diversity of the population, which helps to decrease the chances of becoming trapped in the local optima. Solutions with very high HSI and very low HSI are both equally improbable, while medium-HSI solutions are relatively probable to mutate. Namely, a randomly generated SIV replaces a selected SIV in the solution \(H_{i}\) according to a mutation probability. Note that an elitism approach is employed to save the features of the habitat that has the best solution in the BBO process and guarantees the survival of the best individual(s). The habitat with the best solution has a mutation rate of 0. Mutation is a probabilistic operator that randomly modifies a solution’s SIV based on its priori probability of existence. The probability Ps, which represents that the habitat contains exactly species S, changes from time t to time \(t+\Delta t.\)

It is updated as follows:

$$\begin{aligned} P_{s} (t+\Delta t)= & {} P_{s} (t)(1- \lambda _{s}\Delta t- \mu _{s}\Delta t) \nonumber \\&+ P_{{s-1}\lambda _{s-1}} \Delta t + P_{{s+1}\mu _{s+1}} \Delta t \end{aligned}$$
(11)

Species count probabilities \(P_{s}\) computed from \(\lambda _{i}\) and \(\mu _{j}\) with equation (11) are used to determine the mutation rates. Suppose a habitat with S species is selected to execute the mutation operation, then randomly modify a chosen variable (SIV) based on its associated probability \(P_{s}\). The mutation rate m(s) can be computed according to the following function proportional to \(P_{s}\):

$$\begin{aligned} m(s) = m_\mathrm{max} \left( 1- \frac{P_{s}}{P_\mathrm{max}} \right) \end{aligned}$$
(12)

Suppose that habitat \(H_{i} \in \mathrm{SIV}^ {R}\) represents a feasible solution to some problem; the mutation process can be presented in Algorithm 6 (Wang and Duan 2014).

figure f

If a solution is selected for mutation, it is replaced by a randomly generated new solution set. This random mutation affects the exploration ability of the BBO algorithm (Feng et al. 2017). The mutation habitats are kept in the population only if the quality is better than the original habitats. However, this is not practical when solving a complex optimization problem such as job shop scheduling with time lag constraints. Most of the time, the resulting habitats from a simple mutation operator are unlikely to be better than the original habitats, especially as the algorithm converges. To overcome this weakness of the classical BBO algorithm, we propose replacing the mutation operator with a Tabu search (TS) procedure. Proposed by Glover (1986), TS is a metaheuristic which performs a local search based on the information in the memory. TS is both a neighborhood-based and iterative procedure. At each iteration, the current solution will make a move to the neighborhood solution with the best objective function value. To avoid trapping in local optima, the move that has been made will be stored in a Tabu list, and a reverse move to previous solutions is forbidden. The performance of Tabu search is highly dependent on the neighborhood type used and Tabu list implementation. The Tabu search metaheuristic has been successfully used for solving different combinatorial optimization problems. The advantages of replacing the mutation operator of the classical BBO algorithm with TS are twofold. First, the original aim of the mutation process is maintained, which is to increase the diversity of the population. At the same time, the quality of the resulting habitats is prevented from being degraded (Wee et al. 2016). Different parameters of the TS metaheuristic are presented in the following sections.

5.5.1 Initial solution

The initial solution is the starting step used for the algorithm to begin the search for better configurations in the search space. In this implementation, the initial solution used is the resulting solution of the migration step of the BBO algorithm; the Tabu search process then proceeds iteratively to visit series of locally best configurations following a neighborhood function, see Fig. 8.

Fig. 8
figure 8

Gantt chart of initial solution

Full size image
Fig. 9
figure 9

Swapping moves

Full size image
Fig. 10
figure 10

Exchange moves

Full size image

5.5.2 Neighborhood structure

A neighborhood is a set of solutions (neighbors) created by a specific operator.

A move is a function transforming a solution into one of its neighbors. In the literature, we can find many types of moves. Among the most common we can cite:

Swapping moves: this type of neighborhood is created by reversing two successive elements in the current solution. This movement generates a neighborhood of size \((n-1)\), which can be explored in O(\(n^{2}m\)), see Fig. 9.

Exchange moves: this type of neighborhood is created by swapping the positions \(p_{i}\) and \(p_{j}\) of any two elements. This movement generates a neighborhood of size n\((n-1)\)/2, and exploring the neighborhood reaches \(O(n^{3}m)\), see Fig. 10.

Insertion moves: this type of neighborhood is created b moving an element from its original position \(p_{i}\) to a new position \(p_{j}\). This movement generates a neighborhood of size \((n-1)^{2}\), but it can be evaluated in \(O(n^{2}m)\), see Fig. 11.

Fig. 11
figure 11

Insertion moves

Full size image

Deroussi et al. (2006) proposed a study of different neighborhood structures and showed that local search algorithms based on swap moves do not allow one to reach good-quality solutions, and local search algorithms based on exchange moves provide good-quality local minima, but the neighborhood exploration is in \(O(n^{3}m)\), which can cause considerable computation time for large instances.

In this implementation, we use the insertion move structure, which is considered the most effective and most commonly used in several approaches described in the literature because of its efficiency in terms of quality of the solution and running time. Figure 12 illustrates an example of an insertion move neighborhood structure for the job shop scheduling problem with time lag constraints.

As mentioned earlier, the insertion move neighborhood structure is performed by simply moving a selected operation from its original position \(p_{i}\) to a new position \(p_{j}\). Assuming that the operation \(O_{13}\) is chosen to be moved, the resulting neighbor solution produced is shown in Fig. 13.

5.5.3 Tabu List

The Tabu list (TL) can be used to avoid searching the previously tested solutions of the minimization or maximization problem. The TL stores the attributes of the moves that have been made. When the length of the list reaches the maximum fixed value \(L_\mathrm{max}\), before adding the next element, the oldest one is deleted. When, in a given step, all the moves are forbidden by the Tabu list, the oldest elements are deleted from the list until at least one move is allowed.

5.5.4 Diversification

In order to ensure sufficient diversity in the search, a specific diversification must be incorporated to complement the neighborhood. The diversification step is activated when the number of iterations continuously increases without any improvement in the current solution, which means that the best solution found has not been replaced by one of these neighbors for some time, which is a sign that the Tabu search was probably trapped in a local optimum. In this case, a simple effective method is used to achieve diversity. A new schedule is generated using a new insertion order of jobs in order to explore a new region of the search space, and the resolution process is started again. Next, the number of iterations diversification, i.e., the number of iterations after the last improvement, is reset, and the research process continues by considering the solution obtained by diversification phase as a new current solution until reaching the stopping criterion.

Fig. 12
figure 12

Insertion moves structure

Full size image
Fig. 13
figure 13

Gantt charts of insertion moves neighborhood

Full size image

6 Experimental results

In order to evaluate the performance of the proposed hybrid biogeography-based optimization algorithm for the job shop scheduling problem with minimum and maximum time lag constraints, we give in this section the results of the HBBO algorithm for the job shop scheduling problem with time lags between successive operations of the same job (JSPTL) and the results of the job shop scheduling problem with generic time lags between whatever pairs of operations of different jobs (JSPGTL). Several experiments were conducted on a set of benchmarks for job shop problems with additional time lag constraints existing in the literature.

Table 2 Results for JI/OI/TS/MATS/CAPTS/GBBO/HBBO for Fisher and Thompson instances
Full size table

6.1 Experimental results for JSPTL

For the JSPTL problem, we use the instances of Fisher and Thompson (1963), Lawrence (1984), and Carlier (1978). For instances of Fisher and Thompson (1963) and Lawrence (1984), we compare the results of the HBBO algorithm with:

  • Generalized disjunctive constraint propagation based on a job insertion heuristic JI (Artigues et al. 2011)

  • Approach based on operation insertion heuristic OI (Caumond et al. 2005b)

  • Tabu Search algorithm TS (Caumond et al. 2004)

  • Multi-agent model based on Tabu search metaheuristic MATS (Harrabi and Belkahla Driss 2015)

  • Competitive agents implementing parallel Tabu searches CAPTS (Harrabi et al. 2017a, b, c)

  • Greedy biogeography-based optimization GBBO (Harrabi et al. 2018)

For instances of Carlier (1978), we compare the results of the HBBO algorithm with:

  • Tabu search algorithm TS (Caumond et al. 2004)

  • Memetic algorithm Mem (Caumond et al. 2008)

  • Multi-agent model based on Tabu search metaheuristic MATS (Harrabi and Belkahla Driss 2015)

  • Competitive agents implementing parallel Tabu searches CAPTS (Harrabi et al. 2017a, b, c)

  • Greedy biogeography-based optimization GBBO (Harrabi et al. 2018)

For all instances, TL\(^\mathrm{min} _{(i, j), (ij+1)}\) = 0.

For each instance, TL\(^\mathrm{max} _{(i, j), (ij+1)}= \{0, 0.5, 1, 2\}\).

Instances are designed with NameTL\(^\mathrm{min} _{(i, j), (ij+1)} \mathrm{TL}^\mathrm{max} _{(i, j), (ij+1)}\).

For example, ft06-0-0.5 is the instance of Fisher and Thompson 6 with TL\(^\mathrm{min} _{(i, j), (ij+1)}\) = 0 and TL\(^\mathrm{max} _{(i, j), (ij+1)}\)= 0.5. For some instances, HBBO gives an optimal solution with a makespan value equal to the lower bound. We mark the values of these instances with “*”.

6.1.1 Comparison results of Fisher and Thompson instances for the JSPTL problem

Table 2 presents results for JI/OI/TS/MATS/CAPTS/GBBO/HBBO for Fisher and Thompson instances.

For the ft06 instances, the proposed HBBO algorithm gives better results than the job insertion heuristic method in 100% of instances and better results than TS, MATS, and GBBO in 75%. Compared with CAPTS, HBBO gives better results in 25% and gives 50% better than the OI heuristic (see Table 2).

6.1.2 Comparison results of Lawrence instances for the JSPTL problem

Table 3 presents results for JI/OI/TS/MATS/CAPTS/GBBO/HBBO for Lawrence instances.

Table 3 Results for JI/OI/TS/MATS/CAPTS/GBBO/HBBO for Lawrence instances
Full size table

For Lawrence instances with ten jobs and five machines, results show that the BBO algorithm gives better results than the job insertion heuristic and Tabu search heuristic in 95% of instances, and better results than the operation insertion heuristic, MATS, CAPTS, and Greedy BBO in 100% of instances, see Table 3.

6.1.3 Comparison results of Carlier instances for the JSPTL problem

Table 4 presents results for TS/Mem/MATS/CAPTS/GBBO/HBBO for Carlier instances.

Table 4 Results for TS/MEM/MATS/CAPTS/GBBO/HBBO for Carlier instances
Full size table

For Carlier’s instances, results show that the HBBO algorithm gives better makespan values than the Tabu search in 87.5% of instances and better results than the memetic algorithm in 40% of instances. Compared with CAPTS and GBBO, HBBO gives better results in 25% and better results than MATS in 50%. See Table 4.

Table 5 Results for DCP/GR-ARP-MD/TS/GATS/MAHGA/GBBO/HBBO for Carlier instances
Full size table
Table 6 Results for DCP/GR-ARP-MD/TS/GATS/MAHGA/GBBO/HBBO for Carlier instances
Full size table

6.2 Experimental results for the JSPGTL problem

For the JSPGTL problem, we use the instances of Lawrence (1984) and Carlier (1978).

For instances of Carlier, we compare the results of the proposed HBBO algorithm with:

  • Dedicated constraint propagation DCP (Lacomme et al. 2011)

  • Greedy randomized propagation rules modified ARP-MD Lacomme and Tchernev (2012)

  • Tabu search (TS) metaheuristic (Harrabi and Belkahla Driss 2016);

  • Genetic algorithm combined with the Tabu search (GATS) metaheuristic (Harrabi et al. 2017a, b, c);

  • Multi-agent model based on the hybrid genetic algorithm (MAHGA) (Harrabi et al. 2017a, b, c);

  • Greedy biogeography-based optimization (GBBO) (Harrabi et al. 2018).

6.2.1 Comparison results of Lawrence instances for the JSPGTL problem

Table 5 presents results for DCP/GR-ARP-MD/TS/GATS/MAHGA/GBBO/HBBO for Carlier instances.

For Carlier instances, results show that the HBBO algorithm gives better results than the dedicated constraint propagation in 62% of instances and better results than the greedy randomized propagation rules and greedy biogeography-based optimization in 100% of instances. Compared with the Tabu search, HBBO gives better results in 37%, and compared with the hybrid genetic algorithm, the HBBO algorithm gives better results in 87% of instances and better results in 75% than the multi-agent model based on the hybrid genetic algorithm.

6.2.2 Comparison results of Lawrence instances for the JSPGTL problem

Table 6 presents results for DCP/GR-ARP-MD/TS/GATS/MAHGA/GBBO/HBBO for Lawrence instances.

For Lawrence instances, results show that the HBBO algorithm gives better results than the dedicated constraint propagation in 82% of instances and better results than the greedy randomized propagation rules and greedy biogeography-based optimization in 100% of instances. Compared with the Tabu search, HBBO gives better results in 65%, and compared with hybrid genetic algorithm, the HBBO algorithm gives better results in 85% of instances and better results in 62% than the multi-agent model based on the hybrid genetic algorithm.

6.3 Analysis of results

The proposed hybrid biogeography-based optimization was evaluated by using 88 well-studied instances with different sizes of problem; 40 instances for a job shop with time lags and 48 instances for a job shop with generic time lags in order to prove its efficiency and effectiveness. These problem instances are commonly utilized for benchmarking job shop scheduling with time lags with the objective of minimizing makespan.

Results show that hybrid BBO gives 14 optimal solutions from 80 instances compared with the lower bound found using CPLEX, proposed (by Lacomme and Tchernev 2012)

The proposed hybrid biogeography-based optimization was able to achieve 11 optimal solutions for the following instances of a job shop with time lags: ft06-0-0, ft06-0-2, la01-0-2, la02-0-1, la02-0-2, la03-0-2, Car5-0-1, Car5-0-2, Car6-0-1, Car 7-0-1, Car 8-0-1.

In addition, hybrid BBO was able to achieve three optimal solutions for the following instances of a job shop with generic time lags: la01, la12, la22.

Moreover, hybrid BBO was able to achieve near-optimal schedules for the majority of all problem instances. It is clear that the proposed optimization technique achieved 36% of the optimal solutions for JSPTL and near-optimal solutions for the rest of instances.

For the job shop with generic time lags, the best-known solution considered is the DCP approach. The proposed hybrid biogeography-based optimization gives the best-known solutions in some instances (la01, la04) and gives for the remaining instances the near-optimal schedules in which they were generally better than those of the other algorithms.

Based on the above results, it appears that the proposed technique was able to provide optimal schedules in some cases and near-optimal schedules in most cases. Based on these results, the proposed approach can be considered as an efficient algorithm for solving job shop scheduling problems with time lags and generic time lags.

7 Conclusion

Over the past few decades, a number of new types of algorithms have been developed for solving optimization problems. Biogeography-based optimization is a new simulated bio-inspired intelligent algorithm which has some features that are distinct from other biology-based optimization methods. We propose an improved biogeography-based optimization algorithm hybridized with the Tabu search metaheuristic for solving the job shop scheduling problem including minimum and maximum time lag constraints, which is an NP-hard problem, and obtaining a feasible solution is a difficult problem. According to an analysis and comparisons of the test results of HBBO through different instances of job shop scheduling problems with additional time lag constraints described in the literature, this algorithm is better able to solve well-known benchmarks. Compared with other proposed algorithms, the HBBO algorithm has significantly better performance. Based on the good results of the proposed HBBO algorithm, it can be used to solve other extensions of our problem. We can develop the hybridization of BBO with other algorithms such as ACO, PSO, or GA in order to solve the same problem. We can also adopt the distributed BBO via the multi-agent system.