Negative weights in network time model

Abstract

Time does not go backward. A negative duration, such as “time period” at first sight is difficult to interpret. Previous network techniques (CPM/PERT/PDM) did not support negative parameters and/or loops (potentially necessitating recursive calculations) in the model because of the limited computing and data storage capabilities of early computers. Monsieur Roy and John Fondahl implicitly introduced negative weights into network techniques to represent activities with fixed or estimated durations (MPM/PDM). Subsequently, the introduction of negative lead and/or lag times by software developers (IBM) apparently overcome the limitation of not allowing negative time parameters in time model. Referring to general digraph (Event on Node) representation where activities are represented by pairs of nodes and pairwise relative time restrictions are represented by weighted arrows, we can release most restraints in constructing the graph structure (incorporating the dynamic model of the inner logic of time plan), and a surprisingly flexible and handy network model can be developed that provides all the advantages of the abovementioned techniques. This paper aims to review the theoretical possibilities and technical interpretations (and use) of negative weights in network time models and discuss approximately 20 types of time-based restrictions among the activities of construction projects. We focus on pure relative time models, without considering other restrictions (such as calendar data, time-cost trade-off, resource allocation or other constraints).

Graphical abstract

Keywords

graph technique / network technique / construction management / scheduling

References

[1] Dijkstra E W (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1): 269–271

[2] Douglas III E E, Calvey T T, McDonald Jr D F, Winter R M (2006). The great negative lag debate. AACE International Transactions, PS21

[3] Floyd R W (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6): 345

[4] Fondahl J W (1962). A non-computer approach to the critical path method for the construction industry. Technical Report No. 9. Stanford, California: The Construction Institute, Department of Civil Engineering, Stanford University

[5] Hajdu M (2015a). Continuous precedence relations for better modelling overlapping activities. Procedia Engineering, 123: 216–223

[6] Hajdu M (2015b). Point-to-point versus traditional precedence relations for modelling activity overlapping. Procedia Engineering, 123: 208–215

[7] Hajdu M, Skibniewski M J, Vanhoucke M, Horvath A, Brilakis I (2016). How many types of critical activities exist? A conjecture in need of proof. Procedia Engineering, 164: 3–11

[8] IBM (1966). 1440 Project Control System (1440-MX-02X). User’s Manual. New York: IBM

[9] Kelley Jr J E (1961). Critical-path planning and scheduling: Mathematical basis. Operations Research, 9(3): 296–320

[10] Kelley Jr J E, Walker M R (1959). Critical-path planning and scheduling. In: Proceedings of Eastern Joint Computer Conference. Boston, MA, 160–173

[11] Kerbosch J A G M, Schell H J (1975). Network planning by the Extended Metra Potential Method (EMPM). Report KS-1.1. Eindhoven: Department of Industrial Engineering, University of Technology Eindhoven

[12] Kim S G (2018). A new networking technique—The beeline diagramming method. In: International Conference on Mechanical, Electronic and Information Technology (ICMEIT 2018), 511–523

[13] Malcolm D G, Roseboom J H, Clark C E, Fazar W (1959). Application of a technique for research and development program evaluation. Operations Research, 7(5): 646–669

[14] Roy B (1964). Scheduling Problems. Paris: Dunod (in French)

[15] Roy B, Sussmann B (1964). Scheduling problems with disjunct constraints. Note DS No. 9 bis. SEMA, Montrouge (in French)

[16] Vattai Z A (2016). Floyd-warshall in scheduling open networks. Procedia Engineering, 164: 106–114

[17] Vattai Z A (2017). “Critical” terminology—Apropos of a conjecture. Procedia Engineering, 196: 754–762

[18] Warshall S (1962). A theorem on Boolean matrices. Journal of the Association for Computing Machinery, 9(1): 11–12

[19] Weaver P (2014). The origins of hammocks and ladders. Project Management World Journal, 3(10): 1–6

[20] Wiest J D (1981). Precedence diagramming method: Some unusual characteristics and their implications for project managers. Journal of Operations Management, 1(3): 121–130

Open Access

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

RIGHTS & PERMISSIONS

2020 The Author(s) 2020. This article is published with open access at link.springer.com and journal.hep.com.cn