A hybrid genetic algorithm with a neighborhood function for flexible job shop scheduling

Abstract

One of the most important issues of manufacturing systems optimization is scheduling. In fact, it plays a great role in reducing the production time and minimizing the required resources for production. Recently, due to the furious competition between companies, manufacturers are pushed to ensure products of high quality with a minimum amount of resources. In addition to that, they should satisfy the deadline of theirs customers. The Flexible Job Shop Scheduling Problem (FJSSP) is a very popular pattern in the real manufacturing systems. This problem is a generalization of the Classical Job Shop problem (JSP). FJJSP is called flexible because a machine can perform many types of operations. Each job in FJSSP has its own production sequence, composed of a set of operations. However, each machine can execute one operation at the same time. The problem is how to ensure the achievement of all jobs in the shortest time (Makespan).

A hybrid genetic algorithm (HGA) to solve FJSSP is proposed. An Improved Tabu Search (ITS) algorithm with an original neighborhood function is designed, to improve the performance of GA. The approach was tested and validated using one of the most known benchmarks. The effectiveness of the proposed approach is proved by tests.

Keywords

Manufacturing optimization flexible job shop scheduling problem hybrid approach genetic algorithm improved Tabu search

1. Introduction

One of the most difficult problems of manufacturing systems controlling is the scheduling problem [1]. In fact, an optimal schedule ensures a maximum quantity of products with low-cost in term of resources. The flexibility of resources (machines) allows managing undesirable events such as machine breakdown, but it increases dramatically the complexity of the problem, due to the second assignment sub-problem, which consists in selecting one machine of each operation.

The aim of this paper is to resolve the flexible job shop scheduling, which consist to organize the execution of many jobs by a set of machines in the shortest time. Each job is composed of a set of elementary operations. This problem can be divided into two sub problems: (a) Assign each job operation to a machine that is chosen among a set of candidate machines. (b) Find the best jobs sequence in each machine. Thus, searching the best assignment and sequencing combination among a big number of possible solutions, is considered as an optimization problem.

FJSSP problem is NP-Hard [1]. The flexibility increases greatly the complexity of the problem because it requires an additional level of decision (selection of a machine for each operation).

These are many real problems which are classified as FJSSP such us, assembling of manufacturing parts to get final products. FJSSP exists in many industrial processes, such as crane operations (simulation and optimization of transport systems), scheduling in real manufacturing systems, aircraft scheduling, etc. [2].

This paper is organized as follow: In the first section, we present a literature review about the flexible job shop scheduling problem. In the second section, the considered problem is illustrated. To simplify our approach, clarification of the proposed model for optimization is introduced, and how the Tabu search was integrated in the genetic algorithm (GA) and what is our contribution. The next two sections will cover the proposed Tabu search and GA used to reach good or optimal solutions. The last section is devoted to experiments and results.

2. Literature review

Due to the large application of FJJSP, especially in scheduling and control of manufacturing systems, FJJSP attracted many researchers in the last decades to provide solutions to manufacturers’ requests.

Mastrolili and Gambardella [3] proposed a new method based on the local search with two neighborhood functions. The assignment sub problem was solved by a special neighborhood function. A second neighborhood function was applied to sequencing sub problem.

A new approach based on the localization method with an evolutionary algorithm was proposed by Kacem et al. [4]. Two criteria were used to evaluate solutions: minimization of Makespan and the total machines workload. This method allows solving the assignment sub problem. Kacem used a procedure that takes into consideration the period of each operation and the workloads of machines. The second sequencing sub problem was solved by an evolutionary algorithm controlled by an assignment model using advanced genetic manipulations.

Zrib et al. [5] created an approach adapted especially for high flexibility problems. They proposed two methods for the assignment sub problem: The first one was based on the local search and the Branch & bound technique was used as a second method. The quality of assignment was evaluated by a boundary method. Then, a GA was used to solve the sequencing sub problem. However, the two sub problems are usually related for high quality of solutions.

Later, El-Kamel et al. [6] considered the FJSSP problem under machines availability constraints. These constraints are linked to a set of fixed machines breakdown periods. Two approaches were proposed: The first one begins with an assignment phase via local search, after that, a GA was used for operations sequencing. However, the second approach solved the two sub problems at the same time using an exact method, but only for two jobs.

Raich et al. [7] created a new method based on simulating annealing (SA) for FJSSP. They compared the results of SA with other methods such as SPT and LPT. The results showed that it is possible to obtain a global minimum solution but only for small instances.

Sridhar et al. [8] have considered many objectives which are the minimization of the overall completion time (Makespan), the total workload of machines and the workload of the most loaded machine. The results indicate the possibility to achieve optimal solutions. But the Makespan remain the most important criterion for FJJSP and find a solution that satisfies all objectives remain a hard task.

Ziaee [9] proposed a heuristic based on a constructive procedure to produce quickly good schedules. This constructive procedure is simple and doesn’t require a lot of execution time. However, this constructive procedure can be limited in the case of a big number of manufacturing operations.

The authors [2] proposed an algorithm using a new initialization method to improve the quality of the initial population and to accelerate the speed of the GA convergence. Authors [10] tried to improve the GA for flexible job shop scheduling with overlapping in operations. However, unknown instances were used in this study.

Several hybrid approaches were proposed for FJSSP but specifically for multi objective problems. Fatahi [11] proposed a hybrid multi objective algorithm for flexible job shop scheduling to minimize the completion time and the total tardiness. The author combined simulated annealing with Tabu search. Authors [12] combined simulated annealing with local search for multi objective flexible job shop scheduling. In another study [13], a hybrid approach was proposed, they used Ants colony with GA for preventive maintenance of machines. [14] proposed a hybrid algorithm using swarm optimization and GA.

Generally, the initial population of the GA is generated randomly which can create weak initial population and decrease the global performance of GA. To face this issue, a strong heuristic based on the concept of the active schedule (schedule without delay) is proposed, to generate the initial population. As a result, the high quality of the initial population solutions will contribute to accelerate the speed the GA convergence to an optimal solution.

According to the precedent works, the combination of the GA with the Tabu search stills limited in this field. The GA is a strong search method but, reinforces it with an efficient metaheuristic such as Tabu search, represents an excellent hybrid method to find solutions of high quality. In addition, contrary of the precedent works, an improved Tabu search based on new two concurrent algorithms is presented, which work as neighborhood function. The FJJSP has two main issues:

(a) (a)
Assignment sub problem: A machine chosen among a set of candidate machines for each manufacturing operation.
(b)
Sequencing sub problem: Prepare an execution order to perform the manufacturing operations on each machine. According to the literature, there are two main approaches of FJSSP:

–
The hierarchical approach: Both of sub problems are resolved separately.
–
The integrated approach: In this approach, the two sub problems are resolved at the same time. Due to the speed and efficiency of the integrated approach, an integrated hybrid GA is adopted in this paper.

Table 1
Chromosome coding

MACHINE 2 1 3 3 …

OPERATION $O_{1,3}$ $O_{1,1}$ $O_{2,3}$ $O_{3,3}$ …

Table 2
Example of flexible job shop problem

M1 $P(O_{j,i,1})$ M2 $P(O_{j,i,2})$ M3 $P(O_{j,i,3})$

J1 $O_{1,1}$ 6 6 8

$O_{1,2}$ 4 5 6

$O_{1,3}$ 5 4 5

J2 $O_{2,1}$ 8 7 9

$O_{2,2}$ 4 5 9

$O_{2,3}$ 3 2 3

$O_{2,4}$ 6 7 /

J3 $O_{3,1}$ 5 10 8

$O_{3,2}$ 2 3 4

$O_{3,3}$ 2 4 3

J4 $O_{4,1}$ 5 4 7

$O_{4,2}$ 10 7 11

J5 $O_{5,1}$ 7 10 11

$O_{5,2}$ 9 / 10

3. The genetic algorithm with the improved tabu search for flexible job shop scheduling

MACHINE	2	1	3	3	…
OPERATION	$O_{1,3}$	$O_{1,1}$	$O_{2,3}$	$O_{3,3}$	…

	M1 $P(O_{j,i,1})$	M2 $P(O_{j,i,2})$	M3 $P(O_{j,i,3})$
J1	$O_{1,1}$	6	6	8
	$O_{1,2}$	4	5	6
	$O_{1,3}$	5	4	5
J2	$O_{2,1}$	8	7	9
	$O_{2,2}$	4	5	9
	$O_{2,3}$	3	2	3
	$O_{2,4}$	6	7	/
J3	$O_{3,1}$	5	10	8
	$O_{3,2}$	2	3	4
	$O_{3,3}$	2	4	3
J4	$O_{4,1}$	5	4	7
	$O_{4,2}$	10	7	11
J5	$O_{5,1}$	7	10	11
	$O_{5,2}$	9	/	10

3.1 Problem formulation

In this section, a mathematical model of FJSSP with the constraints for feasible schedules is presented. In FJSSP, the aim is to organize the execution of N jobs $j\in\{J_{1},\ldots,J_{N}\}$ on M machines $k\in\{M_{1},\ldots,M_{m}\}$ to minimize the total time. Each job $J_{j}$ is composed of a set of $n_{j}$ ordered operations $\{O_{j,n_{1}},\ldots,O_{j,n_{j}}\}$ (precedence constraint). Each operation must be executed by one machine. The execution of the operation $O_{j,i,k}$ (operation number i of the job j) on the machine $M_{k}$ , makes this machine unavailable for the other operations for a certain period $P_{j,i,k}$ (resources constraint) (Table 2). If any operation can be executed by any machine, the flexibility is total. However, if the candidate machines of an operation represent a subset of the total number of machines, the flexibility is partial. In our case, both types of flexibility is considered. The precedence and resource constraints are necessary to get a feasible schedule. The schedule of a solution is evaluated by calculating the total completion time of jobs: Makespan (Eq. (1)).

$\displaystyle C_{\max}=\textit{Max}({tf}_{1},\ldots,{tf}_{N})$ (1)

${tf}_{j}$ : The finishing time of the job j (Eq. (2)).

$\displaystyle{tf}_{j}=\sum\nolimits_{i=1}^{O_{nj}}{P(O_{j,i,k})}∼{}∼{}k\in\{M_% {1},\ldots,M_{m}\}$ (2)

where for each operation $O_{j,i,k}$ :

•

$n_{j}$ : The total number of operations in the job $J_{j}$ .

•

$P_{j,i,k}$ : The execution time of $O_{j,i,k}$ performed by the machine $M_{k}$ .

•

$tO_{j,i,k}$ & $tfO_{j,i,k}$ are respectively the starting and the finishing time of $O_{j,i,k}$ in the machine ${M}_{k}$ .

•

$O^{-1}_{j,i,k}$ & $O^{+1}_{j,i,k}$ are respectively the precedent and the next operation of $O_{j,i,k}$ in the machine ${M}_{k}$ .

•

$O_{j,i-1,k}$ & $O_{j,i+1,k}$ are respectively the precedent and the next operation of $O_{j,i,k}$ in the same job j.

•

$O_{j,i,k}$ is critical operation if ${tf}_{j}=C_{\max}$ .

The resolution of FJSSP is very hard due to its high complexity. In the following part, an explanation of the designed optimization approach is presented.

3.2 The proposed model of optimization

In this part, answers to three main questions are given: why we have combined the GA with the Tabu search; how this combination was made; and what is our contribution.

Figure 1.

Genetic algorithm with improved Tabu search for flexible job shop scheduling.

The force of the GA is its capacity to explore the space of feasible solutions in a global way. However, sometimes, an optimal solution can hide behind any feasible solution (a neighbor solution). In this situation, the GA becomes inefficient to achieve these neighbor solutions, which can be better than the precedent solutions or even, the best one. To face this problem, the Tabu search is perfectly adapted to explore these neighbors. Figure 1 illustrates how the Tabu search reinforces the GA. The aim of the Tabu search is to explore deeply the neighbors of each generated chromosome (child) from the genetic operators. As a result, each selected solution will be replaced by its best neighbor.

Algorithm 1. hybrid algorithm
1.	Begin
2.	while (not max_iteration)
3.	$P$ $\leftarrow$ Initial_population(size)
4.	$P_{1},P_{2}$ $\leftarrow$ Select_parent ( $P$ ); $\Omega_{c}$ $\leftarrow$ Crossover ( $P_{c}$ )
	{ $P_{c}\textit{ selected population for crossover}$ . $\Omega_{c}$ : generated population from crossover}
