۴-۳-۱) مسائل نمونه استفاده شده برای تنظیم پارامترها ۷۵

۴-۳-۲) تنظیم پارامترها ۷۷
۴-۴) نتایج محاسباتی ۷۹
۴-۴-۱) مسائل با ۳۰ فعالیت ۸۰
۴-۴-۲) مسائل با ۶۰ فعالیت ۸۲
۴-۴-۳) مسائل با ۹۰ و ۱۲۰ فعالیت ۸۴
فصل پنجم: نتیجه گیری و پیشنهادات آتی
۵-۱) نتیجه گیری کلی ۸۶
۵-۲) پیشنهادات ۸۷
۵-۲-۱) تعریف مسائل جدید مرتبط و بررسی آنها با الگوریتم ASO 87
۵-۲-۲) استفاده از روش های فراابتکاری دیگر برای حل مساله مورد بررسی ۸۸
 ۹۰
 ۹۴
فهرست جدول ها و شکل­ها
جدول ‏۱‑۱: علائم استاندارد مورد استفاده در مسئله زمانبندی پروژه ۶
جدول ‏۴‑۱: مراحل انجام عملگر crossover2 69
جدول ‏۴‑۲: تنظیم پارامترهای متغیر برای مسائل دارای ۳۰، ۶۰ و ۹۰ فعالیت ۷۳
جدول ‏۴‑۳: مسائل انتخاب شده برای انتخاب پارامترها برای ۳۰، ۶۰ و ۹۰ فعالیت ۷۵
جدول ‏۴‑۴: مسائل انتخاب شده برای انتخاب پارامترها برای ۱۲۰ فعالیت ۷۶
جدول ‏۴‑۵: عاملها و سطوح آنها برای تنظیم پارامترهای الگوریتم ASO 77
جدول ‏۴‑۶: طرح L16 تاگوچی برای الگوریتم ASO 77
جدول ‏۴‑۷: سطوح بهینه بدست آمده ۷۸
جدول ‏۴‑۸: مقایسه الگوریتم ASO طراحی شده با الگوریتمهای دیگر برای مسائل سری ۳۰ فعالیت ۸۱
جدول ‏۴‑۹: درصد میانگین انحراف از کران پایین بدست آمده تا سال ۲۰۰۶ برای سری ۶۰ فعالیت ۸۳
شکل ‏۳‑۱: فلوچارت الگوریتم ASO 57
شکل ‏۴‑۱: شکل شماتیک یک مثال از مساله RCPSP 63
شکل ‏۴‑۲: ساختار جواب مرتبط با مثال شکل ۴-۱ ۶۳
شکل ‏۴‑۳: نحوه انجام عملگر Crossover1 68
شکل ‏۴‑۴: نحوه انجام عملگر Crossover2 69
شکل ‏۴‑۵: نمودار نسبت S/N برای هر سطح عامل ۷۸
شکل ‏۴‑۶: نمودار مجموع تابع هدفهای مسائل آزمایش شده ۷۹

فصل اول
مفاهیم وکلیات زمانبندی پروژه

مقدمه

