To effectively manage and control the execution of production process, a correct scheduling activity must be performed. In any manufacturing environment, resources utilization, production rate, customer service level can be switched across the definition of suitable jobs’ sequence and tasks’ allocation. Being a NP complete and highly constrained problem, the resolution of the Job Shop Scheduling Problem (JSSP) is recognized as a key point to the factory optimization process. In recent years, a great number of multi-objective meta-heuristics has been proposed to evaluate the quality of a scheduling solution and obtain sets of compromising solutions. Powerful methods for running these kinds of optimization problems have been inspired by research on evolutionary theory and swarm intelligence approach. The cooperative behaviour that emerges from the organization of multi agent systems is the inspiring source of the two implemented approaches. The pursuit of optimal solution, on both benchmark and real-world job shop problem, has been successful tested for Genetic Algorithms (GA) and Ant Colony Optimization (ACO) techniques. This work starts with analysis on optimization methods for JSSP. Across the implementation of a new Genetic Algorithm and an improved model based on ant’s way, the performance of the two meta-heuristic approaches has been evaluated and compared. Similarity/dissimilarity of evolutionary and swarm intelligent approaches has pointed out. The logic, the parameters, the representation schemes and operators used in these two approaches have been widely discussed during this paper. A guide to the implementation of GAs and ACO approach to JSSP was performed.

Evolutionary Computing and Swarm Intelligence algorithms for JSSP: Genetic Algorithm vs. Ant Colony Optimization techniques

FRUGGIERO, FABIO;
2007

Abstract

To effectively manage and control the execution of production process, a correct scheduling activity must be performed. In any manufacturing environment, resources utilization, production rate, customer service level can be switched across the definition of suitable jobs’ sequence and tasks’ allocation. Being a NP complete and highly constrained problem, the resolution of the Job Shop Scheduling Problem (JSSP) is recognized as a key point to the factory optimization process. In recent years, a great number of multi-objective meta-heuristics has been proposed to evaluate the quality of a scheduling solution and obtain sets of compromising solutions. Powerful methods for running these kinds of optimization problems have been inspired by research on evolutionary theory and swarm intelligence approach. The cooperative behaviour that emerges from the organization of multi agent systems is the inspiring source of the two implemented approaches. The pursuit of optimal solution, on both benchmark and real-world job shop problem, has been successful tested for Genetic Algorithms (GA) and Ant Colony Optimization (ACO) techniques. This work starts with analysis on optimization methods for JSSP. Across the implementation of a new Genetic Algorithm and an improved model based on ant’s way, the performance of the two meta-heuristic approaches has been evaluated and compared. Similarity/dissimilarity of evolutionary and swarm intelligent approaches has pointed out. The logic, the parameters, the representation schemes and operators used in these two approaches have been widely discussed during this paper. A guide to the implementation of GAs and ACO approach to JSSP was performed.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11563/13995
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact