Schemaläggning av genetisk algoritm
Den genetiska algoritmen är en operativ forskningsmetod som kan användas för att lösa schemaläggningsproblem i produktionsplaneringen .
Vikten av produktionsschemaläggning
För att vara konkurrenskraftiga måste företag minimera ineffektivitet och maximera produktiviteten. Inom tillverkning är produktiviteten naturligt kopplad till hur väl företaget kan optimera de tillgängliga resurserna, minska avfallet och öka effektiviteten. Att hitta det bästa sättet att maximera effektiviteten i en tillverkningsprocess kan vara extremt komplicerat. Även på enkla projekt finns det flera ingångar, flera steg, många begränsningar och begränsade resurser. I allmänhet består ett resursbegränsat schemaläggningsproblem av:
- En uppsättning jobb som måste utföras
- En ändlig uppsättning resurser som kan användas för att slutföra varje jobb
- En uppsättning begränsningar som måste uppfyllas
- Temporala begränsningar – tidsfönstret för att slutföra uppgiften
- Procedurmässiga begränsningar – ordningen varje uppgift måste slutföras
- Resursbegränsningar – är den tillgängliga resursen
- En uppsättning mål för att utvärdera schemaläggningsprestanda
En typisk fabriksinställning är ett bra exempel på detta, där det är nödvändigt att schemalägga vilka jobb som ska utföras på vilka maskiner, av vilka anställda, i vilken ordning och vid vilken tidpunkt.
Användning av algoritmer i schemaläggning
I mycket komplexa problem som schemaläggning finns det inget känt sätt att komma till ett slutgiltigt svar, så vi tar till att söka efter det för att försöka hitta ett "bra" svar. Schemaläggningsproblem använder oftast heuristiska algoritmer för att söka efter den optimala lösningen. Heuristiska sökmetoder lider när indata blir mer komplexa och varierande. Denna typ av problem är känt inom datavetenskap som ett NP-Hard problem. Det betyder att det inte finns några kända algoritmer för att hitta en optimal lösning i polynomtid.
Genetiska algoritmer är väl lämpade för att lösa produktionsschemaläggningsproblem , eftersom till skillnad från heuristiska metoder fungerar genetiska algoritmer på en population av lösningar snarare än en enda lösning. I produktionsschemaläggning består denna population av lösningar av många svar som kan ha olika ibland motstridiga mål. Till exempel kan vi i en lösning optimera en produktionsprocess för att slutföras på minimal tid. I en annan lösning kan vi optimera för en minimal mängd defekter. Genom att öka hastigheten med vilken vi producerar kan vi stöta på en ökning av defekter i vår slutprodukt.
När vi ökar antalet mål vi försöker uppnå ökar vi också antalet begränsningar för problemet och ökar på liknande sätt komplexiteten. Genetiska algoritmer är idealiska för den här typen av problem där sökutrymmet är stort och antalet möjliga lösningar är litet.
Tillämpning av en genetisk algoritm
För att tillämpa en genetisk algoritm på ett schemaläggningsproblem måste vi först representera det som ett genom. Ett sätt att representera ett schemaläggningsgenom är att definiera en sekvens av uppgifter och starttiderna för dessa uppgifter i förhållande till varandra. Varje uppgift och dess motsvarande starttid representerar en gen.
En specifik sekvens av uppgifter och starttider (gener) representerar ett genom i vår befolkning. För att säkerställa att vårt genom är en genomförbar lösning måste vi se till att det följer våra prioritetsbegränsningar. Vi genererar en initial population med slumpmässiga starttider inom prioritetsbegränsningarna. Med genetiska algoritmer tar vi sedan denna initiala population och korsar den, och kombinerar genom tillsammans med en liten mängd slumpmässighet (mutation). Avkomman till denna kombination väljs utifrån en fitnessfunktion som inkluderar en eller flera av våra begränsningar, som att minimera tid och minimera defekter. Vi låter denna process fortsätta antingen under en förutbestämd tid eller tills vi hittar en lösning som uppfyller våra minimikriterier. Sammantaget kommer varje efterföljande generation att ha en högre genomsnittlig kondition, det vill säga tar kortare tid med högre kvalitet än de föregående generationerna. I schemaläggningsproblem, som med andra genetiska algoritmlösningar, måste vi se till att vi inte väljer avkommor som är omöjliga, till exempel avkommor som bryter mot vår prioritetsbegränsning. Vi kan naturligtvis behöva lägga till ytterligare fitnessvärden som att minimera kostnaderna; varje begränsning som läggs till ökar dock sökutrymmet avsevärt och minskar antalet lösningar som är bra matchningar.
Se även
Bibliografi
- Wall, M., A Genetic Algorithm for Resource-Constrained Scheduling (PDF)
- Lim, C.; Sim, E., Produktionsplanering i tillverknings-/återtillverkningsmiljö med hjälp av genetisk algoritm ( PDF)