WisFaq!

Job-shop Scheduling

Beste WisFaq,

Ik ben bezig met het Job-Shop probleem. Dit is een probleem dat NP-hard is. Op internet vind ik veel programmeerwerk hierover, maar heel weinig dat duidelijk een algoritme geeft die dit probleem oplost.

Ik vind veel informatie over de "legendarische" 10x10 matrix.

Wanneer u niet weet wat het job-shop problem is leg ik u dit even uit a.d.h.v. 3x3 matrix:

Stel er zijn 3 machines en 3 jobs, Elke job heeft alle 3 de machines nodig om tot een product te komen. Echter, niet elke job heeft elke machine even lang nodig.

Job 1: (machine 1, 30 sec)(machine 2, 15 sec)(machine 3, 40 sec)
Job 2: (machine 1, 12 sec)(machine 3, 48 sec)(machine 2, 27 sec)
Job 3: (machine 3, 25 sec)(machine 2, 25 sec)(machine 1, 25 sec)

Nu is het natuurlijk zo dat een machine niet aan twee of meer jobs tegelijkertijd kan werken.

Er moet een algoritme zijn die een oplossing hiervoor vindt, zodanig dat de machines niet twee of meer jobs tegelijkertijd moeten werken. Echter staan deze algoritme op het internet in java,C++ taal, en niet in wiskundige of taal-beschrijvende vorm.

Kunt u wel zo'n algoritme geven?

Met vriendelijke groeten,

Wesly Dobbelsteyn

Wesly Dobbelsteyn
5-9-2004

Antwoord

Dit is een LP-probleem (Lineair programmeren). De onderstaande link gaat dieper op de materie in. Vanaf sheet 25 is bijvoorbeeld een oplossings-stategie te vinden.

Zie Volgorde bepalen [http://home.planet.nl/~weppn002/School/productielogistiekdeterminstischevolgordebepalingtbvstudenten.ppt ]

TvR
9-9-2004