P.J. Kramer
Het Job Shop Scheduling Probleem (JSSP).
Literatuuropdracht/scriptie,
Rapport 2001.LT.5559, Transporttechnologie, Logistieke Techniek.
De machinefabriek (job shop) lijkt veel op een reparatiewerkplaats: er wordt
op klantenorder gefabriceerd, men verkoopt eigenlijk geen eigen product maar
kunde en productiecapaciteit om het door de klant gewenste product te maken
[P.H. van der Lee Automatisering in voorraadbeheer en produktiebesturing.
Deventer, Kluwer Bedrijfswetenschappen, 1992, ISBN 90-267-1800-4].
De onderdelenfabricage geschiedt meestal op universele machines. De onderdelen
moeten vaak veel verschillende bewerkingen ondergaan op veel verschillende
machines. Door de sterk wisselende routes van de onderdelen in de machinale
afdeling is een strakke planning met zeer korte wachttijden in de machinale
afdeling onmogelijk. Noodgedwongen moet men lange wachttijden (2 tot 5 dagen)
tussen de bewerkingen incalculeren, hetgeen tot zeer lange totale
doorlooptijden leidt.
Het doel van deze literatuurscriptie is het beschrijven van het job shop
scheduling probleem (JSSP). Hierin moet niet alleen worden beschreven hoe
de job shop wordt gedefinieerd, maar tevens hoe de lijst met orders wordt
gedefinieerd. Daarnaast moet worden onderzocht welke optimalisatiecriteria
worden gebruikt om de job shop te beoordelen.
Naast de beschrijving van het JSSP, moeten de verschillende methoden
worden beschreven, om het JSSP op te kunnen lossen. Hierbij dient een
algemene beschrijving van de methoden te worden gegeven. Naast een
algemene beschrijving van het JSSP moeten toepassingen van de methoden in
de praktijk worden beschreven.
In het job shop scheduling probleem (JSSP) moet een set met jobs worden
verwerkt door een set met machines. Deze set met machines kan weer uit
verschillende typen machines bestaan. Het productieproces van een enkel
product wordt meestal aangeduid met de term job. Een enkele stap in het
proces wordt aangeduid als een operatie. De lijst met orders legt de
eigenschappen van de jobs vast. De volgorde van de operaties, binnen
dezelfde job, liggen vast. Dit wordt de precedence (volgorde)
randvoorwaarde genoemd.
Bij het maken van een schedule moet rekening worden gehouden met gestelde
randvoorwaarden. Deze randvoorwaarden zijn onder andere het aantal
machines, de capaciteiten van de machines, de volgorderelaties en het te
optimaliseren doel. De capaciteit van de iedere machine in de job shop is
beperkt. Iedere machine kan namelijk hooguit één operatie
tegelijk uitvoeren en voor iedere job kan slechts één
operatie tegelijk plaatsvinden.
Het doel van een JSSP is het verkrijgen van een uitvoerbaar, goed schedule.
Het liefst wordt het optimale schedule verkregen, maar een bijna optimaal
schedule zal in de praktijk niet zeer veel slechter zijn dan het optimale
schedule.
Zeer belangrijk bij het JSSP is het optimalisatiecriterium. Twee
optimaliseringscriteria worden meestal op het JSSP toegepast. Dit zijn het
optimaliseren naar de makespan en het optimaliseren naar de tardiness. De
makespan is de tijd die nodig is om alle jobs te voltooien. De tardiness
is het positieve verschil tussen de tijd dat een bepaalde job gereed is en
de due date van deze job. Het optimaliseren van het JSSP naar de makespan,
wordt verreweg het meest toegepast.
Om het JSSP te schedulen worden twee categorieën van scheduling algoritmen
onderscheiden [H.J. Vaes "An event-driven job shop scheduling system, applied
to the Vertex system". Dissertatie TU Eindhoven, 1996, ISBN 90-386-0158-1].
Dit zijn optimalisatie- en benaderingsalgoritmen.
- Optimalisatiealgoritmen
Een optimalisatiealgoritme is een algoritme dat, voor een gegeven
voorbeeld, beslist een optimale oplossing vindt, mits deze optimale
oplossing bestaat. Optimalisatiealgoritmen bestaan slechts in de vorm van
een numeriek algoritme. Hierbij wordt gebruik gemaakt van een numeriek
schema. Het numerieke optimalisatiealgoritme wordt vaak gevisualiseerd met
behulp van een branching tree (vertakte boom) of een disjuncte graaf.
Praktische JSSP's zijn echter te groot om met behulp van een
optimalisatiealgoritme op te lossen. Optimalisatiealgoritmen vergen zeer
veel rekentijd. Om tot een oplossing van een probleem te komen, binnen een
aanvaardbare tijd, dient het probleem zeer klein te blijven. Een bekend
optimalisatiealgoritme is het branch and bound algoritme.
- Benaderingsalgoritmen
Een benaderingsalgoritme vindt een oplossing, als deze oplossing bestaat.
Deze oplossing kan optimaal zijn, maar dit wordt niet gegarandeerd.
Benaderingsalgoritmen kunnen worden onderscheiden in numerieke,
constructieve en iteratieve benaderingsalgoritmen.
- Numerieke benaderingsalgoritmen
Deze algoritmen worden over het algemeen niet veel gebruikt. De reden
hiervoor is de grote hoeveelheid benodigde rekentijd om problemen op te
lossen. In gevallen dat de eliminatieprocedure sterker wordt, wordt de
rekentijd wel verkleind, maar de verkregen oplossing is daardoor van een
mindere kwaliteit. Een voorbeeld van een numeriek benaderingsalgoritme
is het beam search algoritme.
- Constructieve benaderingsalgoritmen
Constructieve algoritmen worden zeer vaak op het JSSP toegepast. De
reden dat dispatchingalgoritmen vaak worden toegepast is de korte
benodigde berekeningstijd en de redelijke resultaten die met deze
dispatchingalgoritmen zijn te behalen. Voornamelijk
dispatchingalgoritmen worden gebruikt als constructief
benaderingsalgoritme.
- Iteratieve benaderingsalgoritmen
De benaderingsalgoritmen worden zeer vaak toegepast, vanwege de goede
resultaten die hiermee worden verkregen. De berekeningstijd is echter
een stuk groter dan de constructieve benaderingsalgoritmen. Voor deze
methoden is een initieel schedule benodigd, van waaruit de iteratieve
verbeteringsstappen kunnen worden uitgevoerd. Enkele voorbeelden van
iteratieve benaderingsalgoritmen zijn: tabu search, simulated annealing,
genetische algoritmen en neurale netwerken.
De belangrijkste conclusies van deze literatuurscriptie worden hierna
opgesomd.
- Optimalisatiealgoritmen
Voor praktische JSSP's (tenzij zeer klein) kunnen optimalisatiealgoritmen
niet worden gebruikt. Vanwege de enorm grote rekentijd kunnen
optimalisatiealgoritmen slechts op zeer kleine problemen worden toegepast.
Ook optimalisatiealgoritmen waarbij een eliminatiemethode wordt toegepast
zijn in de praktijk meestal niet goed toepasbaar. De benodigde rekentijd
is hierdoor een stuk kleiner, maar voor praktische problemen blijft de
rekentijd te groot.
- Benaderingsalgoritmen
Voor grotere JSSP gevallen, waartoe de meeste praktische JSSP's behoren,
kunnen alleen benaderingsalgoritmen met succes worden toegepast. Zulke
algoritmen zijn in staat een min of meer redelijke oplossing, soms zelfs
optimale oplossing, te vinden in een redelijke hoeveelheid tijd. Bij deze
algoritmen bestaat meestal een relatie tussen de berekeningstijd die men
bereid is te spenderen en de kwaliteit die men van de oplossing wil
verkrijgen.
- Optimalisatiecriteria
Twee optimaliseringscriteria worden meestal op het JSSP toegepast. Dit
zijn het optimaliseren naar de makespan en het optimaliseren naar de
tardiness. De makespan is de tijd die nodig is om alle jobs te voltooien.
De tardiness is het positieve verschil tussen de tijd dat een bepaalde job
gereed is en de due date van deze job. Het optimaliseren van het JSSP naar
de makespan, wordt verreweg het meest toegepast.
- Fuzzy logic
Het is opvallend dat fuzzy logic zeer weinig wordt toegepast in het JSSP.
De mogelijkheden om fuzzy logic toe te passen in het JSSP is velerlei.
Hierbij moet niet alleen worden gedacht aan de eerder gemoemde fuzzy
verwerkingstijd en fuzzy due date, maar eveneens aan bijvoorbeeld set-up
tijden en release dates.
Door het gebruik van fuzzy logic in het JSSP kan het probleem dichter bij
de werkelijkheid worden gebracht. In werkelijkheid liggen vastgestelde
grenzen niet zo strikt vast, als deze in een JSSP worden vastgelegd zonder
gebruik van fuzzy logic.
Rapporten studenten Logistieke Techniek
Gewijzigd: 2002.05.16;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.