Planning met open source software

Veel bedrijven laten geld liggen als de planning niet optimaal is. Vaak is men al tevreden áls er een planning is, al dan niet uit een ERP systeem of in Excel opgesteld. Met vrij verkrijgbare software kan men echter de planning eenvoudig optimaliseren.

Open source software is vrij verkrijgbare software waarvan de broncode is vrijgegeven en die voor iedereen beschikbaar is. Vaak is dergelijke software volledig gratis te gebruiken, ook in het bedrijfsleven.

Lineaire programmering

Er is veel open source software die gebruikt kan worden voor vele doeleinden, bijvoorbeeld het optimaliseren van de planning. Met een voorbeeld gaan we dit laten zien. We gebruiken daarbij de wiskundige techniek Lineair Programmeren (LP).

Het “lineair” slaat er op dat de wiskundige vergelijkingen lineair geformuleerd zijn, oftewel “rechte lijnen”. Met andere woorden, er komen geen kwadratische of exponentiële waarden voor.

Voor wie direct zelf aan de gang wil gaan: de software die we hier gebruiken is GUSEK, een gebruiksvriendelijk interface met de GLPK optimalisatie software. Dit programma is open source en kan vrij worden gedownload en geïnstalleerd vanaf: http://gusek.sourceforge.net/

Eenvoudig voorbeeld

We houden het eenvoudig: een bedrijf maakt twee producten. De beide producten worden gemaakt uit twee materialen, maar in verschillende hoeveelheden. Om de producten te maken zijn drie bewerkingen nodig, maar met verschillende bewerkingstijden.

Beide producten hebben een verschillende opbrengst. Het bedrijf kan echter geen voorraad aanhouden. De mogelijke afzet van beide producten kent echter wel een maximum. De planning moet aangeven hoeveel producten er gemaakt moeten worden om de omzet te maximaliseren.

Product 1 Product 2
Opbrengst per stuk 12 8
Maximale afzet (stuks) 100 300
Materiaal 1 (stuks) 8 2
Materiaal 2 (stuks) 2 1
Bewerking 1 (tijd) 10 min 25 min
Bewerking 2 (tijd) 25 min 25 min
Bewerking 3 (tijd) 50 min 15 min

Van beide materialen zijn 400 stuks voorhanden en de capaciteit van beide bewerkingen is 40 uur.

Wiskundige formulering

De eerste stap is om de situatie te vertalen naar wiskundige vergelijkingen. Wat hierboven staat beschreven, wordt in formules uitgewerkt, te beginnen met de doelfunctie. Met andere woorden: wat willen we bereiken?

Beslissingsvariabelen
Daarvoor hebben we allereerst twee waarden nodig, die nu nog onbekend zijn, maar die onze planning bepalen. Wat willen we berekenen? Onze beslissingsvariabelen zijn de hoeveelheden van de twee producten die we gaan produceren.

We noemen we p1 en p2, zijnde het aantal dat we van beide producten gaan maken:

p1 = het aantal stuks product 1 dat geproduceerd wordt
p2 = het aantal stuks product 2 dat geproduceerd wordt

Vergelijk dit ook met een spreadsheet. Je kunt verwijzen naar een bepaalde waarde met verwijzingen. Bijvoorbeeld de formule “A1+B1” betekent: tel de waarden van cel A1 en B1 op. In dit geval hebben we dus p1 en p2, de hoeveelheden van product 1 en product 2.

Met deze twee variabelen kunnen we de doelfunctie en de restricties in formules uitdrukken.

Doelfunctie
Beide producten hebben verschillende opbrengsten. Als we p1 stuks maken, levert dat 12 p1 euro op. De de productie van product 2 levert 8 p2 euro op. En die opbrengst willen we maximaliseren. Kort gezegd willen we:

Maximaliseer: 12 p1 + 8 p2

Restricties
Dan de restricties, dat zijn de beperkingen voor de planning. Als er geen beperkingen waren, zouden de opbrengsten onbeperkt kunnen zijn. Doordat er nu eenmaal beperkingen zijn in vrijwel iedere planning, kunnen we geen oneindige opbrengsten behalen. De restricties bepalen wat er maximaal mogelijk is. En naar dat maximum zijn we op zoek.

