Multi-project scheduling: The application of a decoupled schedule generation scheme and a game mechanic
Project management is geen spel. Of toch?
Wat hebben farmaceuticabedrijven, softwareontwikkelaars en aannemers met elkaar gemeen? Ze proberen unieke kwaliteitsvolle producten af te leveren: nieuwe geneesmiddelen, software of bouwwerken. Daarbij moeten ze voldoen aan strakke deadlines en binnen de perken van hun budget blijven. Er kan snel iets fout lopen waardoor het project bijvoorbeeld vertraging oploopt. Hoe vaak gebeurt het niet dat wegenwerken uitlopen of dat grote gebouwen later klaar zijn dan gepland?
De drievuldigheid
Om bedrijven te ondersteunen bij het beheersen van deze chaos doen wetenschappers onderzoek naar project management. Zij zien drie belangrijke gebieden waar de bedrijfswereld kan geholpen worden door de wetenschap. Het eerste is de planning, waarbij gepuzzeld wordt om alle taken van een project zo goed mogelijk op elkaar te laten volgen. Het tweede gebied is de risicoanalyse. Hier wordt onderzocht hoe bedrijven zich het beste kunnen wapenen tegen onverwachte problemen zoals slecht weer of machinedefecten. Bij de controle, het derde gebied, onderzoekt men hoe bedrijven het beste hun projecten opvolgen om binnen het budget te blijven en de deadlines te halen.
Mijn thesis focust zich op de planning. De uitdaging hier is dat een bedrijf maar een beperkt aantal ‘resources’ ter beschikking heeft. Dit kan alles zijn wat je nodig hebt om delen (of taken) van het project uit te voeren. Zo zijn bij een aannemer de belangrijkste resources de bouwvakkers en machines. Door hun beperkte beschikbaarheid duurt de uitvoering van projecten langer en wordt het moeilijk om alles af te werken voor de deadline. Als kers op de taart werkt men vaak aan meerdere projecten tegelijk en moet men beslissen hoe de resources onderling verdeeld worden. Een concreet voorbeeld: als een aannemer maar één graafmachine heeft, kan hij niet op twee werven graafwerken uitvoeren op hetzelfde moment. Dit kan voor vertragingen zorgen omdat een van de tweewerven moet wachten tot de graafmachine beschikbaar is. De coördinatie van de planning van meerdere projecten heet multi-project planning en is een relatief nieuw onderzoeksonderwerp binnen project management.
Kolonisten versus projectmanagers
In mijn scriptie benader ik multi-project planning vanuit een nieuwe invalshoek. Je zou het hele planningsproces kunnen zien als een groot gezelschapsspel met verschillende spelers. Elke projectverantwoordelijke probeert resources te krijgen van zijn baas om zijn taken zo snel mogelijk af te werken. De baas moet zorgen dat elke verantwoordelijke ongeveer gelijke kansen krijgt, zodat alle projecten van het bedrijf hun deadlines halen. Deze situatie lijkt hard op gezelschapsspellen zoals Kolonisten van Catan, waar spelers grondstoffen verdienen en die zo goed mogelijk proberen te investeren in nieuwe gebouwen.
In de thesis bouw ik een planningsmethode op uit spelelementen. Er zijn twee soorten spelers: de ‘bouwers’ (elk verantwoordelijk voor een project) en de ‘baas’ (verantwoordelijk voor de coördinatie). Zoals in Kolonisten van Catan kan een bouwer in elke ronde fictieve grondstoffen verdienen. Wanneer hij genoeg grondstoffen heeft verdiend, zal hij proberen een taak van zijn project toe te voegen aan de planning. Daarvoor betaalt hij grondstoffen aan de baas, die de taak inplant op het eerste tijdstip met genoeg beschikbare resources. Dat herhaalt zich tot de taken van elke bouwer zijn toegevoegd. Het eindresultaat is een volledige planning voor alle projecten.
De manier waarop de bouwers grondstoffen verdienen is gebaseerd op kansen. Dat betekent dat je in de ene beurt veel grondstoffen kan krijgen en in de volgende minder of zelfs helemaal niets. Door die kansen krijg je na elk spel een andere uitkomst. Als je het spel meerdere keren uitvoert, kan je de verschillende uitkomsten vergelijken en de beste planning selecteren.
Je zou dit spel echt kunnen spelen, maar in mijn scriptie doet de computer het zware werk. Dankzij de snelle rekenkracht kan het spel vaak gespeeld worden op korte tijd, in dit geval 25 keer in anderhalve seconde. De spelers volgen een geprogrammeerde logica bij het nemen van beslissingen. Zo moet een bouwer beslissen welke taken hij als eerste wil plannen en moet de baas kiezen aan welk project hij voorrang geeft en hoe hij grondstoffen uitdeelt. De logica voor deze beslissingen heeft invloed op hoe goed de uiteindelijke planning is. Bijvoorbeeld, als de baas voorrang geeft aan het project met de kortste duurtijd zal de duurtijd van de uiteindelijke multi-project planning ook korter zijn dan wanneer de baas voorrang geeft aan het project met de langste duurtijd.
De eindstand
Je weet pas hoe goed of slecht iets werkt wanneer je iets heb om mee te vergelijken. In dit geval gebruik ik enkele referentiemethodes die vaak in wetenschappelijke artikels voorkomen. Deze zijn op te splitsen in twee categorieën: simpele en complexere systemen. De tweede categorie vindt meestal betere oplossingen, maar heeft ook meer tijd nodig om die betere uitkomst te verkrijgen (ook wel rekentijd genoemd). Wanneer je methodes vergelijkt, moet je kijken naar de kwaliteit van hun oplossing en naar de rekentijd. De complexe methode haalt een verbetering van 27% tegenover de simpele methode, maar heeft wel 28 keer zo veel rekentijd nodig. De nieuwe methodiek uit mijn scriptie vindt een verbetering van 23% tegenover de simpele methode en doet er slechts 3 keer zo lang over. Met andere woorden, met een relatief kleine toename in rekentijd slaagt ze erin om vrij grote verbeteringen te behalen.
Een probleem benaderen vanuit een andere invalshoek kan leiden tot nieuwe oplossingen en inzichten. Dit was een eerste stap, maar er zijn mogelijkheden voor verder onderzoek. Kan je andere spelconcepten toepassen? Misschien kunnen de spelers geprogrammeerd worden om betere beslissingen te nemen? Hoe kan speltheorie betrokken worden om tot sterkere oplossingsmethodes te komen?
Door het toepassen van elementen uit gezelschapsspellen op multi-project planning is een nieuwe methode ontwikkeld die tot sterke resultaten leidt. Misschien gebruikt iemand ooit elementen uit project management om een nieuw gezelschapsspel te maken?
Agnetis, A., Briand, C., Billaut, J.-C., and Scha, P. (2015). Nash equilibria for the multi-agent project scheduling problem with controllable processing times. Journal of Scheduling, 18(1):15-27.
Bock, D. B. and Patterson, J. H. (1990). A comparison of due date setting, resource as-signment, and job preemption heuristics for the multiproject scheduling problem. Decision Sciences, 21(2):387-402.
Browning, T. R. and Yassine, A. A. (2010a). A random generator of resource-constrained multi-project network problems. Journal of scheduling, 13(2):143-161.
Browning, T. R. and Yassine, A. A. (2010b). Resource-constrained multi-project schedul-ing: Priority rule performance revisited. International Journal of Production Economics, 126(2):212-228.
Confessore, G., Giordani, S., and Rismondo, S. (2007). A market-based multi-agent sys-tem model for decentralized multi-project scheduling. Annals of Operations Research, 150(1):115-135.
Demeulemeester, E., Dodin, B., and Herroelen, W. (1993). A random activity network gen-erator. Operations Research, 41(5):972-980.
Demeulemeester, E., Vanhoucke, M., and Herroelen, W. (2003). Rangen: A random network generator for activity-on-the-node networks. Journal of scheduling, 6(1):17-38.
Dumond, J. (1992). In a multi-resource environment, how much is enough? THE INTER-NATIONAL JOURNAL OF PRODUCTION RESEARCH, 30(2):395-410.
Dumond, J. and Mabert, V. A. (1988). Evaluating project scheduling and due date assignment procedures: an experimental analysis. Management Science, 34(1):101-118.
Elmaghraby, S. E. (1977). Activity networks: Project planning and control by network models. Wiley New York.
Goncalves, J. F., Mendes, J. J., and Resende, M. G. (2008). A genetic algorithm for the resource constrained multi-project scheduling problem. European Journal of Operational Research, 189(3):1171-1190.
Homberger, J. (2007). A multi-agent system for the decentralized resource-constrained multi-project scheduling problem. International Transactions in Operational Research, 14(6):565-589.
Homberger, J. and Fink, A. (2017). Generic negotiation mechanisms with side payments{ design, analysis and application for decentralized resource-constrained multi-project scheduling problems. European Journal of Operational Research.
Knotts, G., Dror, M., and Hartman, B. C. (2000). Agent-based project scheduling. Iie Transactions, 32(5):387-401.
Kolisch, R. (1996a). Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management, 14(3):179-192.
Kolisch, R. (1996b). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2):320-333.
Kolisch, R. and Meyer, K. (2006). Selection and scheduling of pharmaceutical research projects. In Perspectives in Modern Project Scheduling, pages 321-344. Springer.
Kolisch, R., Schwindt, C., and Sprecher, A. (1998). Benchmark instances for project schedul-ing problems, 197-212.
Kolisch, R., Sprecher, A., and Drexl, A. (1995). Characterization and generation of a general class of resource-constrained project scheduling problems. Management science, 41(10):1693-1703.
Kumanan, S., Jose, G. J., and Raja, K. (2006). Multi-project scheduling using an heuristic and a genetic algorithm. The International Journal of Advanced Manufacturing Technology, 31(3-4):360-366.
Kurtulus, I. (1985). Multiproject scheduling: Analysis of scheduling strategies under unequal delay penalties. Journal of Operations Management, 5(3):291-307.
Kurtulus, I. and Davis, E. (1982). Multi-project scheduling: Categorization of heuristic rules performance. Management Science, 28(2):161-172.
Lawrence, S. R. and Morton, T. E. (1993). Resource-constrained multi-project scheduling with tardy costs: Comparing myopic, bottleneck, and resource pricing heuristics. European Journal of Operational Research, 64(2):168-187.
Lee, Y.-H., Kumara, S. R., and Chatterjee, K. (2003). Multiagent based dynamic resource scheduling for distributed multiple projects using a market mechanism. Journal of Intelli-gent Manufacturing, 14(5):471-484.
Lova, A., Maroto, C., and Tormos, P. (2000). A multicriteria heuristic method to improve resource allocation in multiproject scheduling. European Journal of Operational Research, 127(2):408-424.
Lova, A. and Tormos, P. (2001). Analysis of scheduling schemes and heuristic rules per-formance in resource-constrained multiproject scheduling. Annals of Operations Research, 102(1-4):263-286.
Mastor, A. A. (1970). An experimental investigation and comparative evaluation of produc-tion line balancing techniques. Management Science, 16(11):728-746.
Shtub, A., LeBlanc, L. J., and Cai, Z. (1996). Scheduling programs with repetitive projects: a comparison of a simulated annealing, a genetic and a pair-wise swap algorithm. European Journal of Operational Research, 88(1):124-138.
Tsubakitani, S. and Deckro, R. F. (1990). A heuristic for multi-project scheduling with limited resources in the housing industry. European Journal of Operational Research, 49(1):80-91.
Vanhoucke, M., Coelho, J., Debels, D., Maenhout, B., and Tavares, L. V. (2008). An evaluation of the adequacy of project network generators with systematically sampled networks. European Journal of Operational Research, 187(2):511-524.