محاسبه پارامترهای نمودارهای شبکه. روش های محاسبه نمودار شبکه

ساختمان گرافیک شبکهاستفاده از چهار عنصر موجود در برنامه را فراهم می کند: کار، رویداد، انتظار و وابستگی. عناصر نمودار شبکه با استفاده از اعداد عربی کدگذاری می شوند. در این صورت کد کار (وابستگی) اعداد رویدادهای اولیه و نهایی در رابطه با آن خواهد بود. عناوین نشان داده شده در شکل 5.

در زیر قطعاتی از نمودارهای شبکه برای اجرای کار سیکل صفر روی دو و سه گیره آورده شده است.

نصب گزیده پس پرکن عایق گودال پایه معکوس هیدرولیک

چنگ میزنم

دوم گرفتن

برنج. 4.1. بخشی از برنامه شبکه برای اجرای کار روی دو دستگیره

گزیده نصب هیدرو معکوس

پس پرکن عایق گودال فونداسیون

برنج. 4.2. بخشی از برنامه شبکه برای اجرای کار در سه گریپ

پس از ساخت نمودار شبکه و شماره گذاری رویدادهای آن، پارامترها با استفاده از یکی از روش های دستی (جدول یا بخش) محاسبه می شوند. هنگام محاسبه برنامه شبکه، پارامترهای زیر تعیین می شود: شروع اولیه (t r i، j) و پایان زودهنگام (t r i، j) کار. دیر شروع(t n n i , j) و دیر اتمام (t n o i , j) کار. ذخایر زمانی عمومی (R i, j) و خصوصی (r i, j).

3.2. محاسبه نمودار شبکه به روش جدولی

محاسبه به روش جدولی در 5 مرحله انجام می شود (شکل 7 و جدول 3 را ببینید):

مرحله I - پر کردن 1، 2، 3 ستون از نمودار شبکه.

مرحله دوم - محاسبه ترم های اولیه، از رویداد اولیه تا رویداد نهایی و با استفاده از روابط زیر بین پارامترهای محاسبه شده: t r ref = 0. t pH i , j = max t po k , i ; t po i , j = t pH i , j +t i , j ;

مرحله III - محاسبه تاریخ های دیرهنگام، با شروع از رویداد نهایی برنامه شبکه و با استفاده از روابط زیر: t p o head = max t po head.

t p o i , j =min t mon j , k ; t mon i , j = t p o i , j - t i , j ;

مرحله IV - محاسبه ذخایر کل (تمام) زمان بر اساس فرمول های محاسباتی شناخته شده: R i , j = t mon i , j - t r i , j or R i , j = t by i , j - t r i , j ;

مرحله V - محاسبه ذخایر زمانی خصوصی (آزاد) بر اساس وابستگی زیر: r i , j = t rn j , k - t r i , j .

برنج. 7 - نمونه ای از نمودار شبکه با محاسبه روش جدولی

جدول 3

محاسبه نمودار شبکه به روش جدولی

پیش قطب شماره شروع رویداد. آثار	کد کار	زمان کار	تاریخ های اولیه	تاریخ های دیرهنگام	ذخایر زمان	تاریخ شروع زودهنگام
			شروع کنید	پایان	شروع کنید	پایان	عمومی (کامل)	خصوصی (رایگان)
-	1-2
	2-3
	2-4
	3-4
	3-5
	3-6
2, 3	4-5
3, 4	5-7
	6-7

3.3 محاسبه نمودار شبکه به روش سکتور

برای محاسبه نمودار شبکه به روش سکتور، هر رویداد به چهار بخش تقسیم می شود که داده های زیر وارد می شود:

برنج. 8. برنامه چرخه زمینی

محاسبه در 5 مرحله انجام می شود (شکل 9 را ببینید):

I - شماره گذاری رویدادهای نمودار.

II - محاسبه شروع اولیه و پر کردن بخش های چپ و پایین.

III - محاسبه پایان های دیررس و پر کردن بخش مناسب.

IV - محاسبه کل (کامل) ذخیره زمان کار و پر کردن مستطیل سمت چپ زیر هر کار.

مرحله V - محاسبه زمان اختصاصی (آزاد) و پر کردن مستطیل سمت راست زیر هر اثر.

برای محاسبه ذخایر زمان، از مشتقات فرمول های شناخته شده قبلی استفاده می شود. به عنوان مثال (شکل 9 را ببینید): زمان ذخیره کل (کامل):

R i، j = t توسط ij - t i، j – t pH i، j، برای وابستگی 4-5: 12-0-9=3; برای کار 4-7: 28-8-9=11.

ذخیره زمانی خصوصی (رایگان): r i , j = t r j , k - t i , j - t r i , j , برای کار 1-3: 8-0-2=6; برای کار 2-6: 9-8-1=0.

13.01.99 14.01.99

13-2-4

شکل 4.5. نمونه ای از محاسبه دستی نمودار شبکه به روش سکتور

3.4. بهینه سازی نمودار شبکه و اتصال به تقویم

بهینه سازی برنامه شبکه به موقع باعث کاهش ارزش می شود مسیربحرانیبرای تعداد معین (مشخص) روز. برای انجام این کار، فعالیت ها در مسیر بحرانی (که در شکل 4.3 برجسته شده و در جدول 6 مشخص شده است) باید به ترتیب افزایش هزینه کاهش یابد. . قیمت کاهش (P c i, j) تعداد کارمندان در روز از مدت زمان برنامه شبکه است و با فرمول تعیین می شود.

برای نمودار نشان داده شده در شکل. 4.3 ، هزینه کاهش کار به ترتیب برابر است با: C s 1-2 \u003d 0.5. C s 2-3 = 2; C s 3-5 = 0.5; C s 5-7 = = 1.5. بنابراین کاهش مدت زمان فعالیت در مسیر بحرانی را می توان به ترتیب زیر انجام داد: 1-2، 3-5، 5-7، 2-3. طول مسیر بحرانی را کاهش دهید مقدار را تنظیم کنیدبا هزینه یک یا چند کار با افزودن همزمان تعداد کارگران به حداکثر تعداد توصیه شده، بر اساس نوع کار در جدول، امکان پذیر است. 3، بر اساس این شرط که t i، j * n i، j = const. به عنوان مثال، مقدار مسیر بحرانی نمودار شبکه که با محاسبه به دست می آید، نشان داده شده در شکل. 4.3 (T cr = 31 روز)، لازم است 6 روز کاهش یابد، زیرا مدت این مقدار کار 25 روز تعیین شده است.

ما اولویت را به کار 1-2 می دهیم، اما می توان آن را فقط 5 روز کاهش داد، زیرا مقدار را محدود کنیدبه کارگران تیپ 10 نفر داده می شود (12 * 6 = 72 نفر روز، 72:10 = 7.2 روز، 12-7.2 = 4.8 ~ 5 روز). ما یک روز دیگر را از کار 3-5 حذف می کنیم، که همان قیمت کاهش را دارد، اما مدت زمان تخمینی کمتری نسبت به کار 1-2 دارد (8 * 4 = 32 نفر-روز، 32: 7 = 4.6 ~ 5 روز) . \

پس از تغییر پارامترهای طراحی اولیه فعالیت های مسیر بحرانی (شکل 4.3 را در فعالیت های 1-2 و 3-5 ببینید)، مقدار مسیر بحرانی برابر با مدت زمان تعیین شده (25 روز) خواهد بود، اما برنامه زمان بندی نیاز به محاسبه مجدد دارد.

جزوه

وظیفه 1. مدت زمان کار را تعیین کنید، یک برنامه تقویم خطی برای جریان کار و یک نمودار از بارگیری منابع کار بسازید.

وظیفه 2. محاسبه ریتم کار نصاب و سنگ تراشی و ساخت یک سیکلوگرام از یک جریان موزون در طول ساخت قسمت زمینی یک ساختمان 6 طبقه قاب آجری. بررسی کنید که آیا کل زمان تکمیل کار روی زمین از 10 روز تجاوز نمی کند.

وظیفه 3. پارامترهای جریان غیر ریتمیک را محاسبه کنید روش ماتریسیو یک سیکلوگرام کار در تاسیسات بسازید

وظیفه 4. یک برنامه شبکه برای اجرای درون خطی کار "چرخه صفر" تهیه کنید، آن را با استفاده از روش جدولی محاسبه کنید و در شروع اولیه آن را بر اساس تاریخ شروع مشخص شده برای ساخت و ساز به تقویم پیوند دهید. امکانات:

وظیفه 5. یک قطعه از نمودار شبکه بسازید، با روش بخش محاسبه کنید و مسیر بحرانی را با یک مقدار مشخص کوتاه کنید.

کتابشناسی - فهرست کتب

1. Dikman L.G. سازمان تولید ساختمان: کتاب درسی دانشگاه های ساختمانی - م.: انتشارات DIA. 2002. - 512 ص.