Afzet
De maximale afzet voor product 1 is 100 stuks en voor product 2 300 stuks. Oftewel: p1 moet kleiner of gelijk zijn aan 100, en p2 moet kleiner of gelijk zijn aan 300. Het kleiner of gelijk teken is hier “<=”. Dit laat zich vertalen in de volgende twee regels:

Max afzet product 1: p1 <= 100
Max afzet product 2: p2 <= 300

Materialen
Vervolgens de beperkte beschikbaarheid van de materialen. Ieder product heeft zijn eigen mix. Voor elk product 1 heb je 8 stuks van materiaal 1 nodig en 2 stuks van materiaal 2. Voor elk product 2 heb je 2 stuks van materiaal 1 nodig en 1 stuks materiaal 2. Voor beide materialen zijn 400 stuks beschikbaar. De restricties zijn dan als volgt:

Beschikbaar materiaal 1: 8 p1 + 2 p2 <= 400 
Beschikbaar materiaal 2: 2 p1 + 1 p2 <= 400

Bewerkingen
De beiden producten ondergaan drie bewerkingen, maar met verschillende tijden. De maximale capaciteit van iedere bewerking is bekend, 40 uur oftewel: 60x 40 = 2.400 minuten.

Bewerking 1: 10 p1 + 25 p2 <= 2400 
Bewerking 2: 25 p1 + 25 p2 <= 2400 
Bewerking 3: 50 p1 + 15 p2 <= 2400

Optimalisatie

Nu de wiskundige formulering compleet is, gebruiken we het eerder genoemde programma om de oplossing te laten berekenen. De berekeningen die nodig zijn, worden al jaren verbeterd door de slimste wiskundigen en van die kennis maken wij gebruik.

Invoeren
Als het programma GUSEK is opgestart, kunnen we de wiskundige formulering invoeren aan de linkerzijde:

Maximize 
12 p1 + 8 p2

Subject To 
p1 <= 100 
p2 <= 300   

8 p1 + 2 p2 <= 400 
2 p1 + p2 <= 400

10 p1 + 25 p2 <= 2400 
25 p1 + 25 p2 <= 2400 
50 p1 + 15 p2 <= 2400

End

Je kunt deze wiskundige formulering ook opslaan als een bestand in het programma, om het later opnieuw te gebruiken.

Berekenen
Zorg dat de optie Tools > Generate Output is aangevinkt, zodat je de complete rapportage krijgt. Ook moet de juiste taal zijn geselecteerd: Language > CPLEX LP.

Met F5 of Tools > Go worden de berekeningen gestart. Bij complexere problemen kan je de voortgang aan de rechterzijde volgen. Als de optimale oplossing is gevonden, wordt dat ook daar gemeld.

Uitkomsten
De resultaten worden nu getoond aan de linkerzijde waar een nieuw tabblad is geopend. De doelfunctie (objective) heeft een maximum van afgerond 878. De waarden voor p1 en p2 zijn afgerond 27 en 69.

Oftewel: de maximaal haalbare opbrengst is 878 en deze wordt bereikt door het produceren van 27 stuks van product 1 en 69 stuks van product 2. Dit is waar we naar op zoek waren.

Beperkingen
Ook is te zien dat de restricties voor bewerking 2 en 3 de grootste beperkingen zijn. Deze restricties worden ten volle benut, de activity is gelijk aan de upperbound van 2400 minuten.

In de kolom marginal staan de schaduwprijzen, de marginale kosten van de restricties. Die zijn te lezen als de extra opbrengst die te behalen is, als de restrictie met één eenheid wordt verhoogd. Oftewel: als je één extra minuut zou kunnen produceren op bewerking 3 dan zou dat een extra opbrengst genereren van 0,11.

De schaduwprijzen zijn een interessante bron van informatie. Vooral als een bedrijf op zoek is naar de bottleneck van de productie en de kosten die daarmee gemoeid zijn. Door de processen op deze wijze te modelleren worden de beperkingen duidelijk en in getallen uitgedrukt.