5.	$\Omega_{m}$ $\leftarrow$ mutation ( $P_{m}$ )
	{ $P_{m}\textit{ selected population for mutatin}$ . $\Omega_{m}$ : generated population from mutation}
6.	$\Omega_{TS}$ $\leftarrow$ Tabu_search ( $\Omega_{c}\cup\Omega_{m}$ )
	{ $\Omega\_TS$ : generated population from Tabu search}
7.	$\Omega_{\textit{best}}$ $\leftarrow$ best_individuals ( $P\cup\Omega_{c}\cup\Omega_{m}\cup\Omega_{TS}$ )
8.	End ${}_{\text{while}}$
9.	End.

Parents are selected by taking randomly, a rate of individuals $P_{c}$ from the initial population. Similarly, the number of individuals which will be mutated ( ${\text{Individuals}}_{\text{mut}}=\text{size}_{\text{Initial}.\text{Population% }}*P_{m}$ ). Our approach is based on the corporation of the Tabu search with the GA. In the next part, an illustration of our contribution is presented, to improve the performance of Tabu search.

3.3 The Tabu search

The Tabu search (TS) is a metaheuristic based on the local search [15]. It explores the feasible solutions to get the optimal ones. Starting from an initial solution, the best neighbour is selected at each iteration. The neighborhood process is made by one transition on the current solution using special neighborhood functions. Thus, these solutions are called neighbours of the current solution [16]. Tabu search uses memorization structure in which, it saves the last visited solutions (Tabu list). A solution is forbidden for a certain number of iterations, which equals to the size of the Tabu list. Then, the best neighbour non-Tabu will be selected for the next iteration (Fig. 1). Tabu search is an efficient method for many difficult problems, but it remains difficult to be adapted to FJSSP. In fact, it requires the definition of several parameters such as the initial solution, neighborhood functions, evaluation of solutions, the size of Tabu search, etc.

3.3.1 The neighborhood functions

For the FJSSP, the traditional neighborhood functions are related to the notion of critical path.

Definition 1. A critical path is the path which its length equals to the schedule’s length and it is composed of operations linked either by, precedence links (operations of the same job) or disjunctive links (operations realized by the same machine) [16].

Definition 2. A public critical operation is an operation that belongs to all critical paths.

Definition 3. A public critical block is a maximal sequence of adjacent public critical operations processed by the same machine. Any transition is applied only on the public critical blocks.

The traditional neighborhood functions are made by making a simple transition on critical operations. These transitions can be a permutation between two critical operations or a mutation of a critical operation to another machine. However, these transitions can’t guarantee an improvement of the initial solution and all the possible transition have to be explored before finding a possible improvement.

In this context, an original neighborhood function designed to find derived solutions of better quality is presented in this paper. Instead of making random transitions which could be obsolete and take a lot of time, our approach is based on a deep analyze of the initial solution in order to take decisions which allow an improvement for each critical operation. The proposed neighborhood function is based on two concurrent algorithms using probabilities of improvement. The first one is for optimization by free windows and the second for optimization by occupied windows. Both of them allow assignment and sequencing improvement. Both of the two algorithms will be illustrated in the next part.

A probability is proposed for each algorithm, to measure the degree of improvement by each one for each critical operation $O_{j,i,k}$ , in order to find its best neighbor. The Algorithm having the highest probability will be applied on the actual critical operation.

Probability of optimization A for free windows (Algorithm 2)

$\displaystyle P_{\textit{free}-\textit{win}}(s,O_{j,i,k})=\frac{1}{1+\left(% \frac{{PO}_{j,i,k}}{{\textit{Avr}\_\textit{free}\_\textit{win}}_{j,i,k}}\right% )}\text{ and }{(PO}_{j,i,k}\leqslant{\textit{Avr}\_\textit{free}\_\textit{win}% }_{j,i,k})$ (3)

Probability of optimization B for occupied window (Algorithm 3)

$\displaystyle P_{\textit{occu}-\textit{win}}(s,O_{j,i,k})=\frac{1}{1+\left(% \frac{{PO}_{j,i,k}}{{\textit{Avr}\_\textit{occu}\_\textit{win}}_{j,i,k}}\right% )}\text{ and }(PO_{j,i,k}\leqslant{\textit{Avr}\_occ\_\textit{win}}_{j,i,k})$ (4)

where

•

S: The initial schedule or solution to be optimized.

•

${\textit{Avr}\_\textit{free}\_\textit{win}}_{j,i,k}=\sum\nolimits_{w=1}^{w_{TF% }}{(\beta_{w}-\alpha_{w})}/{WF}_{TF}$ the average free windows for O ${}_{j,i,k}$ . $W_{TF}$ The total number of free windows for $O_{j,i,k}$ .

•

${\textit{Avr}\_\textit{occu}\_\textit{win}}_{j,i,k}=\sum\nolimits_{w=1}^{w_{TO% }}{({\textit{finish}}_{w}-{\textit{start}}_{w})}/{WO}_{TO}$ the average occupied windows for O ${}_{j,i,k}$ . $W_{TO}$ the total number of occupied windows for O ${}_{j,i,k}$ .

•

$P_{\textit{free}-\textit{win}}(s,O_{j,i,k})$ : The probability of improvement using optimization A for free windows (Algorithm 2).

•

$P_{\textit{occu}-\textit{win}}(s,O_{j,i,k})$ : The probability of improvement using optimization B for occupied windows (Algorithm 3).

Definition of free window for $O_{j,i,k}$

$\displaystyle\textit{Max}({tfO}_{j,i-1},\alpha)+P_{j,i,k^{\prime}}\leqslant% \textit{Min}(\beta,{tO}_{j,i+1},{tfO}_{j,i,k})$ (5)

Definition of occupied window for $O_{j,i,k}$

$\displaystyle\textit{Max}({tfO^{-1}}_{j^{\prime},i^{\prime},k^{\prime}},{tfO}_% {j,i-1,})+P_{j,i,k^{\prime}}\leqslant\textit{Min}({tO^{+1}}_{j^{\prime},i^{% \prime},k^{\prime}},{tO}_{j,i+1})$ (6) $\displaystyle\textit{Max}({tfO^{-1}}_{j,i,k},{tfO}_{{j^{\prime},i}^{\prime}-1}% )+P_{{j^{\prime},i}^{\prime},k}\leqslant\textit{Min}({tO^{+1}}_{j,i,k},{tO}_{{% j^{\prime},i}^{\prime}+1})$