2. سازماندهی و برنامه ریزی تولید ساخت و ساز / ویرایش. دکتر فنی پروفسور علوم A.K. شرایبر. - م: دانشکده تحصیلات تکمیلی. 1987.

3. محاسبه و بهینه سازی زمانبندی شبکه های ساختمانی / V.A. خدا، SI. پاولنکو، وی.یا. زلرمایر. - م: انتشارات DIA، 2001. - 240 ص.

4. SNiP 3.01.01 - 85 سازمان تولید ساخت و ساز - M.: Stroyizdat، 1981.

1. رهنمودهاسازمان از تمرین های عملی

2. مفاد نظری اصلی سازمان جریان کار 3

2.1. محاسبه و ساخت نمودار تقویم خطی 3

2.2. محاسبه پارامترها و ساخت سیکلوگرام جریان ریتمیک 4

2.3. محاسبه پارامترها و ساخت سیکلوگرام یک جریان غیر ریتمیک 6

3. ساخت و محاسبه نمودارهای شبکه 8

3.1.روش های ساخت نمودارهای شبکه 12

3.2. محاسبه نمودار شبکه با استفاده از روش جدولی 12

3.3.محاسبه نمودار شبکه به روش سکتور 13

3.4 بهینه سازی برنامه شبکه و پیوند دادن به تقویم 14

4. جزوه 15
کتابشناسی - فهرست کتب

محاسبه و تجزیه و تحلیل نمودارهای شبکه

مفاهیم و تعاریف اساسی

1.1. برنامه ریزی و مدیریت شبکه (SPM) سیستمی برای برنامه ریزی مجموعه ای از کارهای متمرکز بر دستیابی به هدف نهایی است. SPU بر اساس تصویر گرافیکیمجموعه خاصی از کارها، که منعکس کننده توالی منطقی، رابطه و مدت زمان آنها است، با بهینه سازی بعدی برنامه توسعه یافته با استفاده از روش های ریاضیات کاربردی و علوم کامپیوترو استفاده از آن برای هدایت فعلی این آثار.

هدف مدیریت در سیستم SPM تیمی از افراد است که دارای منابع خاصی (انسانی، مادی، مالی و غیره) هستند و مجموعه خاصی از کارهای (پروژه) را انجام می دهند که برای اطمینان از دستیابی به هدف مورد نظر طراحی شده است.

1.2. نمودار شبکه (مدل شبکه یا به سادگی یک شبکه) مدلی از کل فرآیند اجرای یک مجموعه ربات معین است که به عنوان یک گراف جهت دار به تصویر کشیده شده و رابطه و پارامترهای همه کارها را منعکس می کند.

1.3. کار یک فرآیند کاری است که به نتیجه ای منجر می شود و به زمان و منابع نیاز دارد. انتظار کار محسوب می شود.

انتظار کاری است که به نیروی کار (و سایر منابع) نیاز ندارد، اما نیازمند زمان است.

کار بر روی نمودار شبکه نشان داده شده است خط توپربا یک فلش

مدت زمان کار با عدد بالای فلش مشخص می شود. واحد اندازه گیری برای مدت کار می تواند یک روز، یک هفته، یک دهه، یک ماه باشد. طول فلش خودسرانه انتخاب می شود. مدت زمان کار را منعکس نمی کند. کار با رمزهای رویداد شروع و پایان نشان داده می شود ( ij). زمان کار tij.

وابستگی یا ساختگی یک رابطه منطقی بین دو یا چند رویداد است که نیازی به صرف زمان یا منابع ندارد. در نمودار، کار ساختگی با یک فلش نقطه‌دار نشان داده می‌شود.

1.4. یک رویداد نتیجه تکمیل یک یا چند کار است که شروع یک یا چند کار زیر را ممکن می سازد. این رویداد هیچ مدت زمان در زمان ندارد، این فقط به معنای واقعیت تکمیل برخی از کارها است. رویداد روی نمودار با یک دایره ( من) که داخل آن شماره آن درج شده است. رویدادی که پس از آن کار انجام می شود رویداد اولیه نامیده می شود (که با شاخص مشخص می شود - من) و قبل از آن یک ربات - نهایی ( j). یک رویداد آغازگر در شبکه وجود دارد ( جی) و یک نهایی - (ج).

I.5. مسیر هر توالی ربات است مدل شبکه، که در آن رویداد پایانی هر کار با رویداد شروع کار بعد از آن منطبق است. مسیر با شاخص ( L). مدت زمان مسیر با مجموع مدت آثار وارد شده به مسیر مشخص شده تعیین می شود و با نشان داده می شود. t(L). تشخیص مسیر کامل ( L(جی- سی))، یعنی مسیر از رویداد اولیه به رویداد نهایی، و مسیر از هر رویداد به رویداد دیگر L(متر1 - متر 2).

مسیر بحرانی مسیر کاملی است که طولانی ترین مدت زمان ممکن را در یک گراف معین − دارد L cr. در یک نمودار شبکه چندین مسیر حیاتی وجود دارد. مسیر بحرانی مهلت تکمیل مجموعه ای از کارها (کل پروژه) را تعیین می کند.

با توجه به مدل شبکه ساخته شده، برای هر کار، مدت زمان مورد انتظار اجرای آن تعیین می شود - تی oj و همچنین واریانس زمان اجرای کار - .

در سیستم STC از دو روش برای تعیین زمان اتمام کار استفاده می شود. در صورتی که کار اغلب تکرار می شود (یعنی برخی از داده های هنجاری در مورد مدت زمان آن وجود دارد)، یا نمونه اولیه به اندازه کافی نزدیک باشد، مدت زمان کار به طور منحصر به فرد تعیین می شود (شبکه هایی با تخمین های قطعی). اما برای اکثر کارهایی که برای اولین بار انجام می شود (مثلاً طراحی تحقیقاتی، آزمایشی، آزمایشی) نمی توان این کار را انجام داد. در این حالت مدت زمان کار نامحدود است و از روش هایی برای تخمین زمان لازم برای تکمیل آن استفاده می شود. آمار ریاضی. مدت زمان کار به عنوان یک متغیر تصادفی در نظر گرفته می‌شود که تابع قانون توزیع مشخصی است و زمان مورد انتظار برای تکمیل آن (و همچنین پراکندگی) با استفاده از فرمول‌های تقریبی خاصی بر اساس برآوردهای کارشناسی دریافت شده از مجریان مسئول محاسبه می‌شود. کار کردن

مدت زمان محاسبه شده به این ترتیب، با تقریبی شناخته شده است، ارزش مورد انتظارزمان اجرای آن، به عنوان یک متغیر تصادفی، مشروط به قانون پذیرفته شده توزیع آن.

در عمل STC، فرمول های زیر بیشترین کاربرد را برای تعیین مدت زمان مورد انتظار کار و پراکندگی زمان اجرای آن دارند.

در زیر سه نوع از این فرمول ها وجود دارد که با گزینه هایی برای وظایف فردی مطابقت دارد:

راه 1 ; ;

روش دوم؛ ;

راه سوم ; .

برای محاسبه بر اساس این فرمول ها از مجریان مسئول به وسیله نظرسنجی موارد زیر دریافت می شود: نظرات کارشناسیزمان کاری:

آ(یا tmin) - حداقل (خوشبینانه) مدت کار، به عنوان مثال، برآورد طول مدت کار با فرض مطلوب ترین مجموعه شرایط.

ب(یا tmax) - حداکثر مدت (بدبینانه) کار، یعنی مدت زمان کار با فرض نامطلوب ترین شرایط.

متر(یا تی n ج) - محتمل ترین تخمین مدت زمان کار - تخمین مدت زمان در معمول ترین شرایط برای انجام کار.

محاسبه پارامترهای نمودار شبکه

پارامترهای نمودار شبکه مقادیری هستند که وضعیت کار و رویدادها را مشخص می کنند که امکان تجزیه و تحلیل وضعیت کار و اتخاذ تصمیمات لازم را فراهم می کند. مدت زمان عملیات (tij) به عنوان نقطه شروع برای تعیین تمام پارامترهای زمانی مدل های شبکه عمل می کند. بر اساس مدت زمان کار در برنامه شبکه، پارامترهای زمانی آن تعیین می شود که اصلی ترین آنها به شرح زیر است.

1. زمان سفر

,

جایی که به- تعداد مشاغل موجود در این مسیر.

بنابراین، مدت زمان مسیر، کل مدت زمان فعالیت هایی است که این مسیر را تشکیل می دهند.

طول مسیر بحرانی

Тcr = تی[L(جی-سی)حداکثر] .

مدت زمان مسیر بحرانی زمان رویداد شبکه نهایی را تعیین می کند، یعنی مدت زمان پروژه (مجموعه کارهای برنامه ریزی شده) را به عنوان یک کل تعیین می کند.

