Scheduling probleem

woensdag 22 februari 2006 10:58

Het scheduling problem is een redelijk vaak voorkomend probleem in de informatica en er zijn dus een heleboel algoritmen te vinden op internet met onderbouwing. Zoek eens op "scheduling problem" eventueel in combinatie met "dynamic programming".

Acties:

Verwijderd

Topicstarter

Ok sorry dat het mss wat onvolledig was, ik dacht ik hou het kort en krachtig.

Het gaat over het plannen van productieorders. Tussen elk order zit ik met ombouwtijden & spoelkosten voor men machines. Als ik vb: eerst ketchup in grote flessen maak en dan mayo in klein flesjes zorgt dit ervoor dat ik men machine moet ombouwen en moet spoelen.

Je zou kunnen denken oke, produceer alle ketchup in grote flessen , dan alle ketchup ik kleine flessen en dan alle mayo in kleine flessen ofzo. Dit gaat ervoor zorgen dat de ombouwtijden & productiekosten(spoelkosten bijvoordbeeld) minimaal zijn.

Nu heeft elk order ook een deadline en een deadzone (dwz: hoever mag ik de productie van het order naar voor schuiven in de tijd alvorens het geleverd gaat worden-->versheid garanderen). Die ervoor gaan zorgen dat ik niet zomaar alle orders met hetzelfde product samen kan plannen. We willen nog op tijd kunnen leveren ook.

Dus de volgorde waarbinnen ik men orders ga plannen gaat zorgen voor een bepaalde totale ombouwtijd & ombouwkost. De planning ABCDE zal dus andere 'kost' krijgen dan ABCED.

Eerst dacht ik aan Branch and Bound waarbij ik ga zoeken naar een globale oplossing, maar dit zou in veel gevallen nog zeer lang duren & ik ben niet geintereseert in een sortering die ervoor zorgt dat mijn orders voor volgend jaar al optimaal staan.

Het doel is dus ervoor zorgen dat ik vrij snel een productieplanning bekom die op korte termijn goedkoop is. Hierdoor dacht ik via heuristiek een sortering op te stellen waarbij ik elke keer lokaal beslis hoe ik het beste plan:

Ik begin met A en ik bereken wat er best na A komt. Ik vind B
dan zoek ik wat best na AB komt , ....

Ik heb geen ervaring met dit soort algoritmen & weet dus niet of ik op een goede weg zit.
Ik dacht eventueel achteraf een soort optimaliseringsalgoritme te draaien dat men korte-termijnplanning nog even doorzoekt naar betere oplossingen. Hier heb ik ook geen ervaring in.

Hopelijk is deze wanordelijke uitleg wat duidelijk

woensdag 22 februari 2006 11:02

Acties:

Verwijderd

Topicstarter

matthijsln schreef op woensdag 22 februari 2006 @ 10:55:
Het scheduling problem is een redelijk vaak voorkomend probleem in de informatica en er zijn dus een heleboel algoritmen te vinden op internet met onderbouwing. Zoek eens op "scheduling problem" eventueel in combinatie met "dynamic programming".

Ik heb al zeer veel gelezen en het probleem waar ik mee zit wordt beschreven als:
"Single Machine Total Tardiness Problem"
Hierrond heb ik al menig thesis doorgenomen maar met weinig resultaat want ik ben wiskundig niet echt sterk.

woensdag 22 februari 2006 11:07

Acties:

woensdag 22 februari 2006 11:12

Je probleem is wel interessant omdat het niet de simpele versie van het scheduling probleem is waarvan de taken onafhankelijk van elkaar zijn qua kosten (tijd).

Je zal dus moeten zoeken in de richting van scheduling algoritmen met deadlines en kosten afhankelijk van de volgorde (zoals je uitlegde).

Ik kan die algoritmen niet zomaar uit mn mouw schudden maar ik denk dat je met deze zoektermen misschien wel wat algoritmen kan vinden waar je wat mee kunt.

Acties:

woensdag 22 februari 2006 11:12

Verwijderd schreef op woensdag 22 februari 2006 @ 11:02:
[...]

Ik heb al zeer veel gelezen en het probleem waar ik mee zit wordt beschreven als:
"Single Machine Total Tardiness Problem"
Hierrond heb ik al menig thesis doorgenomen maar met weinig resultaat want ik ben wiskundig niet echt sterk.

Je hebt de juiste term dus al gevonden. Ik denk dat daarmee je met Google toch snel je eerste vraag over alternatieve oplossingen kan beantwoorden.