•

The first formula in Eq. (3.3.1) controls the constraints of $O_{j,i,k}$ which will replace $O_{j^{\prime},i^{\prime},k^{\prime}}$ in the $M_{k^{\prime}}$ . The second formula controls the constraints of $O_{j^{\prime},i^{\prime},k^{\prime}}$ , which will replace the $O_{j,i,k}$ in the $M_{k}$ .

3.3.2 Algorithm of optimization A for free windows

Algorithm 2. optimization A for free windows
1.	Input: initial schedule (S), $O_{j,i,k}$
2.	Output: optimized schedule (S ${}^{\prime}$ )
3.	Begin
4.	${\textit{Tab}}_{\lambda F}$ $\leftarrow$ Get_Free_Windows(S, $O_{j,i,k}$ ) {get the earliest free window on Mk}
5.	${tf}_{\textit{Best}}$ $\leftarrow$ ${tfO}_{j,i,k}$ {the initial best finishing time of $O_{j,i,k}$ }
6.	$M_{\textit{Best}}$ $\leftarrow$ $M_{k}$ {the initial best machine of $O_{j,i,k}$ }
7.	For $w=$ 1 to $W_{F}$ do {explore the ordered $W_{F}$ free windows}
8.	$\lambda^{k^{\prime}}_{W}={\textit{Tab}}_{\lambda F}[w]$ {get the current free window in $M_{k^{\prime}}$ }
9.	$(\alpha,\beta)$ $\leftarrow$ Bornes( $\lambda^{k^{\prime}}_{W}$ ) {the bornes of the free windows}
10.	If Max( ${tfO}_{j,i-1}\alpha)+P_{j,i,k^{\prime}}\leqslant$ Min( $\beta,{tO}_{j,i+1,k},{tfO}_{j,i,k}$ ) then {move $O_{j,i}$ to $M_{k^{\prime}}$ }
11.	If Max( ${tfO}_{j,i-1,}\alpha$ ) $+P_{j,i,k^{\prime}}<{tf}_{\textit{best}}$ then
12.	$M_{\textit{Best}}\leftarrow M_{k^{\prime}};{tf}_{\textit{Best}}\leftarrow$ Max( ${tfO}_{j,i-1},\alpha)+P_{j,i,k^{\prime}}$
13.	${\mathrm{end}}_{\mathrm{if}}$
14.	${\mathrm{end}}_{\mathrm{if}}$
15.	${\mathrm{end}}_{\mathrm{for}}$
16.	if ( ${tf}_{\textit{Best}}\neq{tf}_{j,i,k}$ or $P_{j,i,\textit{best}}<P_{j,i,k}$ ) then
17.	update_schedule(S, $t_{\textit{Best}}$ ) {start the updating from the earliest point}
18.	${\mathrm{end}}_{\mathrm{if}}$
19.	End.

This algorithm can improve assignment and sequencing of a critical operation by detecting the best adequate free window, without breaking the resource and the precedence constraints and without delaying others operations. The free windows are detected from all the candidate machines of the current critical operation. After, a test is released to check if the current improvement (assignment or sequencing) is the best one among the precedent improvements. At the end of the algorithm, the updating procedure is executed, to update the starting and the finishing time of specific operations.

3.3.3 Algorithm of optimization B for occupied windows

Algorithm 3. optimization B for occupied windows
1.	Input: initial schedule (S), $O_{j,i,k}$
2.	Output: optimized schedule (S ${}^{\prime}$ )
3.	Begin
4.	${\textit{Tab}}_{\lambda O}$ $\leftarrow$ Get_Occupied_Windows(S, $O_{j,i,k}$ ) {get the earliest occupied window on Mk}
5.	${tf}_{\textit{Best}}$ $\leftarrow$ $tfO_{j,i,k}$ {the initial best finishing time of $O_{j,i,k}$ }
6.	$M_{\textit{Best}}$ $\leftarrow$ $M_{k}$ {the initial best machine of $O_{j,i,k}$ }
7.	For $w=$ 1 to $W_{O}$ do {explore the ordered $W_{O}$ occupied windows}
8.	$O_{j^{\prime},i^{\prime},k^{\prime}}\leftarrow\textit{get}\_\textit{oper}({% \textit{Tab}}_{\lambda O}[w])$ {get operation of the current occupied window}
9.	If Max $({tfO^{-1}}_{j^{\prime},i^{\prime},k^{\prime}},{tfO}_{j,i-1})+P_{j,i,k^{\prime% }}\leqslant\textit{Min}({tO^{+1}}_{j^{\prime},i^{\prime},k^{\prime}},{tO}_{j,i% +1},{tfO}_{j,i,k})$ then {move $O_{j,i}$ to $M_{k^{\prime}}$ }
10.	If Max $({tfO^{-1}}_{j^{\prime},i^{\prime},k^{\prime}},{tfO}_{{j^{\prime},i}^{\prime}-% 1})+P_{j^{\prime},i^{\prime},k}\leqslant\textit{Min}({tO^{+1}}_{j,i,k},{tO}_{{% j^{\prime},i}^{\prime}+1})$ then
11.	If Max $({tfO^{-1}}_{j^{\prime},i^{\prime},k^{\prime}},{tfO}_{j,i-1})+P_{j,i,k^{\prime% }}<{tf}_{\textit{Best}}$ then{move $O_{j^{\prime},i^{\prime}}$ to $M_{k}$ }
12.	$M_{\textit{Best}}\leftarrow M_{k^{\prime}};{tf}_{\textit{Best}}\leftarrow$ Max( ${tO}_{j^{\prime},i^{\prime},k^{\prime}},{tf}_{j-1,i}$ )
	${tf}_{\textit{Best}}$ $\leftarrow$ Max( ${tfO^{-1}}_{j^{\prime},i^{\prime},k^{\prime}},{tfO}_{{j^{\prime},i}^{\prime}-1}$ )
13.	${\mathrm{end}}_{\mathrm{if}}$
14.	${\mathrm{end}}_{\mathrm{if}}$
15.	${\mathrm{end}}_{\mathrm{if}}$
16.	${\mathrm{end}}_{\mathrm{for}}$
17.	if ( ${tf}_{\textit{Best}}\neq{tf}_{j,i,k}\text{ or }P_{j,i,\textit{best}}<P_{j,i,k}$ ) then {updating from the earliest point}
18.	update_schedule(S, $\textit{Min}(t_{\textit{Best}},t_{j^{\prime},i^{\prime},k})$ )
19.	${\mathrm{end}}_{\mathrm{if}}$
20.	End.

