MULTI-OBJECTIVE OPTIMIZATION IN JOB-SHOP-LIKE PRODUCTION PROCESSES

MARIANO FRUTOS; FERNANDO TOHMÉ

Rosario

Workshop; II Latinamerican Workshop on Optimization and Control; 2010

Universidad Nacional de Rosario

Programming production processes in Job-Shop-like environments demands a fine tuned allocation of resources. The fulfillment of this goal requires, in turn, of efficient optimization algorithms. Most Job-Shop Scheduling Problems (JSSP) involve the simultaneous optimization of two or more, generally conflicting, objectives. Thanks to their many advantages, evolutionary algorithms have become quite popular in the field of multi-objective optimization. Among evolutionary algorithms, the class of Genetic Algorithms (GA) plays a salient role in the solution of those problems. Nevertheless, the high rate of convergence of Gas increases the cost of finding solutions in multi-objective problems, since it leads to the loss of diversity in the solutions space, which reflects in poorly distributed Pareto frontiers. This drawback can be more than compensated by complementing GAs with efficient local search methods. This is, in fact, the goal of our presentation: to introduce a multi-objective algorithm requiring a small number of evaluations of the target function. This hybrid algorithm is called Multi-objective Memetic Algorithm (MMA). Since any JSSP can be divided in two sub-problems, the MMA operates on two chromosomes. The first one represents the allocation of each task to some machine. The second chromosome codifies the sequence of tasks in each machine. The genes in the chromosomes represent, respectively, a pair task-machine in the former and a sequence of tasks in a given machine, in the latter. The initial population consists of individuals whose chromosomes are constituted by randomly selected genes. Then, the chromosomes are decodified and evaluated according to two functions: Makespan y el Total Operating Cost. This allows determining the criticality of each machine and, thus, controlling the process. The individuals are then subject to genetic operations and afterwards to an improvement operator. The latter is based on the meta-heuristic procedure called Simulated Annealing (SA). This procedure implements a local search for better solutions. SA includes an acceptation strategy which allows exploring temporarily unfavorable areas of the search space. In time, the solution scheme varies with random changes on the genes. The difference of this method with similar ones is that it incorporates a density-guided search procedure. After the application of the genetic and improvement operators and when the population has been decodified, the procedure implements Non-Dominated Sorting Genetic Algorithm II (NSGAII). NSGAII uses an elitist strategy as well as an explicit diversity mechanism.