Production Load balancing - Met changeover

[Armageddon_2k]

Beste Tweakers,

Voor een onderzoek ben ik aan het kijken naar een efficiente manier om load balancing toe te passen in de industrie.

Stel ik heb de volgende hoeveelheid "werk" die verzet moet worden.
Ik heb de hoeveelheid werk hier beperkt, maar er zijn veel meer mogelijkheden, maar dit zijn de interessante parameters.

Werkorder 1	Product 1	Setup type 1	Quantity 500
Werkorder 2	Product 2	Setup type 1	Quantity 150
Werkorder 3	Product 3	Setup type 2	Quantity 50
Werkorder 4	Product 3	Setup type 3	Quantity 100
Werkorder 5	Product 4	Setup type 3	Quantity 50
Werkorder 6	Product 5	Setup type 3	Quantity 150

Er zijn n aantal machines, laten we nu zeggen 2 stuks.
Een machine draait in een specifieke setup, als een machine van setup verandert kost dit tijd.
We gaan uit van een lange setuptijd van 20 minuten oid.

Een werkorder mag op 2 machines tegelijk uitgevoerd worden. Dus bijvoorbeeld van werkorder 1 kunnen er 250 op Machine1 gemaakt worden en de overige 250 op Machine2.

Nu ben ik opzoek naar methoden, algoritmen om deze werklading zo efficent mogelijk te verdelen.
Je zou domweg alle machines op Setup1 kunnen zetten tot deze workload klaar is, dan Setup2 en dan Setup3.
Maar zoals je ziet, is er van Setup2 niet zo heel veel te produceren. Het kan efficienter zijn om 1 machine om te bouwen maar Setup2 en de andere machine naar Setup3,

Mijn huidige zoekwerk levert vooral Management technieken zoals Heijunka ed op.
Maar ik ben opzoek naar handvatten en termen om dit als programmeur op te gaan lossen.
Ik verwacht uiteraard geen 1 op 1 stuk code, maar meer wat pointers waar ik mee verder kan.

[Haan]

Ik denk dat de tijdsfactoren hier ook belangrijk zijn, want dat kan invloed hebben op je keus.
Als bijvoorbeeld je Setup2 lang duurt per stuk, kan het zinnig zijn om die op een dedicated machine te laten verwerken.

Volgens mij kom je uiteindelijk uit op een optimalisatie vraagstuk met x aantal inputs (variabelen, constraints) die je in een formule zou moeten proberen te gieten.

[Verwijderd]

Armageddon_2k schreef op donderdag 02 juli 2015 @ 08:57:
Beste Tweakers,

Voor een onderzoek ben ik aan het kijken naar een efficiente manier om load balancing toe te passen in de industrie.

Stel ik heb de volgende hoeveelheid "werk" die verzet moet worden.
Ik heb de hoeveelheid werk hier beperkt, maar er zijn veel meer mogelijkheden, maar dit zijn de interessante parameters.

Werkorder 1	Product 1	Setup type 1	Quantity 500
Werkorder 2	Product 2	Setup type 1	Quantity 150
Werkorder 3	Product 3	Setup type 2	Quantity 50
Werkorder 4	Product 3	Setup type 3	Quantity 100
Werkorder 5	Product 4	Setup type 3	Quantity 50
Werkorder 6	Product 5	Setup type 3	Quantity 150

Er zijn n aantal machines, laten we nu zeggen 2 stuks.
Een machine draait in een specifieke setup, als een machine van setup verandert kost dit tijd.
We gaan uit van een lange setuptijd van 20 minuten oid.

Een werkorder mag op 2 machines tegelijk uitgevoerd worden. Dus bijvoorbeeld van werkorder 1 kunnen er 250 op Machine1 gemaakt worden en de overige 250 op Machine2.

Nu ben ik opzoek naar methoden, algoritmen om deze werklading zo efficent mogelijk te verdelen.
Je zou domweg alle machines op Setup1 kunnen zetten tot deze workload klaar is, dan Setup2 en dan Setup3.
Maar zoals je ziet, is er van Setup2 niet zo heel veel te produceren. Het kan efficienter zijn om 1 machine om te bouwen maar Setup2 en de andere machine naar Setup3,

Mijn huidige zoekwerk levert vooral Management technieken zoals Heijunka ed op.
Maar ik ben opzoek naar handvatten en termen om dit als programmeur op te gaan lossen.
Ik verwacht uiteraard geen 1 op 1 stuk code, maar meer wat pointers waar ik mee verder kan.

In principe zou je gewoon de kosten moeten berekenen. Of dit nou in minuten of een absolute waarde is.
En dan loop je alle mogelijke setups langs.
- verwerk alles op machine 1
- verwerk 75% op machine 1 en gebruik machine 2(die nog een setup nodig heeft) voor de overige 25%

Kort gezegd kom met een formule om te berekenen hoe "duur" het is om een n quantity te realiseren. Als je dat eenmaal weet kun je de kosten van de verschillende mogelijkheden berekenen en hier de laagste uitkiezen.

Het wordt lastiger als je terwijl een batch bezig is weer nieuw werk erbij krijgt maar ik zou eerst simpel beginnen in een kleine simulatie.

[H!GHGuY]

Je wil misschien wel eens kijken naar Zookeeper.

Zie het vooral als een soort shared-state en communicatie-protocol die het verdelen van werk eenvoudig maakt.

Een voorbeeldje is dat de tasks gepost worden in zookeeper (via een hierarchie) en dat elke machine ook publiceert welke load er is. Je kan dan je algoritme hiervan gebruik laten maken van die informatie om tasks toe te wijzen. Ook als er machines uitvallen, kan je algoritme dit oppikken door tasks elders toe te wijzen.

Eens je dit hebt, wordt het een eenvoudiger scheduling probleem:
- input: jobs, resources, ...
- output: job allocation
(te vergelijken met een CPU scheduler: threads + CPUs + scheduling overhead -> thread allocation)

Dan moet jij in je algoritme enkel nog kiezen wat belangrijk is:
- zijn er priorities en/of deadlines mee gemoeid?
(wil je dus priority scheduling of iets als earliest-deadline-first, of een combinatie (bvb real-prio = base-prio + (max_prio-base_prio)*(deadline-now)
- wil je job-preemption (bvb low-prio laten pauseren en high-prio laten overnemen)?
- zijn er jobs die enkel op bepaalde machines uitgevoerd kunnen worden?

De setup kost zou ik gewoon tellen bij de kost van de job. Dus als je nu in setup1 staat en je hebt jobs voor setup1 en setup2, dan is de cost van setup2 20min hoger.

[Armageddon_2k]

Ik heb de wiki van Zookeeper even vlot doorgenomen.

Misschien even wat extra info ter verduidelijking:
-Het gaat om fysieke machines. Dus niet om servers waar software op draait.
-Centraal is er 1 software systeem dat invloed heeft om de machine een andere status te geven
-Het idee is dat het algoritme kiest in welke setup een machine moet gaan draaien.
-Het verdelen van de workload gaat al automatisch, zodra er 2 machines op Setup1 staan, wordt de load automatisch verdeeld.
-Prio is niet aan de orde.

Waar mijn uitdaging in zit: op welk moment is het rendabel om meerdere machines dezelfde config te laten draaien. en op wel moment kunnenn de machines beter een andere config draaien.

[H!GHGuY]

Als je echt geen enkele andere vereiste hebt (bvb deadlines) dan is het wat mij betreft simpel:

1) een machine blijft zolang mogelijk in een setup, dat is: tot alle jobs afgewerkt zijn, inclusief jobs die later bijkomen.
2) wanneer een machine klaar is, dan
-> filter je alle setups die door andere machines in gebruik zijn (bvb schrap setup2 als machine1 in setup2 staat)
-> sorteer je deze op totale job size (of beter: geschatte doorlooptijd voor alle jobs op de setup)
-> kies die met grootste kost

Dit heeft als gevolg:
- je beperkt het aantal switches tot een minimum
- doordat de grootste kost gekozen wordt, is de kans ook groter dat de batch nog kan groeien terwijl je bezig bent (en de efficientie dus nóg stijgt)

Volgens mij krijg je hierdoor ook de grootste aggregate throughput (want kleinste setup switch kost), maar een grotere latency voor job selectie en lagere individuele throughput (want geen load sharing).