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.


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

Вывод

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


 

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

60047. Складання та розв’язання задач на матеріалі навколишнього світу, як засіб розвитку пізнавальних інтересів учнів 51 KB
  Дитина з малих років повинна розуміти що все досягається працею і що працювати непросто. Як правило всі діти 67 років з великим бажанням йдуть до школу їм все цікаво вони завжди хочуть відповідати руки їх постійно тягнуться вгору вони навіть...
60048. Розв’язання сюжетних задач 245.5 KB
  Мета заняття: дидактична: формувати навички розв’язування текстових задач розвивати в учнів усну і письмову культуру мовлення логічне мислення заохочувати учнів до самостійної навчальної діяльності виховувати у них позитивну мотивацію...