Job sequencing

Job sequencing is een probleem uit de theoretische computerwetenschap en combinatoriek.

Formulering

Een machine, of een mens, moet een aantal jobs (activiteiten, taken,...) na elkaar uitvoeren. Elke job heeft een bepaalde tijd nodig en moet voor een bepaald tijdstip - de deadline - uitgevoerd zijn; zo niet, dient er voor die job een zekere boete betaald te worden. De grootte van de boete varieert van job tot job. De volgorde van uitvoering van de jobs is vrij te kiezen.

Het beslissingsprobleem van job sequencing is dan: bestaat er, voor een gegeven positief geheel getal k, een volgorde van uitvoering van de jobs zodanig dat de totale te betalen boete niet groter is dan k?

Dit beslissingsprobleem is een van de 21 problemen waarvan Richard Karp in 1972 bewees dat ze NP-volledig zijn.

Wiskundig kan het probleem als volgt geformuleerd worden:

• Er zijn p jobs, genummerd van 1 tot en met p.
• De uitvoeringstijden van de jobs worden voorgesteld door de p-dimensionale vector $(T_{1},T_{2},\dots T_{p})$;
• De deadlines van de jobs door de vector $(D_{1},D_{2},\dots D_{p})$;
• De boetes van de jobs door de vector $(B_{1},B_{2},\dots B_{p})$;
• Een job sequence is een permutatie $Q=\{q_{1},q_{2},\dots q_{p}\}$ van $\{1,2,\dots p\}$;
• Het tijdstip waarop de n-de job afgewerkt wordt in de job sequence Q is $T_{(n)}=\sum _{i=1}^{n}T_{q_{i}}$
• De boete voor de n-de job is $B_{(n)}=B_{q_{n}}$ als $T_{(n)}>D_{q_{n}}$, of 0 anderszins;
• $k$ is een gegeven positief geheel getal.
• Bestaat er een permutatie $Q=\{q_{1},q_{2},\dots q_{p}\}$ van $\{1,2,\dots p\}$ zodanig dat $\sum _{n=1}^{p}B_{(n)}\leq k$?

Als optimaliseringsprobleem geformuleerd wordt dit: vind de volgorde van uitvoering van de jobs die de kleinste boete oplevert.

Scheduling-problemen

Job sequencing is slechts een van de zeer uitgebreide groep van scheduling-problemen, waarbij het erom gaat om activiteiten (jobs, taken) toe te wijzen aan beperkte hulpmiddelen (resources), zodanig dat een of meerdere doelstellingen geoptimaliseerd worden.

Afhankelijk van de situatie kunnen de activiteiten en hulpmiddelen uiteenlopende vormen aannemen. De middelen kunnen machines zijn, computer(-processoren), mecaniciens in een autoherstelwerkplaats, landingsbanen op een luchthaven enzovoort. Activiteiten kunnen verschillende bewerkingen zijn in een productieproces, het landen of opstijgen op een luchthaven, een computerprogramma, de reparatie van een auto, enzovoort. Doelstellingen kunnen onder meer zijn het minimaliseren van de totale tijd om de activiteiten uit te voeren; van de totale kostprijs; van het aantal machines of mensen dat nodig is om de gegeven activiteiten binnen een vooropgestelde periode af te werken; of van het aantal jobs dat te laat is (gesteld dat een job voor een bepaald tijdstip klaar dient te zijn); of het maximaliseren van de bezettingsgraad van de machines. Het probleem is dan een schema op te stellen dat aan de doelstelling(en) voldoet, waarin is opgenomen welke machine wanneer aan welke taak werkt.

Job-shop scheduling

De zogenoemde job-shop scheduling-problemen vormen een belangrijke groep van scheduling-problemen uit operationeel onderzoek (bijvoorbeeld productieplanning). De job shop is een (denkbeeldig) atelier met een aantal machines die een aantal jobs moeten uitvoeren. Elke job bestaat uit een aantal bewerkingen en elke machine kan een bepaalde set van bewerkingen uitvoeren. De uitvoeringstijd van een bepaalde bewerking op een bepaalde machine is gekend.

Het job-shop-probleem: voer de jobs uit in een minimum aan tijd, is een veralgemening van het handelsreizigersprobleem; in dat probleem is er een machine (de handelsreiziger) en de jobs zijn de steden die moeten bezocht worden.

Deze problemen hebben twee fundamentele beperkingen: een machine kan niet meer dan een job tegelijk uitvoeren (dit noemt men een "resource constraint"); en twee bewerkingen van een job kunnen niet tegelijk uitgevoerd worden (dit is een "sequence constraint"). Daarnaast kunnen er nog andere bijkomende beperkingen zijn.

Scheduling-problemen kunnen statisch zijn (alle jobs liggen bij het begin vast) of dynamisch (nieuwe jobs arriveren van tijd tot tijd).

Veel van deze problemen zijn NP-moeilijke combinatoriële optimaliseringsproblemen, waarvan de oplossingsruimte exponentieel uitbreidt en waarvoor het meestal zeer moeilijk is om een optimale oplossing te vinden in een redelijke termijn. Hiervoor is een breed gamma aan heuristieke en metaheuristieke technieken ontwikkeld.

Voorbeeld

Als voorbeeld kan men een kopieeratelier beschouwen met een aantal kopieermachines. Sommige machines kunnen enkel kopiëren in zwart-wit, andere ook in kleur; sommige kunnen vergroten en verkleinen en/of sorteren, andere niet; en niet alle machines zijn even snel. In een statisch scenario heeft de uitbater aan het begin van de werkdag een lijst van uit te voeren kopieerjobs voor die dag en moet hij een schema opstellen om de jobs zo snel mogelijk af te werken. In een dynamisch scenario arriveren in de loop van de dag klanten met nieuwe jobs en moet hij deze in het schema inpassen om de totale wachttijd van de klanten te minimaliseren.

Flow-shop scheduling

Een andere groep van scheduling-problemen zijn de flow-shop scheduling-problemen. In een flow shop zijn er een aantal machines die elk een deel van een job uitvoeren. Elke job moet in volgorde door de machines 1, 2, ... verwerkt worden. De tijd die een bepaalde machine nodig heeft voor een bewerking varieert van job tot job. Wat is de volgorde van de jobs op elke machine om al de jobs in een minimale totale tijd af te werken? In het jargon noemt men deze totale tijd de makespan.

Dit is ook een NP-moeilijk probleem. Stel er zijn n jobs en m machines, en elke job moet door de machines 1,2,...m in die volgorde verwerkt worden. Het totaal aantal mogelijke productieschema's is dan (n!)^m.

Wanneer we eisen dat de volgorde waarin de jobs verwerkt worden dezelfde is op elke machine, is het aantal mogelijke schema's slechts n!, het aantal permutaties van n jobs. Dit vereenvoudigde probleem wordt permutation flow-shop scheduling genoemd.

In een no-wait flow shop scheduling problem mag er geen onderbreking zijn bij het verwerken van een job door de verschillende machines: als de eerste machine klaar is met een job, moet de tweede machine onmiddellijk verdergaan met die job. De eerste machine moet eventueel wachten om aan een nieuwe job te beginnen om zeker te zijn dat aan deze voorwaarde voldaan is.

Tijdsbalken voor een no-wait flow-shop scheduling van vijf jobs op twee machines, A en B. Als A klaar is met een job moet B er onmiddellijk mee verdergaan. Bovenaan zijn de jobs verwerkt in de volgorde 1-2-3-4-5 en onderaan in de volgorde 3-4-5-1-2. De verwerkingstijden van de jobs op elke machine zijn dezelfde in de twee gevallen, maar het onderste geval heeft een kleinere totale makespan vanaf het begin van de eerste job op machine A tot het einde van de laatste job op machine B.

Een no-wait-probleem is een bijzonder geval van een permutatieprobleem en is ook NP-moeilijk als er meer dan twee machines zijn; enkel voor kleine problemen kan men met een exact algoritme in een redelijke rekentijd de optimale oplossing vinden. De rekentijd neemt exponentieel toe als het probleem groter wordt. Dan moet men zijn toevlucht nemen tot heuristieke en metaheuristieke methoden, die wel een redelijke rekentijd hebben maar mogelijk slechts een bijna-optimale oplossing geven. Bij de metaheuristieken zijn onder meer simulated annealing, genetische algoritmes, tabu search, particle swarm optimization en combinaties van deze technieken toegepast op deze problemen.

Flow-shop-scheduling komt bijvoorbeeld voor in assemblageprocessen. No-wait-problemen hebben diverse industriële toepassingen zoals in de chemische, farmaceutische of voedingsverwerkende nijverheid waarin een product in een aantal stappen wordt aangemaakt maar waar kwaliteitsverlies kan optreden tussen de stappen.

Bronnen, noten en/of referenties