This algorithm starts by exploring all the adequate occupied windows for the current critical operation ${O}_{j,i,k}$ . The operation that occupies the current occupied time window is called ${O}_{j^{\prime},i^{\prime},k^{\prime}}$ .

The idea is to exchange the position of $O_{j,i,k}$ and ${O}_{{j^{\prime},i}^{\prime},k^{\prime}}$ to improve the assignment or sequencing time of $O_{j,i,k}$ , without breaking the precedence and the resource constraints of $O_{j,i,k}$ and ${O}_{{j^{\prime},i}^{\prime},k^{\prime}}$ .

Before starting the algorithm, all the detected occupied windows are adapted to the current critical operation ${O}_{j,i,k}$ (respect the precedence and the resource constraints). In each iteration, the algorithm chooses the occupied window that makes the best improvement among the precedent ones.

The two precedent algorithms work as neighborhood function for Tabu search. In order to increase the efficiency of Tabu search, three criteria are chosen (Eqs (1), (7) and (8)) to select the individuals which will be subjected to the Tabu search according to the fitness Eq. (9). These individuals are more adapted to the neighborhood function than the others.

Both Algorithms 2 and 3 use the updating procedure after the optimization of the current critical operation. The pseudo algorithm of updating is given in part:

Algorithm 4 Update_schedule
1.	Input: initial schedule (S), ${t}_{\min}$
2.	Output: new schedule (S ${}^{\prime}$ )
3.	Begin
4.	For $o=$ 1 to $o_{T}$ do {explores all operations}
5.	$O_{j^{\prime},i^{\prime},k^{\prime}}$ $\leftarrow$ Tab_O[o] {get the current operation}
6.	If ${tO}_{j^{\prime},i^{\prime},k^{\prime}}\geqslant t_{\min}$ then
7.	${tO}_{j^{\prime},i^{\prime},k^{\prime}}$ $\leftarrow$ Max( ${tfO}_{j^{\prime},i^{\prime}-1,k^{\prime}},{tfO^{-1}}_{j^{\prime},i^{\prime},k% ^{\prime}}$ )
8.	${tfO}_{j^{\prime},i^{\prime},k^{\prime}}$ $\leftarrow$ ${tO}_{j^{\prime},i^{\prime},k^{\prime}}+P_{j^{\prime},i^{\prime},k^{\prime}}$
9.	${\mathrm{end}}_{\mathrm{if}}$
10.	${\mathrm{end}}_{\mathrm{for}}$
11.	End.

The schedule updating changes only the starting and the finishing times of the operations which are affected by either Algorithm 2 or Algorithm 3.

In the next point, the three criteria used for selecting individuals for Tabu search application are presented, and a pseudo algorithm of the Tabu search is given.

The makespan: this criterion represents the completion time of all jobs. It reflects the quality of the schedule (Eq. (1)).

$\displaystyle C_{\max}=\textit{Max}({tf}_{1},\ldots,{tf}_{N})$

The average quantity of free windows: the average unexploited time reinforces the efficiency of Algorithm 2. Where ${\mathrm{WF}}_{\mathrm{k}}$ is the total free unexploited time on the machine ${\mathrm{M}}_{\mathrm{k}}$ .

$\displaystyle{\textit{Avr}}_{WF}=\sum\nolimits_{k=1}^{M}\frac{{WF}_{k}}{M}$ (7)

The workload distribution between machines: a schedule more equilibrated makes easy the application of optimization by occupied windows (Algorithm 3).

$\displaystyle\delta_{W}=\sum\nolimits_{k=1}^{M}\frac{|W_{k*}-W_{k}|}{W_{T}}$ (8)

where

•

$W_{k*}=\textit{MAX}[W_{k}],k\in[1,M]$ the most important workload among all machines.

•

$W_{k}$ : The workload of the machine $M_{k}$ .

•

$W_{T}$ : The total workload of all machines.

According to these three criteria, the individuals will be selected for Tabu search using the following equation:

$\displaystyle\textit{Fitness}\_TS(S)=\frac{{\textit{AVR}}_{W_{F}}}{C_{\max}*% \delta_{W}+1)}$ (9)

The purpose of this equation is to choose solutions, which have the maximum average of free time, and the minimum value of makespan and the most balanced workload distribution between machines.

3.3.4 The Tabu search algorithm

The following pseudo-algorithm summarizes how the ITS (Improved Tabu Search) was implemented:

Algorithm 5 Improved_Tabu_Search
1.	Input: initial solution (S)
2.	Output: the best neighbor (S ${}_{n}$ )
3.	Begin
4.	${\mathrm{Tabu}}_{\mathrm{list}}\leftarrow\emptyset;{\mathrm{solution}}_{% \mathrm{current}}\leftarrow{\mathrm{solution}}_{\mathrm{initial}};$
5.	${\mathrm{solution}}_{\textit{best}}\leftarrow{\mathrm{solution}}_{\mathrm{% current}};{\mathrm{nb}}_{\mathrm{iterations}}\leftarrow;$
6.	$\mathrm{TabCriticalOperation}$ {Initialize the table of the critical operations}
7.	$\mathrm{while∼{}}({\mathrm{nb}}_{\mathrm{iterations}}\leqslant{\mathrm{nbMax}}% _{\mathrm{iterations}})\mathrm{∼{}do}$
8.	$\mathrm{for∼{}}o=1\mathrm{∼{}to∼{}}{\mathrm{nb}}_{\mathrm{critical\_operations% }}\mathrm{∼{}do}$ {explore the critical operations}
9.	$\mathrm{O}_{j,i,k}\leftarrow\mathrm{TabCriticalOperation}[\mathrm{o}]$ {get the current critical operation from the table $\mathrm{TabCriticalOperation}$ }
	{use Algorithms of optimization A, B for the best neighbor}
