Keywords

1 Introduction

The scheduling problem is one of the most encountered problems in the management of production system. It occurs in all the economic domains, from computer engineering to manufacturing techniques. The Job Shop Problem with Time Lags and Single Transport Robot (JSPTL-STR) is a special case of the classical Job shop problem, it arises in many real-life scheduling applications such as steel industry, chemical reactions, hoist-scheduling problems, perishable product production and in biotechnology and chemistry.

JSPTL-STR as a new sub-problem in a Job shop environment where additional minimum and maximum Time Lags constraints between operations are considered and jobs have to be transported between machines by a single transport robot. The addition of time lag constraints between operations and transportation time of operations between machines makes difficult even the usually simple task of finding a feasible schedule. This problem belongs to NP-hard combinatorial optimization problems that need “strong” resolution method. The Biogeography Based Optimization algorithm was successfully used for solving many scheduling problems in the literature. We propose a Hybrid Biogeography-Based Optimization algorithm (HBBO) for solving the JSPTL-STR problem with makespan minimization. In the proposed HBBO, the effective greedy constructive heuristic is adapted to generate the initial population of habitat. Moreover, a local search metaheuristic is investigated in the mutation step in order to ameliorate the solution quality and enhance the diversity of the population. To assess the performance of HBBO, a series of experiments on well-known benchmark instances for job shop scheduling problem with time lag constraints are performed. The reminder of the paper is organized as follows. Section 2 presents the related works, in Sect. 3, we present the problem formulation. In Sect. 4, the disjunctive graph model is given. In Sect. 5, we give the basic concepts of BBO algorithm. In Sect. 6, we present the adaptation of HBBO algorithm for our problem. Section 7 analyzes the performance results of HBBO when applied to solve instances of benchmark problems. At last, we come to our conclusion and some possible future directions.

2 Related Works

We study the Job shop Scheduling Problem with Time Lags and Single Transport Robot which is a new extension of Job shop Scheduling problem and consists of two sub-problems; the Job shop Scheduling Problem with Time Lags and the Job shop Scheduling Problem with Single Transport Robot. Time lag means 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 applications of Job shop, either minimum or maximum time lags. Minimum time lag constraints can be corresponded to overlap time, storage time, transit time, communication time between processes of a computer system, etc. Maximum time lags can be used to demand the waiting time between operations must not be overly long to avoid deterioration of products. Minimum and maximum time lag constraints arise in many real-life scheduling applications such as: steel industry, chemical reactions, hoist-scheduling problems, perishable product production and biotechnology and chemistry problems.

Different methods were proposed for solving the Job shop Scheduling Problem with Time Lags in the literature. Caumond et al. [4,5,6] and [7] introduced different metaheuristics such as tabu search algorithm, genetic algorithm and memetic algorithm. Deppner [9] proposed some heuristics for solving the Job shop problem with additional time lags constraints. Karoui et al. [21] investigated a Climbing Discrepancy Search method. Artigues et al. [2] proposed a job insertion heuristic and generalized resource constraint propagation mechanisms. González et al. [10] proposed a scatter search procedure combining the path relinking and the tabu search metaheuristic. Harrabi et al. [12,13,14,15,16,17] and [18] proposed a variety of metaheuristics, hybrid approaches, and distributed models using multi-agent system. Lacomme et al. [23] and [24] proposed some dedicated constraint propagation and greedy randomized priority rules. Different methods were proposed for solving the Job shop Scheduling Problem with Single Transport Robot. Hurink and Knust [19] and [20] proposed a tabu search metaheuristic. Lacomme et al. [22] proposed a branch and bound procedure combined with a discrete events simulation model. Caumond et al. [8] proposed a mixed integer linear program and a heuristic branch and bound approach. Afsar et al. [1] proposed a disjunctive graph modeling and a Greedy Randomized Adaptive Search Procedure with an Evolutionary Local Search procedure (GRASP \(\times \) ELSE) for solving the Job shop problem with time lags and transportation constraints and they considered the waiting time between operations as the transportation time of operations.

In this paper, we propose the first resolution of the Job shop Scheduling Problem with Time Lags and Single Transport Robot using the Hybrid Biogeography-Based Optimization algorithm combined with greedy heuristic in the initialisation step and local search procedure in the mutation step.

3 Problem Formulation

