the tabu search is described. An illustrative example is given in section 4. The last section will be devoted to the presentation of some results and some conclusions relating to this research work. CHAPTER 2 LITERATURE SURVEY Ant Colony Optimization (ACO) is a paradigm for designing metaheuristic algorithms for combinatorial optimization problems. The first algorithm which can be classified within this framework was presented in 1991 and, since then, many diverse variants of the basic principle have been reported in the literature. The essential trait of ACO algorithms is the combination of a priori information about the structure of a promising solution with a posteriori information about the structure of previously obtained good solutions. Metaheuristic algorithms are algorithms which, in order to escape from local optima, drive some basic heuristic: either a constructive heuristic starting from a null solution and adding elements to build a good complete one, or a
most significant theoretical results so far published about convergence properties of ACO variants. 5.2.1 Ant System The importance of the original Ant System (AS) resides mainly in being the prototype of a number of ant algorithms which collectively implement the ACO paradigm. AS already follows the outline presented in the previous subsection, specifying its elements as follows. The move probability distribution defines probabilities pιψk to be equal to 0 for all moves which are infeasible (i.e., they are in the tabu list of ant k, that is a list containing all moves which are infeasible for ants k starting from state ι), otherwise they are computed by means of formula (5.1), where α and β are userdefined parameters (0 ≤ α,β ≤ 1): In formula 5.1, tabuk is the tabu list of ant k, while parameters α and β specify the impact of trail and attractiveness, respectively. After each iteration t of the algorithm, i.e., when all ants have completed a solution, trails are updated by means of formula (5.2): where Δτιψ represents the sum of the contributions of all ants that used move (ιψ) to construct their solution, ρ, 0 ≤ ρ ≤ 1, is a user-defined parameter called evaporation coefficient, and Δτιψ represents the sum of the contributions of all ants that used move (ιψ) to construct their solution. The ants’ contributions are proportional to the quality of the solutions achieved, i.e., the better solution is, the higher will be the trail contributions added to the moves it used. For example, in the case of the TSP, moves correspond to arcs of the graph, thus state ι could correspond to a
Mk µM entails the occupation of the latter one during a processing time, noted pi; j;k. The problem is thus to both determine an assignment scheme and a sequence of the operations on all machines that minimize some criteria. • A set of J independent jobs. • Each job is characterized by the earliest starting time r j and the latest finishing time dj. • Denote by pti; j and ri; j respectively the processing time and the ready date of the operation Oi; j. The pi; j;k represent the processing time pti; j with the machine Mk. • A started operation can not be interrupted. • Each machine can not perform more than one operation at the same time. • The objective is to find an operation ordering set satisfying a cost function under problem constraints. The considered objective is to minimize the makespan Cmax. ACO and Tabu search for FJSP Scheduling In this stage, the application of the combined ant systems with tabu search techniques in the resolution of FJSP problem are described. Construction Graph and Constraints Generally, the FJSP can be represented by a bipartite graph with two categories of nodes: Oi; j and Mk. A task is mapped to a Oi; j node; a machine is mapped to a Mk. There is an edge between the Oi; j node and the Mk node if and only if the corresponding task can be assigned to the corresponding machine while respecting the availability of the machine and the precedence