##
**Simplifying activity networks under generalized precedence relations to extended CPM networks.**
*(English)*
Zbl 1348.90163

Summary: The critical path method (CPM) is a network planning technology with a simple and intuitive representation. However, it can only represent a special precedence relation – the finish-to-start minimum time lag. Currently, generalized precedence relations (GPRs) are represented by complex activity networks. We simplify complex activity networks under GPRs by representing the GPRs in a new way. This new extended CPM network is similar to the standard CPM network with the exception that arcs may have negative lengths and cycles. The extended CPM network facilitates problems with GPRs. Although many current models and algorithms are advanced and efficient for the CPM network problem, they are difficult or impossible to improve for GPRs applications. The extended CPM network, however, combats these problems and serves as an illustration of resource leveling with activity splitting. The current 0-1 binary model formulation for the resource leveling with just finish-to-start minimum time lags is also applied to the problem with GPRs using the extended CPM network.

### MSC:

90B10 | Deterministic network models in operations research |

90C35 | Programming involving graphs or networks |

### Keywords:

network planning; simplification; generalized precedence relations; CPM network; resource leveling
PDFBibTeX
XMLCite

\textit{Z.-X. Su} et al., Int. Trans. Oper. Res. 23, No. 6, 1141--1161 (2016; Zbl 1348.90163)

Full Text:
DOI

### References:

[1] | Atilla, D., David, A., Gul, P., 2013. Resource leveling in line‐of‐balance scheduling. Computer‐Aided Civil and Infrastructure Engineering28, 9, 679-692. |

[2] | Bianco, L., Caramia, M., 2011. A new formulation of the resource‐unconstrained project scheduling problem with generalized precedence relations to minimize the completion time. Networks56, 4, 263-271. · Zbl 1202.90123 |

[3] | Bianco, L., Caramia, M., 2011. A new lower bound for the resource‐constrained project scheduling problem with generalized precedence relations. Computers and Operations Research38, 1, 14-20. · Zbl 1231.90177 |

[4] | Brinkmann, K., Neumann, K., 1996. Heuristic procedures for resource‐constrained project scheduling with minimal and maximal time lags: the resource‐levelling and minimum project‐duration problems. Journal of Decision Systems5, 1-2, 129-155. |

[5] | Chanas, S., Zielinski, P., 2002. The computational complexity of the criticality problems in a network with interval activity times. European Journal of Operational Research136, 3, 541-550. · Zbl 1008.90029 |

[6] | Chassiakos, A. P., Sakellaropoulos, S., 2005. Time‐cost optimization of construction projects with generalized activity constraints. Journal of Construction Engineering and Management131, 10, 1115-1124. |

[7] | DeRecyck, B., Herroelen, W., 1998. A branch‐and‐bound procedure for the resource‐constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research111, 152-174. · Zbl 0948.90077 |

[8] | Dubois, D., Fargier, H., Fortin, J., 2005. Computational methods for determining the latest starting times and floats of tasks in interval‐valued activity networks. Journal of Intelligent Manufacturing16, 4-5, 407-421. |

[9] | Elmaghraby, S.E., 1964. An algebra for the analysis of generalized activity networks. Management Science10, 494-514. |

[10] | Elmaghraby, S.E., Kamburowski, J., 1989. The analysis of activity networks under generalized precedence relations (GPRs), Parts I and II. Report in NC State University, Raleigh, pp. 27695-27913. |

[11] | Elmaghraby, S.E., Kamburowski, J., 1992. The analysis of activity networks under generalized precedence relations (GPRs). Management Science38, 9, 1245-1263. · Zbl 0758.90044 |

[12] | Georgy, M.E., 2008. Evolutionary resource scheduler for linear projects. Automation in Construction17, 5, 573-583. |

[13] | Hariga, M., El‐Sayegh, S.M., 2011. Cost optimization model for the multiresource leveling problem with allowed activity splitting. Journal of Construction Engineering and Management137, 1, 56-64. |

[14] | Kallantzis, A., Soldatos, J., Lambropoulos, S., 2007. Linear versus network scheduling: a critical path comparison. Journal of Construction Engineering and Management133, 7, 483-491. |

[15] | Kamburowski, J., Michael, D.J., Stallmann, M.F.M., 2000. Minimizing the complexity of an activity network. Networks36, 1, 47-52. · Zbl 0969.90017 |

[16] | Kelley, J.E., Walker, M.R., 1959. Critical‐path planning and scheduling. Ambler: Proceedings of Eastern Joint IRE‐ACM Computer Conference, pp. 160-173. |

