Variabelen ?

Ik ben al een poosje van school en weet niet precies in welk categorie mijn probleem past.
Ik heb een verzameling van 600 applicaties die moeten worden verbouwd. Ik heb een verzameling van 400 applicatie profielen die allen deelverzamelingen zijn van de eerste verzameling. Het ene profiel bevat applicatie a, b,c. Het tweede profiel bevat applicatie b,c,d,e enzovoort. Niet alle profielen zijn even groot.
Tenslotte heb ik 6000 collega's die allemaal 1 profiel hebben toegewezen gekregen. Sommige profielen zijn toegewezen aan 500 collega's, andere maar aan 1 of 2.

Applicaties moeten worden verbouwd. Als iemand gebruik maakt van een profiel waarvan alle applicaties zijn verbouwd krijgt hij een nieuwe pc.
Nu de vraag: Hoe bepaal ik de volgorde van applicaties verbouwen als ik zo snel mogelijk de nieuwe pc's wil uit leveren ?

Paul K
Iets anders - donderdag 19 augustus 2004

Antwoord

dag Paul,

Hoewel deze site voornamelijk bedoeld is voor middelbare scholieren, en we ons niet graag wagen op het commerciële terrein, wil ik toch proberen om je vraag te beantwoorden.
Je zou je probleem kunnen formuleren als een lineair programmeringsprobleem (LP-probleem).
Ik ga uit van de veronderstelling dat elke verbouwing van een applicatie even lang duurt (een tijdssegment). Verder neem ik aan dat er maar één applicatie tegelijk verbouwd kan worden.
Ik nummer de profielen met index i, de applicaties met j en de tijdssegmenten met k.
Noem x_i het nummer van het tijdssegment waarop profiel nummer i helemaal klaar is.
Noem fp_i de frequentie van profiel nummer i (dus het aantal collega's met profiel i).
a_j,k is een 0,1-variabele, die gelijk is aan 1 als applicatie nummer j in tijdssegment k wordt verbouwd, en anders gelijk is aan 0.
De doelfunctie is nu:
minimaliseer åfp_i·x_i
De restricties zijn er nogal wat!
Voor profiel nummer i moeten voor elke applicatie j die in dit profiel zit 600 ongelijkheden opgesteld worden, namelijk:
x_i k·a_j,k (k=1..600)
Verder mag elk tijdssegment maar voor één applicatie gebruikt worden. Dit levert nog eens 2·600 vergelijkingen op, namelijk:
voor elke j geldt: å_ka_j,k = 1
voor elke k geldt: å_ja_j,k = 1
Ik heb geen idee of dit LP-probleem binnen haalbare tijd tot een oplossing komt.
In de praktijk zou ik eerder voor een pragmatische oplossing kiezen: zorg eerst dat de meestvoorkomende profielen helemaal omgebouwd worden.
Hopelijk heb je iets aan dit antwoord,
groet

dinsdag 24 augustus 2004

Re: Variabelen ?

©2001-2024 WisFaq