Genetic Algorithm for Job Shop Scheduling in High-Variety, Low-Volume Production Environments

Abstract

Produksjonsplanlegging i produksjonsmiljø som er preget av store produktvarianter og et lavt volum er en stor utfordring i tider hvor korte ledetider og svært tilpassede produkter er høyt ettertraktet. Arbeidet med å planlegge produksjonsprosesser er svært omfattende, og blir beregningsmessig uhåndterlig når antall unike produksjonsruter økes, og resulterer ofte i at suboptimale produksjonsplaner blir laget. Avanserte systemer for å takle de ovennevnte utfordringene finnes, men produksjonsplanleggere har en tendens til å holde fast på tradisjonelle planleggingsmetoder ettersom strevet med å bli kjent med nye systemer blir sett på som et problem, og fordelene en slik implementasjon medfører ofte blir forbisett.

Denne studien tar sikte på å identifisere karakteristikker i produksjonsmiljøer hvor flere jobber utføres på en og samme tid, på et utvalg av maskiner, og utvikle en optimeringsmodell som tar sikte på produsere optimale tidsplaner basert på ulike objektivfunksjoner. Resultatene fra optimaliseringsmodellene ligner de fra litteraturen, og viser gode evner til å løse store optimeringsproblemer. Videre identifiseres styrker ved avanserte planleggingsystemer, og paralleller trekkes fra slike systemer til de utviklede modellene.

De konkrete resultatene skildrer optimaliserte tidsplaner basert på data og begrensninger som modellen håndterer i henhold til ulike objektivfunksjoner. Tidsplaner er produsert med minimert gjennomløpstid, tidsfrister som er holdt, med sen-start tilnærming, og en kombinasjon av de tre nevnte trekkene. Lovende resultater oppnås ved å etablere nøyaktige begrensninger, muliggjort ved implementering av et avansert system for planlegging, integrert blant støttesystemer. Dette muligjør effektive omplaneringsfunksjoner som gir dynamisk produksjonsplanlegging og planleggingskapasitet, i stand til å reagere raskt til forstyrrelser på verkstedsgulvet.

Production planning and scheduling in high-variety, low-volume production environments is a challenging task, in times where short lead times and highly customized products are sought after. The act of scheduling manufacturing processes becomes increasingly computationally intractable when also the number of unique production routings increases, often resulting in sub-optimal production plans being produced. Advanced systems for coping with the aforementioned challenges do exist, but yet production planners tend to hold on to traditional planning approaches as becoming familiar with new systems is regarded as a hassle, and the set of advantages often are looked past.

This study aims to identify characteristics in jobbing environments belonging to the field of the engineer-to-order production process and to develop three variants of an optimization model which aim to obtain optimal schedules based on different objective functions. The results from the optimization models are in agreement with the literature, depicting exceptional abilities to solve large optimization problems. Furthermore, effective capabilities of advanced planning and scheduling (APS) systems are identified, and parallels are drawn to the production planning and scheduling capabilities which become enabled by the optimization models.

The results depict optimized schedules based on the input data and constraints, according to various objective functions. Schedules are produced with minimized total makespan, satisfied deadlines, with a late start approach, and a combination of the three aforementioned traits. Promising results are obtained by setting accurate constraints enabled by the implementation of an APS system, integrated among supporting systems. In turn, rescheduling capabilities are enabled, rendering dynamic production planning and scheduling capabilities that are able to respond to disruptions on the shop floor.