Developing a new model for simultaneous scheduling of two grand projects based on game theory and solving the model with Benders decomposition

Abstract

Grand infrastructure projects, such as dam, power plant, petroleum, and gas industry projects, have several contractors working on them in several independent sub-projects. The concern of reducing the duration of these projects is one of the important issues among various aspects; thus, our aim is to fulfill the requirements by using the game theory approach. In this study, a mixed-integer programming model consisting of game theory and project scheduling is developed to reduce the duration of projects with a minimum increase in costs. In this model, two contractors in successive periods are entered into a step-by-step competition by the employer during dynamic games, considering an exchange in their limited resources. The optimum solution of the game in each stage are selected as the strategy, and the resources during the game are considered to be renewable and limited. The strategy of each contractor can be described as follows: 1) share their resources with the other contractor and 2) not share the resources with the other contractor. This model can act dynamically in all circumstances during project implementation. If a player chooses a non-optimum strategy, then this strategy can immediately update itself at the succeeding time period. The proposed model is solved using the exact Benders decomposition method, which is coded in GAMS software. The results suggest the implementation of four step-by-step games between the contractors. Then, the results of our model are compared with those of the conventional models. The projects’ duration in our model is reduced by 22.2%. The nominal revenue of both contractors has also reached a significant value of 46078 units compared with the relative value of zero units in the original model. Moreover, we observed in both projects the decreases of 19.5%, 20.9%, and 19.7% in the total stagnation of resources of types 1, 2, and 3, respectively.

Graphical abstract

Keywords

project scheduling / resource leveling between projects / constrained resources / game theory / Benders decomposition

References

[1] Avni G, Tamir T (2016). Cost-sharing scheduling games on restricted unrelated machines. Theoretical Computer Science, 646: 26–39

[2] Baptiste P, Le Pape C, Nuijten W (1999). Satisfiability tests and time-bound adjustments for cumulative scheduling problems. Annals of Operations Research, 92: 305–333

[3] Barough A S, Shoubi M V, Skardi M J E (2012). Application of game theory approach in solving the construction project conflicts. Procedia: Social and Behavioral Sciences, 58: 1586–1593

[4] Beşikci U, Bilge Ü, Ulusoy G (2015). Multi-mode resource constrained multi-project scheduling and resource portfolio problem. European Journal of Operational Research, 240(1): 22–31

[5] Briand C, Billaut J C (2011). Cooperative project scheduling with controllable processing times: A game theory framework. In: 16th Conference on Emerging Technologies & Factory Automation (ETFA). Toulouse: IEEE,1–7

[6] Browning T R, Yassine A A (2010). Resource-constrained multi-project scheduling: Priority rule performance revisited. International Journal of Production Economics, 126(2): 212–228

[7] Brucker P, Drexl A, Möhring R, Neumann K, Pesch E (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1): 3–41

[8] Calhoun K M, Deckro R F, Moore J T, Chrissis J W, Van Hove J C (2002). Planning and re-planning in project and production scheduling. Omega, 30(3): 155–170

[9] Cavalcante C C B, Carvalho de Souza C, Savelsbergh M W P, Wang Y, Wolsey L A (2001). Scheduling projects with labor constraints. Discrete Applied Mathematics, 112(1–3): 27–52

[10] Chen J, Askin R G (2009). Project selection, scheduling and resource allocation with time dependent returns. European Journal of Operational Research, 193(1): 23–34

[11] Chu Y, You F (2013). Integrated scheduling and dynamic optimization of complex batch processes with general network structure using a generalized Benders decomposition approach. Industrial & Engineering Chemistry Research, 52(23): 7867–7885

[12] Confessore G, Giordani S, Rismondo S (2007). A market-based multi-agent system model for decentralized multi-project scheduling. Annals of Operations Research, 150(1): 115–135

[13] Drezet L E, Billaut J C (2008). A project scheduling problem with labour constraints and time-dependent activities requirements. International Journal of Production Economics, 112(1): 217–225

[14] Etgar R (1999). Scheduling project activities to maximize the net present value the case of linear time-dependent cash flows. International Journal of Production Research, 37(2): 329–339

