New Evolutionary Algorithm for Highly Capacitated Lotsizing and Scheduling

• Type: Chapter or Part of a Book
• Date: 2011

Authors

Maristela Santos (Author) FEUP; B. Almada-Lobo (Author) FEUP; Sadao Massago (Author) FEUP

Book

Title: Metaheuristics: Intelligent Decision Making, Operations Research/Computer Science Interfaces Series, Vol. 50

Pages: 309-324

Indexing

Scopus

Scientific classification

FOS: Engineering and technology > Other engineering and technologies

CORDIS: Technological sciences

Other information

Resumo (PT): Finding a first feasible solution is a very difficult task for a variety of problems. In some cases, it is the only goal. In this paper, we present a genetic algorithm (GA) to solve the multi-item capacitated lot sizing and scheduling problem with sequence dependent setup times and costs. It is a hard and important optimization problem that often arises in industry. When considering highly constrained problems, commercial solvers fail even to find a feasible solution. We develop new features that enable the GA to deal with feasible and infeasible solutions, based on the concept of nested domains. The expansion of the domain is done by bands, which represent additional overtime. Within each band, the solutions are only differentiated by the value of the objective function (fitness). Throughout generations, the amplitudes of the bands are dynamically updated to improve the convergence towards the feasible domain. Different approaches to this end are discussed. Computational results show the efficiency of the GA approach in finding feasible solutions for highly capacitated instances.

Language: English

Type (Professor's evaluation): Scientific