[Optimaliseringsprobleem] Ideale machine volgorde / From-To

[Oscar Mopperkont]

Beetje vreemde titel, maar ik zit in ieder geval met het volgende. Ik heb een set machines en een set artikelen. Elk artikel wordt op de machines bewerkt en kent zijn eigen volgorde waarin dat gebeurt. Overigens is het niet zo dat alle artikelen ook echt alle machines gebruiken, het kan wel.

Maar je hebt dus verkeer tussen de machines en dat kun je weergeven in een From-To matrix. Als ik bijvoorbeeld machine A,B,C en D heb dan kan dat er zo uitzien:

code:

   A  B  C  D
A  -  2  1  -
B  -  -  -  9
C  -  3  -  -
D  -  -  -  -

Nu wil ik de machines in zo'n volgorde zetten dat de stroom van artikelen zoveel mogelijk 1 kant opgaat. Als ik ze in de volgorde A-B-C-D zet dan is er een stroom van 12 in de volgorde en 3 tegen de stroom in. Verander ik de volgorde naar A-C-B-D dan is de gehele stroom van 15 in de volgorde. Als je het uittekent kun je dat snel zien, maar ook als je de from-to wijzigt naar die volgorde, want dan krijg je dit:

code:

   A  C  B  D
A  -  1  2  -
C  -  -  3  1
B  -  -  -  9
D  -  -  -  -

Alles staat dan rechtsboven als het ware (boven de denkbeeldige diagonaal van A-A naar D-D).

Waar ik nu naar op zoek ben is een methode om dit voor elke willekeurige from-to te kunnen optimaliseren. Ik had al zitten denken om per machine te berekenen wat de "netto-uitgaande" stroom is (dus hoeveel artikelen gaan er naar de machine - artikelen die vanaf die machine naar een andere machine gaan) en die dan te sorteren en aan de hand daarvan de volgorde te bepalen, maar dat leidt wel tot aardige resultaten, maar niet tot het optimum. Bij kleine matrixen zou je natuurlijk alle mogelijkheden kunnen nagaan, maar als het aantal machines een beetje groot wordt, dan wordt dat allemaal veel te traag. Dat beschouw ik dus niet als optie. Het lijkt mij dat hier wel een eenvoudig algoritme voor moet zijn die de boel in een ideale volgorde zet, maar ik kan het zo niet bedenken. Het is misschien wel een bekend probleem, maar ik zou niet weten hoe het dan heet. Als iemand de oplossing weet dan hoor ik dat graag

Mocht het allemaal nog niet duidelijk zijn dan moet je het ook even zeggen dan probeer ik het wat beter toe te lichten.

[MrBucket]

Je geeft in je verhaal zelf al aan dat je zo min mogelijk getallen onder de diagonaal a-a - d-d wilt zien. Alle mogelijke ordeningen bepalen van deze kolommen gaat inderdaad veel werk kosten (n! voor n kolommen), maar waarom niet beginnen met een configuratie waarin je de kolommen waarvan de getallen het meest onderin staan rechts plaatst, en de kolommen waar alleen maar getallen bovenin staan links. Dan moet je al een aardige configuratie hebben.

Daarna kan je, door elke keer de positie van twee kolommen te verwisselen, vanuit deze configuratie varieren om zo te proberen een betere configuratie te krijgen. Natuurlijk moet je dan alleen twee kolommen van positie verwisselen als tenminste 1 van beide getallen onder de diagonaal heeft liggen.

Trouwens, voor hoeveel kolommen moet je algoritme werken? 10? 30? 100?

[ Voor 5% gewijzigd door MrBucket op 18-08-2005 10:49 ]

[Oscar Mopperkont]

Een vrij goede oplossing is redelijk snel te vinden, maar het gaat mij echt om de beste oplossing. Wat ook een probleem is, is dat als je een kolom verwisselt dat de rijen ook verwisselen. Dus kolommen met veel getallen onderin naar rechts verplaatsen heeft ook meteen als effect dat de getallen niet meer onderin staan. Kijk maar in mijn voorbeeldje. Rij B is de rij met de meeste getallen onderin, toch is het niet ideaal om hem helemaal rechts te plaatsen.

De problemen die ik nu heb liggen in de orde van grootte van 30 machines. En bij elk probleem dat ik oplos moet ik het zo'n 150 keer doen. Maar het programma moet ook met grotere problemen kunnen werken. Aftellen wordt dus echt te langzaam.

[ Voor 21% gewijzigd door Oscar Mopperkont op 18-08-2005 10:55 ]

[Verwijderd]

Kun je het niet omschrijven naar een graaf-probleem en dan oplossen met Dijkstra's kortste pad algoritme? (of een ander kortste pad algoritme natuurlijk)

Bijvoorbeeld in je voorbeeld:

code:

   A  B  C  D
A  -  2  1  -
B  -  -  -  9
C  -  3  -  -
D  -  -  -  -

Je neemt A,B,C en D als knopen in je graaf. De afstand van A naar B is 2, dus kant (A,B) in de graaf heeft lengte 2 enz. Wanneer je nu met Dijkstra's kortste pad algorithme het korste pad van A naar D berekent heb je de volgorde met de minste 'stroming' in die richting. Dit is natuurlijk eenvoudig aan te passen voor de meeste 'stroming'.

Just a thought, geen idee of het in de praktijk goed werkt.