۲-۳)روش حل ابتکاری سازنده

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

۲-۳-۱)قوانین اولویت

در هر الگوریتم ابتکاری سازنده ابتدا یک لیست اولویت فعالیتها ایجاد میشود، در این لیست بر اساس یک قانون اولویت دهی فعالیتها مرتب میشود به گونه ای که محدودیت های تقدمی فعالیتها نقض نشود، از این لیست به عنوان لیست اولویت فعالیتها برای زمانبندی یاد میشود.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

بر اساس بررسی که توسط کلین^[۸۰] صورت گرفته است تا کنون بیش از هفتاد قانون اولویت مختلف تعریف شده که مورد استفاده قرار میگیرد. متداولترین قوانین اولویت دهی را میتوان به صورت ذیل طبق منبع ]۱[ تقسیم بندی کرد:

۲-۳-۱-۱)قوانین اولولیت بر اساس خصوصیت فعالیتها^[۸۱]

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

1. 1. اولویت بر اساس کوتاه ترین مدت زمان اجرا^[۸۲] (SPT)

1. 1. اولویت بر اساس طولاترین مدت زمان اجرا^[۸۳] (LPT)

1. 1. اولویت بر اساس اولویت تصادفی^[۸۴] (RND)

۲-۳-۱-۲)قوانین اولویت بر اساس شبکه فعالیتها^[۸۵]

در این نوع قانون اولویت فقط اطلاعاتی که شامل شبکه می شود را در نظر میگیریم (نه اطلاعاتی درباره منابع مورد استفاده که ممکن است برای قوانین اولویت در نظر گرفته شود). از انواع مهم این نوع قانون اولویت میتوان به موارد ذیل اشاره کرد:

1. 1. اولویت براساس بیشترین پسنیاز بدون واسطه^[۸۶] (MIS)

1. 1. اولویت بر اساس تعداد کل پس نیاز^[۸۷] (MTS)

۲-۴-۱-۳-قوانین اولویت بر اساس منبع^[۸۸]
این نوع قانون اولویت بر اساس منابعی که در فعالیتهای مختلف مورد استفاده قرار میگیرد به وجود آمده است. از انواع مهم این نوع قانون اولویت میتوان به موارد ذیل اشاره کرد:

1. 1. اولویت بر اساس بیشترین تقاضای منبع^[۸۹] (GRD)

1. 1. اولویت بر اساس بیشترین مقدار تجمعی تقاضای منبع^[۹۰] (GCUMRD)

۲-۳-۱-۴)قوانین اولویت بر اساس خصوصیات مسیر بحرانی^[۹۱]

در این نوع قانون اولویت محاسبات بر اساس مسیر بحرانی پیشرو(forward) و پسرو(backward) است. از انواع مهم این نوع قانون اولویت میتوان به موارد ذیل اشاره کرد:

1. 1. اولویت بر اساس زودترین زمان شروع^[۹۲] (EST)

1. 1. اولویت بر اساس دیرترین زمان شروع^[۹۳] (LST)

1. 1. اولویت بر اساس زودترین زمان اتمام^[۹۴] (EFT)

1. 1. اولویت بر اساس دیرترین زمان اتمام^[۹۵] (LFT)

1. 1. اولویت بر اساس کوچکترین شناوری^[۹۶] (MSLK)

۲-۳-۱-۵)قوانین اولویت بر اساس قوانین اولویت ترکیبی^[۹۷] :
این نوع قانون اولویت میتواند بر اساس جمع وزنی مقادیر اولویت که به وسیله چهار قانون اولویت یاد شده بوجود میاید محاسبه گردد. از مهمترین موارد قابل اشاره از این قانون اولویت میتوان به موارد ذیل اشاره کرد:

1. 1. اولویت بر اساس روش زمانبندی منابع بهبود دهنده^[۹۸] (IRSM)

1. 1. اولویت بر اساس بدترین مورد شناوری^[۹۹] (WCS)

۲-۳-۲)طرح تولید زمانبندی^[۱۰۰]

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

۲-۳-۲-۱)طرح تولید زمانبندی سریالی^[۱۰۱] (SSGS)

طرح تولید زمانبندی سریالی توسط کلی^[۱۰۲] (۱۹۶۳) بوجود آمده است. در این روش فعالیتها به ترتیب به زمانبندی اضافه می شود تا یک زمانبندی کامل شدنی بدست آید. در هر مرحله فعالیت بعدی کاندید زمانبندی از لیست اولویت فعالیتها بر اساس قانون اولویت انتخاب میشود و برای این فعالیت انتخاب شده در زودترین زمان ممکن شروع، زمانبندی میشود به طوریکه هیچ یک از محدودیت های منبع و تقدمی مسئله RCPSP نقض نگردد. به عبارت دیگر برای هر فعالیت i بازه زمانی به صورت [ EST_i , EFT_i­ ) در نظر گرفته میشود و با این هدف که پروژه در مینیمم زمان ممکن به اتمام برسد فعالیت i ام را در این بازه زمانی زمانبندی میکنیم. در این طرح تولید زمانبندی از فعالیتهایی که بر اساس قانون اولویت مرتب شده اند یک فعالیت را که هم روابط تقدمی را نقض نکند و هم در اولویت این لیست باشد را انتخاب میکنیم و به بررسی این موضوع می پردازیم که آیا با زمانبندی فعالیت i ام در زمان t = EST_i ، محدودیت منابع نقض میشود یا خیر، اگر جواب خیر باشد فعالیت i ام را در زمان t = EST_i زمانبندی میکنیم در غیراینصورت دوباره همین سوال را در زمان۱ t=EST_i+ برای فعالیت i ام مطرح میکنیم و این روال را تا زمانیکه فعالیت i ام زمانبندی شود ادامه خواهیم داد. پس از اینکه فعالیت i ام زمانبندی شد فعالیت بعدی را از لیست اولویت که بر اساس قانون اولویت مرتب شده و نیز روابط تقدمی را نقض نمیکند انتخاب و روال بالا را روی آن پیاده میکنبم. این کار را تا زمانیکه همه فعالیتها زمانبندی شود ادامه میدهیم بنابراین تعداد مراحل طرح تولید زمانبندی سریالی مساوی با تعداد فعالیتهای موجود در پروژه خواهد بود. یکی از مهمترین خواص طرح تولید زمانبندی سریالی آنست که برنامه ایجاد شده توسط آن جزء زمانبندی فعال^[۱۰۳] است. زمانبندی فعال در فضایی به دنبال جواب میگردد که شامل جواب بهبنه نیز میباشدکه این میتواند از خصوصیات مثبت این نوع زمانبندی باشد. اسپرچر^[۱۰۴] نشان داده است که حداقل یکی از جوابهای بهینه مسئله RCPSP جزء زمانبندی فعال است]۱۳[. کولیش^[۱۰۵] (b1996) نشان داد که زمانبندی به دست آمده به وسیله طرح تولید زمانبندی سریالی شامل مجموعه زمانبندی فعال میشود]۱۴[. بنابراین استفاده از طرح تولید زمانبندی سریالی به خاطر خصوصیات یاد شده در ادبیات زماتنبندی پروژه با محدودیت منابع به وفور مورد استفاده قرار میگیرد.
پینسون^[۱۰۶] (۱۹۹۴) نشان داد که برای یک لیست اولویت فعالیتها کاربرد روش طرح تولید زمانبندی سریالی به زمان O(mn²) که زمان چند جمله ای است برای اجرا نیاز دارد که زمان معقولی است]۱[.

۲-۳-۲-۲)طرح تولید زمانبندی موازی^[۱۰۷] (PSGS)

طرح تولید زمانبندی موازی توسط بروکز^[۱۰۸] و وایت^[۱۰۹] (۱۹۶۵) بوجود آمده است. تعداد مراحل در این طرح تولید زمانبندی برخلاف طرح تولید زمانبندی سریالی، به تعداد فعالیتها وابسته نیست بلکه این مراحل به تعداد دفعاتی که زمانبندی فعالیتهای در حین انجام، تکمیل میشود تا فرصت برای تخصیص منابع برای سایر فعالیتهای زمانبندی نشده بوجود میاید وابسته است. به عبارت دیگر برخلاف طرح زمانبندی سریالی، در طرح تولید زمانبندی موازی در هر مرحله حرکتی به اندازه یک (یاچند) واحد زمانی صورت میگیرد تا فعالیتی که درحال انجام است تکمیل شود و در نتیجه منبع تخصیص یافته به آن آزاد شود، در این لحظه از میان فعالیتهای باقیمانده در لیست اولویت که بر اساس قوانین اولویت با رعایت قوانین تقدمی مرتب شده اند فعالیتی را انتخاب و آن را در زودترین زمان ممکن در بازه زمانیش به گونه ای زمانبندی میکنیم که هیچ از محدودیتهای منبع مساله نقض نگردد. طرح تولید زمانبندی موازی طبق تحقیقات کولیش(b1996) یک مجموعه زمانبندی غیر تاخیری را بوجود میاورد که این مجموعه زمانبندی یک زمانبندی فعال نیست بنابراین نمیتواند هیچ یک از جوابهای بهینه مسئله لزوما در این مجموعه باشد. از آنحاییکه در زمانبندی غیر فعال جستجو در فضای بهینه جواب صورت نمیگرد بنابراین طرح تولید زمانبندی موازی نمیتواند برای شروع حل مسئله RCPSP زیاد مناسب باشد چون زمان رسیدن تا جواب نزدیک به بهینه را احتمالا به تاخیر میاندازد. زمان لازم برای اجرای طرح تولید زمانبندی موازی بر روی یک لیست فعالیت مرتب شده بر اساس قانون اولویت، طبق تحقیقات کولیش و هارتمن(۱۹۹۹) به اندازه O(mn²) که زمانی معقول است چون زمان چندجمله ای مشخص است]۱[. در الگوریتمهای ابتکاری سازنده علاوه بر دو بخش مهم این الگوریتمها که شامل مشخص کردن قانون اولویت مورد استفاده برای مرتب کردن فعالیتها و نیز نوع طرح تولید زمانبندی است باید جهت برنامه ریزی را هم مورد توجه قرار بدهیم. سه طرح برنامه ریزی که جهت برنامه ریزی را مشخص می کنند شامل برنامه ریزی رو به جلو^[۱۱۰]، برنامه ریزی رو به عقب^[۱۱۱] و برنامه ریزی دو سویه^[۱۱۲] است که برای مسائل مختلف مورد استفاده قرار میگیرد. ما در این پایان نامه از طرح تولید زمانبندی سریالی با رویکرد جهت برنامه ریزی رو به جلو استفاده میکنیم.

۲-۴) روش حل ابتکاری بهبود دهنده