The formulation of Job shop Scheduling problem with Time Lags and Single Transport Robot is an extension of the Lacomme’s formulation [23] extended by adding the transportation time constraints. The JSPTL-STR 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 \(j^{th}\) operation of job i. Every operation must be assigned to a unique machine without interruption. For some pairs of operations (i, j) and (i’, j’) there are minimum and maximum time lag constraints respectively denoted by \(TL^{min}_{(i, j), (i', j')}\) and \(TL^{max}_{(i,j), (i',j')}\) restricting the distance between the end of (i, j) and the start of (i’, j’) to the interval \([TL^{min} _{(i,j), (i',j')}, TL^{max} _{(i,j), (i',j')}]\). Additionally, each job \(J_{i}\) (\(J_{1}\), ... , \(J_{n}\)) is composed of \(n_{i-1}\) transport operations {\(T_{i,1}\), \(T_{i,2}\), ... , \(T_{i,n_{i-1}}\)} to be made by a robot R from one machine to another. They occur if a job changes from one machine to another, i.e. if job \(J_{j}\) is processed on machine \(M_{k}\) and afterwards on machine \(M_{l}\), a transportation time \(T_{jkl}\) arises. We assume that all transportations have to be done by a single transport robot R which can handle at most one job at a time.

Solving the JSPTL-STR consists in sequencing all operations on the machines, such that the following constraints are satisfied:

  1. (i)

    Precedence constraints for operations of the same job;

  2. (ii)

    Minimum and Maximum Time Lag constraints;

  3. (iii)

    Each machine processes at most one operation at a time;

  4. (iv)

    The robot can transport at most one operation at a time;

The objective is to find a schedule that minimizes the makespan which is the total completion time \(C_{max}\) = Max \(C_{i}\) where \(C_{i}\) is the finish time of job i.

4 Disjunctive Graph Model

The disjunctive graph model for the classical Job shop problem developed by Roy and Sussmann [28] was extended to the Job shop Scheduling Problem with Single Transport Robot by Hurink and knust [20] which incorporate the scheduling of the robot into the model. We extend this representation by adding arcs for time lags between operation into the model.

In the disjunctive graph, each operation is modeled by a node and an arc from operation (i, j) to operation (i’, j’) 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. 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 extra arc from operation (i, j) to operation (i’, j’) and it is 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, to have null minimum time lags and infinite maximum time lags. Additionally, transport operations are introduced for all needed transports as additional vertices in the disjunctive graph and requiring that these operations have to be processed by the robot. Furthermore, the empty moving times are modeled as sequence-dependent setup times. The disjunctive graph \(\hbox {G} = (\hbox {V, C}\cup \hbox {D}_{M}\cup \hbox {D}_{R}\)) consists of a set of vertices V containing all operations (machine operations and transport operations) and two dummy nodes 0 and *, a set of conjunctions C representing the job orders, disjunctions for the machines (\(D_{M}\)) and the robot (\(D_{R}\)). For each job \(J_{j}\) (\(\hbox {j}= 1, ..., \hbox {n}\)) we introduce \(n_{j}\) \(-\)1 so-called transport operations \(t_{ij}\) (\(\hbox {i}= 1, \ldots , n_{j-1}\)) with precedences \(O_{ij} \rightarrow T_{ij} \rightarrow O_{i+1, j}\). The processing time of \(T_{ij}\) is equal to the transportation time of job \(J_{j}\) from machine \(\mu _{ij}\) to \(\mu _{i+1, j}\), i.e. \(\hbox {p}(T_{ij}) = T_{jkl}\), when \(\mu _{ij} = M_{k}\), \(\mu _{i+1, j}= M_{l}\).

Example

We consider an instance of Job shop Scheduling Problem with Time Lags and Single Transport Robot given in Table 1 with 3 jobs and 3 machines. So we have 9 “ordinary” operations and 6 “transport” operations. Transportation times of robot between each pairs of machines is 5.

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

$$TL^{min} _{(O11), (O13)} = 36 \qquad TL^{max} _{(O11), (O13)} = 95$$
$$TL^{min} _{(O11), (O22)} = 15 \qquad TL^{max} _{(O11), (O22)} = 50$$
$$TL^{min} _{(O21), (O31)} = 13 \qquad TL^{max} _{(O21), (O31)} = 35$$

The corresponding disjunctive graph is given in Fig. 1.

Table 1. Example of instance Job shop J
Full size table
Fig. 1.
figure 1

Disjunctive graph model

Full size image

5 Biogeography-Based Optimization

BBO algorithm, proposed in 2008 by Simon [29], is inspired by the mathematics of biogeography and mainly the work from MacArthur and Wilson [26]. Later, a large amount of theoretical, methodological, and practical studies on BBO have come into being. The two main concepts of BBO are Habitat Suitability Index (HSI) and Suitability Index Variables (SIVs). Features that correlate with HSI include rainfall, diversity of topographic features, land area, and temperature. Moreover, SIVs are considered as the independent variables of the habitat. The two main operators of BBO are migration and mutation. Migration operator, including immigration and emigration, bridges the communication of habitats in an ecosystem. Deciding whether or not a habitat performs emigration or immigration is up to its HSI. Mutation operator is used to enhance the diversity of the population, which helps to decrease the chances of getting trapped in local optima.

BBO algorithm was successfully used for solving many scheduling problems. Rabiee et al. [27] developed a modified BBO algorithm for hybrid flow shop scheduling problem. Habib et al. [11] introduced a new BBO algorithm for solving the flexible Job shop scheduling problem. Wang et al. [30] proposed a hybrid BBO algorithm for Job shop scheduling problem. Yang [31] investigated a modified BBO algorithm with machine-based shifting decoding strategy for solving the flexible Job shop scheduling problem. Lin et al. [25] introduced a hybrid discrete BBO algorithm for flow shop scheduling problem.

In this work, we use an Hybrid BBO algorithm for the Job shop Scheduling Problem with Time Lags and Single Transport Robot with makespan minimization.

6 Hybrid BBO Algorithm for JSTL-STR Problem

6.1 Representing Habitat

The Job shop Scheduling Problem with Time Lags and Single Transport Robot is composed of two types of operations: the machine operations and the transport operations, that’s why the representation is encoded in two vectors: firstly, a vector V1 contains the machine operations sequence with length L1 equal to the total number of machine operations and where each index represents the selected operation to be processed on machine indicated at position p. Secondly, a vector V2 contains the machine operations and transport operations sequence with length L2 equal to the total number of machine operations and transport operations and where each index represents the selected machine operation or transport operation indicated at position p. See Fig. 2.

Fig. 2.
figure 2

Habitat representation

Full size image

6.2 Initialisation 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 [32] in order to get out of a local optimum and provide a good exploration of the search space. This heuristic is one of the popular methods to solve hard optimization problems. It is easy to be implemented and expanded and it produces solutions with good quality.

6.3 Selection Strategies

This step is one of the distinctive steps of BBO with other algorithms, which is executed through two different strategies, one for migration and one for mutation. To explain the selection strategies for migration, we should firstly define the immigration rate \(\lambda _{i}\) and the emigration rate \(\mu _{j}\). During the migration process, we face two types of selection. Firstly, we should determine whether a special habitat \(H_{i}\) should be immigrated or not. 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}\). During the mutation process, a habitat \(H_{i}\) selected to be mutated according to a simple comparison of the mutation probability with a random number.

6.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}\). It means that a solution is selected for immigrating or emigrating depends on its immigration rate \(\lambda _{i}\), or emigration rate \(\mu _{j}\); the migration process can be shown as:

$$H_{i}(\hbox {SIV})\leftarrow H_{j}(\hbox {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(1 - \frac{k_{i}}{n}) \end{aligned}$$
(1)
$$\begin{aligned} \mu _{j} = E(\frac{k_{i}}{n}) \end{aligned}$$
(2)

In (1) and (2), \(k_{i}\) represents the rank of the \(i^{th}\) habitat after sorting all habitats according to their HSIs. It is clear that since more HSI represents a better solution, more \(k_{i}\) represents the better solution. Therefore, the \(1^{st}\) solution is the worst and the \(n^{th}\) solution is the best. I is the maximum immigration rate and E the maximum emigration rate which are both usually set to 1, n is the number of habitats in the population. 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. Figure 3 illustrates an example of migration operator of BBO for the Job shop Scheduling Problem with Time Lags and Single Transport Robot.

Fig. 3.
figure 3

Migration operator of BBO algorithm

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 Job shop Scheduling Problem with Time Lags and Single Transport Robot presented in Table 1. Suppose, based on immigration and emigration rates, that an immigrating habitat \(H_{i}\) = (\(O_{11}\), \(O_{21}\), \(O_{32}\), \(O_{12}\), \(O_{23}\), \(O_{33}\), \(O_{22}\), \(O_{31}\), \(O_{13}\)) and an emigrating habitat \(H_{e}\) = (\(O_{11}\), \(O_{21}\), \(O_{32}\), \(O_{12}\), \(O_{33}\), \(O_{23}\), \(O_{31}\), \(O_{22}\), \(O_{13}\)). The migration process is: \(H_{e}(\hbox {SIV})\leftarrow H_{i}(\hbox {SIV})\)

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

  1. (1)

    SIVs of machine 2 \(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 of \(H_{i}\) (\(O_{12}\), \(O_{23}\), \(O_{33}\)) replace SIVs of \(H_{e}\) (\(O_{12}\), \(O_{33}\), \(O_{23}\)).

  3. (3)

    SIVs (\(O_{11}\), \(O_{21}\), \(O_{32}\)) of machine 1 and SIVs (\(O_{31}\), \(O_{22}\), \(O_{13}\)) of 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_{13}\)) is produced.

6.5 Mutation Operator

Mutation is a probabilistic operator that randomly modifies a solution’s SIV based on its priory probability of existence. Mutation is used to enhance the diversity of the population, which helps to decrease the chances of getting trapped in 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_{m}\) 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 BBO process. The habitat with the best solution has a mutation rate of 0.

