Abstract: The objective of this study is the resolution of a combinative optimization problem. This problem is scheduling in the production systems of the type Hybrid Flow Shop (HFS). This resolution is made with using Sequential and Parallel Tabu Search (TS). In this study we propose an implementation of a parallel algorithm of Tabu Search based on Multiples research with Synchronous Interaction (TS_MSI). The basic idea of this method is that several processes (threads) carry out each one a TS and they communicate between them at defined points of synchronization. Numerical experiments are carried out to make a comparison in term of quality of solution, between the sequential TS and parallel TS. The results obtained show well that this strategy of parallelization (TS_MSI) improves the results compared to the sequential TS.
INTRODUCTION
The scheduling problems in the production system are generally problems which make party of the class of the problems known as Np-Complete. The strategies of resolution (meta-heuristics) are applied more and more to this type of problem. These meta-heuristics and among them Tabu Search (TS), represents an effective strategy for the search of the approximate solutions of the combinative optimization problems. But the disadvantage of this method more evoked is the computing time and the quantity of memory used and moreover they are closely related on the size of the problem and obtaining a certain quality of solution. With the increase of the parallel machines, powerful workstations and great communication networks, the parallelization of meta-heuristic makes it possible to accelerate the search of the approximate solutions (reduction of the execution time) and also to improve quality of the solution obtained. So these algorithms become interesting to parallel.
For that, in the case of the parallelization of the TS, we adapted and implemented Parallel Tabu Search based on Multiples research with Synchronous Interaction (TS_MSI). In this strategy, each process executes independent sequential TS and communicates with the other processes at defined points of synchronization. Thus they exchange information. Exchanged information is in the majority of the cases the good solutions found since the last step of synchronization. The different TS choose a new solution to start again their research after synchronization. Four possible implementation plans are instancied according to the unicity of the initial solution and the unicity of the strategy of research. Synchronization depends on a frequency fixed a priori and the model of programming which supports this execution is of type Master/Slaves (Crainic et al., 1995; Porto and Ribeiro, 1996).
MATERIALS AND METHODS
Hybrid flow shop problem: In the literature, the notion of hybrid flow shop has emerged in the 70s. An organization in Hybrid Flow Shop (HFS) is consisted of a set of stages, where each stage is composed of one or more parallel machines. The various jobs visit the stages in the same order. On each stage, a job is treated by only one machine. Between each stage, the jobs can wait or not in limited or unlimited stocks (Billaut et al., 2000; Vignier et al., 1999) (Fig. 1).
The treated problem is the scheduling of N jobs in entry of the system and the assignment of these jobs on the machines. We research a scheduling and an assignment which optimize a criterion of performance. The criterion to be optimized is Cmax (the time of total completion of the jobs (works)).
| Fig. 1: | Hybrid flow-shop (HFS) |
| Fig. 2: | Objective function |
Sequential Tabu search: The method of Tabu Search (TS) is high level heuristics or metaheuristics which was introduced by Glover (1998). He details the various algorithms containing tabu lists. Since, many contribution were made to this method, in particular where Widmer (1991) applied it to the optimization of the flexible manufacturing systems.
The TS is based on local research but with a probability to continue research beyond the local optima. This is done by accepting a solution of quality worse than the current solution. What makes it possible to be extracted from the local minima. At each stage, we choose the best solution among the whole of the solutions which belong in the neighbouring of the current solution, even if this solution is less interesting than the preceding one (Alg. 1). The fact of using local research with the possibility of selecting a neighbour (X') which decreases the value of the objective function, can involve cycles (reconsideration of the preceding solutions) in the exploration of research (Fig. 2). To avoid this problem, we avoid in the TS revisiting the solutions already tested. We say: these solutions are Tabu for a certain time. The prohibited movements are put in a list called Tabu List and are prohibited with the current iteration of the algorithm. These movements remain Tabu for one duration equal to the size of the Tabu List (Talbi, 1999).
| Algorithm 1: Algorithm of the sequential RT |
The sequential TS is based essentially on the fixing of its parameters which are:
Size of the Tabu List (the period during which a movement remains tabu): It is a parameter which is fixed at the starting of the execution and which remains unchanged.
Size of the candidates movements list: The strategy used is the Strategy of Better Improvement (SBI), for that a candidate list was used containing the best evaluated movements. Because the system of neighbouring used for the HFS is very large, it is very difficult to completely evaluate all the neighbours of a solution at each iteration. For that subset or sample of these neighbours generated by randomise was considered. The first solutions of this subset are put in the list. This list contains the following informations: the solution (scheduling + assignment), the cost of the solution and attributes of movements used to succeed to this solution.
Criterion of aspiration: It cancels the tabu state of a movement if this movement is well adapted. The level of aspiration is reached when the cost of the solution generated by this movement is lower than the value of aspiration of this movement.
Criterion of intensification-diversification: To reinforce (to intensify) research in the good areas, the choice of the best improvement was selected where at each iteration a list of good movements is created. To diversify research, after a number of iterations without improvements, a jump is carried out (Kangourou jump) (Fleury, 1993).
The parallel Tabu search: Crainic (1997 and 2002) presented a taxonomy which summarizes the strategies of parallelization of the TS. This taxonomy has the advantage to being more general. It makes it possible to be applied to any problem of combinative optimization. According to this taxonomy, a strategy of parallelization is defined by three large axes: the control of execution which can be centralized (1-control) or be distributed (P-controls), the type of control which can be synchronous or asynchronous and strategy of research which is a possible configuration of the operating parameters.
We distinguish also the existence of two approaches to parallelize research according to the number of trajectories implied in parallel research. The parallelization of the TS can be with single trajectory (Single Walk) (Blesa et al., 2001; Porto and Ribeiro, 1996) or with multiple trajectories (Walks Multiple) (Van and Martin, 2001; Taillard, 1998; Crainic et al., 1995; Porto and Ribeiro, 1996; Glover et al., 1998; Cavalcante et al., 2001; Talbi, 1999).
In the implementation of the parallel TS for the scheduling problem of the HFS (Aribi and Belkadi, 2003), we adapted and implemented the parallel algorithm of Tabu search based on Multiples research with Synchronous Interactions (TS_MSI) of the taxonomy of Crainic (1997). In this strategy, each process executes independent sequential TS and communicates with the other processes at defined points of synchronization. The various TS choose a new solution to start again their research after synchronization. We have instancied four possible implementation plans according to if the initial solution is single or multiple and if the strategy of research is single or multiple. Synchronization depends on a frequency to fix a priori and the model of programming which supports this execution is centralized on Master/Slaves.
Description of the TS_MSI algorithm: The algorithm of the TS_MSI follows a model of programming in Master/Slaves. The Master initialises the different TS which are launched by the slaves. At each point of synchronization, the slaves turn over their final state to the thread Master which chooses a solution among the turned over solutions and starts again research of the slaves until reaching a maximum number of synchronizations (Alg. 2). At each launch, the slaves preserve the same strategies of research and empty all the Tabu lists (Alg. 3.).
| Algorithm 2: Algorithm of master-TS_MSI |
| Algorithm 3: Algorithm of the slave-TS_MSI |
Parameters of the TS_MSI: The parameters which influence the algorithm of the TS_MSI are:
Strategy of research used: The TS launched by Threads can share or not the initial solution and can also share or not the strategy of research; from where four classes of execution which can be instancied: SPSS (Single Point Single Strategy), MPSS (Multiple Point Single Strategy), SPMS (Single Point Multiple Strategy) and MPMS (Multiple Point Multiple Strategy).
Frequency of synchronization: It determines the number of points of synchronization to carry out all along research. It also determines the number of iteration to carry out in a TS between two points of synchronization.
Number of Multiple Tabu search (a number of slaves or Threads): This number determines the number of research which are launched in parallel.
Choice strategy of initial solution after synchronization: At each point of synchronization, the Master chooses a solution among the solutions turned over by the slaves. This choice is not inevitably the best solution because this last can create a deteriorating determinism. Three choice strategies of solution are studied: Best, Mean and Prob. In Best, we choose the best solution among the local current solutions. In Mean, we choose the current solution which has the cost value near the average of all the cost values of the current solutions. In Prob, the choice of the solution is a probabilist and each solution has a certain probability to being chosen and it depends on its cost value compared to the sum of cost values of the other solutions.
RESULTS AND DISCUSSION
The Tabu Search (TS) was tested on Hybrid Flow Shop (HFS) with two stages and with three machines in the first stage and two machines in the second stage (Fig. 3). The type of HFS is a HFS with a stock at the entry of the first stage and between the stages. The number of jobs is N = 5, 10, 15 and 20. The treated problem is the scheduling of N jobs in entry of the system and the assignment of these jobs on the machines. We research a scheduling and an assignment which optimize a criterion of performance. The criterion to be minimized is the Cmax (the time of total completion of the jobs (work)). By using the notation of Vignier et al. (1999), we can represent it by FH2 (P3, P2)||Cmax.
| Fig. 3: | FH2 (P3, P2)||Cmax |
The sequential TS applied to HFS (Sahraoui et al., 2002; Belkadi et al., 2003) gave good results with the size of the Tabu List fixed at 7, the size of the list of the candidates at 500 and the number of iteration at 1000. The initial solution is generated by randomize.
The obtained results are shown in Table 1 (values of cost Average Cmax and execution time) (average of 10 tests of the Cmax value). These values go to be used as reference for a comparison between the sequential TS and the parallel TS.
Comparison between the sequential TS (TS_Sequ) and the parallel TS (TS_MSI): The algorithm of TS_MSI was implemented on an architecture Bi-processor (Intel Literatur Center, 2000) and it was tested on Hybrid Flow Shop of the same type as that studied for sequential TS (Aribi and Belkadi, 2003). The strategy of selected parallelization is with centralized synchronization (Master/Slaves). In the case of the parallel TS (TS_MSI), a study of choice of parameters was made and that made it possible to fix their values. The values of these parameters are as follows:
| • | The frequency of synchronization is fixed at 20%, |
| • | The number of slaves at 5, |
| • | The strategy of choice is Mean |
| • | And the schema of Tabu parallelism is MPMS. |
These values will be used as reference for the comparison carried out in term of quality of solution between the sequential TS and the parallel TS.
Figure 4 represents this comparison of quality of solution and it comprises two sets of data: the series concerning TSSequ and that concerning the TS_MSI on the problem FH2 (P3, P2)||Cmax for the number of jobs (N = 5, 10, 15 and 20).
| Table 1: | Average Cmax and average CPUs for sequential Tabu Search |
| Fig. 4: | Comparison between the TS_Sequ and the TS_MSI for N = 5, 10, 15 and 20 |
According to the graphs of the Fig. 4 we notice well the improvement which the strategy of parallelization of Tabu search based on Multiples research with Synchronous Interaction (TS_MSI) compared to the sequential TS. This improvement remained constant with the increase in the complexity of the studied HFS (increase in the number of jobs N = 5, 10, 15 and 20).
We notice that several Tabu search carried out in parallel and synchronize with themselves to guide their research (TS_MSI) is a powerful strategy of parallelism, in particular when various Tabu search follow different strategies of research (MS: Multi Strategy) and start their research in dispersed points (MP: Multi point) of the space of research.
CONCLUSIONS
The objective of this study was the resolution of a combinative problem of optimization by using a resolution method which is Taboo Search (TS). This method is iterative metaheuristic described as local research in the broad sense. The goal is to parallel this method to improve the results (Cmax) by using the TS_MSI. According to the results obtained, we notice that the fact of using and applying parallelism to the Tabu resolution method (TS_MSI) enabled us to improve the results of the method by giving better results that the sequential TS and that for an equivalent computing time. The required result is a good scheduling at the entry of the Hybrid Flow Shop (HFS) which optimizes (minimizes) the Cmax (makespan). The results obtained by TS_MSI are an improvement of the results obtained previously by the TS sequential.
The results obtained can be obtained in smaller CPUs times if the implementation is done on a mutiliprocessor architecture instead of a biprocessor. The next work concerns an implementation of this method of parallelization on an architecture of the type Grid computing and with an asynchronous mode of communication instead of a synchronous mode as it is done in this study. Among work under development, we are making a comparative study with other methods of optimization (GA, SA, PSO…) and to compare the results.
The originality of the study is the adaptation and the implementation of the TS_MSI to solve the scheduling problem in the production systems of the type hybrid Flow shop. The results obtained by TS_MSI compared to TS sequential are promising.