روش های حل ابتکاری بهبود دهنده یا به عبارتی ساده تر الگوریتم های ابتکاری بهبود دهنده که از آنها با عنوان الگوریتم های جستجوی محلی^[۱۱۳] نام برده میشود، از یک جواب اولیه شدنی که به وسیله الگوریتم های ابتکاری سازنده یا به طور تصادفی تولید میشود، شروع میشود و سعی میکند تا جواب بهتری را در یک همسایگی از جواب فعلی که به طرز مناسبی تعریف شده است به دست آورد. در کلی ترین حالت که حالت بهبود پی در پی نامیده میشود، الگوریتم در همسایگی خود برای یافتن یک جواب بهبود دهنده تقلا میکند ،در صورت یافته شدن چنین جوابی آن را جایگزین جواب فعلی میکند و به همین منوال جستجوی محلی ادامه میابد. این قدم ها تا جایی ادامه پیدا میکند که هیچ جواب همسایگی بهتری در همسایگی جواب فعلی یافت نشود و درنتیجه الگوریتم در یک بهینه محلی^[۱۱۴] متوقف میشود. توجه به این نکته بسیار با اهمیت است که انتخاب نوع ساختار همسایگی مناسب در کارایی الگوریتمهای جستجوی محلی نقش بسزایی دارد و باید در تعریف آن بسیار دقت کرد. برای داشتن یک الگوریتم بهبود دهنده کارا باید یک الگوی آزمودن جوابهای همسایگی مشخص شود تا به وسیله این الگو مشخص گردد که در بین جوابهای متفاوت همسایگی کدامیک ارجحیت دارد. مشکل اساسی الگوریتمهای ابتکاری بهبود دهنده غیر از نحوه تعریف همسایگی، کوچک بودن فضای جوابی است که در الگوریتمهای بهبود دهنده مورد بررسی قرار میگیردو از آنجاکه الگوریتمهای ابتکاری بهبود دهنده به دنبال جوابی در همسایگی جواب فعلی هستیم سایر جوابها را مورد توجه قرار نداده و با توجه به ساختار ویژه مسائل بهبنه سازی ترکیباتی و بزرگ بودن نسبی فضای جواب در بیشتر مسائل کاربردی از این رده، نمیتوان به یافته شدن جوابهای مناسب به وسیله این الگوریتمهای ابتکاری بهبود دهنده به دلیل افتادن در جواب بهینه محلی و جستجوی محدود فضای جواب امید زیادی داشت به همین خاطر محققین به فکر به وجود آوردن الگوریتمهای ابتکاری بهبود دهنده جدیدی افتادند که نقصهای یاد شده را نداشته باشد. این الگوریتمها به الگوریتمهای فراابتکاری^[۱۱۵] معروف شدند.
از الگوریتمهای ابتکاری بهبود دهنده مشهور میتوان به روش نزولی بر اساس تندترین شیب^[۱۱۶] اشاره کرد که در این روش در بین همسایگان جواب فعلی جوابی که بیشترین بهبود را در تابع هدف ایجاد میکند به عنوان جایگزین جواب فعلی انتخاب میشود. از روش های مهم دیگر الگوریتمهای ابتکاری بهبود دهنده میتوان به روش نزولی بر اساس تندترین سرعت^[۱۱۷] اشاره کرد که در این روش در بین همسایگان جواب فعلی، اولین جواب بهبود دهنده به عنوان جایگزین جواب فعلی انتخاب می شود. از آنجاییکه طرح نمایش جواب^[۱۱۸] و نوع عملگر همسایگی^[۱۱۹] برای تبیین الگوریتمهای ابتکاری بهبود دهنده و فراابتکاری با اهمیت است ابتدا به صورت خلاصه انواع روش های طرح نمایش جواب و انواع عملگرهای همسایگی مهم را به صورت خلاصه در ادامه میاوریم که از اجزای الگوریتمهای ابتکاری بهبوددهنده و فرابتکاری هستند.

۲-۴-۱)انواع طرح های نمایش جواب

پنج روش مهم برای نمایش جواب وجود دارد که تشریح هر یک از آنها را میتوان در مرجع ]۱[ مشاهده کرد. ما فقط عناوین آنها را در اینجا ذکر میکنیم: