(530g) A Computational Comparison of New Models for the Multi-Mode Resource Constrained Project Scheduling Problem with Optional Activities

Project scheduling is a fundamental component of project management. However, the often large number of activities to be performed over long horizons, in conjunction with complicating constraints and sometimes conflicting objectives can pose serious challenges to obtaining optimal project scheduling solutions [1]. As a result, the multiple variants of the resource constrained project scheduling problem (RCPSP) have been a very active topic of research with a wide variety of proposed solution approaches that involve mathematical optimization, constraint programming, propositional satisfiability algorithms, and heuristic based methods [2].

The original RCPSP problem involves a set of activities that are represented via a directed graph. These activities have to be executed exactly once throughout the given horizon, while not exceeding the available resources and while not violating the prescribed precedence between them. The typical objective of this problem is to minimize the total makespan. An extension of the RCPSP is the Multi-mode RCPSP (MMRCPSP) [3], where activities are allowed to be executed in one out of multiple available modes, where each mode can have a different set of characteristics (such as duration, resource consumption, cost of execution).

While both of the aforementioned variants have illustrated proven modelling flexibility for a wide range of problems, they do rely on the fact that the directed graph of activities is fixed and is not part of the decision making. This is an assumption that can be rather limiting in environments where a decision may lead to different sets of tasks that have to be executed, or in cases where one may select to execute an optional activity that can lead to higher profit in the future.

To that end, we propose an extension to the original MMRCPSP to allow for the execution of optional activities with the use of propositional logic. To solve the MMRCPSP with optional activities to optimality, we will present a set of new Mixed Integer Linear Optimization models, and we will further extend existing MMRCPSP models [4,5,6] to handle optional tasks. Since the above models address generalizations to the RCPSP and plain MMRCPSP variants, we will conduct a comprehensive computational study across the models to compare their performance using both established RCPSP & MMRCPSP benchmarks from the PSPLIB [7], as well as synthetic benchmarks with optional activities. Finally, preprocessing and fine-tuning approaches will be presented that can further improve the computational performance of the newly introduced models.

References:

[1] J. Weglarz, "On certain models of resource allocation problems.", Kybernetes, vol. 9(1), pp. 61-66, 1980.

[2] C. Schwindt and J. Zimmermann, Handbook on Project Management and Scheduling Vol. 1., Springer International Publishing, 2015.

[3] F. B. Talbot, "Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case.", Management science, vol. 28(10), pp. 1197-1210, 1982.

[4] O. Koné, C. Artigues, P. Lopez, and M. Mongeau, "Event-based MILP models for resource-constrained project scheduling problems.", Computers & Operations Research, vol. 38(1), pp. 3-13, 2011.

[5] T. S. Kyriakidis, G. M. Kopanos, and M. C. Georgiadis, "MILP formulations for single-and multi-mode resource-constrained project scheduling problems.", Computers & Chemical Engineering, vol. 36, pp. 369-385, 2012.

[6] R. K. Chakrabortty, R. A. Sarker, and D. L. Essam, "Event based approaches for solving multi-mode resource constraints project scheduling problem.", Proceedings of IFIP International Conference on Computer Information Systems and Industrial Management, Springer, pp. 375-386. 2014.

[7] R. Kolisch and A. Sprecher, "PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program.", European Journal of Operational Research, vol. 96(1), pp. 205-216, 1997.