| dc.description.abstract | Over de siste tiårene har produksjonsbedrifter flyttet store deler av sin produksjon til lavkostnadsland. I tillegg har store produsenter benyttet seg av strømlinjeformede produksjonsinstallasjoner og høye produksjonsvolum for å senke enhetskostnadene sine. Mindre produsenter i høykostnadsland sliter med å få ned sine enhetskostnader og må konkurrere med lavere budsjett enn sine større konkurrenter. Et lovende område for kostnadseffektivisering for slike bedrifter er datadrevet produksjonsplanlegging. Dette innebærer metoder for å effektivt lage gode produksjonsplaner ved hjelp av rimelige datamaskiner.
Dette studiet undersøker en variant av flowshop planleggingsproblemet, inspirert av produksjonsmiljøet til en liten norsk produsent, Haugstad Møbel (Haugstad). Maskinene i fabrikken er gruppert etter funksjonalitet i ulike trinn og alle produkter følger samme flyt gjennom trinnene. Minst ett trinn har mer enn en maskin tilgjengelig, noe som gjør produksjonsmiljøet til en hybrid flowshop. Videre antas det at alle maskinene er identiske. Ikke alle produkter behøver å prosesseres i alle trinn. Dette gjør at produksjonsmiljøet betegnes som fleksibelt. Maskinene må klargjøres før de kan prosessere et nytt produkt, og tiden det tar avhenger også av hvilket produkt som sist ble prosessert. Dette kalles sekvensavhengig klargjøringstid. Klargjøringen er ikke mulig å starte før produktet som skal prosesseres ankommer maskinen. Denne kombinasjonen av utvidelser kalles et hybrid fleksibelt flowshop problem med sekvensavhengige klargjøringstider. Målet er å finne produksjonsplaner som minimerer den totale tiden det tar å produsere en kjent mengde produkter.
Av 172 vitenskapelige artikler publisert om det hybride flowshop planleggingsproblemet det siste tiåret, er det bare tre som bruker genetiske algoritmer til å løse den ovennevnte varianten og med minimering av total produksjonstid som mål. I denne oppgaven introduserer vi en ny genetisk algoritme som på under to minutter finner gode produksjonsplaner for opptil 120 produkter, åtte trinn, og fire maskiner i hvert trinn. Dette oppnås ved å benytte operatorer som aldri har blitt brukt for å løse problemet før. Best Cost Block Crossover (BCBX) er en krysningsoperator adaptert fra et ruteplanleggingsproblem. Greedy Construction Heuristic (GCH) er en ny konstruksjonsheuristikk for å initialisere den første populasjonen. I tillegg brukes et adaptivt valg av krysningsoperatorer.
Den genetiske algoritmen gjør det bedre enn tre implementerte referansealgoritmer for alle problemstørrelser, både i relativt avvik fra beste løsning og antall beste løsninger funnet. Videre er BCBX den beste krysningsoperatoren for små probleminstanser, GCH er den dominerende metoden for å initialisere populasjonen, og det adaptive valget av krysningsoperatorer gjør det bedre enn noen enkelt operator for seg selv. Oppsummert er den nye genetiske algoritmen effektiv til å finne gode produksjonsplaner til fabrikker av ulike karakteristikker, inkludert karakteristikker som kjennetegner Haugstad. | |
| dc.description.abstract | Over the last decades, manufacturing businesses have seen mass outsourcing of production to low-cost countries. Furthermore, larger manufacturers have enjoined reduced costs per produced unit due to their streamlined factories and production volume. The small production facilities in high-cost countries are losing the war on efficiency and need to improve at a lower cost than their larger competitors. One promising area of improvement is within production planning. This area concerns the generation of effective production schedules in a reasonable time on affordable hardware.
This thesis examines a variant of the flowshop scheduling problem (FSP), inspired by the production environment of a small Norwegian manufacturer, Haugstad Furniture Factory (Haugstad). The machines in the factory are grouped by function into stages, and all products, also called jobs, follow the same flow through these stages. At least one stage contains more than one machine, making it a hybrid flowshop. The machines of a given stage are assumed to be identical. Not all products need to be processed in every stage, which also makes it flexible. Moreover, machines need to be prepared before processing each job, and the set-up time depends on the machine's previously processed product. This final extension is called sequence-dependent set-up times. Set-up is also non-anticipatory, meaning that it cannot start before the product arrives physically at the machine. This combination of flowshop extensions is called the hybrid flexible flowshop scheduling problem with sequence-dependent set-up times (HFFSP SDST). The objective is to find production schedules minimising the total time it takes to produce a known quantity of products, also known as makespan.
Out of 172 research papers on the hybrid flowshop scheduling problem (HFSP) in the last decade, only three papers use genetic algorithms (GA) to solve the HFFSP SDST with minimising makespan as the objective. We propose a new GA that finds production schedules for problem instances containing up to 120 jobs, eight stages, and four machines in each stage in less than two minutes. The GA consists of several operators yet to be tested for the FSP. The Best Cost Block Crossover (BCBX) is a crossover operator adapted from the vehicle routing problem. The Greedy Construction Heuristic (GCH) is a new construction heuristic used to create the initial population. Also, an adaptive choice of crossovers is introduced.
The GA performs better than all benchmark algorithms across all sizes of problem instances, both in the average relative distance from the best solution found by any method and the number of best solutions found. Furthermore, BCBX is the best crossover for smaller problem instances, GCH is the dominant initialisation method, and the adaptive choice of crossover operator shows superior to each operator's single performance. In conclusion, the GA can be said to provide high-quality production schedules for production environments of different characteristics, including those of Haugstad. | |