2. ذخیره زمان سفر، تفاوت بین مدت زمان مسیرهای بحرانی و داده شده است. این نشان می دهد که بدون تغییر در مدت زمان پروژه ها، مدت زمان کار متعلق به این مسیر در مجموع چقدر قابل افزایش است.

آر(L) = Tcr - تی(L) .

3. مهلت اولیه برای تکمیل رویداد - دوره مورد نیاز برای تکمیل تمام کارهای قبل از این رویداد من

Tr( من) = تی[L(جی-من)حداکثر] یا Tr( j) = حداکثر .

مدت اولیه رویداد شبکه اولیه صفر در نظر گرفته می شود: Tr( جی) = 0 .

4. تأخیر برای اتمام رویداد آخرین مهلت قابل قبول برای اتمام رویداد است که بیش از مقداری آن باعث تأخیر مشابه در شروع رویداد نهایی می شود.

Tp( من) = Tcr - تی[(من-سی)حداکثر] یا Tp( من) = [Tp( j)-tij]دقیقه .

ترم پایانی رویداد نهایی برابر است با ترم اولیه آن Tp( از جانب)=Tr( از جانب)، همین امر در مورد رویدادهای واقع در مسیر بحرانی Tp( من) = Tp( من).

5. مدت زمان تکمیل یک رویداد، حداکثر مدت مجاز است که می توان بدون ایجاد افزایش در مدت زمان مسیر بحرانی (یعنی بدون تغییر زمان اتمام آن، اتمام این رویداد را به تاخیر انداخت. رویداد نهایی)، یعنی کل پروژه به عنوان یک کل.

رویدادهای مسیر بحرانی هیچ سستی ندارند. سستی رویداد به صورت زیر تعریف می شود:

آر(من) = Tp( من) - Tp( من) = آر(Lmax) .

وقفه زمانی رویداد برابر است با افت زمانی حداکثر مسیرهای عبوری از این رویداد.

6. تاریخ شروع زودهنگام، اولین تاریخ شروع ممکن برای کار است: تیآر. n.( ij) = Tp( من) .

7. زودترین پایان کار، زودترین پایان ممکن کار است

تیآر. در باره.( ij) = تیآر. n.( ij) + tij= Tp( من) + tij .

8. تاریخ شروع دیرهنگام - آخرین تاریخ شروع که در آن مدت مسیر بحرانی افزایش نمی یابد، یعنی تاریخ پایان پروژه به عنوان یک کل.

تیلیسانس.( ij) = تیبر.( ij) - tij= Tp( j) - tij .

9. تاریخ پایان دیر - آخرین تاریخ پایانی که در آن طول مسیر بحرانی افزایش نمی یابد، یعنی تاریخ پایان پروژه وجود دارد.

تیبر.( ij) = Tp( j) .

برای فعالیت های مسیر بحرانی:

تیآر. n.( ij) = تیلیسانس.( ij) و تیآر. در باره.( ij) = تیبر.( ij) .

10. ذخیره کل زمان کار مقدار ذخیره زمان حداکثر مسیرهای عبوری از این اثر است. برابر است با تفاوت بین تاریخ دیرهنگام رویداد و تاریخ اولیه رویداد، منهای مدت زمان کار.

آرپ( ij) = Tp( j) - Tp( من) - tij .

سستی کل نشان می دهد که چقدر می توان مدت یک فعالیت فردی را افزایش داد یا شروع آن را می توان به تأخیر انداخت تا مدت زمان حداکثر مسیری که از آن عبور می کند از مدت زمان مسیر بحرانی تجاوز نکند (یعنی به طوری که مدت زمان پروژه به عنوان یک کل تغییر نمی کند).

استفاده از سستی کامل در یک کار معین، تمام سستی را از فعالیت هایی که در تمام مسیرهایی که از کار می گذرد وجود دارد، می گیرد.

سستی کل برای فعالیت های مسیر بحرانی صفر و برای سایر فعالیت ها مثبت است.

11. ذخیره رایگان زمان کار - برابر با تفاوت بین تاریخ های اولیه رویدادها jو منمنهای مدت کار ( ij):

آرج( ij) = Tp( j) - Tp( من) - tij .

ذخیره رایگان بخشی از کل ذخیره زمان کار است. حداکثر زمانی را مشخص می‌کند که یک فعالیت فردی می‌تواند بدون تغییر تاریخ شروع اولیه فعالیت‌های بعدی، تمدید یا به تاخیر بیفتد، مشروط بر اینکه رویداد بلافاصله قبل در تاریخ اولیه آن رخ داده باشد.

در عین حال، با توجه به تاریخ های برنامه ریزی شده برای شروع کار، تاریخ های اولیهوقوع حوادث سستی کل وارد شده است به معنای خاصیذخیره مستقل، یعنی استفاده از آن در یکی از مشاغل، میزان ذخیره وقت آزاد سایر مشاغل شبکه را تغییر نمی دهد.

3.12. عامل استرس کاری در برنامه ریزی شبکهبرای مشخص کردن شدت زمان کار و با فرمول زیر تعیین می شود:

,

جایی که تی(Lmax) - مدت زمان حداکثر مسیر عبور از این اثر.

تی¢( L kr) - مدت زمان بخش مسیر تی(Lmax) که با مسیر بحرانی مطابقت دارد.

با کمک ضریب کشش، برآوردی از شدت کار در مسیرهایی با مدت زمان مساوی و دارای ذخایر زمانی یکسان به دست می آید.

مقدار ضریب کشش y کارهای مختلفدر شبکه در 0 £ Kn قرار دارد ( ij) £ من.

برای تمام کارهای مسیر بحرانی Kn( ij) = 1.

مقدار ضریب تنش به هنگام تعیین مهلت های برنامه ریزی شده برای اجرای کار کمک می کند تا ارزیابی کنید که چقدر آزادانه می توانید ذخیره زمان موجود را دفع کنید. این ضریب به مجریان کار درجه فوریت کار را می دهد و به شما این امکان را می دهد که ترتیب اجرای آنها را در صورتی که با اتصالات تکنولوژیکی کار تعیین نشده باشد، تنظیم کنید.

روشهای محاسبه پارامترهای نمودارهای شبکه

دو روش برای محاسبه دستی پارامترهای نمودارهای شبکه وجود دارد (علاوه بر این، در ادبیات STC انواع مختلفی از این روش ها وجود دارد): مستقیماً روی نمودار. روش جدولی

