اگر بیشترین مدت زمان فعالیت، قاعده اولویت­ بندی در نظر گرفته­شود، لیست فعالیت­های زیر بدست می ­آید.

۸
۶
۵
۱
۲
۷
۴
۳
۰

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

۸
۷
۶
۵
۴
۳
۲
۱
۰

برای تعیین زمان شروع فعالیت­ها، الگوریتم SGS^[60] از عمومی­ترین روش­ها است. خروجی روش SGS یک زمانبندی شدنی بصورت S=(s₁,s₂,…,s_n) است که در آن s_i زمان شروع فعالیت i را نشان می­دهد. این روش محور بیشتر الگوریتم­های ابتکاری برای مسئله RCPSP است[۴۷]. در این روش، فعالیت­های پروژه به ترتیب یک لیست اولویت، در زودترین زمانی که محدودیت منابع برقرار باشد، زمانبندی می­شوند. ترتیب موجود در لیست اولویت، معرف اولویت فعالیت­های پروژه برای زمانبندی است. بنابراین، با تعیین این لیست می­توان یک زمانبندی اولیه ارائه کرد. در این پایان نامه، فعالیت­های پروژه به ترتیب نزولی عدد تصادفی تولید شده برای هر شماره فعالیت، وارد لیست می­شوند. همچنین هنگام ایجاد لیست روابط پیش­نیازی را نیز رعایت می­کنیم، یعنی باید قبل از وارد کردن هر فعالیت در لیست همه پیش­نیازهای آن وارد شده­باشند. روش SGS حتی برای مسائل و پروژه­ های بسیار بزرگ نیز به زمان بسیار اندکی برای اجرا نیاز دارند. ضمن اینکه استفاده از SGS و قوانین اولویت­ بندی به صورت ترکیبی بسیار کاربردی می­باشد. در ادامه روش­های تولید زمانبندی سری، موازی، پسرو و پیشرو که از الگوریتم­های سازنده هستند را شرح می­دهیم.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

۴-۳-۱ روش تولید زمانبندی سری
یکی از مهمترین الگوریتم­های سازنده برای حل یک مسئله زمانبندی پروژه با منابع محدود، روش S-SGS^[61] می­باشد. این روش را کلی^[۶۲] در سال ۱۹۶۳ کلی برای ایجاد یک زمانبندی از روی یک لیست اولویت اریه داد[۶۵]. پس از آن در سال ۱۹۹۴ پینسون و همکارانش^[۶۳] بیان کردند که پیچیدگی این الگوریتم از مرتبه O(mn²) می­باشد. n تعداد فعالیت­ها و m تعداد منابع می­باشد[۶۶]. فرض کنید که فعالیت­های یک پروژه با بهره گرفتن از یک قانون اولویت­ بندی خاص رتبه­­بندی شده ­اند. حال با توجه به لیست اولویت­های بدست آمده، الگوریتم S-SGS بدین صورت عمل می­ کند که از ابتدای لیست اولویت، فعالیت­ها یکی یکی در انتخاب می­شوند، فعالیت انتخاب شده با توجه به محدودیت­های منبع و پیش­نیازهایش درزودترین زمان ممکن انجام می­گیرد. مثال ۴-۲ این روش را روشن­تر بیان می­ کند.
مثال ۴-۲
در شکل ۴-۲ پروژه­ای با ۵ فعالیت تعریف شده­است. یک نوع منبع با ظرفیت ۲ واحد داریم. فعالیت­های ۰و ۴ مجازی هستند.

شکل ۴-۲ شبکه فعالیت­های متناظر با مثال ۴-۲[۶۴]