10.	${\mathrm{neighbour}}_{\textit{best}j,i,k}\leftarrow\mathrm{getBestNeighbour(% Optimiz}(\mathrm{A}),\mathrm{Optimiz}(\mathrm{B})\mathrm{O}_{j,i,k},\mathrm{S)}$
	${\mathrm{Tabu}}_{\mathrm{list}}\leftarrow\mathrm{addTabu(}{\mathrm{neighbour}}% _{\textit{best}j,i,k}\mathrm{)}$
11.	$\mathrm{if}(\mathrm{cost}({\mathrm{neighbour}}_{\textit{best}})<\mathrm{cost}(% {\mathrm{solution}}_{\mathrm{current}}))\mathrm{then}$
12.	${\mathrm{solution}}_{\textit{best}}\leftarrow{\mathrm{neighbour}}_{\textit{% best}};{\mathrm{nb}}_{\mathrm{iteration++}}$
13.	${\mathrm{end}}_{\mathrm{if}}$
14.	${\mathrm{end}}_{\mathrm{for}}$
15.	${\mathrm{end}}_{\mathrm{while}}$
16.	End.

3.4 Genetic algorithm

The Tabu search illustrated in the precedent section will be used to improve the solutions of the GA which are created by the genetic operators. This Improved Tabu Search has a double goal; first, it works to discover new solutions in the neighborhood space. Second, it contributes to accelerating the speed of the GA by reducing the number the generations required to achieve a solution of high quality.

GA is one of the best metaheuristics to deal with flexible job shop scheduling problem [17]. This algorithm uses crossover as a genetic operator for recombination of parental genes to form new descendants. The second genetic operator ‘Mutation’ changes randomly the values of certain genes, in order to avoid premature convergence of GA. But, due to the combinatory nature of the present problem, it stills difficult to ensure optimal or quasi-optimal solutions via this algorithm. Thus, a combination of the Tabu search approach with the GA is suggested to get stronger solutions (Fig. 1). GA is an algorithm that tries to improve the best solution found from generation to generation. However, the first generation is important, because the future populations depend on it.

A good initial population must be composed of individuals (solutions) of different nature and good quality. The following subsection illustrates how the initial population is created to ensure both of individuals’ diversity and quality.

3.4.1 The initial population

The generation of the initial population is prepared as follows:

•
Fifty percent of individuals are created randomly in order to ensure the diversity of this population, which is useful to avoid a premature convergence.
•
The rest of individuals are made by a strong heuristics such as SPT (shortest processing time), MWR (most work remaining), etc.

In the following part, an efficient heuristic is proposed, able to find the best free window of time for each operation. This heuristic provides active schedules in which, it is impossible to advance any operation without delaying other one [18]. This schedule reflects a solution of high quality.

•
$W_{k}=\sum\nolimits_{j=1}^{n}\sum\nolimits_{i=1}^{o_{nj}}{P(O_{j,i,k}){*X}_{j,% i,k}}$ : The workload of the machine $M_{k}$
•
$X_{j,i,k}=1ifO_{j,i}$ is assigned on $M_{k}$ , else $X_{j,i,k}=0$
•
$W_{T}=\sum\nolimits_{k=1}^{M}W_{k}$ : The total workload of machines
•
${WR}_{k}=\frac{W_{k}}{W_{T}}:$ The workload rate of the machine $M_{k}$
•
$S_{k,X}$ : The starting time of the free window X located on $M_{k}$ . Equation (10) measures the cost of placing operation the Oj i on the machine $M_{k}$ and precisely in the free window X.

$\displaystyle{\textit{Cost}(O_{j,i,k})}_{X}=\textit{MAX}(tf[O_{j,i-1}],S_{k,X}% )+P(O_{j,i,k})+{WR}_{k}$ (10) $\displaystyle{\textit{best}\_\textit{window}}_{k}=\textit{MIN}({\textit{Cost}(% O_{j,i,k})}_{X},\ldots,Cost(O_{j,i,k})_{{nb}_{x}})$ (11)

Equation (11) provides the best free window for $O_{j,i}$ among a set of ${nb}_{x}$ free windows located on the machine ${M}_{k}$ . Equation (11) selects the best free window among the windows of all candidate machines for the operation ${O}_{j,i}$ .
3.4.2 Chromosomes coding

To exploit the GA, each solution (schedule) must be coded using a specific representation to obtain a chromosome, this representation will be used later by the genetic operators such as crossover and mutation to discover new solutions.

This representation is linear and reflects the chronology of scheduled operations.

Respecting the precedence constraints on each job is necessary. However, avoid a correction process on the generated solutions, which increases dramatically the completion time, will be more interesting. This is why the crossover operator developed by [19] is adopted, which respects the problem’s constraints. In the second genetic operator, mutation is applied by choosing randomly a chromosome and a machine, which will be subjected to this perturbation (modifies some chromosome genes). Next, two operations are chosen randomly, on which, the mutation will be applied.

3.4.3 Crossover

This operator exchanges information from the chosen parents in order to obtain better descendants. Crossover is applied to each pair of chromosomes (parents) to get two new individuals (children). An improved Precedence Preserving Order-based crossover (POX) is adopted in this study [19].

Figure 2.

GA vs HGA (TS $+$ GA).

3.4.4 Mutation

In this study, we apply assignment mutation and sequencing mutation:

In the assignment mutation, two different indexes L1 and L2 are chosen from the interval $\{1,\rho\}$ such as $\rho$ is the total number of operations. Then, choose randomly for each gene between L1/L2 another machine from the set of the alternative machines.

In the sequencing mutation, two different operations are chosen randomly (from different jobs) then, these two operations will be permuted.

3.5 Parameters of the genetic algorithm

The performance of the GA depends strongly on a set of parameters. After many tests, these parameters are configured as follows:

The fitness function reflects the quality of each solution. It is calculated using the following equation:

$\displaystyle\textit{fitness}(\textit{chromosome})=1/C\_\max$ (12)

The probability of crossover $P_{c}$ must be important (more than 0.6) to explore deeply the space of solutions and find new descendent. However, the probability of mutation $P_{m}$ is between 0.01 and 0.2, because the purpose of this operator is to apply a low degree of perturbation on chromosomes in order to avoid a premature convergence of GA to a local optimal solution. A greater value of $P_{m}$ may destroy the chromosome’s information.

The population’s size is a parameter which depends on the size of instances. In our case, the initial population contains 100 chromosomes, but this number increases when the size of the instance became more important.

In our case, the best individuals according to their fitness (Elitism) are selected for the next generation. The GA is iterated until the maximum number of iterations is reached.