In this step of the algorithm, we choose to use the local search procedure based on exchange moves neighborhood mechanism. This step starts using the solution result of migration step as the initial solution then, applying the neighborhood structure to generate a modified solution. Figure 4 illustrates an example of mutation operator of BBO. We propose to use a local search procedure based on exchange moves neighborhood mechanism. This type of neighborhood is to swap the positions \(p_{i}\) and \(p_{j}\) of any two elements. This movement can generate good neighborhood solutions and more explore the solution space.

Fig. 4.
figure 4

Mutation Operator of BBO

Full size image

As mentioned earlier, the local search mutation mechanism is performed by replacing a selected SIV of a habitat with other generated SIV. In our example the mutation process consists in:

  1. (1)

    SIV \(O_{11}\) is chosen to mutate.

  2. (2)

    Assume that the new SIV which is randomly generated is \(O_{21}\). SIV \(O_{11}\) is replaced with \(O_{21}\).

  3. (3)

    SIV \(O_{21}\) takes the place of \(O_{11}\).

  4. (4)

    The resulting mutated habitat is produced.

7 Experimental Results

We study for the first time the Job shop Scheduling problem with Time Lags and Single Transport Robot and we propose a new data set of benchmarks. The studied problem is composed of two sub-problems; the Job shop Scheduling Problem with Time Lags constraints and the Job shop Scheduling Problem with Single Transport Robot. For this reason, the new benchmark data set is based on benchmark from the literature of these two sub-problems. In fact, we combine benchmark data set of Carlier [3] for Job shop Scheduling Problem with Generic Time Lags and data set of Hurink and Knust [20] for Job shop Scheduling Problem with Single Transport Robot. For instances of Carlier, we add the full and empty moving transportation time of single robot between machines from Hurink and Knust data set [20]. In Table 2, we give results of Hybrid Biogeography-Based Optimization algorithm used for solving Carlier’s instances of Job shop Scheduling Problem with Time Lags and Single transport Robot. We give for each instances the name, size, results of CPLEX linear programming model, results of classic Biogeography-Based Optimization algorithm and results of Hybrid Biogeography-Based Optimization.

Each instance is executed 20 times then, we return the average. The experimental parameters used are:

  • Number of iterations: 200

  • Population size: 75

  • Immigration rate: 0.7

  • Emigration rate: 0.3

  • Mutation rate: 0.5

Table 2. Makespan results for Carlier instances
Full size table

Analysis of Results

In order to prove the efficiency of the proposed Hybrid Biogeography-Based Optimization, it was evaluated by using 24 instances of problem generated from Carlier [3] benchmark instances for Job shop Scheduling Problem with Generic Time Lags combined with Hurink and Knust [20] benchmark for Job shop Scheduling Problem with Single Transport Robot. These problem instances are commonly utilized for benchmarking the Job shop Scheduling Problem with Time Lags and Single Transport Robot with the objective of minimizing makespan.

Results show that the Hybrid Biogeography-Based Optimization gives solutions near of the optimal solutions founded using CPLEX for most of the instances. Moreover, it’s clear that the Hybrid BBO was improved using greedy heuristic and local search algorithm and was able to enhance the BBO results for all tested instances of the problem.

8 Conclusion

During the last decades, different 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 unique to other biology-based optimization methods. We propose an Hybrid Biogeography-Based Optimization algorithm combined with greedy heuristic and local search procedure for solving the Job shop Scheduling Problem with Time Lags and Single Transport Robot, which is an NP-hard problem and the obtaining of 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 Problem with Time Lags and Single Transport Robot, this algorithm can better solve most of instances. Due to 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.