×

Maximising the weighted number of activity execution modes in project planning. (English) Zbl 1403.90308

Summary: In multimode resource-constrained project scheduling, activity modes are selected and activity start times are determined to minimise the project makespan subject to resource constraints. When disruptions occur during project execution delays to project activities may ensue. Therefore, the a priori selected modes restrict the options to adapt the project schedule given the deadline. During the project scheduling phase, information on the best execution mode to include in the baseline schedule for each activity is usually not available. Scheduling these projects requires decisions on the modes to incorporate in the solution to maximise the flexibility during project execution and to postpone the decision on how to implement the activity until more information is available. In this paper, we study a project scheduling problem with multiple execution alternatives. Our objective is to maximise the weighted number of alternative activity execution modes in the project solution under three different assumptions. The research is motivated by real-life project scheduling applications, where the activities to be planned are known in advance, but the execution of these activities is subject to uncertainty. We present a problem description and three mathematical formulations. Additionally, computational results on the efficiency of the formulations and the increased flexibility are reported.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming

Software:

Gurobi; PSPLIB
Full Text: DOI

References:

[1] Abernathy, W. J.; Rosenbloom, R. S., Parallel strategies in development projects, Management Science, 15, 10, B486-B505, (1969)
[2] Akkan, C.; Drexl, A.; Kimms, A., Network decomposition-based benchmark results for the discrete time-cost tradeoff problem, European Journal of Operational Research, 165, 339-358, (2005) · Zbl 1066.90021
[3] Artigues, C.; Billaut, J. C.; Esswein, C., Maximization of solution flexibility for robust shop scheduling, European Journal Of Operational Research, 165, 314-328, (2005) · Zbl 1066.90022
[4] Artigues, C.; Koné, O.; Lopez, P.; Mongeau, M., Handbook on project management and scheduling vol.1, Mixed-integer linear programming formulations, 17-41, (2015), Springer International Publishing
[5] Bard; Jonathan, F., Parallel funding of r& d tasks with probabilistic outcomes, Management Science, 31, 7, 814-828, (1985)
[6] Beck, C. J.; Fox, M., Constraint-directed techniques for scheduling alternative activities, Artificial Intelligence, 121, 211-250, (2000) · Zbl 0948.68009
[7] Bianco, L.; Caramia, M., A new formulation for the project scheduling problem under limited resources, Flexible Service Manufacturing Journal, 25, 6-24, (2013)
[8] Boctor, F., Heuristics for scheduling projects with resource restrictions and several resource-duration modes, International Journal of Production Research, 31, 2547-2558, (1993)
[9] Boctor, F., A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes, European Journal of Operational Research, 90, 349-361, (1996) · Zbl 0916.90143
[10] Brucker, P.; Drexl, A.; Möhring, R.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: notation, classification, models, and methods, European Journal of Operational Research, 112, 3-41, (1999) · Zbl 0937.90030
[11] Brucker, P.; Knust, S., A linear programming and constraint propagation-based lower bound for the RCPSP, European Journal of Operational Research, 127, 355-362, (2000) · Zbl 0990.90055
[12] Budai, G.; Huisman, D.; Dekker, R., Scheduling preventive railway maintenance activities, The Journal of the Operational Research Society, 57, 9, 1035-1044, (2006) · Zbl 1171.90392
[13] Capacho, L.; Pastor, R.; Dolgui, A.; Guschinskaya, O., An evaluation of constructive heuristic methods for solving the alternative subgraphs assembly line balancing problem, Journal of Heuristics, 15, 109-132, (2009) · Zbl 1172.90377
[14] Čapek, R.; Šůcha, P.; Hanzálek, Z., Production scheduling with alternative process plans, European Journal of Operational Research, 217, 300-311, (2012) · Zbl 1244.90090
[15] Creemers, S.; De Reyck, B.; Leus, R., Project planning with alternative technologies in uncertain environments, European Journal Of Operational Research, 242, 465-476, (2015) · Zbl 1341.90066
[16] Deblaere, F.; Demeulemeester, E.; Herroelen, W., Proactive policies for the stochastic resource-constrained project scheduling problem, European Journal of Operational Research, 214, 308-316, (2011) · Zbl 1218.90082
[17] Deblaere, F.; Demeulemeester, E.; Herroelen, W.; Van de Vonder, S., Robust resource allocation decisions in resource-constrained projects, Decision Sciences, 38, 1, 5-37, (2007)
[18] Demeulemeester, E., & Herroelen, W. (2002). Project scheduling: A research handbook. Kluwer Academic Publishers.; Demeulemeester, E., & Herroelen, W. (2002). Project scheduling: A research handbook. Kluwer Academic Publishers. · Zbl 1059.90068
[19] Ding, M.; Eliashberg, J., Structuring the new product development pipeline, Management Science, 48, 3, 343-363, (2002)
[20] Gurobi Optimization, I. (2015). Gurobi optimizer reference manual. http://www.gurobi.com; Gurobi Optimization, I. (2015). Gurobi optimizer reference manual. http://www.gurobi.com
[21] Hartmann, S.; Briskorn, D., A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207, 1-15, (2010) · Zbl 1205.90123
[22] Herroelen, W.; De Reyck, B.; Demeulemeester, E., Resource-constrained project scheduling: A survey of recent developments, Computers & Operations Research, 25, 279-302, (1998) · Zbl 1040.90525
[23] Herroelen, W.; Leus, R., Project scheduling under uncertainty: survey and research potentials, European Journal of Operational Research, 165, 289-306, (2005) · Zbl 1066.90050
[24] Jehle, G., & Reny, P. (2011). Advanced microeconomic theory. Financial Times/Prentice Hall.; Jehle, G., & Reny, P. (2011). Advanced microeconomic theory. Financial Times/Prentice Hall.
[25] Kellenbrink, C.; Helber, S., Scheduling resource-constrained projects with a flexible project structure, European Journal Of Operational Research, 246, 379-391, (2015) · Zbl 1346.90356
[26] Kis, T., Job-shop scheduling with processing alternatives, European Journal Of Operational Research, 2003, 151, 307-332, (2005) · Zbl 1052.90033
[27] Klein, R., Scheduling of rresource-constrained projects, (2000), Springer · Zbl 0949.90042
[28] Kolisch, R.; Drexl, A., Local search for nonpreemptive multi-mode resource-constrained project scheduling, IIE Transactions, 29, 987-999, (1997)
[29] Kolisch, R.; Padman, R., An integrated survey of deterministic project scheduling, Omega The International Journal of Management Science, 29, 3, 249-272, (2001)
[30] Kolisch, R.; Sprecher, A., PSPLIB - A project scheduling problem library, European Journal of Operational Research, 96, 205-216, (1996) · Zbl 0947.90587
[31] Koné, O.; Artigues, C.; Lopez, P.; Mongeau, M., Event-based MILP models for resource-constrained project scheduling problems, Computers & Operations Research, 38, 3-13, (2011) · Zbl 1231.90202
[32] Kuster, J.; Jannach, D.; Friedrich, G., Applying local rescheduling in response to schedule disruptions, Annals of Operations Research, 180, 265-282, (2010) · Zbl 1202.90136
[33] Loch, C. H.; Terwiesch, C.; Thomke, S., Parallel and sequential testing of design alternatives, Management Science, 47, 5, 663-678, (2001)
[34] Naber, A.; Kolisch, R., Mip models for resource-constrained project scheduling with flexible resource profiles, European Journal of Operational Research, 239, 335-348, (2014) · Zbl 1339.90249
[35] Nelson, R. G.; Azaron, A.; Aref, S., The use of a GERT based method to model concurrent product development processes, European Journal of Operational Research, 250, 2, 566-578, (2016)
[36] Neumann, K., Project scheduling: recent models, algorithms and applications, Scheduling of projects with stochastic evolution structure, 309-332, (1999), Springer US Boston, MA
[37] Pich, M. T.; Loch, C. H.; de Meyer, A., On uncertainty, ambiguity, and complexity in project management, Management Science, 48, 8, 1008-1023, (2002) · Zbl 1232.90216
[38] Pritsker, A., Gert: graphical evaluation and review technique, (1966), Santa Monica, CA: RAND Corporation
[39] Salewski, F.; Schirmer, A.; Drexl, A., Project scheduling under resource and mode identity constraints: model, complexity, methods and application, European Journal of Operational Research, 102, 88-110, (1997) · Zbl 0948.90060
[40] Schrage, L., Solving resource-constrained network problems by implicit enumeration - nonpreemptive case, Operations Research, 18, 2, 263-278, (1970) · Zbl 0197.46005
[41] Sprecher, A.; Hartmann, S.; Drexl, A., An exact algorithm for project scheduling with multiple modes, OR Sprektrum, 19, 195-203, (1997) · Zbl 0885.90059
[42] Talbot, F., Resource-constrained project scheduling problem with time-resource trade-offs: the nonpreemptive case, Management Science, 28, 1197-1210, (1982) · Zbl 0493.90042
[43] Vansteenwegen, P.; Dewilde, T.; Burggraeve, S.; Cattrysse, D., An iterative approach for reducing the impact of infrastructure maintenance on the performance of railway systems, European Journal Of Operational Research, 252, 39-53, (2016) · Zbl 1346.90185
[44] Weglarz, J.; Józefowska, J.; Mika, M.; Waligóra, G., Project scheduling with finite or infinite number of activity processing modes - A survey, European Journal of Operational Research, 208, 177-205, (2011) · Zbl 1208.90082
[45] Weitzman, M. L., Optimal search for the best alternative, Econometrica, 47, 3, 641-654, (1979) · Zbl 0426.90017
[46] Zhu, G.; Bard, J.; Yu, G., Disruption management for resource-constrained project scheduling, Journal of the Operational Research Society, 56, 365-381, (2005) · Zbl 1104.90025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.