4. Computational experiments

In order to evaluate the quality of our approach, one of the well-known benchmarks of the flexible job shop scheduling problem is used. Many tests are performed in term of quality and performance. The proposed approach was implemented using java as a programming language and eclipse as an IDE.

Figure 2 illustrates the role of the Improved Tabu Search on the performance of the GA. This figure shows that the best solution found by the hybrid GA is better than the simple GA. The most critical step of the GA is the generation of the initial population. In fact, a good initial population must provide both of diversity and quality of individuals.

According to Fig. 2, the improvement of the makespan by the proposed HGA is clearly better than the one obtained by the traditional GA.

In Table 3, a comparison is presented between the proposed heuristic (last column) and many other methods used to generate the initial population, the values represent the makespan of the best solution found among 100 generated individuals.

J $\times$ O $\times$ M represents the number of jobs, operations and machines for each instance.

Table 3
Heuristics for the initial population

Instances	J $\times$ O $\times$ M	Random	MWR	SPT	Proposed heuristic*
MK01	10 $\times$ 55 $\times$ 6	70	58	46	43
MK02	10 $\times$ 58 $\times$ 6	49	44	41	30
MK03	15 $\times$ 150 $\times$ 8	326	270	246	205
MK04	15 $\times$ 90 $\times$ 8	123	116	89	74
MK05	15 $\times$ 106 $\times$ 4	246	208	219	191
MK06	10 $\times$ 150 $\times$ 15	148	118	106	72
MK07	20 $\times$ 100 $\times$ 5	224	203	188	161
MK08	20 $\times$ 225 $\times$ 10	688	577	650	540
MK09	20 $\times$ 240 $\times$ 10	552	476	468	341
MK10	20 $\times$ 240 $\times$ 15	489	375	368	248

Table 4

Results using Brandimart’s instances

Instance	N $\times$ M	Ho&Ta	Po&JA, Gi	HGA*
mk01	10 $\times$ 55 $\times$ 6	41	40	40
mk02	10 $\times$ 58 $\times$ 6	29	26	26
mk03	15 $\times$ 150 $\times$ 8	N/A	204	204
mk04	15 $\times$ 90 $\times$ 8	67	66	62
mk05	15 $\times$ 106 $\times$ 4	178	174	173
mk06	10 $\times$ 150 $\times$ 15	68	77	61
mk07	20 $\times$ 100 $\times$ 5	153	143	142
mk08	20 $\times$ 225 $\times$ 10	523	523	523
mk09	20 $\times$ 240 $\times$ 10	327	328	311
mk10	20 $\times$ 240 $\times$ 15	235	247	216

According to the results mentioned in Table 3, the proposed heuristic based on the concept of active schedule provides the best solutions.

The second best heuristic is SPT (shortest processing time). However, the SPT heuristic is improved by taking into consideration the workload of machines.

The MWR (most work remaining) is less efficient than the two last heuristics. It gives priority to the operation belonging to the job that has the most remaining time.

The solutions generated randomly are not as good as the precedent heuristics solutions but, this method is crucial to maintain the diversity of the initial population. Its advantage is to avoid a premature convergence of the GA.

Table 4 represents a comparison between the proposed approach (HGA: Hybrid GA) and other approaches. The values reflect the best makespan found by each approach using the same instances of Brandimarte. Improved values found by our approach are written in bold style.

Table 5

Obtained results of Cmax (seconds)

Products order	MILP	PF	IGIT	GA	ORCA-FMS	IGA*
1 $\times$ A-I-P	219*	–	229	224	224	219
2 $\times$ A-I-P	309*	–	346	335	314	313
3 $\times$ A-I-P	409**	–	522	425	415	416
B-E-L-T-A-I-P	570**	448	431	410	–	396

*Optimal solution. **The best found solution.

Figure 3.

Gantt diagram for the product order 1XAIP by IGA.

Table 4 shows that 60% of the results obtained by our approach (less than 5 minutes) are better than the other approaches results, such as Po&JA, Gi and Ho&TA [19, 20]. The results of the remained instances (40%) are as good as the other approaches.

The obtained results can be explained by the proposed approach for the generation the initial population and the improved proposed neighborhood function used in the Tabu search to get solution of better quality.

We have tested our approach IGA (Improved GA) on another special benchmark which reflects a real manufacturing cell, developed by the University of Valenciennes in France [15]. This benchmark takes into consideration the transportation time between machines. We have compared our approach with five approaches which are MLIP: the Mixed-Integer Linear Program [15], PF: Potential Field [21], IGT: the Iterative Greedy Insertion Technique [22], GA: and ORCA-FMS [23]. The obtained results are presented in Table 5.

There exist many schedules representation forms. However, the most used one is the Gantt diagram. Figure 3 shows the best solution found by IGA method for the product order 1XAIP.

5. Conclusion

In this paper, the Genetic algorithm (GA) is adopted for flexible job shop scheduling problem. However, the GA is considered as a global search method and it can’t explore deeply the neighborhood solutions, which can be better than the initial one. To solve this problem, the Tabu search is incorporated, which can cover perfectly the weakness of the GA and improve the global performance of the proposed approach.

The proposed Neighborhood function is original and more efficient than the traditional ones, which are based on random transitions. The proposed neighborhood function is based on tow concurrent algorithms which exploit deeply the information about the schedule to be optimized. A probability is proposed to measure the degree of optimization of either algorithm of optimization A for free windows or optimization B for occupied windows 2 or 3. According to the highest probability, one of the two algorithms will be applied to optimize each critical operation.

The proposed heuristic based on the concept of the active schedule, creates solutions of good quality. This heuristic allows enhancing the quality of the GA’s initial population. This heuristic accelerates the speed of GA’s convergence.

Actually, the two algorithms, of optimization A, B for free windows and occupied windows, are being adapted for an uncertain environment such as energy volatility.

Footnotes

Authors’ Bios

Mohammed El Amine Meziane after B.S, he received Engineer and Magister degrees in computer science from the University of Oran 1 Ahmed Ben Bella (Algeria), 2008 and 2012. A. Meziane is phd student, researcher at the level of the laboratory LIO of the University of Oran 1 Ahmed Ben Bella, Algeria. His main interest is operations research and optimization of the manufacturing systems using artificial intelligence.