Je zult toch enige onderlegging voor informatica/wiskunde nodig hebben om het te begrijpen/implementeren, maar daar ontkom je denk ik zowiezo niet aan wil je een enigszins optimale oplossing, toch?

Acties:

woensdag 22 februari 2006 11:15

Dit is toch heel simpel? Je ontwerpt een penalty functie met daarin het ombouwen en spoelen van zo'n machine (in uren). Dan kijk je naar wat er gepland moet worden (voor een bepaalde deadline) en dan ga je recurief alles door (het zijn toch grote orders?) op zoek naar de laagste penalty functie.

Als je vervolgens een taak uitvoerd haal je die uit het systeem.. als je er eentje toevoegd dan reken je het zaakje nog een keer door.

Het lijkt me verstandig om (zoals je zelf al zei) het vooruitplannen te limiteren tot een dag/week.

[ Voor 12% gewijzigd door BCC op 22-02-2006 11:14 ]

Na betaling van een licentievergoeding van €1.000 verkrijgen bedrijven het recht om deze post te gebruiken voor het trainen van artificiële intelligentiesystemen.

Acties:

woensdag 22 februari 2006 11:21

BCC schreef op woensdag 22 februari 2006 @ 11:12:
Dit is toch heel simpel? Je ontwerpt een penalty functie met daarin het ombouwen en spoelen van zo'n machine (in uren). Dan kijk je naar wat er gepland moet worden (voor een bepaalde deadline) en dan ga je recurief alles door (het zijn toch grote orders?) op zoek naar de laagste penalty functie.

Als je vervolgens een taak uitvoerd haal je die uit het systeem.. als je er eentje toevoegd dan reken je het zaakje nog een keer door.

Brute force oplossingen zijn meestal wel simpel ja

maar volgens de TS geen oplossing voor de omvang van zijn probleem.

Acties:

woensdag 22 februari 2006 11:28

Dat geloof ik niet.. Voor korte termijn kun je voor zoiets simpels echt VEEL doorrekenen. En anders doe je het met een Greedy, maar dan moet je wel orders kunnen clusteren op dagen oid.

[ Voor 37% gewijzigd door BCC op 22-02-2006 11:22 ]

Na betaling van een licentievergoeding van €1.000 verkrijgen bedrijven het recht om deze post te gebruiken voor het trainen van artificiële intelligentiesystemen.

Acties:

woensdag 22 februari 2006 11:35

Andere manier zou zijn om te kijken naar lokaal zoeken. Probleem is dat vrij veel van de schedulings problemen die te maken heb met tardiness al snel zeer lastig worden om optimaal op te lossen.

Je zou hier kunnen kijken naar een random start oplossing. Je kunt hiervan redelijk snel de kosten bepalen. Daarna een kleine verandering doorvoeren (twee producten omdraaien) en opnieuw de kosten doorrekenen. Dan zijn er twee mogelijkheden: Of de nieuwe kosten zijn lager dan de vorige, dit is altijd goed. Of de oude kosten zijn hoger dan de vorige kosten. Deze nieuw gevonden oplossing is dan niet wenselijk. Afhankelijk van type lokaal zoeken wat je gebruikt kun je deze alsnog eventueel accepteren.

Vermoed dat lokaal zoeken voor dit probleem niet zo heel erg lastig is om te implementeren en dat het verder vrij snel oplossingen zal geven.

Aviation is proof that given the will, we have the capacity to achieve the impossible.
--Eddie Rickenbacker

Acties:

woensdag 22 februari 2006 11:47

Je weet dat je net bijna een Greedy algorithme omschreven hebt

? Enige wat je vergeten bent is dat je algoritme niet terug mag komen op genomen beslissingen, anders wordt het een brute-force met alle extra rekentijd die erbij hoort.. En je moet dus groeperen, aangezien je een aantal mogelijke keuzes moet hebben waaruit je greedy moet kiezen.

[ Voor 76% gewijzigd door BCC op 22-02-2006 11:36 ]

Na betaling van een licentievergoeding van €1.000 verkrijgen bedrijven het recht om deze post te gebruiken voor het trainen van artificiële intelligentiesystemen.

Acties:

woensdag 22 februari 2006 11:49

Is standaard recept voor lokaal zoeken. Het belangrijkste is dat je hier randomness gebruikt. Eigenlijk had ik netjes neer moeten zetten "Daarna een kleine willekeurige verandering...".

Overigens ben ik het niet helemaal mee eens dat dat greedy is, aangezien je als je bijvoorbeeld Simulated Annealing of Tabu Search gebruikt je ook verslechteringen mag accepteren om hopelijk later een verbetering te vinden. Het is dus niet alle mogelijkheden brute-force doorrekenen, je maakt gebruik van randomness om hopelijk een goede oplossing te vinden.

