اگر بیشترین مدت زمان فعالیت، قاعده اولویت بندی در نظر گرفتهشود، لیست فعالیتهای زیر بدست می آید.
۸
۶
۵
۱
۲
۷
۴
۳
۰
رعایت پیشنیازی، مقدم بر قانون اولویت است. به همین دلیل با اینکه فعالیت ۶ دارای بیشترین زمان فعالیت است ولی تقریبا در انتهای لیست قرار گرفتهاست. اگر قانون اولویت بندی را براساس زودترین زمان شروع انجام دهیم، لیست زیر بدست می آید که با لیست قبل متفاوت میباشد.
۸
۷
۶
۵
۴
۳
۲
۱
۰
برای تعیین زمان شروع فعالیتها، الگوریتم SGS[60] از عمومیترین روشها است. خروجی روش SGS یک زمانبندی شدنی بصورت S=(s1,s2,…,sn) است که در آن si زمان شروع فعالیت i را نشان میدهد. این روش محور بیشتر الگوریتمهای ابتکاری برای مسئله RCPSP است[۴۷]. در این روش، فعالیتهای پروژه به ترتیب یک لیست اولویت، در زودترین زمانی که محدودیت منابع برقرار باشد، زمانبندی میشوند. ترتیب موجود در لیست اولویت، معرف اولویت فعالیتهای پروژه برای زمانبندی است. بنابراین، با تعیین این لیست میتوان یک زمانبندی اولیه ارائه کرد. در این پایان نامه، فعالیتهای پروژه به ترتیب نزولی عدد تصادفی تولید شده برای هر شماره فعالیت، وارد لیست میشوند. همچنین هنگام ایجاد لیست روابط پیشنیازی را نیز رعایت میکنیم، یعنی باید قبل از وارد کردن هر فعالیت در لیست همه پیشنیازهای آن وارد شدهباشند. روش SGS حتی برای مسائل و پروژه های بسیار بزرگ نیز به زمان بسیار اندکی برای اجرا نیاز دارند. ضمن اینکه استفاده از SGS و قوانین اولویت بندی به صورت ترکیبی بسیار کاربردی میباشد. در ادامه روشهای تولید زمانبندی سری، موازی، پسرو و پیشرو که از الگوریتمهای سازنده هستند را شرح میدهیم.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
۴-۳-۱ روش تولید زمانبندی سری
یکی از مهمترین الگوریتمهای سازنده برای حل یک مسئله زمانبندی پروژه با منابع محدود، روش S-SGS[61] میباشد. این روش را کلی[۶۲] در سال ۱۹۶۳ کلی برای ایجاد یک زمانبندی از روی یک لیست اولویت اریه داد[۶۵]. پس از آن در سال ۱۹۹۴ پینسون و همکارانش[۶۳] بیان کردند که پیچیدگی این الگوریتم از مرتبه O(mn2) میباشد. n تعداد فعالیتها و m تعداد منابع میباشد[۶۶]. فرض کنید که فعالیتهای یک پروژه با بهره گرفتن از یک قانون اولویت بندی خاص رتبهبندی شده اند. حال با توجه به لیست اولویتهای بدست آمده، الگوریتم S-SGS بدین صورت عمل می کند که از ابتدای لیست اولویت، فعالیتها یکی یکی در انتخاب میشوند، فعالیت انتخاب شده با توجه به محدودیتهای منبع و پیشنیازهایش درزودترین زمان ممکن انجام میگیرد. مثال ۴-۲ این روش را روشنتر بیان می کند.
مثال ۴-۲
در شکل ۴-۲ پروژهای با ۵ فعالیت تعریف شدهاست. یک نوع منبع با ظرفیت ۲ واحد داریم. فعالیتهای ۰و ۴ مجازی هستند.
شکل ۴-۲ شبکه فعالیتهای متناظر با مثال ۴-۲[۶۴]