یک زمانبندی شدنی که محدودیتهای منابع و پیشنیازی را رعایت کرده است در شکل ۲-۳ نمایش داده شدهاست. محور افقی زمان و محور عمودی میزان استفاده هر فعالیت از منبع مورد نظر را مشخص می کند. طبق زمانبندی انجام شده مدت اجرای پروژه ۱۳ است، یعنی makespan=13 میباشد.
شکل ۲-۳: یک زمانبندی شدنی برای پروژه مثال ۲-۳-۱ [۳]
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
۲-۴ معیارهای مدل کردن مسئله زمان بندی پروژه با منابع محدود
در قسمت قبل، مدل مسئله زمان بندی پروژه با منابع محدود بیان شد. این مسئله دارای انواع گوناگونی است و در حالتهای مختلفی مورد بررسی قرار گرفته است. مهمترین معیارهای این دستهبندیها در ادامه بررسی میگردند[۴و۵].
۲-۴-۱ ماهیت فعالیت ها
یک دستهبندی کارا برای سهولت در مرور مدلهای متنوع در این زمینه، توجه به ماهیت فعالیتهای فرض شده برای این مدلهاست. این دستهبندی شامل موارد زیر است :
- تک وضعیت / چند وضعیت بودن فعالیت: یک وضعیتی بودن فعالیت به این معنی است که آن فعالیت را فقط می توان با یک سناریو از نظر طول زمان اجرا و میزان منابع مورد نیاز انجام داد. در حالت چند وضعیتی می توان فعالیت را با ترکیبهای مختلفی از نظر طول زمان اجرا و میزان منابع مورد نیاز به انجام رساند. مثلا یک فعالیت را با یک کارگر در ۱۰ ساعت میتوان انجام داد، همان فعالیت را با دو کارگر در ۵ ساعت میتوان انجام داد که دو سناریو برای این فعالیت وجود دارد.
- قابلیت انقطاع فعالیت[۱۳] : اگر بتوان یک فعالیت را در حین اجرا متوقف کرد و در زمانی دیگر آن را ادامه داد به آن، فعالیت قابل انقطاع میگویند. در غیر این صورت این فعالیت غیر قابل انقطاع میباشد. برای مثال این مسئله با قابلیت انقطاع بوسیله روش شاخه و کران حل شدهاست[۶].
- احتمالی /قطعی[۱۴] : درصورتیکه طول زمان اجرای فعالیتها غیرقطعی یا احتمالی باشد، مدل زمانبندی احتمالی خواهد بود.
۲-۴-۲ نوع منبع
دستهبندی دیگر مدل زمانبندی براساس نوع منبع است که قبلا نیز بیان شدهاست. در این دستهبندی منابع به دو دسته تجدیدپذیر و غیرتجدیدپذیر تقسیم میشوند. اگر میزان مشخصی از منبع به طور مداوم در طول اجرای فعالیتها موجود باشد، منبع تجدیدپذیر است (مانند ماشین آلات و نیروی انسانی). اگر منبعی در اجرای فعالیتها مصرف شود و به پایان برسد منبع غیرتجدیدپذیر است (مانند بودجه و مواد اولیه). دسته دیگری از منابع نیز هستند که به آنها شبه تجدیدناپذیر گویند. منابع غیرتجدیدپذیری هستند که در پایان اجرای پروژه دوباره تجدید میشوند(مانند سرمایه). کمتر به این نوع منابع پرداخته شده است. گاهی اوقات یک منبع هم محدودیت از نظر ظرفیت در دسترس در طول اجرای پروژه دارد و هم مصرف منبع در واحد زمان سقف معینی دارد( مانند موادی که تاریخ انقضا دارند) که به آن منبع با محدودیت توام[۱۵] میگویند.
۲-۴-۳ نوع روابط پیش نیازی
یکی از عوامل تعیین کننده در توسعه مدلهای مسئله زمانبندی نوع روابط پیشنیازی است. در برخی مسایل فعالیت می تواند بدون تاخیر پس از فعالیت پیشنیازش شروع شود و در برخی مسائل با تاخیر زمانی[۱۶] پس از فعالیت پیشنیازش شروع می شود. تاخیر زمانی نیز می تواند حداکثر و حداقل داشته باشد. همچنین بین رابطه بین دو فعالیت پیشنیاز را براساس زمان شروع و رمان پایان هر یک میتوان در نظر گرفت که باعث ایجاد چهار نوع روابط بصورتهای start to start ، start to finish، finish to start و finish to finish می شود. این روابط به همراه تاخیر زمانی در روابط کلی پیشنیازی موسوم به GPR موجود است که همراه با روابط مربوط به زودترین زمان شروع هر فعالیت[۱۷] و مهلت زمانی[۱۸] مدلی موسوم به GRSPSP از مسائل زمانبندی با محدودیت منابع را ایجاد کرده اند. دمولیمستر[۱۹] و هروئلن[۲۰] روش کران و حل برای مسئله زمانبندی GRCPSP استفاده کرده اند[۷]. همچنین اگر علاوه بر زمان تاخیر حداقلی، زمان تاخیر حداکثری نیز داشتهباشیم مسئله را RCPSP-GPR مینامند. در مسئله پایه زمانبندی با منابع محدود که در بخش ۲-۳ مطرح شد یک نوع روابط پیشنیازی داشتیم و تاخیر زمانی و مهلت زمانی نیز نداشتیم.
۲-۴-۴ نوع تابع هدف
دستهبندی مسائل براساس تابع هدف با توجه به اهداف انجام پروژه اهمیت زیادی دارد. حداقل کردن طول زمان پروژه معمولا تابع هدف بیشتر مسائل زمانبندی پروژه است. با توجه به این تابع هدف، دو نوع دستهبندی مسایل زمانبندی زیر را داریم.
-
- تابع هدف معمولی[۲۱]: یک تابع غیر نزولی از زمان اتمام فعالیتهاست. به این معنی که هنگامی که زمان اتمام فعالیتها افزایش یابد مقدار تابع هدف افزایش مییابد یا ثابت میماند.حداقل کردن کل هزینه های پروژه شامل جریمههای دیرکرد با توجه به زمانهای تحویل فعالیتها یا پروژه دیگر تابع هدف معمولی است. این تابع هدف برای مدل کردن مسئله زمانبندی پروژه های چندگانه به کار میرود که در آن چندین پروژه باید به صورت همزمان زمانبندی میشوند.
-
- تابع هدف غیر معمول[۲۲] :تابعی است که به تاخیر افتادن فعالیتها تابع هدف را بهبود میدهد. حداقل کردن وزنی زودکرد- دیرکرد فعالیتها نسبت به موعد تحویل، حداکثر کردن ارزش خالص فعلی[۲۳] نمونههایی از این نوع تابع هدف هستند. بعنوان نمونه، دمولیمستر الگوریتم کارایی، برای حل مسئله زمانبندی براساس تابع هدف حداکثر کردن ارزش خالص فعلی ارائه دادهاست[۸].
۲-۴-۵ تعداد تابع هدف
گاهی مدل دارای بیش از یک تابع هدف است. در موارد اندکی محققان برای حل مسئله زمان بندی پروژه با منابع محدود از چند تابع هدف استفاده کرده اند که تحت عناوینی مانند دوهدفه[۲۴] و چندهدفه[۲۵] از آنها یاد شدهاست.
۲-۴-۶ تعداد پروژه ها
مسئله زمانبندی پروژه با منابع محدود در حالت کلی برای اجرای یک پروژه بیان می شود. با توجه به غنی بودن ادبیات این مسئله، برای زمانبندی پروژه های یک یا چند سازمان بصورت یکپارچه، مدل مسئله زمان بندی چند پروژهای[۲۶] با منابع محدود نیز ایجاد شده است.