Aviation is proof that given the will, we have the capacity to achieve the impossible.
--Eddie Rickenbacker

Acties:

woensdag 22 februari 2006 12:13

Sorry.. slecht gelezen vanaf mijn kant. Maar gezien de complexiteit van de TS is tabu-searching nogal over the top voor zijn probleem... als hij z'n probleem volledig beschreven heeft (wat mij niet het geval lijkt).

[ Voor 38% gewijzigd door BCC op 22-02-2006 11:51 ]

Na betaling van een licentievergoeding van €1.000 verkrijgen bedrijven het recht om deze post te gebruiken voor het trainen van artificiële intelligentiesystemen.

Acties:

woensdag 22 februari 2006 12:36

Tabu search is misschien wat over de top (iets wat lastiger te implementeren). Aan de andere kant, als ik kijk naar zijn gehele probleem is het toch een vrij complex probleem.

Het andere voorbeeld van lokaal zoeken wat ik gaf, Simulated Annealing, is zeer simpel te implementeren en je kunt zeer makkelijk zijn feasibility-constraints (wordt iets geproduceerd NA de deadzone en VOOR de deadline) controleren en ook de totale kosten berekenen.

De TS heeft het over dat B&B te lang duurt, maar wat is ongeveer de tijd die aan rekentijd besteed mag worden voor het vinden van een oplossing? Als het gaat om een vrij OK oplossing, dan zou SA deze in niet al te lange tijd moeten kunnen geven.

Aviation is proof that given the will, we have the capacity to achieve the impossible.
--Eddie Rickenbacker

Acties:

Verwijderd

Topicstarter

Wow veel reacties, merci mannen!

Ik besprak inderdaad een soort van Greedy Algoritme. Waarbij ik wel ga moeten zorgen dat ik via een of andere wegingsfactor het halen van deadlines ga kunnen afwegen tov ombouwtijd/kost.

Enige voorstellen?

Het willekeurig wisselen van orders + herberekenen was al in me opgekomen maar brengt veel berekenwerk met zich mee & mits ik meer geinteresseerd ben in enkel de eerste week van men sorteringsperiode brengt dit niet echt op.Ik begin meer en meer te denken dat een globaal optimaliseringsalgoritme draaien op het resultaat van men greedy algoritme niet de goede weg is.

Ik ga nu even "Simulated Annealing" uitpluizen. Bedankt voor de tip. Ik was het al eens ergens tegengekomen, maar was de term niet verder gaan uitdiepen.

woensdag 22 februari 2006 13:00

Acties:

RickN

Ik zou eens kijken naar Earliest Deadline First Scheduling. Das een dynamisch scheduling algorithme. Bijkomend voordeel is dat je eenvoudig om kunt gaan met een order die op het laatste moment binnenkomt.

In principe komt het erop neer dat je ten alle tijden werkt aan de order die het eeste klaar moet zijn. Je onderbreekt dus eventueel een order tijdelijk als er een order met een vroegere deadline binnenkomt.

EDF garandeert dat je al je deadlines haalt, mits je systeem voldoende capaciteit heeft. EDF wordt lastig (onvoorspelbaar) wanneer je een deadline mist, maar aangezien dat een indicatie is dat je systeem teweinig capaciteit heeft, kun je zo'n situatie eenvoudig voorkomen, door orders te weigeren die het missen van een deadline bij EDF scheduling tot gevolg zouden hebben.

He who knows only his own side of the case knows little of that.

woensdag 22 februari 2006 13:01

Acties:

woensdag 22 februari 2006 13:03

Verwijderd schreef op woensdag 22 februari 2006 @ 12:36:
Het willekeurig wisselen van orders + herberekenen was al in me opgekomen maar brengt veel berekenwerk met zich mee & mits ik meer geinteresseerd ben in enkel de eerste week van men sorteringsperiode brengt dit niet echt op.Ik begin meer en meer te denken dat een globaal optimaliseringsalgoritme draaien op het resultaat van men greedy algoritme niet de goede weg is.

Simulated Annealing doet niets anders dan dat willekeurige wisselen en verslechteringen worden met een bepaalde kans (die afhangt van de tijd in het proces, hoe lang het al draait, en de mate van verslechtering) toch geaccepteerd.