قدمت مدیریت پروژه بدون توجه به دانش مدیریت پروژه^[۱]، حداقل به ۴۵۰۰ سال پیش برمیگردد، سازندگان اهرام مصر و معابد مایا در آمریکای مرکزی اغلب به عنوان اولین مدیران پروژه دنیا محسوب می شوند]۱[. پیدایش مدیریت پروژه به عنوان یک علم از جنگ جهانی اول آغاز شد به طوریکه در سال ۱۹۱۷، هنری ال .گانت^[۲] نمودار معروف گانت چارت^[۳] را ابداع کرد. بعد از سال ۱۹۵۰ سایر تکنیک های معروف مدیریت پروزه مانند روش مسیر بحرانی^[۴] و … توسعه یافت. علم مدیریت پروژه به طور ویژه در دهه های گذشته از مهمترین و کاربردیترین موضوعات مورد توجه بوده است. با پیشرفت علوم و پیجیده تر شدن ساختارهای پروژه های تعریف شده در بخش های مختلف علمی وتجربی، مدیریت پروژه دائما به عنوان یک جزء لاینفک در کلیت پروژه خودنمایی میکند. در دنیای امروز با افزایش فضای رقابتی، تحویل به موقع کالا یا خدمات با کیفیت مورد نظر با رعایت محدودیتهای مختلف مانند نیروی کار، سرمایه و …، بسیار با اهمیت جلوه میکند. با توجه به صرفه جویی حاصل از مدیریت پروژه در زمان و منابع و هزینه، علاقه مندان به این رشته در سراسر جهان به طور تصاعدی در حال افزایش است. در میان اجزای مختلف مدیریت پروژه، زمان بندی پروژه^[۵] به جهت اهمیت و نقش به سزای آن در سطح مدیریت کلان برنامه ریزی پروژه های مختلف جایگاه ویژه ای را به خوداختصاص داده است. از بعد عملی با بهبود زمان بندی پروژه که جزئی از مدیریت پروژه است، سود شرکت ها به خصوص شرکت هایی که کار تولید و فروش را به طور همزمان انجام میدهند(تولید به مصرف) به میزان چشمگیری افزایش می یابد. از کاربردهای عملی زمان بندی پروژه می توان در زمینه های توسعه نرم افزار، برنامه ریزی در سازمان های حمل و نقل و کارهای عمرانی و بسیاری زمینه های دیگر اشاره کرد. زمان بندی پروژه علاوه بر بعد عملی، از بعد نظری و تحقیقاتی نیز بسیار حائز اهمیت است و در سال های اخیر، تحقیقات بسیاری در این زمینه صورت گرفته است. از آنجاییکه بسیاری از مسائل بهینه سازی معروف حالت خاصی از مسائل مطرح در زمانبندی پروژه هستند، این مقوله یک زمینه تحقیقاتی جذاب برای علاقه مندان علم تحقیق در عملیات است، به عنوان مثال مسئله زمانبندی کارکارگاهی^[۶] (jssp) که یکی از معروف ترین مسایل بهینه سازی ترکیبی است که حالت خاصی از مسئله زمانبندی با محدودیت منابع است که در آن منابع مسئله فقط ماشین ها هستند.
طبق استاندارد PMBOK 2008 ^[۷]مدیریت پروزه شامل ۴۲ فرایند است که زمان بندی پروژه تنها یکی از این فرایندها محسوب می شود. در یک تقسیم بندی کلی تر بر طبق استاندارد PMBOK 2008 مدیریت پروژه شامل ۵ مجموع فرایند اصلی به شرح ذیل است:

• • فرایندهای آغازین

• • فرایندهای برنامه ریزی

• • فرایندهای اجرا

• • فرایندهای کنترلی

• • فرایندهای اختتامی

زمان بندی پروژه که موضوع اصلی در این پایان نامه است، طبق این تقسیم بندی در گروه فرایندهای برنامه ریزی قرار میگیرید. زمان بندی پروژه به صورت تعیین توالی زمانی، جهت انجام یک سری فعالیت های وابسته به هم که تشکیل دهنده پروژه هستند تعریف می شود. منظور از وابستگی فعالیتها ، وجود روابط تقدمی در انجام آنهاست، بدین معنا که ممکن است انجام یک فعالیت وابسته به انجام یک یا چند فعالیت دیگر باشد، که در این حالت گفته می شود که پروژه دارای محدودیتهای تقدمی است. تعیین این برنامه زمانبندی میتواند تحت یک هدف و یا چند هدف خاص صورت گیرد. علاوه بر محدودیت های تقدمی که در تمام پروژه ها بین فعالیت ها موجود هستند، نوع دیگری از محدودیتها تحت عنوان محدودیت منابع نیز ممکن است در پروژه وجود داشته باشد. مسائل زمانبندی پروژه که فقط محدودیت تقدمی در آن وجود داشته باشد، به مسائل زمانبندی پروژه بدون محدودیت منابع معروف هستند. در مسائل زمانبندی پروژه اگر علاوه بر محدودیت تقدمی، محدودیت منابع نیز وجود داشته باشد، به مسئله زمانبندی پروژه با محدودیت منابع^[۸] (RCPSP) معروفند. اولین مدل ها و روش های زمانبندی پروژه که برای مقیاس بزرگ (بیش از صد فعالیت) طراحی شده اند به اواخر دهه ۱۹۵۰ برمیگردد. از معروفترین این روشها میتوان به روش مسیر بحرانی اشاره کرد که درسال ۱۹۶۱ توسط کلی^[۹] برای پروژه هایی که دارای فعالیت هایی با زمان های قطعی و مشخص هستند طراحی شد.از روش های معروف دیگر در زمانبندی پروژه میتوان به روش تکنیک ارزیابی و بازنگری پروژه^[۱۰] (PERT) اشاره کرد که در سال ۱۹۵۶ توسط مالکولم^[۱۱] ابداع شد و برای پروژه هایی که دارای فعالیتهایی با زمان غیر قطعی و احتمالی هستند به وجود آمد. روش تکنیک ارزیابی و بازنگری گرافیکی^[۱۲] در سال ۱۹۶۷ توسط پریتسکر^[۱۳] و هاپ^[۱۴] ابداع شد که در آن فعالیت های پروژه به صورت احتمالی هستند. روش ها و مدل های اولیه زمانبندی پروژه که به سه روش مهم آن اشاره شد، برای پروژه هایی طراحی شده بودند که فقط دارای محدودیت تقدمی بین فعالیتها هستند در حالیکه در دنیای واقعی یکی از مهمترین مشکلات زمانبندی پروژه با محدودیت منابع است. از اواخر ۱۹۶۰، مدلهای زمانبندی پروژه که در آن هم محدودیت تقدمی و هم محدودیت منابع به طور همزمان مد نظر گرفته می شد گسترش یافتند. حل این نوع مسائل نسبت به مدل های قبلی بسیار سخت بود به طوریکه روش های یادشده برای حل این نوع مسائل کارایی نداشت، در این نوع مسائل جدید زمان حل مسئله با افزایش فعالیتها به صورت نمایی افزایش می یافت و در نتیجه در مسائل بزرگ(بیش از صد فعالیت) به خاطر بزرگ شدن فضای جستجو استفاده از روش های دقیق نیز از لحاظ زمانی مرقون به صرفه نبود چراکه این نوع مسائل به خصوص در ابعاد بزرگ جزء مسائل بهینه سازی NP-hard ^[۱۵] محسوب می شدند. مسئله زمانبندی پروژه با محدودیت منابع در حالت کلاسیک (RCPSP) ساده ترین نوع مسائل زمانبندی پروژه با محدودیت منابع است که در ابعاد بزرگ (بیش از صد فعالیت) هیچ روش دقیقی برای حل آن وجو ندارد. بلازویچ^[۱۶] ثابت کرد که مسئله PCPSP به عنوان تعمیمی از مسئله JSSP یک مسئله NP-hard است به طوریکه زمان لازم برای یافتن جواب بهینه توسط بهترین روش های دقیق برای شبکه های مشتمل بر بیش از سی فعالیت بسیار زیاد است]۲[. در نتیجه محققان برای حل مسئله RCPSP در ابعاد بزرگ به روش های ابتکاری^[۱۷] و فراابتکاری^[۱۸] روی آوردند، چرا که این روشها نیاز به پیمودن کل فضای جستجو ندارند و میتوان با آنها در زمان معقول به جواب نزدیک به بهینه رسید. به همین خاطر ما در این پایان نامه سعی داریم تا از الگوریتم جدید فراابتکاری بهینه سازی جامعه نامنظم (ASO) ^[۱۹] که در سال ۲۰۱۱ توسط احمدی جاوید^[۲۰] به وجود آمده]۳[، برای اولین بار برای حل مسئله زمانبندی پروژه با محدودیت منابع در حالت کلاسیک به کار بگیریم و نتایج آن را با بهترین الگوریتم های معروف، که قبلا بکار گرفته شده مقایسه کنیم.

۱-۱)اجزای زمانبندی پروژه

اجزای یک مسئله زمانبندی پروژه در سه جزء خلاصه می شود که عبارتند از : فعالبت ها، منابع و روابط تقدمی. در ادامه به طور اجمالی به بررسی هر یک از این اجزا میپردازیم. قبل از ادامه بحث در این قسمت، جدول ۱ -۱ را به عنوان جدول استادارد علائم مورد استفاده در این پایان نامه معرفی میکنیم.
جدول ‎۰۱‑۱: علائم استاندارد مورد استفاده در مسئله زمانبندی پروژه