Genetisk opgaveplanlægning

Planlægning af jobbutik er et udfordrende problem for matematisk programmering. Men når det er relevant, kan den operationelle effekt være stor. I dagens blogindlæg vil jeg bidrage til dette emne med et teknisk eksempel, der dækker genetisk jobplanlægning.

Et simpelt opgaveplanlægningsproblem med en maskine

Eksemplet, som jeg foreslår, omfatter 3 maskiner (M1, M2 og M3) og 5 opgaver (T1, T2, T3, T4 og T5). Jobbene skal behandles i en jobshop. Hver opgave kan behandles på enhver maskine, men der er visse begrænsninger, der begrænser den mulige rækkefølge af opgaver på hver maskine.

For eksempel kan begrænsningerne være som følger:

T1 skal behandles før T2 på M1
T4 skal behandles før T5 på M2
T2 og T3 kan ikke behandles på samme maskine

Jeg vil nu finde en opgaveplan på hver maskine, der minimerer den samlede behandlingstid for alle opgaver.

Jobshop opgaveplanlægning med genetiske algoritmer

For at løse dette problem ved hjælp af en genetisk algoritme repræsenterer jeg et skema som en sekvens af heltal. Hvert heltal repræsenterer den opgave, der skal behandles næste gang. For eksempel betyder et skema [1, 2, 3, 4, 5], at vi behandler opgave 1 på maskine 1, efterfulgt af opgave 2 på maskine 2, efterfulgt af opgave 3 på maskine 3, og så videre.

Vi kan bruge en simpel fitnessfunktion, der beregner den samlede behandlingstid for en given tidsplan under hensyntagen til begrænsningerne. For eksempel kan vi beregne behandlingstiden som følger:

For hver maskine skal du beregne behandlingstiden som summen af behandlingstiderne for alle opgaver, der er tildelt den pågældende maskine.
Hvis der er overtrædelser af begrænsninger (f.eks. hvis T2 og T3 er tildelt den samme maskine), skal du tilføje en straf til behandlingstiden.
Et skemas egnethed er det negative ved behandlingstiden.

Vi kan derefter bruge en genetisk algoritme til at generere og udvikle tidsplaner, indtil vi finder en god.

Eksempel på genetisk planlægningsalgoritme

Her er et eksempel på, hvordan algoritmen kan fungere:

Generer en indledende population af tidsplaner, som hver består af en tilfældig række af opgaver, der er tildelt maskiner.
Beregn konditionen for hver tidsplan ved hjælp af fitnessfunktionen.
Vælg en undergruppe af populationen til at opdrætte den næste generation af skemaer ved hjælp af en udvælgelsesmetode, såsom turneringsudvælgelse.
Opdrætte nye skemaer ved hjælp af crossover- og mutationsoperatorer.
Udskift den gamle befolkning med den nye befolkning, og gentag trin 2-4 i et vist antal generationer.
Den bedste tidsplan, der er fundet, er den med den højeste fitnessværdi.

Planlægningsproblemer i jobbutik er kendt for at være NP-hårde, hvilket betyder, at det er beregningsmæssigt vanskeligt at finde den optimale løsning for store problemtilfælde. Som følge heraf kan det tage lang tid at konvergere genetiske algoritmer eller slet ikke være i stand til at finde den optimale løsning.

Afsluttende bemærkninger og relateret jobshop planlægningsindhold

Jobbutiksplanlægning er et udfordrende emne. Matematisk programmering, og i dette tilfælde genetiske algoritmer, kan være effektive i nogle tilfælde. I andre tilfælde kan problemer være for komplekse til at løse analytisk med rimelig indsats. Skulle dette være tilfældet, kan simulering af diskrete hændelser hjælpe med at overvinde nogle af udfordringerne ved matematisk programmeringsapplikation. Følgende SCDA-blogindlæg beskriver udfordringerne ved planlægning af jobbutik:

Link : Udfordringer med jobshop planlægning

Du kan læse mere om simulering, især simulering af disrete hændelser, i følgende SCDA-publikationer. Simuleringsmodellering kan implementere planlægningsløsninger, der kan overvinde de udfordringer ved matematisk programmering, der gør den uegnet til anvendelse i problemer i den virkelige verden.