Konepajaongelman ratkaiseminen evoluutioalgoritmilla

Abstract

Konepajaongelma on yleinen optimointi ongelma, jolla on useita eri ratkaisu menetelmiä. Ongelmassa on tavoitteena löytää optimaalinen suoritusjärjestys kappaleille ja niiden työvaiheille. Ongelman ratkaisemisessa ja menetelmän valitsemisessa pitää ottaa huomioon eri tapausten erilaiset rajoitteet. Erilasisissa ongelmissa voi olla paljon erilaisia rajoitteita ja menetelmä tulee valita rajoitteet huomioiden. Optimaalinen suoritusjärjestys mahdollistaa konepajan toiminnan mahdollisimman tehokkaasti.

Tässä työssä tarkasteltiin evoluutioalgoritmin soveltuvuutta konepajaongelman ratkaisemisessa. Evoluutioalgoritmi inspiroituu biologisesta evoluutiosta. Algoritmi aloittaa satunnaisilla järjestyksillä ja muokkaa niitä sukupolvien myötä mahdollisimman tehokkaiksi. Algoritmi säilyttää parhaat järjestykset ja vertaa niitä keskenään. Uusia ehdokkaita parhaalle järjestykselle muodostetaan risteyttämällä aikaisempia järjestyksiä.

Keskeiset havainnot työssä olivat, että evoluutio algoritmi toimii hyvin konepajaongelman optimointiin ja on hyvin sovellettavissa erilaisiin ongelmiin. Evoluutio algoritmin etu on sen soveltuvuus monimutkaisissa ja laajoissa ongelmissa, joiden ratkaisemisessa muut menetelmät voisivat olla hitaita tai liian epäkäytännöllisiä.

The machine shop problem is a general optimization problem that has several different solution methods. The goal of the problem is to find the optimal execution order for parts and their work steps. When solving the problem and choosing a method, the different constraints of different cases must be taken into account. There can be many different constraints in different problems and the method must be chosen taking the constraints into account. The optimal execution order enables the machine shop to operate as efficiently as possible.

This work examined the applicability of the evolutionary algorithm in solving the machine shop problem. The evolutionary algorithm is inspired by biological evolution. The algorithm starts with random orders and modifies them as efficiently as possible over generations. The algorithm stores the best orders and compares them with each other. New candidates for the best order are formed by crossing previous orders.

The key findings in the work were that the evolutionary algorithm works well for optimizing the machine shop problem and is well applicable to various problems. The advantage of the evolutionary algorithm is its applicability to complex and large-scale problems that other methods might be slow or too impractical to solve.