Production Scheduling Approaches

4.6. Tabu Search (TS)

Tabu search is an iterative search approach characterised by the use of a flexible memory. The process with which tabu search overcomes local optimality is based on the evaluation function that chooses the highest evaluation solution at each iteration. The evaluation function selects the move, in the neighbourhood of the current solution, that produces the most improvement or the least deterioration in the objective function. Since, movement are accepted based on a probability function, a tabu list is employed to store characteristics of accepted moves so to classify them as taboo (i.e., to be avoided) in the later iteration. This is used to dodge cycling movements. A strategy called forbidding is employed to control and update the tabu list. This method was formalized by Glover. An algorithm based on tabu search requires some elements: (i) the move, (ii) the neighbourhood, (iii) an initial solution, (iv) a search strategy, (v) a memory, (vi) an objective function and (vii) a stop criterion. The of TS is based on the definition of a first feasible solution S, which is stored as the current seed and the best solution, at each iteration, after the set of the neighbours is selected between the possible solutions deriving from the application of a movement. The value of the objective function is evaluated for all the possible movements, and the best one is chosen. The new solution is accepted even if its value is worse than the previous one, and the movement is recorded in a list, named taboo list.

For the problem of the scheduling in the job shops, generally a row of assignments of n jobs to m machines is randomly generated and the cost associated is calculated to define the fitness of the solution. Some rules of movements can be defined as the crossover of some jobs to different machines and so on, defining new solutions and generating new values of the objective functions. The best solution between the new solutions is chosen and the movement is recorded in a specific file named taboo list. The stopping criterion can be defined in many ways, but simplest way is to define a maximum number of iterations.

In figure 8 are reported the pseudo-code and the flowchart for the application of TS to JSSP.

Figure 8.
The Tabu Search approach; 8a. the TS pseudo code; 8b. the flow chart of a general TS procedure.