Noria Taghezout is an assistant professor at university of Oran 1 Ahmed BenBella, Algeria. She holds her doctorate thesis in MITT at PAUL SABATIER UNIVERSITY in France in 2011. She also received another doctorate thesis in Distributed Artificial Intelligence from university of Oran 1 Ahmed BenBella in 2008. She holds a Master degree in Simulation and Computer aided-design. She conducts her research at the LIO laboratory as a chief of the research group in Modeling of enterprise process by using agents and WEB technologies. Since she studied in UPS Toulouse, she became a member of the EWG-DSS (Euro Working Group on Decision Support Systems). She is currently lecturing Collaborative decision making, Enterprise management and Interface human machine design. Her seminars, publications and regular involvement in Conferences, journals and industry projects highlight her main research interests in Artificial Intelligence.

References

Talbi

E.-G.

Yalaoui

and Amodeo

, Metaheuristics for Production Systems, 1st ed., S.I. Publishing, Ed. London, United Kingdom: Springer, 2016.

Liangxiao

and Zhongjun

, An improved genetic algorithm for flexible job shop scheduling problem, in 2nd International Conference on Information Science and Control Engineering, Shanghai, China (2015), 127–131.

Mastrolilli

and Gambardella

L.M.

, Effective neighbourhood functions for the flexible job shop problem, Journal of Scheduling 3(1) (2000), 3–20.

Kacem

Hammadi

and Borne

, Approach by localization and mult-iobjective evolutionary optimization for flexible job-shop scheduling problems, IEEE Transactions on Systems, Man, and Cybernetics, Part C 32(1) (2002), 1–13.

Zribi

Kacem

Kamel

A.E.

and Borne

, Assignment and scheduling in flexible job-shops by hierarchical optimization, IEEE Transactions on Systems, Man, and Cybernetics 37(4) (2007), 652–661.

Zribi

El-Kamel

and Borne

, Minimizing the makespan for the MPM job-shop with availability constraints, International Journal of Production Economics 112(1) (2008), 151–160.

Raich

Nikumbh

P.J.

and Patil

, Flexible job–shop scheduling problem using simulated annealing, International Journal of Research & Reviewes in Computer Science 3(2) (2012), 1491–1501.

Sridhar

Victor Raj

and Chandra Sekar

, Minimizing manufacturing cost in flexible job-shop scheduling problems, International Journal of Artificial Intelligence and Mechatronics 1(5) (2013), 2320–5121.

Ziaee

, A heuristic algorithm for solving flexible job shop scheduling problem, The International Journal of Advanced Manufacturing Technology 71(1) (2014), 519–528.

10.

Yiyong

Wei

and Shigeru

, Improvements to genetic algorithm for flexible job shop scheduling with overlapping in operations, in 16th International Conference on Computer and Information Science (ICIS), Wuhan, China (2017), 791-796.

11.

Fattahi

, A hybrid multi objective algorithm for flexible job shop scheduling, International Journal of Mathematical and Statistical Sciences 1(1) (2009), 21–26.

12.

Xia

and Wu

, An effective hybrid optimization approach for multi-objective, Computers and Industrial Engineering 48(2) (2005), 409–425.

13.

El Khoukhi

Boukachour

and El Hilali Alaouic

, The dual-ants colony: A novel hybrid approach for the flexible job shop scheduling problem with preventive maintenance, Computers & Industrial Engineering 106 (2017), 236–255.

14.

Tang

Zhang

and Lin

, A hybrid algorithm for flexible job-shop scheduling problem, Procedia Engineering 15(1) (2011), 3678–3683.

15.

Trentesaux

Pach

and Bekrar

, Benchmarking flexible job-shop scheduling and control systems, Control Engineering Practice 21(9) (2013), 1204–1225.

16.

Eikelder

Aarts

Verhoeven

and Aarts

, Sequential and Parallel Local Search Algorithms for Job Shop Scheduling, B.M. Springer, Ed. Boston, USA: Springer Book Archive, 1999.

17.

Ennigrou

, Approche multiagents basee sur la recherche tabou pour le job shop flexible, in 14eme Congres Francophone AFRIF-AFIA de Reconnaissance des Formes et Intelligence Artificielle RFIA, Toulouse, France (2004), 28–30.

18.

Gen

Gao

and Lin

, Multistage-based genetic algorithm for flexible job-shop scheduling problem, in Studies in Computational Intelligence, B.H. Springer, Ed. Berlin, Germany: Springer 187 (2009), 183–196.

19.

Lee

K.-M.

Yamakawa

and Lee

K.-M.

, A genetic algorithm for general machine scheduling problems, in Knowledge-Based Intelligent Electronic Systems, Proceedings KES 98, Adelaide, SA, Australia, Australia (1998), 60–66.

20.

Ponnambalam

S.G.

Jawahar

and Girish

B.S.

, An ant colony optimization algorithm for flexible job shop scheduling problem, in New Advanced Technologies, A. Lazinica, Ed. InTech, Mar. March (2010), ch. 4, 74–95,https://www.intechopen.com/books/new-advanced-technologies/an-ant-colony-optimization-algorithm-for-flexible-job-shop-scheduling-problem.

21.

Raja

and Pugazhenthi

, Path planning for mobile robots in dynamic environments using particle swarm optimization, in Advances in Recent Technologies in Communication and Computing, 2009. ARTCom ’09. International Conference on, Kottayam, Kerala, India (2009), 27–28.

22.

Bekkar

et al., An iterative greedy insertion technique for flexible job shop scheduling problem, in 8th IFAC Conference on Manufacturing Modelling, Management and Control, Troyes, France (2016), 1956–1961.

23.

Pach

Berger

Bonte

and Trentesaux

, ORCA-FMS: A dynamic architecture for the optimized and reactive control of flexible manufacturing scheduling, Computers in Industry 65(4) (2014), 706–720.

A hybrid genetic algorithm with a neighborhood function for flexible job shop scheduling

Abstract

Keywords

1. Introduction

2. Literature review

3.1 Problem formulation

3.3.1 The neighborhood functions

3.3.3 Algorithm of optimization B for occupied windows

3.4 Genetic algorithm

3.4.1 The initial population

3.4.3 Crossover

3.5 Parameters of the genetic algorithm

Table 3 Heuristics for the initial population

Footnotes

Authors’ Bios

References

Table 3
Heuristics for the initial population