A Hybrid Technique for Handling The Flexible Job-Shop Scheduling Problem

MARIANO FRUTOS; ANA CAROLINA OLIVERA; FERNANDO TOHMÉ

Buenos Aires, Argentina

Conferencia; 24th IFIP TC 7 Conference on System Modelling and Optimization; 2009

Ministerio de Ciencia, Tecnología e Innovación Productiva de la Nación

To schedule production in a Job-Shop environment means to allocate adequately the available resources. To do that it is necessary to rely on efficient optimization procedures. In fact, the Job-Shop Scheduling Problem is a NP-Hard problem [Ullman, 1975], so ad-hoc algorithmshave to be applied to its solution [Frutos et al., 2008]. This is similar to other combinatorial programming problems [Larrazábal, 2003], [Olivera et al., 2006], [Cortés et al., 2004].Most instances of the Job-Shop Scheduling Problem involve the simultaneous optimization of two usually conflicting goals. This one, like most multi-objective problems, tends to have many solutions. The Pareto frontier reached by an optimization procedure has to contain a uniformly distributed number of solutions close to the ones in the true Pareto frontier. This feature facilitates the task of the expert who interprets the solutions [Kacem et al., 2002]. In this paper we present a Genetic Algorithm linked to a Simulated Annealing procedure able to schedule the production in a Job-Shop manufacturing system [Cortés et al., 2004], [Tsai and Lin, 2003], [Wu et al., 2004].