1. روش اول (محاسبه پارامترها به طور مستقیم بر روی نمودار) تعیین پارامترهای زیر را فراهم می کند. رویدادها و مسیر بحرانی هنگام محاسبه با این روش، دایره ای که رویداد را نشان می دهد به چهار بخش تقسیم می شود. بخش بالایی برای شماره رویداد رزرو شده است - من، بخش سمت چپ برای دوره اولیه رویداد Tr( من، درست برای تاریخ اتمام دیرهنگام رویداد Tp( من، و بخش پایین تر برای زمان ذخیره رویداد - آر(من)

پارامترها بر اساس تعاریف و فرمول های فوق (روابط منطقی) محاسبه می شوند قوانین خاص. محاسبه با تعیین تاریخ های اولیه برای اتمام رویدادها آغاز می شود - Tp( من). تعریف Tp( من) از رویداد اولیه شروع می شود و سپس از طریق رویدادهای بعدی به رویداد نهایی می رسد (یعنی محاسبه از چپ به راست انجام می شود) که توسط موارد زیر هدایت می شود. قانون کلیبرای تعیین تاریخ های اولیه رویدادها

تاریخ اتمام زودهنگام رویداد jبا افزودن به تاریخ اولیه رویداد قبل از آن تعیین می شود منمدت زمان کار منتهی به رویداد j. در صورتی که رویداد jشامل چندین اثر است، شما باید تاریخ اولیه هر یک از این آثار را تعیین کنید و حداکثر از بین آنها را انتخاب کنید که تاریخ اولیه برای اتمام رویداد خواهد بود. j. برای رویداد اصلی جیاولین تاریخ سررسید صفر در نظر گرفته می شود.

Tp( جی) = 0 .

تعیین تاریخ های دیرهنگام برای اتمام رویدادها به ترتیب معکوس انجام می شود، یعنی از راست به چپ، یعنی از رویداد نهایی تا اولیه. هنگام تعیین تاریخ های دیرهنگام، فرض بر این است که برای رویداد نهایی، زودترین تاریخ برای اتمام آن نیز آخرین است.

Tr( از جانب) = Tp( از جانب) .

تاریخ اتمام دیرهنگام رویداد jبا کسر از تاریخ دیرهنگام رویداد قبل از آن تعیین می شود منمدت کار منتهی به این رویداد j.

در صورت وقوع jاگر چند اثر مناسب باشد، ارزش تاریخ تأخیر برای هر یک از این آثار مشخص می‌شود و حداقل از بین آنها انتخاب می‌شود که تاریخ تأخیر برای اتمام این رویداد را مشخص می‌کند.

سستی رویداد منمستقیماً در شبکه با کم کردن مقدار ثبت شده در بخش سمت راست رویداد تعیین می شود Tp( من) مقدار نوشته شده در بخش چپ - Тр( من). مقدار یافت شده ذخیره زمانی برای رویداد است و در بخش پایین رویداد ثبت می شود.

همه رویدادهای شبکه، به استثنای رویدادهای مسیر بحرانی، سستی دارند. مسیر بحرانی در نتیجه شناسایی همه رویدادهای متوالی با ذخایر برابر صفر و مدت زمان آن بر اساس ارزش مهلت دیرهنگام (همچنین زودترین) برای تکمیل رویداد نهایی تعیین می شود.

روی انجیر 1 محاسبه شبکه را مستقیماً روی نمودار نشان می دهد.

برنج. 1. محاسبه پارامترهای نمودار شبکه

2. با روش محاسبه جدولی، به عنوان یک قاعده، پارامترهای مربوط به کار تعیین می شود، یعنی: تاریخ های اولیه و دیرهنگام شروع و پایان کار، ذخیره زمان کار. محاسبه پارامترها در این مورد در جدول مطابق با فرم معین. نمونه ای از چنین محاسبه ای برای نمودار شبکه نشان داده شده در شکل. 1 در جدول زیر نشان داده شده است. یکی

محاسبه به صورت جدولی یا فقط بر اساس فرمول ها و نمودار شبکه با پارامترهای رویداد یا بر اساس قوانین خاص (الگوریتم) قابل انجام است. در مورد دوم، ترکیب پارامترها و ترتیب ترتیب آنها ممکن است متفاوت باشد. محاسبه با چنین الگوریتم هایی در ادبیات شرح داده شده است (به منابع مراجعه کنید).

میز 1

محاسبه پارامترهای کار نمودار شبکه

من-j	مدت کار، tij	شروع زود هنگام، تیآر. n	پایان زودهنگام کار تیآر. در باره.	دیر شروع کار تیلیسانس.	دیر اتمام کار تیبر.	ذخایر زمان	ضریب شدت کار، به n
پر شده، آرپ	رایگان، آربا

تجزیه و تحلیل و بهینه سازی نمودار شبکه

پس از محاسبه پارامترهای نمودار شبکه، آنالیز شده و در موارد ضروری، بهینه سازی آن اهداف تجزیه و تحلیل، تجدید نظر در ساختار شبکه به منظور تعیین امکان افزایش تعداد کار موازی، تعیین ضرایب شدت کار است که همراه با محاسبه ذخایر زمان کار و مسیرها، امکان توزیع را فراهم می کند. همه کار بر اساس مناطق (بحرانی، زیر بحرانی و ذخیره). یکی از وظایف مهم تحلیل شبکه، تعیین احتمال تکمیل رویداد نهایی در یک زمان معین است.

مهلت مشخص شده برای تکمیل رویداد نهایی (یعنی مهلت پروژه) Td ممکن است با Tcr محاسبه شده بر اساس مسیر بحرانی متفاوت باشد، اما با وجود این (به دلیل این واقعیت است که مدت زمان مورد انتظار کار به عنوان متغیرهای تصادفی تعیین شد)، احتمال مشخصی وجود دارد که رویداد پایانی در زمان دستور داده شده یا قبل از آن رخ دهد. هنگام تعیین این احتمال، فرض می شود که مدت زمان پروژه (یعنی مقدار مسیر بحرانی) یک متغیر تصادفی است که از آن تبعیت می کند. قانون عادیتوزیع

احتمال تحلیلی که رویداد نهایی در یا قبل از یک زمان معین (دستورالعمل) رخ دهد به صورت زیر تعیین می شود:

,

جایی که - مقدار مربوط به تابع Ф( ز) از جدول گرفته شده است توزیع نرمال; زآرگومان تابع توزیع احتمال نرمال است.

ریشه میانگین مربع انحراف مدت وقوع رویداد نهایی با فرمول تعیین می شود:

,

جایی که ij cr دنباله ای از فعالیت ها در مسیر بحرانی است.

به- تعداد فعالیت هایی که مسیر بحرانی را تشکیل می دهند.

واریانس کار در مسیر بحرانی.

مثال.برای نمودار نشان داده شده در شکل. 1، احتمال تکمیل پروژه در یک مهلت معین، معادل 8 واحد را تعیین کنید. زمان. قبلا مشخص شده بود که زمان تخمینی اتمام پروژه Tcr = 9 واحد است. فرض کنید واریانس کارهایی که مسیر بحرانی را تشکیل می دهند نیز تعریف شده اند، به عنوان مثال:

سپس و .

استفاده از جدول مقادیر تابع لاپلاس در قدر ز= - 1.7 (جدول 2 را ببینید)، احتمال مورد نظر RK » 0.045 را پیدا می کنیم.

نتیجه.هنگام برنامه ریزی در سیستم های SPM، فرض بر این است که اگر:

0,85 < РК < 0,65 - то это считается границами допустимого риска (то есть считается нормальным положением); при РК < 0,85 - то считается, что опасность нарушения заданного срока очень большая (неприемлема) и необходимо в этом случае и произвести повторное планирование с перераспределением ресурсов с целью минимизации срока выполнения проекта; при РК >0.65 - احتمال خیلی زیاد در نظر گرفته می شود، یعنی منابع اضافی در مشاغل مسیر بحرانی وجود دارد. در این صورت برنامه ریزی مجدد نیز به منظور کاهش منابع مورد نیاز انجام می شود.

اگر دستیابی به مقدار رضایت بخش QM غیرممکن باشد، ممکن است نیاز به تغییر مهلت پروژه داده شده باشد. این مشکل برعکس موردی که در بالا توضیح داده شد حل می شود. با توجه به مقدار مورد نظر احتمال RC برای تکمیل رویداد نهایی در یک زمان معین، می توان مقدار تابع را از معادله بالا تعیین کرد. و با دانستن مقادیر Tcr و مقدار Td را تعیین کنید.

پس از تجزیه و تحلیل نمودار شبکه، در صورت لزوم، بهینه سازی آن انجام می شود. لازم است اطمینان بیشتر از اتمام رویداد نهایی در یک زمان معین، برای یکسان سازی حجم کار کارگران، تخصیص بهتر منابع و غیره تضمین شود. منابع) با انتقال منابع از مسیرهای غیر بحرانی با داشتن ذخایر زمانی در مسیر بحرانی انجام می شود که منجر به کاهش مدت زمان آن می شود. در محدوده مدت، تمام مسیرهای کامل می توانند برابر و بحرانی باشند و سپس تمام کارها با ولتاژ یکسان انجام می شود و کل زمان پروژه به میزان قابل توجهی کاهش می یابد.

جدول 2

جدول مقادیر تابع لاپلاس Рк = Ф ( ز)

• 1. مسیر بحرانی را انتخاب کنید و طول آن را بیابید.
• 2. تعیین زمان ذخیره برای هر رویداد.
• 3. ذخایر زمانی همه کارها و ضریب شدت کار کار ماقبل آخر را تعیین کنید.

راه حل

برای حل مشکل، نماد زیر را اعمال می کنیم.

عنصر شبکه	نام پارامتر	نماد پارامتر
رویداد I	تاریخ اتمام زودهنگام رویداد
تاریخ اتمام دیرهنگام رویداد
سستی رویداد
کار (i، j)	زمان کار
زمان شروع زودهنگام
پایان زودهنگام کار
زمان شروع دیرهنگام
دیر پایان کار
ذخیره کامل زمان اجرا
	زمان سفر
طول مسیر بحرانی
رزرو زمان سفر

برای تعیین ذخایر زمانی برای رویدادهای شبکه، اولین t p و آخرین تاریخ t p برای تکمیل رویدادها محاسبه می شود. هیچ رویدادی نمی‌تواند قبل از تکمیل همه رویدادهای قبل از آن و تکمیل نشدن تمام کارهای قبلی رخ دهد. بنابراین، زمان اولیه (یا مورد انتظار) tp(i) رویداد i با طول مدت حداکثر مسیر قبل از این رویداد تعیین می شود:

t p (i) = max(t(L ni)) (1)

که در آن L ni هر مسیری است که قبل از رویداد i-ام است، یعنی مسیری از اولیه تا رویداد i-ام شبکه.

اگر رویداد j چندین مسیر قبلی و در نتیجه چندین رویداد قبلی i داشته باشد، پیدا کردن تاریخ اولیه برای تکمیل رویداد j با استفاده از فرمول راحت است:

t p (j) = حداکثر (2)

تأخیر در تکمیل رویداد i نسبت به تاریخ اولیه آن تأثیری بر زمان اتمام رویداد نهایی (و در نتیجه زمان اتمام مجموعه آثار) تا زمان جمع‌بندی زمان اتمام این رویداد نخواهد داشت. مدت (طول) حداکثر مسیرهای زیر از طول مسیر بحرانی تجاوز نمی کند. بنابراین، مدت تأخیر (یا حد) t p (i) تکمیل رویداد i برابر است با:

t p (i) = t kp - max(t(L ci)) (3)

که در آن Lci هر مسیری است که از رویداد i-ام پیروی می کند، i.e. مسیر از i-امین تا رویداد شبکه نهایی.

اگر رویداد i چندین مسیر بعدی داشته باشد و در نتیجه چندین رویداد بعدی j داشته باشد، تاریخ تکمیل دیرهنگام رویداد i را می‌توان به راحتی با استفاده از فرمول پیدا کرد:

t p (i) = min

ذخیره زمانی R(i) رویداد i به عنوان تفاوت بین تاریخ‌های دیرهنگام و اولیه تکمیل آن تعریف می‌شود:

R(i) = t p (i) - t p (i)

سستی رویداد نشان می دهد که چه مدت می توان رویداد را بدون افزایش مدت بسته کاری به تاخیر انداخت.

رویدادهای بحرانی سستی ندارند، زیرا هرگونه تأخیر در تکمیل یک رویداد در مسیر بحرانی باعث همان تأخیر در تکمیل رویداد نهایی می شود. بنابراین، با تعیین مدت اولیه رویداد نهایی شبکه، طول مسیر بحرانی را تعیین می کنیم.

هنگام تعیین زمان اولیه رویدادهای tp(i)، در طول نمودار شبکه از چپ به راست حرکت می کنیم و از فرمول های (1)، (2) استفاده می کنیم.

محاسبه زمان وقایع

برای i=0 (رویداد اولیه)، بدیهی است tp(0)=0.

i=1: t p (1) = t p (0) + t(0,1) = 0 + 0 = 0.

i=2: t p (2) = t p (1) + t(1,2) = 0 + 8 = 8.

i=3: t p (3) = t p (1) + t (1,3) = 0 + 3 = 3.

i=4: max(t p (2) + t(2,4);t p (3) + t(3,4)) = max(8 + 6;3 + 3) = 14.

i=5: tp(5) = tp(4) + t(4,5) = 14 + 0 = 14.

i=6: max(t p (4) + t(4,6);t p (5) + t(5,6)) = max(14 + 5;14 + 3) = 19.

i=7: t p (7) = t p (6) + t(6,7) = 19 + 9 = 28.

i=8: max(t p (2) + t(2.8);t p (6) + t(6.8);t p (7) + t(7.8)) = max(8 + 18;19 + 5; 28 + 4 ) = 32.

i=9: max(t p (5) + t(5,9);t p (7) + t(7,9)) = max(14 + 2;28 + 4) = 32.

i=10: max(t p (4) + t(4,10);t p (7) + t(7,10);t p (9) + t(9,10)) = max(14 + 4;28) + 2؛ 32 + 0) = 32.