Het berekenwerk moet denk ik ook best meevallen. Kun je aangeven om hoeveel productie units te planning totaal gaat. Stel dat je een bepaalde sequence van productie hebt en je wisselt de eerste twee om, dan veranderen alleen in het begin de kosten. Het enige wat je dan nog moet doen is controleren of de rest van de sequence nog op tijd is, maar voor wat betreft de kosten verandert er totaal niets. Als het totaal aantal elementen in de sequence (dus van de totale planning) extreem groot is, dan gaat dit dus wel wat meer tijd kosten (maar hier zijn ook nog wel wat slimmigheden voor te verzinnen)

Aviation is proof that given the will, we have the capacity to achieve the impossible.
--Eddie Rickenbacker

Acties:

woensdag 22 februari 2006 13:09

RickN schreef op woensdag 22 februari 2006 @ 13:00:
Ik zou eens kijken naar Earliest Deadline First Scheduling. Das een dynamisch scheduling algorithme. Bijkomend voordeel is dat je eenvoudig om kunt gaan met een order die op het laatste moment binnenkomt.

In principe komt het erop neer dat je ten alle tijden werkt aan de order die het eeste klaar moet zijn. Je onderbreekt dus eventueel een order tijdelijk als er een order met een vroegere deadline binnenkomt.

EDF garandeert dat je al je deadlines haalt, mits je systeem voldoende capaciteit heeft. EDF wordt lastig (onvoorspelbaar) wanneer je een deadline mist, maar aangezien dat een indicatie is dat je systeem teweinig capaciteit heeft, kun je zo'n situatie eenvoudig voorkomen, door orders te weigeren die het missen van een deadline bij EDF scheduling tot gevolg zouden hebben.

EDF houdt toch geen rekening met de omstelkosten (en ook de spoelkosten)?

Aviation is proof that given the will, we have the capacity to achieve the impossible.
--Eddie Rickenbacker

Acties:

Verwijderd

Topicstarter

RickN schreef op woensdag 22 februari 2006 @ 13:00:
Ik zou eens kijken naar Earliest Deadline First Scheduling. Das een dynamisch scheduling algorithme. Bijkomend voordeel is dat je eenvoudig om kunt gaan met een order die op het laatste moment binnenkomt.

In principe komt het erop neer dat je ten alle tijden werkt aan de order die het eeste klaar moet zijn. Je onderbreekt dus eventueel een order tijdelijk als er een order met een vroegere deadline binnenkomt.

EDF garandeert dat je al je deadlines haalt, mits je systeem voldoende capaciteit heeft. EDF wordt lastig (onvoorspelbaar) wanneer je een deadline mist, maar aangezien dat een indicatie is dat je systeem teweinig capaciteit heeft, kun je zo'n situatie eenvoudig voorkomen, door orders te weigeren die het missen van een deadline bij EDF scheduling tot gevolg zouden hebben.

Hier hou ik niet echt rekening met de ombouwtijden & kosten denk ik. Ik denk dat ik best een gulden middenweg zoek tussen deze deadlines en kosten.

woensdag 22 februari 2006 13:13

Acties:

Verwijderd

Topicstarter

hammerhead schreef op woensdag 22 februari 2006 @ 13:01:
[...]

Simulated Annealing doet niets anders dan dat willekeurige wisselen en verslechteringen worden met een bepaalde kans (die afhangt van de tijd in het proces, hoe lang het al draait, en de mate van verslechtering) toch geaccepteerd.

Het berekenwerk moet denk ik ook best meevallen. Kun je aangeven om hoeveel productie units te planning totaal gaat. Stel dat je een bepaalde sequence van productie hebt en je wisselt de eerste twee om, dan veranderen alleen in het begin de kosten. Het enige wat je dan nog moet doen is controleren of de rest van de sequence nog op tijd is, maar voor wat betreft de kosten verandert er totaal niets. Als het totaal aantal elementen in de sequence (dus van de totale planning) extreem groot is, dan gaat dit dus wel wat meer tijd kosten (maar hier zijn ook nog wel wat slimmigheden voor te verzinnen)

De sorteringsfunctie moet met dynamische parameters kunnen worden uitgevoerd.
1dag tot 1jaar.

Je kan je inbeelden dat er gedurende 1 jaar er wel wat orders aan bod komen. Het algoritme zouden ze ook liefst gebruiken in andere bedrijven gebruiken. Hiermee wil ik zeggen het moet goed kunnen werken met 100orders/week zowel als 1000000orders/week of meer natuurlijk, ik verzin maar wat cijfers je kan ze dus nog kwadrateren als je wilt

.

Mss is die Simulated Annealing wel handig om men greedy resultaat nog te optimaliseren, ik mag hier echter niet milder worden als ik lang aan het rekenen ben. Dit zou het greedy resultaat teniet doen.

woensdag 22 februari 2006 13:20

Acties: