Two are known method for calculating network graph parameters". calculation directly on the network graph; analytical (tabular).

Calculation main indicators of the network model can produce as follows.

• 1. Calculation of early dates:
  • ? early start of work determined by the duration of the longest path from the initial event to the start of this work,
  • ? early completion dates- This is the earliest possible completion date for the work. Early completion time equal to the sum early date the start of work and the duration of the work itself.
• 2.Calculation of the critical path. Its duration is defined as the total time of activities lying on the critical path, i.e. time for completion of the entire complex of work with the greatest parallelism of all work. This time is equal to the largest of the early completion times of the network graph shutdowns. The critical path passes through events that do not have time reserves (through critical activities).
• 3.Calculation of late start and finish dates for work are determined from the possibilities of a limiting shift to the right along the numerical axis of the work deadlines so that the critical path time is not changed. Therefore, it is logical to carry out calculations from last event to the first and first determine the time of late completion of work, and then calculate the time of late start of work:
  • ?late start date (ij) is defined as the difference between the late completion date of the work and the duration of the work itself,
  • ? late completion date is determined by the value of the minimum duration path leading to it from the final event, and is calculated as the difference between the critical path and the maximum duration of work from the final event network graphics until the final event of this work.
• 4. Calculation of time reserves."

Ifull operating time reserve defined as the difference between a late start and an early start or between a late finish and an early finish. It should be noted that the total time reserves for activities lying on the critical path are equal to zero,

• ? private (free) time reserves."
• 1)private time reserve of the first type determined by the ability to change the late start of work ( ij) to earlier dates without changing the later completion dates of immediately preceding work,
• 2) private reserve time of the second type determined by the ability to change the early end of work (ij) at a later date without changing the early dates for the start of immediately subsequent work; is determined by the difference between the early start of subsequent work and the early finish of this work.

Let's look at the procedure for calculating parameters using an example. The network diagram is shown in Fig. 7.5.

Rice. 7.5.

To calculate the parameters, we will use the tabular method, and in order to simplify perception, we will summarize everything in one table. 7.1.

Rules for the use of time reserves in network planning.