i=11: max(t p (8) + t(8,11);t p (10) + t(10,11)) = max(32 + 12;32 + 4) = 44.

طول مسیر بحرانی برابر با تاریخ تکمیل اولیه رویداد نهایی 11 است: t kp =tp(11)=44

هنگام تعیین تاریخ های دیرهنگام برای اتمام رویدادهای t p (i)، در شبکه در جهت مخالف حرکت می کنیم، یعنی از راست به چپ، و از فرمول های (3)، (4) استفاده می کنیم.

برای i=11 (رویداد نهایی)، تاریخ تأخیر رویداد باید برابر با تاریخ اولیه آن باشد (در غیر این صورت، طول مسیر بحرانی تغییر خواهد کرد): t p (11) = t p (11) = 44

i=10: t p (10) = t p (11) - t (10،11) = 44 - 4 = 40.

i=9: t p (9) = t p (10) - t(9،10) = 40 - 0 = 40.

تمام خطوطی که با شماره 8 شروع می شوند بررسی می شوند.

i=8: t p (8) = t p (11) - t(8،11) = 44 - 12 = 32.

تمام خطوطی که با شماره 7 شروع می شوند بررسی می شوند.

i=7: min(t p (8) - t(7.8);t p (9) - t(7.9);t p (10) - t(7.10)) = min(32 - 4;40 - 4;40 - 2 ) = 28.

i=6: min(t p (7) - t(6.7);t p (8) - t(6.8)) = min(28 - 9؛ 32 - 5) = 19.

تمام خطوطی که با شماره 5 شروع می شوند بررسی می شوند.

i=5: min(t p (6) - t(5.6);t p (9) - t(5.9)) = min(19 - 3;40 - 2) = 16.

i=4: min(t p (5) - t(4.5);t p (6) - t(4.6);t p (10) - t(4.10)) = min(16 - 0;19 - 5;40 - 4 ) = 14.

تمام خطوطی که با شماره 3 شروع می شوند از طریق بررسی می شوند.

i=3: t p (3) = t p (4) - t(3،4) = 14 - 3 = 11.

i=2: min(t p (4) - t(2.4);t p (8) - t(2.8)) = min(14 - 6؛ 32 - 18) = 8.

i=1: min(t p (2) - t(1,2);t p (3) - t(1,3)) = min(8 - 8;11 - 3) = 0.

(0,1): 0 - 0 = 0;

جدول 1 - محاسبه ذخیره رویدادها

شماره رویداد	زمان رویداد: tp(i) اولیه	تاریخ برگزاری: late tp(i)	ذخیره زمانی، R(i)

پر کردن جدول 2

فهرست آثار و مدت زمان آنها به ستون دوم و سوم منتقل می شود. در این حالت، کار باید به ترتیب در ستون 2 ثبت شود: ابتدا از شماره 0 شروع کنید، سپس از شماره 1 و غیره.

در ستون دوم، عددی را قرار می‌دهیم که تعداد آثار بلافاصله قبل (KPR) را برای رویدادی که کار مورد نظر از آن شروع می‌شود، مشخص می‌کند.

بنابراین، برای کار (1،2) در ستون 1 عدد 1 را قرار می دهیم، زیرا شماره 1 به پایان می رسد 1 کار: (0,1).

ستون 4 از جدول 1 (t p (i)) بدست می آید. ستون 7 از جدول 1 (t p (i)) بدست آمده است.

مقادیر ستون 5 با جمع ستون های 3 و 4 به دست می آید.

در ستون 6، شروع دیرهنگام کار به عنوان تفاوت بین اتمام دیرهنگام این کارها و مدت زمان آنها تعریف شده است (داده های ستون 3 از مقادیر ستون 7 کم می شود).

محتوای ستون 8 (سستی کل R(ij)) برابر است با تفاوت بین ستون های 6 و 4 یا ستون های 7 و 5. اگر R(ij) برابر با صفر باشد، کار بسیار مهم است.

جدول 2 - تحلیل مدل شبکه در طول زمان

کار (i,j)	تعداد کارهای قبلی	مدت زمان tij	تاریخ های اولیه: شروع tijR.N.	تاریخ های اولیه: پایان tijР.О.	تاریخ های متاخر: شروع tijP.N.	تاریخ های متاخر: پایان tijP.O.	ذخیره زمان: RijP کامل	ذخیره زمانی مستقل Rij	ذخیره خصوصی از نوع اول Rij1	رزرو خصوصی نوع II، RijC

لازم به ذکر است که علاوه بر ذخیره کامل زمان عملیاتی، سه نوع ذخیره دیگر نیز وجود دارد. وقفه زمانی خصوصی از نوع اول R 1 - بخشی از شلی زمان کل، که با آن می توان مدت زمان کار را بدون تغییر تاریخ دیرهنگام رویداد اولیه آن افزایش داد. R 1 با فرمول پیدا می شود:

R(i,j)= R p (i,j) - R(i)

سستی جزئی نوع دوم یا شلی آزاد Rc کار (i, j) بخشی از سستی کل است که با آن می توان مدت زمان کار را بدون تغییر تاریخ اولیه رویداد پایان آن افزایش داد. Rc با فرمول پیدا می شود:

R(i,j)= Rn (i,j) - R(j)

مقدار شلی زمان اجرای آزاد نشان دهنده محل شلی مورد نیاز برای بهینه سازی است.

ذخیره زمانی مستقل Rn کار (i, j) بخشی از کل ذخیره به دست آمده برای موردی است که تمام کارهای قبلی دیر به پایان می رسد و همه کارهای بعدی زود شروع می شوند. Rn با فرمول پیدا می شود:

R(i,j)= Rп(i,j) - R(i) - R(j)

