Industrial scheduling with evolutionary algorithms using a hybrid representation

by Martin Andersson

Institution: University of Skövde
Year: 2011
Keywords: scheduling; optimisation; simulation; Engineering and Technology; Mechanical Engineering; Production Engineering, Human Work Science and Ergonomics; Teknik och teknologier; Maskinteknik; Produktionsteknik, arbetsvetenskap och ergonomi; Technology; teknik; Industriell informatik - magisterprogram; Industrial Informatics - Master's Programme; Automatiseringsteknik; Automation Engineering
Record ID: 1360710
Full text PDF: http://urn.kb.se/resolve?urn=urn:nbn:se:his:diva-5348


Scheduling problems have been studied extensively in the literature but because they are so hard to solve, especially real-world problems, it is still interesting to find ways of solving them more efficiently. This thesis aims to efficiently solve a real-world scheduling problem by using a hybrid representation together with an optimisation algorithm. The aim of the hybrid representation is to allow the optimisation to focus on the parts of the scheduling problem where it can make the most improvement. The new approach used in this thesis to accomplish this goal, is the combination of simulation-based optimisation using genetic algorithms and dispatching rules. By using this approach, it is possible to investigate the effect of putting specified job sequences in certain machines and using dispatching rules in the other. The hypothesis is that the optimisation can use dispatching rules on non-bottleneck machines that have little impact on the overall performance of the line and some specified job sequences on bottleneck machines that are hard to be scheduled efficiently with dispatching rules. This would allow the optimisation to focus on the bottleneck machines and that would produce a more efficient search. The results from the case study shows it is a viable approach exceeding or equalling existing techniques. The hypothesis that the optimisation can focus its efforts is supported by a bottleneck analysis which corresponds with the experimental results from optimisations.