51211

Сетевое планирование производственных процессов

Лабораторная работа

Информатика, кибернетика и программирование

Цель работы Изучение сетевого планирования процессов на основе построения и расчета сетевого графа. Постановка задачи Построить сетевой граф процесса, 10-15 работ. Провести расчет графа и анализ планируемого процесса. Разработать программу реализации.

Русский

2014-02-07

156 KB

4 чел.

Саратовский государственный технический университет имени Гагарина Ю.А.

Лабораторная работа № 1

по курсу «Теоретические основы автоматизированного управления»

на тему:

«Сетевое планирование производственных процессов»

Выполнил:

студент АСУ-31

Петренко А.Г.

Проверил:

преподаватель

Васильев Д.А.

Саратов 2013

Цель работы

Изучение сетевого планирования процессов на основе построения и расчета  сетевого графа.

Постановка задачи

Построить сетевой граф процесса, 10-15 работ. Провести расчет графа и анализ планируемого процесса. Разработать программу реализации.

Основные теоретические сведения

Сетью называется взвешенный ориентированный граф. Сетевые модели в настоящее время широко распространены при анализе и синтезе автоматизированных систем управления. При анализе структуры системы вначале устанавливают наличие каналов связи между теми или другими агрегатами, т. е. строят неориентированный граф, далее, учитывая направление передачи сигналов между агрегатами и их характеристиками, получают модель системы в виде сети, с которой и работают при дальнейших исследованиях. Большое распространение получили сети или сетевые графики, которые широко используются при изготовлении различных видов вычислительной техники; при построении эффективных алгоритмов  функционирования систем; при изготовлении новой техники; при изготовлении и монтаже новых промышленных и гражданских зданий и сооружений, а так же при капитальном ремонте и реконструкции этих объектов. Столь широкое использование сетей делает возможным применение их в различных учебно-исследовательских работах студентов.

 Сетевой график основан на использовании другой математической модели - графа. Графам (устаревшие синонимы: сеть, лабиринт, карта и т.д.) математики называют "множество вершин и набор упорядоченных или неупорядоченных пар вершин".

Наиболее распространенный тип сетевого графика работ представляет систему кружков и соединяющих их направленных отрезков (стрелок), где стрелки отображают сами работы, а кружки на их концах ("события") - начало или окончание этих работ.

Фактически на сетевом графике приводится множество сведений о производимых работах. Над каждой стрелкой пишется наименование работы, под стрелкой - продолжительность, этой работы (обычно в днях).

В графике могут использоваться пунктирные стрелки - это так называемые "зависимости" (фиктивные работы), не требующие ни времени, ни ресурсов.

Они указывают на то, что "событие", на которое направлена пунктирная стрелка, может происходить только после свершения события, из которого исходит эта стрелка.

В сетевом графике не должно быть тупиковых участков, каждое событие должно соединяться сплошной или пунктирной стрелкой (или стрелками) с каким-либо предшествующим (одним или несколькими) я последующим (одним или несколькими) событиями.

Нумерация событий производится примерно в той последовательности, в какой они будут происходить. Начальное событие располагается обычно с левой стороны графика, конечное — с правой.

Последовательность стрелок, в которой начало каждой последующей стрелки совпадает с концом предыдущей, называется путем. Путь обозначается в виде последовательности номеров событий.

В сетевом графике между начальным и конечным событиями может быть несколько путей. Путь, имеющий наибольшую продолжительность, называется критическим. Критический путь определяет общую продолжительность работ. Все остальные пути имеют меньшую продолжительность, и поэтому в них выполняемое работы имеют резервы времени.

Критический путь обозначается на сетевом графике утолщенными или двойными линиями (стрелками).

Особое значение при составлении сетевого графика имеют два понятия:

  1.  Раннее начало работы - срок, раньше которого нельзя начать данную работу, не нарушив принятой технологической последовательности. Он определяется наиболее долгим путем от исходного события до начала данной работы
  2.  Позднее окончание работы - самый поздний срок окончания работы, при котором не увеличивается общая продолжительность работ. Он определяется самым коротким путем от данного события до завершения всех работ.

При оценке резервов времени удобно использовать еще два вспомогательных понятия:

  1.  Раннее окончание - срок, раньше которого нельзя закончить данную работу. Он равен раннему началу плюс продолжительность данной работы
  2.  Позднее начало - срок, позже которого нельзя начинать данную работу, не увеличив общую продолжительность строительства. Он равен позднему окончанию минус продолжительность данной работы.

Если событие является окончанием лишь одной работы (т.е. в него направлена только одна стрелка), то раннее окончание этой работы совпадает с ранним началом последующей.

Общий (полный) резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не увеличивая общую продолжительность работ. Он определяется разностью между поздним и ранним началом (или поздним и ранним окончанием - что то же самое).

Частный (свободный) резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не меняя раннего начала последующей. Этот резерв возможен только тогда, когда в событие входят две или более работы (зависимости), т.е. на него направлены две или более стрелки (сплошные или пунктирные). Тогда лишь у одной из этих работ раннее окончание будет совпадать с ранним началом последующей работы, для остальных же это будут разные значения. Эта разница у каждой работы и будет ее частным резервом.

Корректировка сетевых графиков производится как на этапе их составления, так и использования. Она состоит в оптимизации строительных работ по времени и по ресурсам (в частности по движению рабочей силы). Если, например, сетевой график не обеспечивает выполнения работ в необходимые сроки (нормативные или установленные контрактом) производится его корректировка по времени, т.е. сокращается продолжительность критического пути. Обычно это делается

  1.  за счет резервов времени некритических работ и соответствующего перераспределения ресурсов
  2.  за счет привлечения дополнительных ресурсов

за счет изменения организационно-технологической последовательности и взаимосвязи работ.


Описание процесса

Построен сетевой граф процесса настройки новокупленной гитары. Описание работ процесса в сетевом графе (рис.1):

рис.1 Сетевой граф

Алгоритм расчета сетевого графа

  1.  Пути графа уже заданы. Определяются веса дуг графа;
  2.  Нахождение L критического пути (максимальный путь в графе);
  3.  Нахождение резерва: Li=Lкр-Li;
  4.  Нахождение раннего срока свершения события: tp(i)=t[L(1÷i)max];
  5.  Нахождение позднего срока свершения события: tп(i)=tкр-t[L(i÷N)max], где N -  максимальный номер среди вершин данного графа;
  6.  Нахождение резерва времени для i-го события: Р(i)=tп(i)-tp(i);
  7.  Нахождение резерва для работы (i,j):  Рn(i,j)= tп(i)-tp(i)-t(i,j);

8) Нахождение коэффициентов нагрузки для работ в сетевом графе:

,

где: t(Lmax) – продолжительность максимального пути, через работу (i,j); а t’(Lкр) – сумма весов дуг максимального пути, через работу (i,j), совпадающих с дугами критического пути, через эту же работу.

Описание программы

 


Код программы

unit Unit1;

interface

uses

 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

 Dialogs, ExtCtrls, StdCtrls, ComCtrls, Grids;

type

 TForm1 = class(TForm)

   Edit1: TEdit;

   Edit2: TEdit;

   Edit3: TEdit;

   Edit4: TEdit;

   Edit5: TEdit;

   Edit6: TEdit;

   Edit7: TEdit;

   Edit9: TEdit;

   Edit10: TEdit;

   Button1: TButton;

   PageControl1: TPageControl;

   TabSheet1: TTabSheet;

   Label1: TLabel;

   Label2: TLabel;

   Label3: TLabel;

   Label4: TLabel;

   Label5: TLabel;

   Label6: TLabel;

   Label7: TLabel;

   Label8: TLabel;

   Label9: TLabel;

   Label10: TLabel;

   Label11: TLabel;

   Button2: TButton;

   Edit8: TEdit;

   Edit11: TEdit;

   Edit12: TEdit;

   Edit13: TEdit;

   Edit14: TEdit;

   Edit15: TEdit;

   TabSheet3: TTabSheet;

   StringGrid1: TStringGrid;

   Edit0: TEdit;

   StringGrid2: TStringGrid;

   Label12: TLabel;

   Image1: TImage;

   procedure Button1Click(Sender: TObject);

   procedure Button2Click(Sender: TObject);

   procedure FormCreate(Sender: TObject);

  

 private

   { Private declarations }

 public

   { Public declarations }

 end;

var

 Form1: TForm1;

 graf: array [0..17,0..17] of byte;

 napr: array [0..17,0..17] of real;

 rann: array [0..17] of integer;

 pozd: array [0..17] of integer;

 rzv: array [0..17] of integer;

 plnrzv: array [0..17,0..17] of byte;

 lenght1,lenght2,crit:integer;

implementation

{$R *.dfm}

procedure TForm1.Button2Click(Sender: TObject);

begin

 randomize;

 graf[0,1]:=random(10)+1;

 graf[1,2]:=random(10)+1;

 graf[2,3]:=random(10)+1;

 graf[3,4]:=random(10)+1;

 graf[3,7]:=random(20)+1;

 graf[7,8]:=random(20)+1;

 graf[4,5]:=random(10)+1;

 graf[5,6]:=random(10)+1;

 graf[8,9]:=0;

 graf[6,9]:=0;

 graf[9,10]:=random(10)+1;

 graf[10,11]:=random(10)+1;

 graf[11,12]:=random(10)+1;

 graf[12,13]:=random(10)+1;

 graf[13,14]:=random(10)+1;

 graf[14,15]:=random(10)+1;

 graf[15,16]:=random(10)+1;

 graf[16,17]:=random(10)+1;

 edit0.Text:=inttostr(graf[0,1]);

 edit1.text:=inttostr(graf[1,2]);

 edit2.text:=inttostr(graf[2,3]);

 edit3.text:=inttostr(graf[3,4]);

 edit4.text:=inttostr(graf[3,7]);

 edit5.text:=inttostr(graf[4,5]);

 edit6.text:=inttostr(graf[5,6]);

 edit7.text:=inttostr(graf[7,8]);

 edit9.text:=inttostr(graf[9,10]);

 edit10.text:=inttostr(graf[10,11]);

 edit8.Text:=inttostr(graf[11,12]);

 edit11.text:=inttostr(graf[12,13]);

 edit12.text:=inttostr(graf[13,14]);

 edit13.text:=inttostr(graf[14,15]);

 edit14.text:=inttostr(graf[15,16]);

 edit15.text:=inttostr(graf[16,17]);

end;

procedure TForm1.Button1Click(Sender: TObject);

var i:byte;

begin

 lenght1:=graf[0,1]+graf[1,2]+graf[2,3]+graf[3,4]+graf[4,5]+graf[5,6]+graf[9,10]

 +graf[10,11]+graf[11,12]+graf[12,13]+graf[13,14]+graf[14,15]+graf[15,16]

 +graf[16,17];

 lenght2:=graf[0,1]+graf[1,2]+graf[2,3]+graf[3,7]+graf[7,8]+graf[9,10]+graf[10,11]

 +graf[11,12]+graf[12,13]+graf[13,14]+graf[14,15]+graf[15,16]+graf[16,17];

 label8.caption:=inttostr(lenght1);

 label9.caption:=inttostr(lenght2);

 if lenght1>lenght2 then

   begin

     label11.Caption:=inttostr(0);

     label12.Caption:=inttostr(lenght1-lenght2);

     crit:=lenght1;

   end

 else

   begin

     label12.Caption:=inttostr(0);

     label11.Caption:=inttostr(lenght2-lenght1);

     crit:=lenght2;

   end;

//ранний путь

 rann[0]:=0;

 rann[1]:=graf[0,1];

 rann[2]:=rann[1]+graf[1,2];

 rann[3]:=rann[2]+graf[2,3];

 rann[4]:=rann[3]+graf[3,4];

 rann[5]:=rann[4]+graf[4,5];

 rann[6]:=rann[5]+graf[5,6];

 rann[7]:=rann[3]+graf[3,7];

 rann[8]:=rann[7]+graf[7,8];

 if lenght1>lenght2 then

   rann[9]:=rann[6]

 else

   rann[9]:=rann[8];

 rann[10]:=rann[9]+graf[9,10];

 rann[11]:=rann[10]+graf[10,11];

 rann[12]:=rann[11]+graf[11,12];

 rann[13]:=rann[12]+graf[12,13];

 rann[14]:=rann[13]+graf[13,14];

 rann[15]:=rann[14]+graf[14,15];

 rann[16]:=rann[15]+graf[15,16];

 rann[17]:=rann[16]+graf[16,17];

 for i:=1 to 17 do

   stringgrid1.Cells[1,i]:=inttostr(rann[i]);

//поздний путь

   pozd[17]:=0;

   pozd[16]:=graf[16,17];

   pozd[15]:=(pozd[16]+graf[15,16]);

   pozd[14]:=(pozd[15]+graf[14,15]);

   pozd[13]:=(pozd[14]+graf[13,14]);

   pozd[12]:=(pozd[13]+graf[12,13]);

   pozd[11]:=(pozd[12]+graf[11,12]);

   pozd[10]:=(pozd[11]+graf[10,11]);

   pozd[9]:=(pozd[10]+graf[9,10]);

   pozd[6]:=pozd[9];

   pozd[5]:=(pozd[6]+graf[5,6]);

   pozd[4]:=(pozd[5]+graf[4,5]);

   pozd[8]:=pozd[9];

   pozd[7]:=(pozd[8]+graf[7,8]);

   if lenght1>lenght2 then

     pozd[3]:=(pozd[4]+graf[3,4])

   else

     pozd[3]:=(pozd[7]+graf[3,7]);

   pozd[2]:=(pozd[3]+graf[2,3]);

   pozd[1]:=(pozd[2]+graf[1,2]);

   for i:=1 to 17 do

     pozd[i]:=crit-pozd[i];

   for i:=1 to 17  do

     stringgrid1.Cells[2,i]:=inttostr(pozd[i]);

//Резерв времени

 for i:=1 to 17 do

   begin

     rzv[i]:=pozd[i]-rann[i];

     stringgrid1.Cells[3,i]:=inttostr(rzv[i]);

   end;

 {plnrzv[1,2]:=pozd[2]-rann[1]-graf[1,2];

 plnrzv[2,3]:=pozd[3]-rann[2]-graf[2,3];

 plnrzv[3,4]:=pozd[4]-rann[3]-graf[3,4];

 plnrzv[4,5]:=pozd[5]-rann[4]-graf[4,5];

 plnrzv[5,6]:=pozd[6]-rann[5]-graf[5,6];

 plnrzv[3,7]:=pozd[7]-rann[3]-graf[3,7];

 plnrzv[7,8]:=pozd[8]-rann[7]-graf[7,8];}

//Полный резерв времени

if lenght1>lenght2 then

 begin

   plnrzv[3,7]:=pozd[7]-rann[3]-graf[3,7];

   stringgrid2.Cells[1,4]:=inttostr(plnrzv[3,7]);

   plnrzv[7,8]:=pozd[8]-rann[7]-graf[7,8];

   stringgrid2.Cells[1,5]:=inttostr(plnrzv[7,8]);

   stringgrid2.Cells[1,1]:='0';

   stringgrid2.Cells[1,2]:='0';

   stringgrid2.Cells[1,3]:='0';

 end

 else

 begin

   plnrzv[3,4]:=pozd[4]-rann[3]-graf[3,4];

   stringgrid2.Cells[1,1]:=inttostr(plnrzv[3,4]);

   plnrzv[4,5]:=pozd[5]-rann[4]-graf[4,5];

   stringgrid2.Cells[1,2]:=inttostr(plnrzv[4,5]);

   plnrzv[5,6]:=pozd[6]-rann[5]-graf[5,6];

   stringgrid2.Cells[1,3]:=inttostr(plnrzv[5,6]);

   stringgrid2.Cells[1,4]:='0';

   stringgrid2.Cells[1,5]:='0';

 end;

 

//Напряженность

 if lenght1>lenght2 then

   begin

     napr[3,7]:=lenght2/lenght1;

     stringgrid2.cells[1,4]:=floattostr(napr[3,7]);

     napr[7,8]:=lenght2/lenght1;

     stringgrid2.cells[1,5]:=floattostr(napr[7,8]);

     napr[3,4]:=1;

     napr[4,5]:=1;

     napr[5,6]:=1;

     stringgrid2.cells[1,1]:='1';

     stringgrid2.cells[1,2]:='1';

     stringgrid2.cells[1,3]:='1';

   end

   else

   begin

     napr[3,4]:=lenght1/lenght2;

     stringgrid2.cells[1,1]:=floattostr(napr[3,4]);

     napr[4,5]:=lenght1/lenght2;

     stringgrid2.cells[1,2]:=floattostr(napr[4,5]);

     napr[5,6]:=lenght1/lenght2;

     stringgrid2.cells[1,3]:=floattostr(napr[5,6]);

     napr[3,7]:=1;

     napr[7,8]:=1;

     stringgrid2.cells[1,4]:='1';

     stringgrid2.cells[1,5]:='1';

   end;

 napr[0,1]:=1;

 napr[1,2]:=1;

 napr[2,3]:=1;

 napr[9,10]:=1;

 napr[10,11]:=1;

 napr[11,12]:=1;

 napr[12,13]:=1;

 napr[13,14]:=1;

 napr[14,15]:=1;

 napr[15,16]:=1;

 napr[16,17]:=1;

end;

procedure TForm1.FormCreate(Sender: TObject);

var i:byte;

begin

 for i:=1 to 17 do

   stringgrid1.cells[0,i]:=inttostr(i);

 stringgrid1.Cells[1,0]:='Ранний срок';

 stringgrid1.Cells[2,0]:='Поздний срок';

 stringgrid1.Cells[3,0]:='Резерв времени';

 stringgrid2.cells[0,1]:='3-4';

 stringgrid2.cells[0,2]:='4-5';

 stringgrid2.cells[0,3]:='5-6';

 stringgrid2.cells[0,4]:='3-7';

 stringgrid2.cells[0,5]:='7-8';

end;

end.


Контрольные примеры

Вывод

В ходе выполнения данной лабораторной работы были изучены основные принципы планирования процессов с помощью сетевых графов, а так же их анализ и оптимизация. Реализована возможность расчета сетевого графа.


 

А также другие работы, которые могут Вас заинтересовать

23477. III склонение. Основы на губные (β, π) 141 KB
  Расстояние от одного места до другого как далеко проходимое пространство какое расстояние а также дорога по которой ктолибо или чтолибо движется каким путём6 обозначаются в греческом языке винительным падежом без предлога accusativus spatii €œвинительным протяжения в пространстве€: ἀπέχει ἡ Πλάταια τῶν Θηβῶν σταδίους ἑβδομήκοντα Thuc. ᾐδέσθην стыдиться совеститься; чтить уважать коголибо асс. ἀπέχω быть удалённым отстоять находиться от чеголибо на расстоянии чеголибо gen. ἐβλάβην вредить комулибо чемулибо ...
23478. III склонение. Основы на переднеязычные (δ, τ, θ) 191 KB
  ἐλπίς gen. ἐσθής gen. κόρυς gen. Образцы склонения ἡ ἐλπίς €œнадежда€ ἡ ἐσθής €œодежда€ ἡ κόρυς €œшлем€ ὁ τάπης €œковёр€ основа ἐλπῐδ ἐσθητ κορῠθ τᾰπητ singularis nominativus ἡ ἐλπίς ἐσθής κόρυς ὁ τάπης genetivus τῆς ἐλπίδος ἐσθῆτος κόρυθος τοῦ τάπητος dativus τῇ ἐλπίδι ἐσθῆτι κόρυθι τῷ τάπητι accusativus τὴν ἐλπίδα ἐσθῆτα κόρυν κόρυθα τὸν τάπητα vocativus ὦ ἐλπί ἐλπίς ἐσθής κόρυ κόρυς ὦ τάπη τάπης pluralis nominativus αἱ ἐλπίδες ἐσθῆτες κόρυθες οἱ τάπητες genetivus τῶν ἐλπίδων ἐσθήτων κορύθων τῶν ταπήτων dativus...
23479. Coniunctivus (сослагательное наклонение) 131.5 KB
  Все времена сослагательного наклонения кроме перфекта впрочем малоупотребительного1 образуются посредством добавления к соответствующей основе глагольной или настоящего времени долгих тематических гласных ω η2 служащих показателем сослагательного наклонения и первичных личных окончаний при соединении которых получается следующий набор практических окончаний:3 activum medium singularis pluralis singularis pluralis 1 ω ωμεν ωμαι ωμεθα 2 ῃς ηις ητε ῃ ηαι ησαι ησθε 3 ῃ ηι ωσιν ηται ωνται Coniunctivus...
23480. Optativus (желательное наклонение) 198.5 KB
  На русский язык формы желательного наклонения вне контекста либо не переводят вовсе либо используют частицу €œо если бы€: например παιδεύοιμεν praes. Все времена желательного наклонения кроме перфекта впрочем малоупотребительного1 образуются посредством добавления к соответствующей основе глагольной или настоящего времени суффикса ι ιη2 служащего показателем желательного наклонения и вторичных личных окончаний. Optativus praesentis activi mediipassivi желательное наклонение настоящего времени действительного и среднего...
23481. Фонетика и графика 457.5 KB
  sing 4 Δ δ δέλτα дельта [d] [д] 5 Ε ε ἒ ψιλόν3 эпсилон [e] краткий [э] краткий 6 Ζ ζ ζῆτα зета [zz]4 [зз] 7 Η η ἦτα эта [e] долгий открытый [э] долгий открытый 8 Θ θ θῆτα тхета [tʰ] [тˣ] 9 Ι ι ἰῶτα йота [i] долгий и краткий [и] долгий и краткий 10 Κ κ κάππα каппа [k] [к] 11 Λ λ λάμβδα ламбда [l] [л] 12 Μ μ μῦ мю [m] [м] 13 Ν ν νῦ ню [n] [н] 14 Ξ ῖ кси [x] [кс] 15 Ο ο ὂ μικρόν5 омикрон [o] краткий [o] краткий 16 Π π πῖ пи [p] [п] 17 Ρ ρ ῥῶ рхо [r]; [rʰ] в начале слова6 в двойном ρρ7 в середине слова после φ θ χ [р]; [рˣ] в начале слова...
23482. Глагол (ῥῆμα, verbum) 142.5 KB
  С категорией вида тесно связана в греческом языке категория времени χρόνος tempus в рамках которой помимо свойственного всем языкам разделения на настоящее прошедшее и будущее времена противопоставлены друг другу в зависимости от видовой характеристики обозначаемого глаголом действия. Категория времени включает в себя семь времён: 1. будущее μέλλων futurum III обозначает любое будущее действие вне зависимости от характера его протекания и соответствует русскому будущему времени как совершенного так и несовершенного вида: παιδεύσω...
23483. Имя (ὄνομα, nomen) 253.5 KB
  Категория рода γένος genus образована противопоставлением трёх родов: 1. родительный падеж γενική genetivus служит падежом определения выраженного существительным кого чего чей а также обозначает лицо или предмет от которого ктолибо или чтолибо удаляется отделяется освобождается от кого от чего; 3. Их можно представить в виде следующей таблицы:7 число singularis pluralis падеж род m f n m f n nominativus ς ø8 ν ø ι ες ᾰ genetivus ς ιο ος ων dativus ῐ ις σῐ accusativus ν который после согласных...
23484. Занимательная Греция 1.66 MB
  Царь Кекроп воцаряется в Афинах. Царь Кадм основатель Кадмеи пришел в Фивы из Финикии и научил греков письменности. Царь Минос сын Зевса воцарился на Крите а фригийские карлики научили греков ковать железо. Аргосский царь Фидон ввел в употребление точные меры весы и деньги Вы скажете: Разве это история Это сказка Это все равно что составлять таблицу по хронологии Киевской Руси и включать в нее даты: тогдато Илья Муромец убил Соловьяразбойника а тогдато Руслан Черномора.