[15] Ghoddousi P, Eshtehardian E, Jooybanpour S, Javanmardi A (2013). Multi-mode resource-constrained discrete time–cost-resource optimization in project scheduling using non-dominated sorting genetic algorithm. Automation in Construction, 30: 216–227

[16] Hartmann S (1999). Project Scheduling under Limited Resources: Models, Methods, and Applications, vol. 478. Berlin: Springer

[17] Herroelen W S (2005). Project scheduling: Theory and practice. Production and Operations Management, 14(4): 413–432

[18] Icmeli O, Erenguc S S (1994). A tabu search procedure for the resource constrained project scheduling problem with discounted cash flows. Computers & Operations Research, 21(8): 841–853

[19] Kis T (2005). A branch-and-cut algorithm for scheduling of projects with variable-intensity activities. Mathematical Programming, 103(3): 515–539

[20] Kis T (2006). RCPs with variable intensity activities and feeding precedence constraints. In: Józefowska J, Weglarz J, eds. Perspectives in Modern Project Scheduling. Boston, Springer, 105–129

[21] Klein R, Scholl A (1998). Scattered branch and bound: An adaptive search strategy applied to resource-constrained project scheduling. Publications of Darmstadt Technical University, Institute for Business Studies (BWL), 14076

[22] Klein R, Scholl A (2000). PROGRESS: Optimally solving the generalized resource constrained project scheduling problem. Mathematical Methods of Operations Research, 52(3): 467–488

[23] Kolisch R, Meyer K (2006). Selection and scheduling of pharmaceutical research projects. In: Jozefowska J, Weglarz J, eds. Perspectives in Modern Project Scheduling. Boston, Springer, 321–344

[24] Li H (2015). Benders decomposition approach for project scheduling with multi-purpose resources. In: Schwindt C, Zimmermann J, eds. Handbook on Project Management and Scheduling. Springer, 1: 587–601

[25] Makui A, Heydari M, Aazami A, Dehghani E (2016). Accelerating Benders decomposition approach for robust aggregate production planning of products with a very limited expiration date. Computers & Industrial Engineering, 100: 34–51

[26] Naber A, Kolisch R (2014). MIP models for resource-constrained project scheduling with flexible resource profiles. European Journal of Operational Research, 239(2): 335–348

[27] Neumann K, Zimmermann J (2000). Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints. European Journal of Operational Research, 127(2): 425–443

[28] Perez-Gonzalez P, Framinan J M (2014). A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems. European Journal of Operational Research, 235(1): 1–16

[29] Pritsker A A B, Waiters L J, Wolfe P M (1969). Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 16(1): 93–108

[30] Russell R A (1986). A comparison of heuristics for scheduling projects with cash flows and resource restrictions. Management Science, 32(10): 1291–1300

[31] Shariatmadari M, Nahavandi N, Zegordi S H, Sobhiyah M H (2017). Integrated resource management for simultaneous project selection and scheduling. Computers & Industrial Engineering, 109: 39–47

[32] Takano Y, Ishii N, Muraki M (2017). Multi-period resource allocation for estimating project costs in competitive bidding. Central European Journal of Operations Research, 25(2): 303–323

[33] Van de Vonder S, Demeulemeester E L, Herroelen W S (2007). A classification of predictive-reactive project scheduling procedures. Journal of Scheduling, 10(3): 195–207

[34] Vanhoucke M, Demeulemeester E L, Herroelen W S (2001). An exact procedure for the resource-constrained weighted earliness-tardiness project scheduling problem. Annals of Operations Research, 102(1/4): 179–196

[35] Wang J, Wei W, Ding L, Li J (2017a). Method for analyzing the knowledge collaboration effect of R&D project teams based on Bloom’s taxonomy. Computers & Industrial Engineering, 103: 158–167

[36] Wang Y, He Z, Kerkhove L P, Vanhoucke M (2017b). On the performance of priority rules for the stochastic resource constrained multi-project scheduling problem. Computers & Industrial Engineering, 114: 223–234

RIGHTS & PERMISSIONS

Higher Education Press