زودترین(دیرترین) زمان شروع فعالیت j ام
T
یک حد بالا بر طول زمانبندی پروژه
t= 0,1,2,…,T
اندیس زمان
(t-1,t]
بازه زمانی متناسب با پریود t
۱-۱-۱) فعالیت ها
یک پروژه متشکل از تعدای فعالیت است که به شکل کارها[۲۱] ، وظایف[۲۲] و یا عملیات[۲۳] مشخص میشوند. به منظور تکمیل یک پروژه با موفقیت، تمام فعالیت های آن باید به صورت کامل انجام گیرند. هر فعالیت ممکن است یک یا چند حالت[۲۴] داشته باشد که هر یک از حالات را یک mode گویند. روش انجام هر فعالیت مشخص کننده طول زمان انجام آن است. بدین معنا که هر حالت ممکن است بر زمان انجام فعالیت که آن را بر مبنای پریودهای زمانی پروژه بیان میدارند(معمولا هر پریود زمانی برابر یک واحد زمانی در نظر گرفته میشود)تاثیرگذار باشد. همچنین ممکن است هر حالت بر میزان مصرف منابع موثر باشد. ما برای نشان دادن یک پروژه از گراف جهت دار هم بند G(V,E) استفاده میکنیم که در آن ,n}…V={1,2, فعالیتهای پرو ژه را نشان میدهد که در آن فعالیت های اول و آخر فعالیتهای مجازی هستند و بقیه فعالیتها، فعالیتهای حقیقی پروژه هستند.} Mj ={۱,۲,…, را مجموعه حالتهای jام مینامیم که در آن بیانگر تعداد اجزای Mj است. برای هر j ، djm را مدت زمان قطعی[۲۵] انجام فعالیت j طبق حالت m است.sj را زمان شروع و fj را زمان پایان فعالیت j ام قرار میدهیم. S = (s1,s2,…,sn) را بردار زمان شروع فعالیت و f = (f1,f2,…,fn) را بردار زمان های پایان فعالیتهای پروژه می نامیم. مجموعه جوابهایی که ازنظر زمانی و محدودیت های تقدمی موجه هستند را زمانبندیهای موجه زمانی[۲۶] و مجموعه جوابهایی که با توجه به محدودیت های منابع موجه هستند را زمانبندی های موجه منبعی[۲۷] مینامیم. بنابراین اشتراک این دو مجموعه بیانگر مجموعه زمانبندی های موجه[۲۸] است. از نظر پیوستگی فعالیت های پروژه به دو دسته فعالیتهای قابل شکسته شدن[۲۹] و غیر قابل شکسته شدن[۳۰] تقسیم میشود. در فعالیت های غیر قابل شکسته شدن به محض شروع فعالیت اجازه قطع انجام آن را تا زمان تکمیل فعالیت نداریم، اما هنگامیکه یک فعالیت قابل شکسته شدن است قبل از به اتمام رسیدن آن میتوان آن را قطع کرد و منابع مورد استفاده آن را به یک فعالیت دیگر منتقل کرد و در زمان های بعدی دوباره آن فعالیت را ادامه داد که البته ادامه دادن آن میتواند با هزینه همراه باشد و یا مستلزم زمان بیشتری برای اجرا باشد. برای مثال بتن ریزی سقف یک ساختمان فعالیتی غیر قابل شکسته شدن است، ولی عملیات گودبرداری قابل شکسته شدن است.
۱-۱-۲) روابط تقدمی
معمولا در انجام یک پروژه به دلیل محدودیت منابع، محدودیت های تکنولوژیکی و نوع فعالیتها، نمیتوان فعالیتهای پروژه را مستقل از هم در نظر گرفت. به طور کلی دو نوع محدودیت تقدمی بین فعالیتهای یک پروژه وجود دارد که به صورت حداقل فاصله زمانی[۳۱] و حداکثر فاصله زمانی[۳۲] بیان می شود و هر کدام دارای چهار حالت مختلف هستند
که عبارتند از: رابطه پایان به شروع[۳۳] ، شروع به شروع[۳۴] ، شروع به پایان[۳۵] و پایان به پایان[۳۶] است. روابط منطقی بین فعالیت های پروژه میتواند به صورت ترکیبی از این عوامل کنترل کننده نیز تعریف شوند. اگر در یک زمانبندی پروژه کلیه محدودیت های تقدمی را در نظر بگیریم، به آن محدودیت های تقدمی عمومی[۳۷] گفته میشود. درحالت وجود محدودیت های تقدمی عمومی، بین فعالیتها هم رابطه وابستگی مینیمم و هم ماکزیمم وجود خواهد داشت که ممکن است در این حالت منجر به ایجاد حلقه در قالب پنجره های زمانی[۳۸] شود که وجود پنجره های زمانی باعث میشود مساله زمانبندی پروژه با محدودیت منابع به شدت Np-hard شود، به طوریکه نرم افزارهای فعلی زمانبندی پروژه غالبا قابلیت تحلیل این نوع روابط وابستگی را ندارند. در مدل RCPSP کلاسیک که در این پایان نامه مورد بحث است تنها رابطه تقدمی FSmin = ۰ در نظر گرفته میشود که این ساده ترین نوع رابطه تقدمی است.
۱-۱-۳)منابع
منابع مورد استفاده فعالیت های یک پروژه براساس ماهیت و مقدارشان دسته بندی میشوند، که کاملترین آنها عبارتند از: منابع تجدید پذیر[۳۹] ، منابع تجدید ناپذیر[۴۰] ، منابع تجدیدپذیر جزئی[۴۱] و منابع با محدودیت دوگانه[۴۲] .
۱-۱-۳-۱)منابع تجدید پذیر
منابعی قابل تجدید محسوب می شوند که صرفنظر از طول مدت پروژه، در هر یک از دوره های زمانی پروژه مقداری ثابت باشند و تنها محدودیت آنها مقداراستفاده از آنها در طی یک دوره پروژه باشد. مقدار این منابع بر حسب واحد منبع د ر دوره اندازه گیری میشود. منابعی همچون ماشین آلات، تجهیزات و نیروی انسانی نمونه هایی ار منابع تجدید پذیر هستند.
۱-۱-۳-۲)منابع تجدید ناپذیر
منابعی غیر قابل تجدید محسوب میشوند که مقدار آنها برای کل طول مدت زمان اجرای پروژه محدود باشد، به عبارت دیگر مقدار این منابع با استفاده ازآنها کاهش مییابد و در دوره یا دوره های بعد تجدید نمی شود ولی در هر دوره زمانی به شرط آنکه از حداکثر مقدار در دسترس آن تجاوز نکنیم، به همان اندازه میتوان از آن استفاده کرد. میزان سرمایه و انرژی نمونه هایی از این منابع هستند.
۱-۱-۳-۳)منابع تجدیدپذیر جزئی
این نوع منبع اولین بار توسط بوچر[۴۳] و همکارانش(۱۹۹۷) معرفی شد]۴[. در این مورد منبع مورد نظر برای استفاده در تعدادی از دوره ها محدود هستند، به عنوان مثال کارگران در یک کارگاه محدودیت مجموعه ساعات کار در هفته دارند به طوریکه مثلا حداکثر ساعات کاری آنها نباید از چهل ساعت در هفته بیشتر شود و در عین حال این تعدادساعات کاری برای هر کارگر در هر هفته قابل برنامه ریزی است و چهل ساعت فوق در هفته تجدید میشود. بوچر همچنین نشان داد که منابع تجدیدپذیر و تجدیدناپذیر حالت های خاصی از این نوع منبع هستند.
۱-۱-۳-۴)منابع با محدودیت دوگانه
منابعی که نه تنها در هر دوره محدودیت در استفاده شدن دارند بلکه مقدار آنها در کل پروژه نیز محدود است. محدودیت بودجه نمونه بارز این نوع منبع است که علاوه بر محدود بودن کل بودجه در طول انجام پروژه میزان آن نیز میتواند در هر دوره زمانی محدود باشد. تالبوت[۴۴] (۱۹۸۲) نشان داده است که هر منبع با محدودیت دوگانه را میتوان با دو منبع که یکی تجدیدپذیر و دیگری تجدیدناپذیر است نمایش داد]۵[ و بنابراین این حالت قابل تبدیل به دو حالت بالا است.
۱-۱-۴)تابع هدف
حل هر مسئله زمانبندی پروژه با توجه به هدف یا اهداف خاصی صورت میگیرد. در اکثر مسائل زمانبندی پروژه کمینه سازی مدت زمان اجرای پروژه[۴۵] به عنوان تابع هدف مورد استفاده قرار میگیرد. مدت زمان اجرای پروژه عبارتست از فاصله زمانی بین شروع و پایان پروژه. چون معمولا زمان شروع پروژه را در لحظه زمانی t = 0 در نظر میگیریم وبا توجه به مجازی بودن فعالیتهای اول و آخرشبکه، کمینه کردن طول مدت اجرای پروژه معادل است با کمینه کردن بزرگترین زمان پایان فعالیتها (fmax) و نیز معادل است با کمینه کردن بزرگترین زمان شروع فعالیتها (smax) ، به عبارت ریاضی داریم:
Min fmax Min smax
نوع دیگری از توابع هدف که در زمانبندی پروژه بسیار با اهمیت است کمینه کردن هزینه های پروژه است که این نوع تابع هدف به دو دسته توابع هدفی که در آن بحث هزینه- زمان مطرح است و توابع هدفی که بحث هزینه-منبع مطرح است تقسیم می شود.. توابع هدف انواع مختلفی میتوان داشته باشد که بحث بر روی آنها خارج از مباحث این پایان نامه است اما برای آگاهی بیشتر میتوان به منبع[۱] مراجعه کرد. در این پایان نامه تابع هدف مورد نظر ما مینیمم کردن زمان تکمیل پروژه است.
۱-۱-۵)شکل نمایش
برای نمایش فعالیتهای یک پروژه و روابط تقدمی بین فعالیتها به طور کلی دو شیوه نمایش مطرح شده است. در هر دو شیوه نمایش از یک گراف همبند جهت دار G(V,E) که V نودهای گراف و E یالهای گراف را نشان میدهد استفاده میشود. در شیوه اول شکل نمایش که به روش AON [۴۶] نام دارد و به شبکه گرهی معروف است، نودهای گراف نشان دهنده فعالیتهای پروژه و یالهای جهت دار گراف نشان دهنده روابط تقدمی بین فعالیتها هستند. در روش دوم که به روش AOA [۴۷] نام دارد و به شبکه برداری معروف است، یالهای جهت دار گراف فعالیتهای پروژه و نودهای گراف رویدادهای[۴۸] پروژه را نشان میدهد. رویداد یک لحظه زمانی است و احتیاجی به صرف زمان وهزینه و منابع نداردو فقط زمان شروع و پایان فعالیتها را در روش نمایش شبکه برداری نشان میدهد. در شبکه های AON فعالیتهای اول و آخر پروژه فعالیتهای مجازی هستند و فقط بیانگر شروع و پایان پروژه هستند و نیاز به صرف هزینه و زمان و منبع نیستند. در شبکه های AOA برای نمایش روابط تقدمی بین فعالیتها گاهی از یالهای مجازی نیز استفاده میشود. معمولا در زمانبندی پروژه که تابع هدف مینمم کردن زمان اجرای پروژه است از شبکه های AON برای نمایش پروژه استفاده میشود. مزیت شبکه های AON بر شبکه های AOA در این است که انواع روابط تقدمی بین فعالیتها را میتوان در شبکه AON نمایش داد اما در شبکه AOA فقط میتوان رابطه تقدمی FSmin = ۰ را نمایش داد. علارغم کاربردی تر بودن شبکه های AON این طور نیست که شبکه های AOA کاملا بلااستفاده باشند، قدرت محاسباتی شبکه های AOA و درک بالای محاسبات توسط آنها باعث شده تا هنوز هم پایه بسیاری از مقالات جدید علمی در زمینه زمانبندی پروژه باشد، از طرف دیگر نمایش فعالیتهای پروژه در تکنیکهای پرت (Pert) و گرت (Gert) بر اساس شبکه هایAOA انجام میپذیرد. ما در این پایان نامه استفاده از شبکه های AON را برای حل مسئله زمانبندی پروژه با محدودیت منابع انتخاب میکنیم به این دلیل که اکثر نرم افزارهای کامپیوتری به خاطر سادگی رسم شبکه ها در طرز نمایش AON از این روش استفاده میکنند.
۱-۲)انواع مسائل زمانبندی پروژه با محدودیت منابع
مسئله زمانبندی پروژه با محدودیت منابع جزء معروفترین مسائل زمانبندی پروژه است که از سال ۱۹۵۰ ذهن محققین را به خود مشغول کرده است و هزاران مقاله ، تز فوق لیسانس و دکترا در این زمینه ارائه شده و هنوز هم این تحقیقات ادامه دارد. یکی از انواع مهم مسئله زمانبندی پروژه که تحت حالات مختلف فعالیتها، منابع و تابع هدف ایجاد میشود مسئله زمانبندی پروژه با محدودیت منابع میباشد که خود این مسئله با توجه به شرایط و فرضیات حاکم بر پارامترهای مسئله دارای مدل های بسیار زیادی است. ما قصد داریم تنها دو مدل معروفتر مسئله زمانبندی پروژه با محدودیت منابع را در ادامه معرفی کنیم.
۱-۲-۱)مسئله زمانبندی پروژه با محدودیت منابع در حالت کلاسیک (RCPSP)
شکل کلاسیک مسئله زمانبندی پروژه با محدودیت منابع، در ادبیات موضوع زمانبندی پروژه کاملا شناخته شده است و به علت کاربرد فراوان و داشتن خواص مفید برای تجزیه تحلیل سایر مسائل مورد بررسی قرار گرفته است. در این مسئله فرض بر آن است که برای هر فعالیت پروژه تنها یک حالت اجرا وجود دارد. روابط تقدمی بین فعالیتها تنها ازنوع FSmin و مقدار آن برابر صفر است. هر فعالبت برای اجرای خود به یک یا تعدادی منبع تجدیدپذیر نیاز دارد و سایر انواع منابع در این مسئله دیده نشده است. طول اجرای هر فعالیت j ، برابر dj و مقدار آن مشخص و قطعی است. میزان استفاده فعالیت j ام از منبع k ام را با rjk نمایش میدهیم که مقدار آن نیز قطعی و مشخص است. در این مدل فعالیتها غیر قابل شکسته شدن هستند، به عبارت دیگر قطعی کار وجود ندارد. مقدار در دسترس منبع تجدیدپذیر از نوعR k را با ARK نمایش میدهیم که مقدار آن در هر دوره زمانی مقداری صحیح و ثابت است. تابع هدف مسئله RCPSP یافتن یک زمانبندی است که محدودیت های تقدمی و منابع را ارضا کرده و موجه باشد و دارای کمترین طول زمانبندی در تکمیل پروژه باشد. مسئله RCPSP کلاسیک ترین مسئله عنوان شده در زمانبندی پروژه با محدودیت منابع است به همین خاطر الگوریتم های بیشماری اعم از روش های دقیق و ابتکاری درچند دهه اخیر برای آن پیشنهاد گردیده که در مرجع [۱] به بررسی تعدادی از آنها پرداخته است. برای داشتن تعریف بهتر و فشرده تر از مسئله RCPSP تعریف ذیل را از مرجع [۱] در ادامه میاوریم: شبکه ای از فعالیتها با مدت زمان اجرای قطعی و به شکل عدد صحیح مثبت، مفروض است. روابط تقدمی در این شبکه به ساده ترین شکل یعنی CPMبوده و تاخیر زمانی نیز در نظر گرفته نمی شود. یک یا چند منبع تجدیدپذیر با سطح دسترسی از پیش تعیین شده موجود است که میزان مصرف هر فعالیت از هر یک از آنها مقداری صحیح و مثبت میباشد. هدف یافتن برنامه ای است که در حین ارضای محدودیتهای تقدمی و منابع فوق الذکر، مدت زمان اجرای پروژه را کمینه بسازد. از آنجاییکه مسئله مورد نظر ما در این پایان نامه مسئله زمانبندی پروژه با محدودیت منابع در حالت کلاسیک است، در ادبیات موضوع به شرح بیشتر روند مطالعات بر روی این مسئله در چند دهه اخیر میپردازیم.
۱-۲-۲)مسئله زمانبندی پروژه با منابع محدود چندحالته[۴۹] (MRCPSP)
در این مسئله برای هر فعالیت j چندین روش انجام وجود دارد که Mj را برابر مجموعه روش های انجام فعالیت j ام در نظر میگیریم. در این مسئله منابع میتواند تجدیدپذیر، تجدیدناپذیر و یا شامل هر دو گونه باشد. همچنین قطع فعالیت بعد از شروع و قبل از اتمام هر فعالیت امکان پذیر نمی باشد و پس از آنکه حالتی برای اجرای یک فعالیت انتخاب شد نمیتوان آن را در حین اجرای فعالیت تغییر داد. روابط تقدمی بین فعالیت ها فقط از نوع FSmin است و مقدار آن نیز برابر با صفر است. در این مسئله نیز همه پارامترها به صورت عدد صحیح و مثبت فرض می شود. در واقع مسئله زمانبندی پروژه با محدودیت منابع چند حالته تعمیمی از مسئله RCPSP است که در آن فعالیتها حالتهای متنوعی برای اجرا دارند و منابع نیز متنوع هستند. در حالت کلی میتوان چهارمسئله بسیار مهم تبادل زمان – هزینه[۵۰] و تبادل زمان – منبع[۵۱] و تبادل هزینه – منبع[۵۲] و مسئله تبادل منبع – منبع[۵۳] را زیرمجموعه ای از مسائل MRCPSP دانست. در بحث تبادل هزینه – زمان، میتوان با افزایش هزینه ها زمان انجام پروژه را کاهش داد مسائل CTCTP [۵۴] و DTCTP [۵۵] جزء مسائل مهم در این رده هستند. همچنین در بحث زمان – منبع میتوان با افزایش بعضی از منابع زمان اجرای فعالیتها را کاهش داد، مسائل CTRTP [۵۶] و DTRTP [۵۷] جزء مهمترین مسائل در این رده هستند. همچنین در بحث تبادل منبع – منبع با افزایش بعضی منابع و کاهش منابع دیگر زمان انجام فعالیتها را کاهش داد. از آنجاییکه مسئله MRCPSP تعمیم از مسئله RCPSP است بنابراین این مسئله نیز جزء مسائل بهینه سازی Np-hard است، بنابراین در چند دهه اخیر الگوریتم های دقیق و ابتکاری زیادی برای حل آن ارائه شده است. با توجه به گستردگی زیاد مسئله زمانبندی پروژه با محدودیت منابع به دلیل اینکه هر مسئله در این حیطه دارای سه جزء منبع و فعالیت و تابع هدف است که با تغییر هر یک از این اجزاء مسئله جدیدی به وجود می آید ما فقط دو مسئله مهم را در این حیطه توضیح دادیم و علاقه مندان برا ی آشنایی با انواع مسائل زمانبندی پروژه با محدودیت منابع میتوانند به منبع ]۱[ مراجعه کنند. ما فقط عناوین چند مسئله بسیار مهم را در ادامه میاوریم:از مسایل مهم در این حیطه میتوان به مسئله سرمایه گذاری منابع[۵۸] ، مسئله زمانبندی پروژه با محدودیت منابع و فعالیتهای قابل شکسته شدن[۵۹] ، مسئله تسطیح منابع[۶۰] ، مسئله زمانبندی پروژه با محدودیت منابع و جریان نقدی تنزیل داده شده[۶۱] ، مسئله هزینه – زمان با روابط پیش نیازی عمومی[۶۲] و…میتوان اشاره کرد.
فصل دوم
مروری بر ادبیات زمانبندی پروژه
مقدمه
از آنجاییکه مسئله زمانبندی پروژه با محدودیت منابع برای آن روش حل دقیقی وجود ندارد (به خصوص در ابعاد بزرگ) در چند دهه اخیر روش های دقیق و ابتکاری و فرا ابتکاری زیادی برای حل مسئله پیشنهاد شده است که ما در این فصل مروری بر این تلاشها خواهیم داشت.
۲-۱)روش های دقیق
در روش های دقیق در انتهای اجرای الگوریتم جواب بهینه مسئله به دست میاید. از جمله این روشها میتوان به روش برنامه ریزی خطی، برنامه ریزی صفر – یک، برنامه ریزی عدد صحیح ، برنامه ریزی غیر خطی و برنامه ریزی پویا و روش های شاخه و کران و … اشاره کرد. ازآنجاییکه در مسئله RCPSP در ابعاد بزرگ روش های فوق در زمان معقول قادر به حل این مسئله نمی باشند معمولا فقط در ابعاد کوچک برای حل مسئله RCPSP مورد استفاده قرار میگیرند. در بین روش های دقیق حل مسئله RCPSP روش شاخه و کران از کارایی بالاتری نسبت به روش های دیگر برخوردار است. در استفاده از روش برنامه ریزی صفر – یک در حل مسئله RCPSP میتوان به تلاشهای پریتسکر[۶۳] و همکارانش(۱۹۶۹) در منبع ]۶ [ و همچنین به تلاشهای پاترسون[۶۴] و روس[۶۵] (۱۹۷۴) در منبع ]۷ [ اشاره کرد. در استفاده از روش برنامه ریزی پویا در حل مسئله RCPSP میتوان به تلاشهای کراسر[۶۶] و باتربای[۶۷] (۱۹۶۶) در منبع ]۸ [ و همچنین به تلاش پتروویچ[۶۸] (۱۹۶۸) در منبع ]۹ [ اشاره کرد. در استفاده از روش شاخه – کران برای حل مسئله زمانبندی پروژه با محدودیت منابع میتوان به تلاشهای دمولمستر[۶۹] و هرولن[۷۰] (۱۹۹۷) در منبع ]۱۰ [ و تلاشهای بروکر[۷۱] و همکارانش(۱۹۹۸) در منبع ]۱۱ [ و نیز از تلاشهای دورند نف[۷۲] و همکارانش (۲۰۰۰) میتوان اشاره کرد]۱۲[. علاقه مندان برای مطالعه مروری بر روش های دقیق حل مسئله RCPSP میتوانندبه منبع ]۱[ مراجعه کنند. ار آنجاییکه ما در این پایان نامه قصد داریم الگوریتم فراابتکاری ASO را برای حل مسئله RCPSP به کار بگیریم و آن را با سایر الگوریتم های فراابتکاری مشهور مقایسه کنبم به همین دلیل از شرح زیاد ادبیات موضوع روش های دقیق در حل مسئله RCPSP خودداری می نماییم.
۲-۲)روش های حل ابتکاری[۷۳]
در این قسمت ما به روش های مختلف ابتکاری برای حل مسئله زمانبندی پروژه با محدودیت منابع می پردازیم. از آنجاییکه مسئله RCPSP یک مسئله Np-hard است مدیران پروژه در ابعاد بزرگ این مسئله به یک زمانبندی نزدیک به بهینه اما در زمان معقول رضایت می دهند. روش های ابتکاری قادر به حل مسئله RCPSP در زمان معقول و جواب نزدیک به بهینه هستند. بهترین استفاده از روش های حل ابتکاری برای مسئله RCPSP میتوان به تلاشهای کولیش[۷۴] و هارتمن[۷۵] (۱۹۹۹) اشاره کرد و نیز یافته های هارتمن و کولیش (۲۰۰۰) جزء بهترین الگوریتم های ابتکاری در حل مسئله RCPSP هستند ]۱[. روش های حل ابتکاری مسئله RCPSP به دو بخش روش های حل ابتکاری سازنده[۷۶] و روش های حل ابتکاری بهبود[۷۷] دهنده تقسیم می شوند، که ما هر کدام از آنها را به صورت جداگانه در ادامه میاوریم]۱[ . روش های حل ابتکاری سازنده از یک برنامه خالی شروع میشود و فعالیتها را یکی یکی اضافه میکند تا یک برنامه زمانبندی شدنی به دست آید. برای رسیدن به این هدف در روش های حل ابتکاری سازنده از دو مرحله استفاده میکنند، در مرحله اول ابتدا فعالیتها را به وسیله استفاده از قوانین اولویت[۷۸] ترتیب خاصی طبق قانون اولویت مورد استفاده به فعالبتها میدهند و در مرحله دوم با بهره گرفتن از یک طرح تولید زمانبندی[۷۹] یک زمانبندی موجه که در آن هم روابط تقدمی و هم محدودیت منابع رعایت شده است تولید میشود. برای آشنایی با این دو مرحله مهم روش های حل ابتکاری سازنده در ادامه انواع قوانین اولویت و انواع طرح تولید زمانبندی را معرفی میکنیم. روش های حل ابتکاری بهبود دهنده جواب موجه تولیدشده به وسیله روش های حل ابتکاری سازنده را گرفته و آن را بهبود می بخشد.