Using genetic algorithms for practical multi-objective production schedule optimisation.

Production scheduling is a notoriously difficult problem. Manufacturing environments contain
complex, time-critical processes, which create highly constrained scheduling problems. Genetic
algorithms (GAs) are optimisation tools based on the principles of evolution. They can tackle
problems that are mathematically complex, or even impossible to solve by traditional methods.
They allow problem-specific implementation, so that the user can develop a technique that suits the
situation, whilst still providing satisfactory schedule optimisation performance.
This work tests GA optimisation on a real-life scheduling application, a chilled ready-meal factory.
A schedule optimisation system is required to adapt to changing problem circumstances and to
include uncertain or incomplete information. A GA was designed to allow successive
improvements to its effectiveness at scheduling. Three objectives were chosen for minimisation.
The GA proved capable of finding a solution that attempted to minimise the sum of the three costs.
The GA performance was improved after experiments showed the effects of rules and preference
modelling upon the optimisation process, allowing 'uncertain' data to be included.
Multi-objective GAs (MOGAs) minimise each cost as a separate objective, rather than as part of a
single-objective sum. Combining Pareto-optimality with varying emphasis on the conflicting
objectives, a set of possible solutions can be found from one run of MOGA. Each MOGA solution
represents a different situation within the factory, thus being well suited to a constantly changing
manufacturing problem.
Three MOGA implementations are applied to the problem; a standard weighted sum, two versions
of a Pareto-optimal method and a parallel populations method. Techniques are developed to allow
suitable comparison of MOGAs. Performance comparisons indicate which method is most
effective for meeting the factory's requirements. Graphical and statistical methods indicate that the
Pareto-based MOGA is most effective for this problem. The MOGA is demonstrated as being a
highly applicable technique for production schedule optimisation.