مسیربحرانی: (0,1)(1,2)(2,4)(4,6)(6,7)(7,8)(8,11)

مدت زمان مسیر بحرانی: 44

بیایید ضریب شدت کار کار ماقبل آخر را پیدا کنیم. از آنجایی که طول مسیر بحرانی 44 است، حداکثر مسیر عبور از کار (1،10) 32 است، پس

K(1.10)=(32-28)/(44-28)=0.296.

4. ISP در شهر کوچکدارای 5 کانال خدمات اختصاصی. به طور متوسط ​​25 دقیقه طول می کشد تا به یک مشتری خدمات رسانی شود. این سیستم به طور متوسط ​​6 acza در ساعت دریافت می کند. اگر کانال رایگان وجود نداشته باشد، رد می شود. مشخصه های سرویس را تعیین کنید: احتمال خرابی، میانگین تعداد خطوط ارتباطی اشغال شده توسط سرویس، توان عملیاتی مطلق و نسبی، احتمال سرویس. پیدا کردن تعداد کانال های اختصاصی که برای آن نسبی توان عملیاتیسیستم حداقل 0.95 خواهد بود. فرض کنید که جریان درخواست ها و خدمات ساده ترین هستند

شدت جریان سرویس:

شدت بار:

c \u003d l * t obs \u003d 6 * 25/60 \u003d 2.5

شدت بار c=2.5 درجه سازگاری بین جریان ورودی و خروجی درخواست های کانال سرویس را نشان می دهد و پایداری سیستم صف را تعیین می کند.

احتمال اینکه سرویس:

کانال 1 مشغول است:

p 1 = با 1/1! p 0 = 2.5 1/1! * 0.0857 = 0.214

2 کانال اشغال شده است:

p 2 \u003d c 2 / 2! p 0 = 2.5 2/2! * 0.0857 = 0.268

3 کانال اشغال شده است:

p 3 \u003d c 3 / 3! p 0 = 2.5 3/3! * 0.0857 = 0.223

4 کانال اشغال شده است:

p 4 = با 4 / 4! p 0 = 2.5 4/4! * 0.0857 = 0.139

5 کانال اشغال شده است:

p 5 = با 5 / 5! p 0 = 2.5 5/5! * 0.0857 = 0.0697

احتمال شکست کسری استدرخواست های رد شده:

این بدان معناست که 7 درصد از درخواست های دریافتی برای خدمات پذیرفته نمی شوند.

احتمال سرویس دهی به درخواست های دریافتی-احتمال اینکه به مشتری خدمات داده شود:

در سیستم های دارای خرابی، رویدادهای خرابی و تعمیر و نگهداری هستند گروه کاملرویدادها، بنابراین:

p open + p obs = 1

توان نسبی Q = p obs .

p obs \u003d 1 - p otk \u003d 1 - 0.0697 \u003d 0.93

در نتیجه به 93 درصد درخواست‌های دریافتی رسیدگی می‌شود. میانگین تعداد کانال های اشغال شده توسط سرویس

n s \u003d s * p obs \u003d 2.5 * 0.93 \u003d 2.326 کانال.

میانگین کانال های بیکار.

n pr \u003d n - n z \u003d 5 - 2.326 \u003d 2.7 کانال.

نرخ اشغال کانال سرویس.

بنابراین سیستم 50 درصد مشغول تعمیر و نگهداری است.

پهنای باند مطلق

A \u003d pobs * l \u003d 0.93 * 6 \u003d 5.581 برنامه در ساعت.

میانگین زمان بیکاری QS.

t pr \u003d p otk * t obs \u003d 0.0697 * 0.417 \u003d 0.029 ساعت.

میانگین تعداد درخواست های ارائه شده.

L obs \u003d s * Q \u003d 2.5 * 0.93 \u003d 2.326 واحد.

میانگین زمان اقامت یک درخواست در CMO(فرمول لیتل).

تعداد درخواست های رد شده در یک ساعت: l * p 1 = 0.418 درخواست در ساعت.

عملکرد اسمی QS: 5 / 0.417 = 12.002 برنامه در ساعت.

عملکرد واقعی CMO: 5.581 / 12.002 = 47٪ از عملکرد اسمی.

بیایید تعداد کانال های مورد نیاز برای اطمینان از عملکرد سیستم را با احتمال P ? 0.95

برای انجام این کار، n را از شرط پیدا می کنیم:

بیایید این احتمال را پیدا کنیم که اگر 6 کانال در سیستم وجود داشته باشد و همه آنها مشغول باشند:

با کمک این برنامه شما می توانید پارامترهای نمودار شبکه را به صورت آنلاین تعیین کنید(زمان رویدادها، ذخایر زمانی و مسیر بحرانی را محاسبه کنید)، ضرایب کشش را بیابید. بهینه سازی برنامه شبکه با توجه به معیارهای زیر انجام می شود: تعداد مجریان، ذخیره-هزینه ها، کاهش شرایط.
یک نمودار شبکه را می توان ترسیم کرد و همچنین می توان آن را در قالب یک ماتریس یا جدول تنظیم کرد (منوی عملیات).

ابعاد بوم گرافیکی

عرض ارتفاع

● ■ ▲ ⊗ ↔ ✍ ⊗

پارامترهای مدل شبکه (مسیر بحرانی، ذخایر زمانی، ساخت نمودار گانت و موارد دیگر).

برای نمودار تولید شده، می توانید اقدامات زیر را انجام دهید:

محاسبه ضرایب کشش
یک نمودار گانت بسازید به تاریخ بپیوندید
حل به روش بخشی
راه حل بالقوه
بهینه سازی برنامه شبکه با توجه به معیار تعداد ذخایر مجری-کاهش هزینه های شرایط
ایجاد مستندات فنی
احتمال تکمیل کل مجموعه کارها را برای روزها
حداکثر زمان ممکن برای اتمام کل مجموعه کارها را با احتمال تخمین بزنید %

دفترچه راهنمای خدمات

برای افزودن راس به بوم گرافیکی، از دکمه Add مربوط به شکل استفاده کنید. همچنین می توان یک شی جدید را ابتدا با انتخاب دکمه سمت چپ ماوس و سپس کلیک بر روی فضای کاری وارد کرد. شماره گذاری رئوس می تواند از 0 شروع شود، برای این کار باید تیک مورد شماره گذاری رئوس شماره 1 را بردارید.
1 2 3 4 1 10 30 15
شماره گذاری راس از 0 شروع می شود
0 1 2 3 1 10 30 15
برای اتصال رئوس ابتدا باید آنها را انتخاب کنید (یک کلیک روی شی) و سپس دکمه Connect را بزنید.
مدل شبکه را می توان به صورت جدولی و به صورت ماتریس وزن (ماتریس فاصله) ارائه کرد. برای استفاده از داده های مشاهده، منوی عملیات را انتخاب کنید.

تعاریف اساسی

گراف جهت دار، که در آن فقط یک راس وجود دارد که کمان ورودی ندارد و فقط یک راس است که قوس خروجی ندارد. شبکه نامیده می شود. شبکه ای که مجموعه آثار را مدل سازی می کند، آن نامیده می شود مدل شبکه یا نمودار شبکه. قوس های متصل کننده رئوس نمودار در جهت دستیابی به نتیجه در اجرای مجموعه ای از کارها جهت گیری می کنند.
رایج ترین روش برای نمایش مجموعه شبیه سازی شده از آثار بر حسب آثار و رویدادها.
مفهوم "کار" معانی زیر را دارد:

• "کار واقعی" - فرآیندی که به زمان و منابع نیاز دارد.
• "کار ساختگی" یک رابطه منطقی بین دو یا چند شغل است که نشان می دهد شروع یک کار به نتایج کار دیگر بستگی دارد. کار ساختگی نیازی به زمان و منابع ندارد، مدت زمان آن صفر است.

کار روی نمودار با یک فلش نشان داده می شود که در بالای آن زمان صرف شده روی آن نشان داده شده است. طول فلش و جهت آن روی نمودار مهم نیست. فقط مطلوب است که جهت فلش ها را حفظ کنید تا اولیهرویداد to work (که با i مشخص می شود) در سمت چپ در نمودار شبکه قرار داشت و نهایی(با j نشان داده شده است) - در سمت راست. برای نمایش آثار ساختگی از فلش‌های نقطه‌دار استفاده می‌شود که روی آن‌ها زمان نشان داده نمی‌شود یا صفر گذاشته می‌شود.

در مدل شبکه، رویدادها با رئوس نمودار مطابقت دارند.

قوانین ساخت مدل شبکه

قانون 1. هر عملیات در شبکه با یک و تنها یک کمان (فلش) نشان داده می شود. هیچ یک از عملیات نباید دو بار در مدل ظاهر شود. در این مورد، باید بین حالتی که هر عملیاتی به قطعات تقسیم می شود، تمایز قائل شد. سپس هر قسمت با یک قوس جداگانه نشان داده می شود.

