51211

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

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

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

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

Русский

2014-02-07

156 KB

3 чел.

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

Лабораторная работа № 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.


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

Вывод

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


 

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

60802. Моделювання виховної роботи з учнями, що мають різний соціометричний статус 61.5 KB
  Проведемо наше методичне об’єднання в нетрадиційній формі деякі засоби роботи вправи ви зможете використати в роботі з класом. Отже сьогодні чого ми очікуємо від процесу виховання Якими ми бачимо труднощі або результати...
60804. Особливості формування ключових компетентностей учнів через міжтематичні зв’язки системи теоретичних понять інформатики та реалізацію гуманітарних аспектів 373 KB
  Особливість предмету інформатики та визначення його ролі і міста серед предметів на формування загальної освіти особистості зміст його предметних та загальноосвітніх компетентностей вже створює проблеми в викладанні змісту...
60807. Урок по моделированию многоэтажного здания в 3ds Max 6.4 MB
  В данном уроке мы рассмотрим способ моделирования высокополигонального современного многоэтажного здания в 3ds Max. Чтобы ясно себе представлять будущую модель, следует пользоваться...