[17] | Kerbosch, J.A.G.M., Schell, H.J., 1975. Network planning by the extended METRA potential method. Report KS‐1.1, Department of Industrial Engineering, University of Technology Eindhoven, Netherlands. |

[18] | Lucko, G., 2009. Productivity scheduling method: linear schedule analysis with singularity functions. Journal of Construction Engineering and Management135, 4, 246-253. |

[19] | Lucko, G., 2011. Integrating efficient resource optimization and linear schedule analysis with singularity functions. Journal of Construction Engineering and Management137, 1, 45-55. |

[20] | Lucko, G., Alves, T.D.C.L., Angelim, V.L., 2014. Challenges and opportunities for productivity studies in linear, repetitive, and location‐based scheduling. Construction Management and Economics32, 6, 575-594. |

[21] | Lucko, G., Pena Orozco, A.A., 2009. Float types linear schedule analysis with singularity functions. Journal of Construction Engineering and Management135, 5, 368-377. |

[22] | Mahdi, I.M., 2004. A new LSM approach for planning repetitive housing projects. International Journal of Project Management22, 4, 339-346. |

[23] | Maravas, A., Pantouvakis, J.P., 2011. Fuzzy repetitive scheduling method for projects with repeating activities. Journal of Construction Engineering and Management‐ASCE137, 7, 561-564. |

[24] | Mattila, K.G., Abraham, D.M., 1998. Resource leveling of linear schedules using integer linear programming. Journal of Construction Engineering and Management124, 3, 232-244. |

[25] | Nadjafi, B.A., Shadrokh, S., 2009. A branch and bound algorithm for the weighted earliness‐tardiness project scheduling problem with generalized precedence relations. Scientia Iranica16, 1, 55-64. |

[26] | Neumann, K., Zhan, J., 1995. Heuristics for the minimum project‐duration problem with minimal and maximal time lags under fixed resource constraints. Journal of Intelligent Manufacturing6, 145-154. |

[27] | Ranjbar, M., 2013. A path‐relinking metaheuristic for the resource levelling problem. Journal of the Operational Research Society64, 1071-1078. |

[28] | Rieck, J., Zimmermann, J., Gather, T., 2012. Mixed‐integer linear programming for resource leveling problems. European Journal of Operational Research221, 27-37. · Zbl 1253.90116 |

[29] | Roy, B., 1962. Graphes et ordonnancements. Rev. Francaise Recherche Operation25, 323-326. |

[30] | Sabzehparvar, M., Seyed‐Hosseini, S.M., 2008. A mathematical model for the multi‐mode resource‐constrained project scheduling problem with mode dependent time lags. Journal of Supercomputing44, 3, 257-273. · Zbl 1187.90143 |

[31] | Sakellaropoulos, S., Chassiakos, A.P., 2004. Project time‐cost analysis under generalised precedence relations. Advances in Engineering Software35, 10, 715-724. · Zbl 1057.90525 |

[32] | Sharma, H., Mclntyre, C., Gao, Z., Nguyen, T.H., 2009. Developing a traffic closure integrated linear schedule for highway rehabilitation projects. Journal of Construction Engineering and Management135, 3, 146-155. |

[33] | Son, J., Mattila, K.G., 2004. Binary resource leveling model: activity splitting allowed. Journal of Construction Engineering and Management130, 6, 887-894. |

[34] | Tang, Y.J., Liu, R.K., Sun, Q. X., 2014. Two‐stage scheduling model for resource leveling of linear project. Journal of Construction Engineering and Management140, 7, 04014022. |

[35] | Valls, V., Lino, P., 2001. Criticality analysis in activity‐on‐node networks with minimal time lags. Annals of Operations Research102, 1, 17-37. · Zbl 1024.90046 |

[36] | Wiesemann, W., Kuhn, D., Rustem, B., 2012. Robust resource allocations in temporal networks. Mathematical Programming135, 1-2, 437-471. · Zbl 1262.90031 |

[37] | Yakhchali, S.H., Ghodsypour, S.H., 2010. Computing latest starting times of activities in interval‐valued networks with minimal time lags. European Journal of Operational Research200, 3, 874-880. · Zbl 1177.90191 |

[38] | Zhang, L.H., Zou, X., Su, Z.X., 2013. GA optimization model for time/cost trade‐off problem in repetitive projects considering resource continuity. Applied Mathematics & Information Sciences7, 2, 611-617. |

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.