قانون 2. هیچ جفت عملیاتی نباید با یک رویداد شروع و پایان تعریف شود. امکان تعریف مبهم عملیات از طریق رویدادها زمانی ظاهر می شود که دو یا بیشترعملیات را می توان به طور همزمان انجام داد.

قانون 3. هنگام گنجاندن هر عملیات در یک مدل شبکه، برای اطمینان از ترتیب صحیح، باید به سوالات زیر پاسخ داده شود:
الف) چه عملیاتی باید بلافاصله قبل از شروع عملیات مورد نظر تکمیل شود؟
ب) پس از اتمام این عملیات بلافاصله چه عملیاتی باید دنبال شود؟
ج) چه عملیاتی را می توان همزمان با عملیات مورد نظر انجام داد؟

هنگام ساخت یک نمودار شبکه، قوانین زیر باید رعایت شود:

• در شبکه نباید "بن بست" وجود داشته باشد، به عنوان مثال، رویدادهایی که هیچ کاری از آنها شروع نمی شود، به جز رویداد نهایی نمودار.
• در نمودار شبکه نباید رویدادهای "دم" وجود داشته باشد، یعنی رویدادهایی که حداقل یک اثر قبل از آنها نباشد، به استثنای اثر اصلی.
• شبکه نباید دارای حلقه های بسته باشد (شکل 1).
• هر دو رویداد نباید بیش از یک اثر مستقیماً مرتبط باشند.
• در یک شبکه، داشتن یک رویداد شروع و یک رویداد پایانی توصیه می شود.
• نمودار شبکه باید ساده باشد. یعنی رویدادها و مشاغل باید طوری قرار بگیرند که برای هر شغلی، رویداد قبلی در سمت چپ قرار داشته باشد و نسبت به رویدادی که این کار را به پایان می رساند، عدد کمتری داشته باشد.

ساخت نمودار شبکه با تصویر رویداد اولیه شروع می شود که با عدد 1 نشان داده شده و دایره می شود. فلش ها از رویداد شروع پرتاب می شوند که مربوط به فعالیت هایی است که هیچ فعالیت دیگری قبل از آنها وجود ندارد. طبق تعریف، لحظه اتمام کار یک رویداد است. بنابراین، هر فلش
با یک دایره به پایان می رسد - رویدادی که در آن شماره این رویداد اضافه شده است. شماره گذاری رویدادها دلخواه است. در مرحله بعدی ساخت، آثاری را به تصویر می‌کشیم که قبل از آن‌ها آثاری از قبل طراحی شده‌اند (یعنی متکی به کارهای ساخته شده از قبل) و غیره. نمودار شبکه، که هیچ کاری بر آن تکیه ندارد. ساخت و ساز به پایان رسیده است، سپس لازم است نمودار شبکه ساده شود.

روش های بهینه سازی گراف شبکه

توصیف منطقی-ریاضی، تشکیل برنامه ها و اقدامات کنترلی بر اساس استفاده از یک کلاس خاص از مدل ها انجام می شود. مدل های شبکه.
پس از ساخت و محاسبه زمانبندی شبکه (تعیین پارامترهای آن)، انجام تجزیه و تحلیل برنامه، که شامل ارزیابی امکان سنجی و ساختار آن، ارزیابی حجم کاری مجریان، ارزیابی احتمال وقوع رویداد نهایی در یک دوره معین است، باید بهینه سازی برنامه شبکه را شروع کنید. روش بهینه سازی عبارت است از تطبیق برنامه با مهلت های داده شده برای اتمام کار، توانایی های پیمانکاران و غیره. AT مورد کلیبهینه سازی باید به عنوان فرآیند بهبود سازمان کار درک شود.

برای اینکه بتوان مدل شبکه را بهینه کرد، تمامی داده های اولیه به صورت جدول (عملیات / افزودن به شکل جدول) وارد می شوند.

• بهینه سازی مدل شبکه با توجه به معیار «تعداد مجری». ستون تعداد اجراکنندگان پر می شود H
• بهینه سازی مدل شبکه با توجه به معیار «هزینه ها». ستون ضریب هزینه برای تسریع کار پر شده است، h(i,j) .
• بهینه سازی نمودار شبکه به روش "زمان - هزینه". ستون‌های t opt، حداقل زمان کار، t min، هزینه عادی، Cn و هزینه ثابت، Cc پر شده‌اند.

نمونه هایی از مدل های شبکه

با استفاده از مثال پخت گل گاوزبان مرغ، گزینه هایی را برای نمودارهای شبکه از زمینه آشپزی در نظر بگیرید. الف) پختن در قابلمه معمولی
10 2 3 4 5 1 10 30 15 7
آثار:

1.3: مرغ را بجوشانید، 30 دقیقه.
2.3: کلم را بگذارید و 10 دقیقه بپزید.
3.4: 1/2 چغندر، هویج و سیب زمینی قرار دهید. 15 دقیقه بجوشانید.
4.5: بقیه چغندر، پیاز، سبزی را اضافه کنید. 7 دقیقه بجوشانید.
ب) پختن در ظرف با افکت فر روسی (ته سه لایه، درب بدون سوراخ) 1 2 3 4 5 10 10 20 30 60
آثار:
1.2: تمیز کردن سبزیجات (کلم، هویج، سیب زمینی، چغندر، پیاز)، 10 دقیقه.
1.4: مرغ را در یک قابلمه معمولی، 30 دقیقه بجوشانید.
2.3: سبزی ها را در ظرف مخصوص بریزید، 3 قاشق غذاخوری آب اضافه کنید، تا 70 درجه سانتیگراد حرارت دهید و 10 دقیقه خاموش کنید.
3.4: پختن سبزیجات در آب خود، 20 دقیقه.
4.5: سبزیجات پخته شده را به مرغ اضافه کنید. دم کرده 60 دقیقه

کتابشناسی - فهرست کتب

1. Mushik E., Muller P. روشهای اتخاذ تصمیمات فنی. مطابق. با او. – م.: میر، 1990.
2. طاها ح. مقدمه ای بر تحقیق در عملیات. در 2 کتاب کتاب. 2. پر. از انگلیسی. - م.: میر، 1985.
3. مدیریت در سیستم های RAV: کتاب درسی. -L.: نشر نظامی، 1980.

ویژگی های راس

متن

اندازه رنگ

ضخامت رنگ

خط چین - - - -
ابعاد در px و پس زمینه

w ساعت

لغو کنید

اتصال (قوس)

متن (وزن)

اندازه رنگ

ضخامت رنگ

خط چین - - -
نشانگر پایان →

هر دنباله ای از فعالیت های شبکه که در آن رویداد پایانی هر فعالیت با رویداد شروع فعالیت پس از آن منطبق باشد، نامیده می شود. از طریق.

مسیر شبکه ای که نقطه شروع همان رویداد شروع و نقطه پایان آن رویداد پایان است فراخوانی می شود کامل.

مسیر از رویداد اصلی تا هر اتفاقی که گرفته شده است قبل ازاین رخداد. یک مسیر پیش از رویداد که دارد بیشترین طول، نامیده میشود حداکثر قبلی. با L 1 (i) نشان داده می شود و مدت آن t است.

مسیری که هر رویداد داده شده را به رویداد نهایی متصل می کند نامیده می شود متعاقبمسیر. این طولانی ترین مسیر نامیده می شود تا آنجا که ممکن است بعدیو با L 2 (i) نشان داده می شود، و مدت آن t است.

مسیر کامل با طولانی ترین طول نامیده می شود بحرانی. مسیرهایی غیر از مسیر بحرانی نامیده می شوند آرام. آنها ذخیره زمانی دارند.

فعالیت ها در مسیر بحرانی با خطوط ضخیم یا خطوط دوتایی برجسته می شوند. مدت زمان مسیر بحرانی پارامتر اصلی نمودار در نظر گرفته می شود.

الگوریتمی را برای تعیین مسیر بحرانی در نمودار شبکه با استفاده از الگوریتم روش برنامه نویسی پویا در نظر بگیرید.

رئوس نمودار را بر اساس رتبه ها مرتب کرده و از انتها به ابتدا شماره گذاری می کنیم. این امکان تطبیق اعداد رتبه را با مراحل حرکت به عقب در هنگام یافتن کنترل‌های بهینه شرطی در مورد آخر، دو مورد آخر و غیره فراهم می‌کند. مراحل یافتن مسیر بحرانی با استفاده از مثال نمودار شبکه نشان داده شده در شکل 1 تجزیه و تحلیل خواهد شد. 10.7.

