Min-cut algorithm for network schedule by merging the vertices

Technology and organization of construction

The task of reducing the total duration of the project ("compression", "crashing") occurs when developing and adjusting schedules. The activities requiring crashing are determined by the minimum of added resources at the unit reduction of the schedule. The minimum cut in a critical network determines such activities. The essence of searching the minimum cut by merging vertices (edge tightening) of the critical network is presented. The procedure of selecting vertices consists of the following. Possible merge options (tentative steps) are evaluated by equivalent cuts. The minimum cut will define priority vertex of a critical network. After this merging algorithm re-examines all the possible options of joining of adjacent vertices (on next step). The general applicability of the algorithm is demonstrated. Conditions of effective application of a method of the merge of vertexes are established. Search results of the minimum cuts of the critical network by means of this method are presented. Calculations have shown that in 14 of 15 examples the algorithm has established the global minimum cuts. Implementation of the proposed approaches will allow determining the activities to be optimized, calculate the size of reduction and the number of resources involved. The suggested methodology can be recommended for use by construction project managers.