• 1. In order for the total and partial work reserves (y) to be equal, it is necessary and sufficient that the final event Y of the work in question is an event on the critical path.
• 2. If full reserve (Me and]1) some work is zero, then the private reserve of the second type (g"f) is also zero. There is always a relationship between these reserves R(IJ) > r" ijy Total and partial time reserves are always greater than or equal to zero.
• 3. In order for the partial reserve of work time (y) to be equal to zero, it is necessary and sufficient that this work lies on the path of maximum length from the first event to event y.
• 4. If the duration of work (y) is increased by the amount p, i.e. p then the early start date of subsequent work will increase by the amount p - g" (" yy
• 5. If the duration of work (y) is increased by the amount of the total reserve time of this work, then a new critical path is formed, the duration of which is equal to the duration of the old one.
• 6. The total reserve of work time (y) is equal to the sum of the private reserve of time of the second type of this work and the minimum of the total reserves of all immediately subsequent work.

Results of calculating network diagram parameters

Table 7.1

	Duration	Early	terms, hours	Late dates, h		Time reserves, h
	work, h	Beginnings	Endings	Beginnings	Endings	Full	Available
	Critical path, h		(works 1-3

7. If the duration of work (g/) is increased by an amount p, then a new critical path will appear, the duration of which will exceed the duration of the old critical path by an amount p -

After the network diagram has been constructed and its main indicators have been calculated, we begin to optimize it.

Calculation and analysis of network diagrams

Basic concepts and definitions

1.1. Network planning and management (NPC) is a system for planning a set of works, focused on achieving the final goal. SPU is based on a graphical representation of a certain set of works, reflecting their logical sequence, relationship and duration, with subsequent optimization of the developed schedule using methods of applied mathematics and computer technology and its use for the ongoing management of these works.

The object of management in the SPU system is a group of people who have certain resources (human, material, financial, etc.) and perform a certain set of works (project) designed to ensure the achievement of the intended goal.

1.2. A network diagram (network model or simply network) is a model of the entire process of performing a given robot complex, depicted in the form of an oriented graph and reflecting the relationship and parameters of all work.

1.3. Work is a labor process that leads to some result and requires time and resources. Waiting is also considered work.

Waiting is work that does not require labor (and other resources), but does require time.

Work on the network diagram is indicated by a solid line with an arrow.

The operating time is indicated by the number above the arrow. The unit of measurement for the duration of work can be a day, a week, a decade, a month. The length of the arrow is chosen arbitrarily. It does not reflect the duration of work. The work is indicated by the ciphers of the initial and final event ( ij). Duration of work tij.

Dependency or dummy work is a logical connection between two or more events that do not require the expenditure of time or resources. On the graph, fictitious work is indicated by a dotted arrow.

1.4. An event is the result of the completion of one or more jobs, which makes it possible to start one or more subsequent jobs. An event does not have a duration; it only means the fact that some work has been accomplished. An event on a chart is represented by a circle ( i), inside which its number is indicated. The event followed by the work is called the initial event (denoted by the index - i), and which is preceded by a robot - final ( j). There is one initial event in the network ( J) and one final one – (C).

I.5. A path is any sequence of robots in a network model in which the final event of each job coincides with the starting event of the next one. The path is indicated by the index ( L). The duration of the path is determined by the sum of the durations of the work involved in this path and is designated t(L). A distinction is made between the full path ( L(J- C)), i.e. the path from the initial event to the final one, and the path from any event to another L(m1 - m 2).

The critical path is the complete path that has the maximum duration of all possible paths on a given graph - L cr. There can be several critical paths in a network diagram. The critical path determines the deadline for completing a given set of works (the project as a whole).

Based on the constructed network model, the expected duration of its completion is determined for each job - t coolant, as well as the dispersion of the work completion time - .

In the SPU system, two methods are used to determine the time for completing work. In the event that the work is often repeated (that is, there is some normative data on its duration), or has a fairly close prototype, then the duration of the work is determined uniquely (networks with deterministic estimates). But for most work carried out for the first time (for example, research, experimental, development work) this cannot be done. In this case, the duration of the work is uncertain and methods are used to estimate the time of its completion. mathematical statistics. The duration of work is considered random variable, subject to a certain distribution law and the expected time of its completion (as well as the variance) is calculated using certain approximating formulas based on expert assessments received from the responsible performers of the work.

The duration of the work calculated in this way is, to a certain approximation, expected value its execution time as a random variable, subordinate adopted law its distribution.

In SPU practice, the most wide application We obtained the following formulas for determining the expected duration of work and the dispersion of its completion time.

Below are three varieties of these formulas that correspond to the options for individual tasks:

1st method ; ;

2nd method; ;

3rd method ; .

To calculate using these formulas, the following are obtained from responsible executors by survey: expert assessments work completion time:

A(or tmin) - minimum (optimistic) duration of work, i.e. an estimate of the duration of work assuming the most favorable set of circumstances;

b(or tmax) - maximum (pessimistic) duration of work, i.e. duration of work assuming the most unfavorable combination of circumstances;

m(or t n. c.) - the most probable estimate of the duration of the work - an estimate of the duration under the most common conditions for performing the work.

Calculation of network diagram parameters

Network diagram parameters are values ​​that characterize the position of work and events, which make it possible to analyze the state of work and make the necessary decisions. The starting point for determining all time parameters of network models is the duration of work (tij). Based on the duration of work in the network diagram, its time parameters are determined, the main ones being the following.

1. Travel time

,

Where TO- the number of jobs included in this path.

Thus, the duration of the path is the total duration of the work that makes up this path.

Critical path duration

Tcr = t[L(J-C)max] .

The duration of the critical path determines the timing of the final event of the network, that is, it determines the duration of the project (planned set of works) as a whole.

2. Travel slack is the difference between the duration of the critical and given paths. It shows how much in total the duration of activities belonging to a given path can be increased without changing the project deadline

R(L) = Tcr - t(L) .

3. Early date for the completion of an event - the period required to complete all work preceding this event i

Tr( i) = t[L(J-i)max] or Tr( j) = max .

The early date of the initial network event is taken equal to zero: Tr( J) = 0 .

4. The late deadline for the completion of an event is the latest of the permissible deadlines for the completion of an event, exceeding which by some amount causes a similar delay in the onset of the final event

Tp( i) = Tcr - t[(i-C)max] or Тп( i) = [Tn( j)-tij]min .

The late term of the final event is equal to its early term Tn( WITH)=Tr( WITH), this also occurs for events lying on the critical path Tr( i) = Тп( i).

5. The time reserve for the completion of an event is the maximum permissible period for which the completion of a given event can be delayed without causing an increase in the duration of the critical path (that is, without changing the deadline for the completion of the final event), that is, the entire project as a whole.

Events on the critical path have no time reserves. The event slack is defined as follows:

R(i) = Tп( i) - Tp( i) = R(Lmax) .

The slack time of an event is equal to the slack time of the maximum of the paths passing through this event.

6. Early start date is the earliest possible start date: t R. n.( ij) = Tp( i) .

7. Early completion date is the earliest possible completion date for work

t R. O.( ij) = t R. n.( ij) + tij= Tp( i) + tij .

8. Late start date - the latest start date for work that does not increase the duration of the critical path, i.e. the completion date of the project as a whole

t p.n.( ij) = t By.( ij) - tij= Tп( j) - tij .

9. Late work completion date - the latest work completion date at which the duration of the critical path does not increase, that is, the project completion date

t By.( ij) = Tп( j) .

For critical path activities:

t R. n.( ij) = t p.n.( ij) And t R. O.( ij) = t By.( ij) .

10. The total operating time reserve is the value of the time reserve of the maximum of the paths passing through this work. It is equal to the difference between the late occurrence of the event and the early occurrence of the event minus the duration of work

R P( ij) = Tп( j) - Tp( i) - tij .

The full operating time reserve shows how much the duration can be increased separate work or its start is delayed so that the duration of the maximum path passing through it does not exceed the duration of the critical path (that is, so that the duration of the project as a whole does not change).

Using the full reserve entirely on a given job takes away all the full reserves of time from the jobs lying on all the paths that pass through this job.

The total float time for activities on the critical path is zero, while for other activities it is positive.

11. Free operating time reserve - equal to the difference between the early dates of events j And i minus the duration of work ( ij):

R c( ij) = Tp( j) - Tp( i) - tij .

Free reserve represents part of the total operating time reserve. He points maximum time, by which you can increase the duration of an individual job, or delay its start, without changing the early start dates for subsequent jobs, provided that the immediately preceding event occurred at its earliest date.

The earliest dates for the occurrence of events are taken as the planned start dates for work. The consolidated time reserve is, in a certain sense, an independent reserve, that is, using it on one of the jobs does not change the value of the free time reserves of the remaining jobs in the network.

3.12. The work intensity coefficient is used in network planning to characterize the intensity of work deadlines and is determined by the following formula:

,

Where t(Lmax) is the duration of the maximum path passing through this work;

t¢( L kr) - duration of the route segment t(Lmax), coinciding with the critical path.

Using the tension coefficient, an estimate of the intensity of work that lies on paths of equal duration and has the same time reserves is obtained.

The value of the tension coefficient for different works in the network lies within 0 £ Kn( ij) £ i.

For all activities on the critical path Kn( ij) = 1.

The value of the tension coefficient helps, when establishing planned deadlines for the completion of work, to assess how freely the available time reserves can be used. This coefficient gives the performers of the work an indication of the degree of urgency of the work and allows them to establish the order of their execution, if it is not determined by the technological connections of the work.

Methods for calculating network diagram parameters

There are two ways to manually calculate the parameters of network graphs (moreover, in the literature on SPC there are various varieties of these methods): directly on the graph; tabular method.

1. The first method (calculating parameters directly on the graph) involves determining, as a rule, the following parameters, early dates for the completion of events, late dates for the completion of events, time reserves for the completion of events and the critical path. When calculating using this method, the circle depicting the event is divided into four sectors. The upper sector is reserved for the event number - i, left sector for the early date of the event Tr( i), right for the late date of the event Tp( i), and the lower sector for the time reserve for the event - R(i)

The parameters are calculated based on the above definitions and formulas (logical relationships) according to certain rules. The calculation begins with determining the early dates of events - Tp( i). Definition Tp( i) begins with the initial event and then through subsequent events to the final one (that is, the calculation is carried out from left to right), guided by the following general rule to determine the early timing of events.

Early date of the event j determined by adding to the early date the event preceding it i duration of work leading up to the event j. In the event that the event j includes several works, you need to determine the early date for each of these works and select the maximum one from them, which will be the early date of the event j. For the original event J the early date of its completion is assumed to be zero.

Tp( J) = 0 .

Determination of the latest dates for the completion of events is carried out in reverse order, that is, from right to left, that is, from the final event to the initial one. When determining the later dates, it is assumed that for the final event, the earliest date of its completion is at the same time the latest.

Tr( WITH) = Тп( WITH) .

Late event completion date j determined by subtracting the event preceding it from the late date i duration of work leading up to this event j.

In case the event j several jobs are suitable, then the late date for each of these jobs is determined and the minimum one is selected, which will determine the late date for the completion of this event.

Event time reserve i is determined directly on the network by subtracting from the value recorded in the right sector of the event Тп( i) value recorded in the left sector - Tr( i). The found value is the time reserve for the event and is recorded in the lower sector of the event.

All events in the network, with the exception of events belonging to the critical path, have a slack time. The critical path will be determined as a result of identifying all consecutive events with reserves equal to zero, and its duration will be determined by the value of the latest (also the earliest) date for the completion of the final event.

In Fig. 1 shows the calculation of the network directly on the graph.

Rice. 1. Calculation of network diagram parameters

2. With the tabular calculation method, as a rule, parameters related to work are determined, namely: early and late dates for the start and end of work, time reserves for work. In this case, the parameters are calculated in a table according to a certain form. An example of such a calculation for the network diagram shown in Fig. 1 is shown in the table below. 1.

Calculation using a tabular method can be made either only on the basis of formulas and a network diagram with event parameters, or according to certain rules (algorithms). In the latter case, the composition of the parameters and the sequence of their arrangement may be different. Calculations using such algorithms are described in the literature (see list of references).

Table 1

Calculation of network schedule work parameters

i-j	Duration of work tij	Early start of work t R. n.	Finishing work early t R. O.	Late start of work t p.n.	Late finish of work t By.	Time reserves	Work intensity coefficient, TO n
full, R P	free, R With

Network diagram analysis and optimization

After calculating the parameters of the network diagram, it is analyzed and, if necessary, optimized. The objectives of the analysis are to revise the structure of the network in order to determine the possibility of increasing the number of parallel works, determining the intensity factors of work, which allows, along with the calculation of reserve time for work and paths, to distribute all work into zones (critical, subcritical and reserve). An important task network diagram analysis is to determine the probability of the completion of the final event within a given time frame.

The specified deadline for the completion of the final event (that is, the target deadline for completing the project) Td may differ from the calculated Tcr obtained on the basis of the critical path, but despite this (due to the fact that the expected duration of work was determined as random variables) there remains a certain probability that the final event will occur on or before the specified target date. When determining this probability, it is assumed that the duration of the project (that is, the value of the critical path) is a random variable that obeys the normal distribution law.

The analytical probability that the final event will occur on or before a given (directive) date is determined as follows:

,

Where - the corresponding value of the function Ф( Z), taken from the table normal distribution; Z- argument normal function probability distributions.

Average standard deviation The timing of the final event is determined by the formula:

,

Where ij kr - sequence of works lying on the critical path;

TO- the number of activities that make up the critical path;

Variance of work lying on the critical path.

Example. For the graph shown in Fig. 1, determine the probability of completing the project within a given target period, equal to 8 units. time. It was previously determined that the estimated project completion time is Tcr = 9 units. Let us assume that the variances of the activities that make up the critical path are also determined, for example:

then and .

Using the table of values ​​of the Laplace function by magnitude Z= - 1.7 (see Table 2), we find the required probability RK » 0.045.

Conclusion. When planning in SPU systems, it is accepted that if:

0,85 < РК < 0,65 - то это считается границами допустимого риска (то есть считается normal position); under the Republic of Kazakhstan< 0,85 - то считается, что опасность нарушения заданного срока очень большая (неприемлема) и необходимо в этом случае и произвести повторное планирование с перераспределением ресурсов с целью минимизации срока выполнения проекта; при РК >0.65 - the probability is considered too high, that is, there are excess resources on the critical path activities. In this case, re-planning is also carried out in order to reduce the required resources.

If it is impossible to achieve a satisfactory RC value, it may be necessary to change the specified project completion date. This problem is solved as the inverse of the one discussed above. Given the desired value of the probability of the RC of the completion of the final event within a given period, it is possible to determine the value of the function from the above equation , and, knowing the values ​​of Tcr and , determine the value of Td.

After analyzing the network diagram in necessary cases its optimization is carried out. It is necessary to ensure greater reliability of completing the final event on time, to level out the workload of workers, better distribution of resources, etc. Optimization of the schedule over time (that is, achieving the minimum project completion time with given resources) is carried out by transferring resources from non-critical paths, having time reserves on the critical path, which leads to a reduction in its duration. In the limit, the duration of all complete paths can be equal and are critical, and then all work is carried out with the same stress, and the overall project completion time will be significantly reduced.

table 2

Table of values ​​of the Laplace function Pk = Ф ( Z)

The network diagram is calculated in a tabular manner using the formulas previously set out in Section 4 (1-10). When determining the parameters of network models analytically, the calculation is performed in the form of a table. Let us consider the features of calculating network models using this method (Appendix 1) using the example of calculating the parameters of the network diagram shown in the task for this course work(option 15).

At the initial stage, it is necessary to describe the initial network model. In this case, the codes of all jobs and dependencies are entered in the first column of the table, starting with the job coming out of the first event. Job codes must be included in the table sequentially; arbitrary order of inclusion of jobs and dependencies in the table is unacceptable. The second column of the table contains the durations of all activities and dependencies.

The calculation of the network diagram begins with determining the values ​​of the early work parameters. The early start of work 1-2 is equal to zero (formula 1), and its early end according to formula 2.

The early start of jobs 2-6 and 2-7 (in accordance with formula 3) is equal to the early finish of jobs 1-2.

The maximum early termination value of 19-21, equal to 36, determines the duration of the critical path and therefore total duration performing all work according to the original network model. The resulting value of the early completion of this work 19-21 = 36 is transferred to the late completion column of the final work 20-21.

Late start of work 20-21 is determined in accordance with formula 5 (= 34)

The late start of work 20-21 is the late finish of the preceding work 15-20 (=).

Further, the calculation of later parameters is performed in the same way, except for cases when the job has several subsequent jobs (for example, job 6-9 has two subsequent ones - 9-10 and 9-14). In this case, in accordance with formula 4, the late finish of work 6-9 is equal to the minimum value of the late start of subsequent works 9-10 and 9-14.

To find the position of the critical path, it is necessary to determine the values ​​of the total and private slack time for each job and dependency of the network diagram and enter their values, respectively, into columns 7 and 8 of the calculation table.

The total work time reserve, according to formulas 8-9, is defined as the difference between the late and early finishes or as the difference between the late and early starts of the corresponding work. It is useful to determine the value of the total slack using both methods; the coincidence of the obtained values ​​can be considered as an additional check. For example, for work 6-7:

The partial work time reserve, according to formula 10, is defined as the difference between the early start value of the subsequent work and the early finish value for this work. For example, for work 6-7:

The critical path is characterized by zero slack time. A comparison of the network model parameters obtained by sector and tabular methods should reveal their complete identity; the presence of discrepancies indicates that the calculations are erroneous.

Graphical method for calculating network diagrams

Calculation of a network diagram graphically is carried out similarly to the tabular method (formulas 1-10), however graphical or sector method calculating network diagram parameters involves recording them directly on the model (Appendix 2). In this case, each event (circle) is divided into four sectors. The designation of the sectors is shown in the following figure:

For activities on the critical path, the values ​​of the total and private float are equal to zero; it is highlighted on the network diagram by a double line.

To check the correctness of the calculations performed, you should make sure that:

• * a continuous critical path has been identified;
• * calculated time reserves have a non-negative value;
• * the value of the private time reserve for all jobs is less than or equal to the value of the general time reserve for these jobs;
• * at least one late start value of jobs (jobs) coming from the first event is zero.

Basic network diagram parameters

The main parameters of the network diagram include:

Critical path

Time reserves for events

Time reserves for completing work

Path – a sequence of jobs in which the final event of one job coincides with the initial event of another.

Full path – a path, the beginning of which is the initial event, and the end of which is the final event.

The duration, the length of the path, is equal to the sum of the durations of the work. Its components.

Critical path – full path. the longest in duration of all paths in the network diagram from the initial event (I) to the final one (C).

The length of the critical path determines the total duration of the entire work package. The critical path allows you to find the timing of the final event.

Full paths may occur outside the critical stage or partially coincide with it. These shorter journeys are called relaxed. Their features are: That they have time reserves. But the critical path is not. For each i-th event the following is determined:

tpi– early onset– the minimum possible time for the occurrence of this event for a given duration of work.

t p i– late onset– the maximum time period for the occurrence of a given event, at which it is still possible to perform all the following work, in compliance with the established time period for the occurrence of the event.

R i – reserve time for event– the period of time by which the onset of this event can be delayed without disrupting the development period of the planned complex as a whole. Defined as the difference between the late ( t p i) and early ( t r i) the timing of the event.

Reserves for a critical path event are equal to zero, since on it t p i =t p i

For each job ( t ij) is determined:

early start date (t р.н. ij)– the minimum possible start date for this work.

early end date (t p.o. ij)– the minimum possible completion date for this work, for a given duration of work

late start date (t bp ij)– the maximum allowable start date for this work

late end date (t p.o. ij)– the maximum permissible deadline for completing this work, at which it is still possible to perform the following works in compliance with the established deadline for the completion event.

Obviously, the early start date of a job coincides with the early start date of its initial event, and the early finish date exceeds it by the duration of the job:

t р.н. ij = t r i

t p.o. ij = t r i + t ij

The late finish date of a job coincides with the late date of its end event, and the late start date of a job is less than the duration of the job:

t p.o. ij = t p j

t p.n. ij = t p j – t ij

Full reserve of time to complete the work R nij– the maximum period of time by which the start can be delayed or the duration of work can be increased without changing the established deadline for the completion event.

Free time reserve for completing work, which is part of the full reserve - the maximum period of time by which the start of work can be delayed or the duration of work can be increased without changing the early start dates for subsequent work.

Activities lying on the critical path have no reserves, since all reserves are created due to the differences in the durations of the critical and considered paths.

A relative indicator characterizing the time reserve for performing work is their tension coefficient, which is equal to the ratio of the duration of path segments between the same events, moreover, one segment is part of the path of maximum duration of all paths passing through a given work, and the other segment is part of the critical path.

3.Calculation of network models

Network parameters for network diagrams are calculated by graphical and tabular methods, and for complex ones by mathematical methods.

Graphically, the calculation method is carried out directly on the graph and is used in cases where the number of events is small. To do this, each circle is divided into 4 sectors.

Upper sector – reserve time for the event to occur R i

left sector – early date of event occurrence tpi

right sector – late date of occurrence of event t p i

below – event number

Parameter calculation method

1) Early timing of events . The early date of completion of the initial (first or zero) event is assumed to be zero. The early dates for the completion of all other events are determined in strict sequence by increasing event numbers. To determine the early date of completion of any event j, all work included in this event is considered, for each work the early date of completion of the final event is determined as the sum of the early date of completion of the initial event of work and the duration of this work t ij , From the obtained values, the maximum early time of the j-th event is selected

t pj = (t pi +t ij) max and is recorded on the graph (left sector of the event)

2) Late timing of events . The late date of completion of the final event is assumed to be equal to its early date. Calculation of the latest dates for the completion of all other events is carried out in reverse order, according to descending event numbers. To determine the late date for the completion of the previous event i, all work resulting from the i-th event is considered. For each job, the late date of completion of the initial event is calculated t p i, as the difference between the late date of completion of the final event of this work t p j and duration of this work t ij.From the obtained value, select the minimum time of the late completion date of the i-th event: t p i = (t p j - t ij)min and is recorded in the right sector.

3) Critical path duration equal to the early date of the completion event.

4) Event time reserves . When determining time reserves for events, the number written in the left sector should be subtracted from the number written in the right sector of the given event and placed in the upper sector.

5) When determining the total reserve time for work, you should subtract from the number written in the right sector of the final event, the number written in the left sector of the initial event, and the duration of the work itself.

6) When determining the free reserve for work, you should subtract from the number written in the left sector of the final event, the number written in the left sector of the initial event, and the duration of the work itself.

Initial data:

Tabular method

Job codes in the table are written in ascending index order i.

Columns 2 and 3 are filled with auxiliary data: codes of previous and subsequent work. This data will be needed for calculations. If the work is initial, that is, there are no previous works, or final, that is, there are no subsequent works, then dashes are placed in the corresponding columns. There can be several preceding and subsequent works in accordance with the number of vectors ending or starting in a given event./

Column 4 contains the work duration values.

The calculated data begins in column 5. The calculation is performed in two passes through the rows of the table. The first pass along the rows from top to bottom, in which the early deadlines of the work are calculated, and the second pass along the rows from the bottom up, in which the late deadlines of the work are calculated.

The early start of work that has no previous ones (in column 2 - a dash) can be taken as 0, unless any other value is specified. The early completion of work is determined according to the formula t p.o. ij = t pH ij + t ij and is recorded in column 6.

The early start of the rest can be defined as, if, for example, work 2.5 is considered, which has an initial event of 2, then the time of its early start is equal to the time of the early end of work 12, since it has an end event of 2. The value from column 6 is rewritten to column 5 Codes of previous work are indicated in column 2. Early completion is also determined by the formula. t p.o. ij = t pH ij + t ij

If, in column 2, it is indicated that a certain job is preceded by more than one job (jobs 5,6 are preceded by jobs 2,5 and 3,5), then you must select the early start value from several value options (9 - according to the end time of job 2 .5 or 13 – according to the time of completion of work 3.5). The selection rule corresponds to the formula t p .n. ij = (t pi +t ij) max , that is, the maximum value is selected (in the example - 16). Early endings are defined as above.

The maximum value of early termination in column 6 corresponds to the value of the duration of the critical path (16).

A second pass along the rows of the table from the work recorded in the last row to the work recorded in the first row allows you to determine the values ​​of the later indicators of the activities. For jobs that do not have subsequent jobs (in column 3 there is a dash, in the example of jobs 46, 5,6), the value of the critical path is written in the late completion column (8). For these jobs, the late start value is calculated using the formula t p.n. ij t by ij - t ij

The late finishing of the rest can be determined as, if, for example, work 3.5 is considered, which has an end event of 5, then the time of its late finish is equal to the time of the late start of work 5,6, since it has an end event of 5. The value from column 7 is rewritten into column 8. Codes for subsequent work are indicated in column 3. Late start is also determined by the formula t p.n. ij t by ij - t ij .

If, in column 3, it is indicated that a certain job is followed by more than one job (work 0,1 is followed by jobs 1,2 and 1,3), then you must select the late finishing value from several value options (3 - according to the start time of work 1 ,3 or 7 – according to the start time of work 1,2), the minimum value is selected (in the example – 3). Late onset is determined as indicated above by the formula t p.n. ij t by ij - t ij .

The value of the total slack time (column 9) is calculated using the formula

R nij = t by ij - t pH ij - t ij.

The value of free time reserve (column 10) is calculated using the formula

R с ij = t ро ij - t рр ij - t ij

Networks or network models have wide practical applications. Of the variety of methods and models, we will consider here only the critical path method (CPM). The network in this case is a graphical representation of a set of works. The main elements of the network here are events and activities.
An event is the moment of completion of a process, reflecting a separate stage of the project. The set of works begins with the initial event and ends with the final event.
Work is a time-long process that is necessary to accomplish an event and, as a rule, requires the expenditure of resources.
Events on a network diagram are usually represented by circles, and activities are usually represented by arcs connecting the events. An event can only happen when all the work preceding it is completed.
There should be no “dead-end” events in the network diagram, with the exception of the final one, there should be no events that are not preceded by at least one job (except for the initial one), there should be no closed circuits and loops, as well as parallel jobs.
We will consider the basic concepts and provisions of the ICP on the basis of the following example. Let the following sequence of works with their time characteristics be given: Let us construct a network diagram so that all work arcs are
directed from left to right (Fig. 2). The duration of the work is indicated above the arcs.

Rice. 2. Example network diagram

The critical path is the path from the initial to the final work that has the longest duration. Any slowdown in the execution of work on the critical path will inevitably lead to disruption of the entire set of works, which is why so much attention is paid to the critical path.
Let's look at the basic concepts associated with the critical path.
Early date of the event(ET). It is determined for each event as it moves through the network from left to right from the start to the end event. For the initial event, ET = 0. For others, it is determined by the formula, where ET 1 is the early date of occurrence of event i, preceding event j; t ij – duration of work (ij).

Late occurrence of the event (LT) is the latest date at which an event can occur without delaying the completion of the entire work package. It is determined when moving through the network from right to left from the final event to the initial one according to the formula:

For the critical path, the early and late timing of events coincide. For a final event, this value is equal to the length of the critical path. Network diagram indicators can be calculated directly using the above formulas. First you need to find the early dates of events (when moving through the network from left to right, from beginning to end), (do the rest yourself).

Then perform the calculations in the opposite direction and find the later dates for the occurrence of events.
Put ET 10 = LT 10. LT 9 = LT 10 – t 9.10 = 51 –11 = 40.
LT 8 = LT 10 – t 89 ​​= 51 – 9 = 42, etc.
Another way to calculate indicators is possible - tabular.
Events are marked in the squares of the “main” diagonal. Works are marked twice in the upper and lower “side” squares relative to the main diagonal of the table. In the upper “side” squares of the table, the row number corresponds to the previous event, and the column number corresponds to the subsequent one. In the lower “side” squares it’s the other way around.
Procedure for filling out the table

1. First, the numerators of the upper and lower side squares are filled in. They record the duration of the relevant work.
2. The denominators of the upper “side” squares are filled in as the sum of the numerator of the main square and the numerator of the upper “side” in the same line.
3. The numerator of the first main square is taken equal to zero, the numerators of the remaining main squares are equal to the maximum of the denominators of the upper “side” squares in the same column.
4. The denominator of the last main square is taken to be equal to the numerator of this square. The denominators of the lower "side" squares are equal to the difference between the denominator of the main square and the numerator of the "lower" side square in the same row.
5. The denominators of the main squares are equal to the minimum of the denominators of the “lower” side squares in the same column.
Calculation of network diagram indicators

From the table you can find the chart indicators:
1. Early dates of events (numerators of the main squares).
2. Late timing of events (denominators of the main squares).
3. Event time reserves (the difference between the denominator and numerator of the main square). In our case, the critical events (without reserves) are 1, 3, 4, 6, 7, 8, 10. They constitute the critical path. The duration of the critical path is 51 (the numerator or denominator of the last main square).
4. Early completion date of work (denominators of the upper “side” squares).
5. Late start date of work (denominators of the corresponding lower “side” squares).

6. General work time reserves (the difference between the denominator of the main square and the denominator of the upper “side” in the same column).
7. Free work time reserves (the difference between the numerator of the main square and the denominator of the upper “side” square in the same column).

Let’s reproduce the network graph, putting “early” above each event on the left, and “early” on the right. late dates occurrence of the event (Fig. 3).

Rice. 3. Network diagram with time characteristics

So, the critical path runs along jobs 1–3–4–6–7–8–10, and its duration is 51.
An event's slack is defined as the difference between its LT and ET. It is clear that the slack time of events along the critical path is zero. For our example, the slack time, for example, event 2 is 28–10 = 18, and event 9 is 40–36 = 4. For these periods of time, the execution of the relevant work can be delayed without the risk of delaying the project as a whole.
These were the temporal characteristics of events. Let's consider the time characteristics of the work. These include free and general (full) work time reserves.
The total operating time reserve (TS) is determined from the relation

TS ij = LT j – ET i – t ij

and shows how much the duration of the work can be increased, provided that the deadline for completing the entire set of works does not change.
Free operating time reserve (FS) is determined from the relation

FS ij = ET j – ET i – t ij

and shows the part of the total time reserve by which the duration of the work can be increased without changing the early date of its final event.
If the free work time reserve can be used for all network jobs simultaneously (then all jobs become critical), then this cannot be said for full reserves; it can be used either for one path work in its entirety, or for different works in parts.
For critical jobs, TS and FS are equal to zero. TS and FS can be used when choosing calendar dates for non-critical work and for partial optimization of network schedules.
Finally we have: Time characteristics of work

Non-critical work	Duration	General	Free reserve FS
1-2	10	18	0
1-4	6	5	5
2-5	9	18	0
4-5	3	23	5
3-6	8	9	9
4-7	4	15	15
5-8	5	18	18
6-9	7	12	8
7-9	6	4	0
7-10	8	13	13
9-10	11	4	4

Problems for test assignments No. 4

Using the following data, construct a network similar to that considered in the example, determine the time characteristics of its operations and events, the critical path and its length. When performing this task, substitute the number of your option for n and round the resulting number to the nearest integer.

Job	(1,2)	(1,3)	(1,4)	(2,5)	(2,4)	(3,4)	(3,6)	(4,5)	(4,6)
Duration	5+n/3	6+n/3	7+ n/3	4+n	8+ n/3	3+n	4+n/2	10+ n/3	2+n
(4,7)	(5,7)	(5,8)	(6,7)	(6,9)	(7,8)	(7,9)	(7,10)	(8,10)	(9,10)
8+ n/3	9+n/2	10+ n/3	12+n/2	9+n	7+ n/3	5+n	9+n	11+n/2	8+ n/3