بر اساس اصل بهینه سازی بلمن، کنترل بهینه در هر مرحله با هدف کنترل و وضعیت ابتدای مرحله تعیین می شود. وضعیت نظام حوادثی است که در صفوف است. برای تکمیل رویداد نهایی X 16 باید رویدادهای قبلی تکمیل شود. حالت های احتمالی سیستم در ابتدای آخرین مرحله کار - وقوع رویدادهای X 14 و X 15. در دایره های نقاط X 14 و X 15 حداکثر مدت زمان کار را در آخرین مرحله قرار می دهیم: X 14 5 , X 15 7 . اجازه دهید حداکثر مدت زمان کار را در دو مرحله آخر پیدا کنیم. وضعیت سیستم در ابتدای مرحله ماقبل آخر ناشی از رویداد X 13 است. حداکثر مدت مسیر منتهی به X 13 به X 16 است.

بنابراین عدد 14 باید در دایره نزدیک رویداد X 13 قرار گیرد و به همین ترتیب. با انجام مراحل از انتها به ابتدا به طول مسیر بحرانی t cr =96 پی می بریم. برای یافتن خود مسیر بحرانی، بیایید فرآیند محاسبه را از رویداد اولیه X 1 تا X 16 نهایی طی کنیم. در مرحله اول (از ابتدا) با جمع 16 به عدد 80 عدد 96 را بدست آوردیم. بنابراین مسیر بحرانی در این مرحله برابر با (X 1, X 3) خواهد بود. عدد 80 = 16 + 64. بنابراین مسیر بحرانی در مرحله دوم از کار (X 3 , X 4) و غیره می گذرد. در نمودار با خط پررنگ مشخص شده است:

X 1 - X 3 - X 4 - X 7 - X 8 - X 10 - X 11 - X 12 - X 13 - X 15 - X 16 .

تاریخ های اولیه و دیرهنگام برای اتمام رویدادها. سستی رویداد

تمام مسیرهایی که از نظر مدت زمان با مسیر بحرانی متفاوت هستند دارای ذخیره زمانی هستند. تفاوت بین طول مسیر بحرانی و هر مسیر غیر بحرانی، سستی کل مسیر غیر بحرانی داده شده نامیده می شود و با علامت زیر مشخص می شود: .

اوایل ترمبه اتمام رساندن یک رویداد، اولین نقطه زمانی گفته می شود که در آن تمام کارهای قبل از این رویداد تکمیل می شود، یعنی. با طول مدت حداکثر مسیر قبل از رویداد تعیین می شود، یعنی:

یا

برای یافتن تاریخ اولیه رویداد j، باید مسیر بحرانی زیرگراف هدایت شده را بدانید که از مجموعه مسیرهای قبل از رویداد j تشکیل شده است. جمله اولیه رویداد اولیه برابر با صفر است: t p (1) = 0.

دیر مهلت رویدادبه نام ترین لحظه دیرزمانی که پس از آن دقیقاً به همان اندازه که برای تکمیل تمام کارهای بعد از این رویداد لازم است وجود دارد. آخرین مهلت مجاز برای اتمام رویداد، در مجموع با مدت زمان اجرای کلیه فعالیت های بعدی، نباید از طول مسیر بحرانی تجاوز کند. مهلت تاخیر برای یک رویداد به عنوان تفاوت بین مدت زمان مسیر بحرانی و مدت زمان حداکثر مسیرهای پس از رویداد محاسبه می شود:

برای رویدادهایی که در مسیر بحرانی قرار دارند، تاریخ های اولیه و دیرهنگام تکمیل این رویدادها یکسان است.

تفاوت بین تاریخ های دیرهنگام و زود هنگام برای اتمام رویداد، زمان رزرو رویداد است: . به این فاصله، فاصله آزادی رویداد می گویند. سستی رویداد حداکثر زمان مجاز را نشان می دهد که یک رویداد می تواند بدون افزایش مسیر بحرانی به عقب برگردد.

از آنجایی که مقدار مدت زمان حداکثر طول عبور از این رویداد را تعیین می کند، سپس، i.e. سستی هر رویداد برابر است با سستی کامل حداکثر مسیر عبور از این رویداد.

هنگام محاسبه پارامترهای زمان به صورت دستی، استفاده از روش چهار بخش راحت است. با این روش، دایره نمودار شبکه نشان دهنده رویداد به چهار بخش تقسیم می شود. شماره رویداد در بخش بالایی قرار می گیرد. در سمت چپ - اولین زمان ممکن رویداد ()؛ در سمت راست - آخرین زمان مجاز رویداد؛ در بخش پایین - زمان رزرو این رویداد: .

برای محاسبه زودترین موعد مقرر برای رویدادها: ، فرمول را اعمال کنید با در نظر گرفتن رویدادها به ترتیب صعودی اعداد، از ابتدایی تا نهایی، با توجه به آثار موجود در این رویداد.

تاریخ تأخیر برای تکمیل رویدادها با فرمول محاسبه می شود ، از رویداد پایانی شروع می شود که برای آن (- شماره رویداد پایانی) با توجه به کارهایی که از آن خارج می شود.

رویدادهای بحرانی یک افت صفر دارند. آنها فعالیت های حیاتی و مسیر بحرانی را تعریف می کنند.

مثال 10.2. اجازه دهید نمودار شبکه نشان داده شده در شکل. 10.8.

راه حل.تاریخ های اولیه برای اتمام رویدادها را محاسبه کنید:

بنابراین، رویداد نهایی می تواند تنها در روز چهاردهم از شروع پروژه رخ دهد. این حداکثر زمانی است که تمام فعالیت های پروژه می تواند در آن تکمیل شود. با طولانی ترین مسیر مشخص می شود. تاریخ تکمیل اولیه کار 6 = 14 مصادف با زمان بحرانی kp است - کل مدت زمان کار در مسیر بحرانی. اکنون می توانید فعالیت هایی را که به مسیر بحرانی تعلق دارند، برجسته کنید و از رویداد پایانی به رویداد اصلی برگردید. از دو شغل موجود در رویداد 6، طول مسیر بحرانی مشاغل (5، 6) را تعیین می کند، زیرا (5 + 56) = 14. بنابراین، کار (5، 6) حیاتی است و غیره. آثار (1، 3)، (3، 4)، (4، 5)، (5، 6) مسیر بحرانی را تعیین کردند: cr = (1-3-4-5-6).

ما اکنون تاریخ های تأخیر برای اتمام رویدادها را محاسبه می کنیم. اجازه دهید . بیایید از روش برنامه نویسی پویا استفاده کنیم. تمامی محاسبات از رویداد نهایی تا رویداد اولیه انجام خواهد شد. تاریخ های تأخیر برای اتمام رویدادها عبارتند از:

از آنجایی که پس از رویداد 5، برای تکمیل پروژه، کار (5، 6) باید به مدت 3 روز تکمیل شود. دو کار از رویداد 4 بیرون می آید، بنابراین:

سستی رویداد 2 این است: . ذخایر رویدادهای باقیمانده برابر با صفر است، زیرا این رویدادها بحرانی هستند.

تاریخ شروع و پایان زودهنگام و دیرهنگام تعیین ذخیره زمان کار. ذخیره کامل زمان کار

رویداد بلافاصله قبل از این اثر نامیده می شود اولیهو نشان می دهد، و رویداد بلافاصله پس از آن، - نهاییو تعیین کنید. سپس هر کار با علامت نشان داده می شود. با دانستن زمان اتمام رویدادها، می توانید پارامترهای زمانی کار را تعیین کنید.

زمان شروع زودهنگامبرابر است با تاریخ اولیه رویداد: .

پایان زودهنگام کار برابر با مجموع استتاریخ اولیه برای تکمیل رویداد اولیه و مدت زمان این کار: یا .

دیر پایان کارمصادف با دیر اتمام رویداد نهایی آن است: .

زمان شروع دیرهنگامبرابر است با تفاوت بین تاریخ پایان پایان رویداد نهایی و ارزش این اثر:

از آنجایی که مهلت های تکمیل کار در محدوده تعیین شده توسط و است، پس ممکن است داشته باشند نوع متفاوتذخایر زمانی

ذخیره زمان کار کامل -حداکثر زمان لازم برای تکمیل هر کار بدون تجاوز از مسیر بحرانی است. به عنوان تفاوت بین رویداد دیر پایان و زمان اولیه تکمیل خود کار محاسبه می شود: . از آن به بعد .

به این ترتیب، ذخیره کامل زمان اجراحداکثر زمانی است که می توان مدت آن را بدون تغییر مدت زمان مسیر بحرانی افزایش داد. همه مشاغل غیر بحرانی دارای یک سستی کل غیر صفر هستند.

رزرو زمان کار رایگان- این حاشیه زمانی است که هنگام اجرای این اثر می تواند در دسترس باشد، مشروط بر اینکه وقایع اولیه و نهایی آن در اولین تاریخ خود رخ دهد: .