ت بدست‌آمده در حين اجرا، يا بواسطه‌ تغييرات پديدآمده در طول پروژه، اصلاح شود و نتايج اصلاح مجددا براي اجرا ارسال‌ گردد.
زمانبندی پروژه در صنعت و کارخانجات و حمل و نقل و فروش و پرداخت و … استفاده میگردد و کمتر سازمانی است که اهمیت آن را درک نکرده باشد. دستهای از مسائل برنامهریزي پروژه که محدودیتهاي منابع در آنها وجود ندارد یا در نظر گرفته نمیشود به مسائل برنامه ریزي پروژه بدون محدودیت منابع و آن دسته که داراي محدودیت منابع میباشند و این محدودیتها در برنامهریزي پروژه در نظر گرفتهمیشوند به مسائل برنامهریزي پروژه با محدودیت منابع2 معروفند. زمانبندي پروژه با در نظر گرفتن محدودیت منابع از جمله مسایل با ادبیات غنی در حوزه مسائل تحقیق در عملیات و مدیریت پروژه است. این مسئله با توجه به شرایط متفاوت کاربردي و صنعتی از نظر تابع هدف، خصوصیات فعالیت ها، منابع و روابط پیش نیازي بسیار متنوع اند و محققین همواره به دنبال ارائه راه حل هاي کاراتري براي حل این مسئله بودهاند. با توجه به اینکه در تمام سطوح پروژه با محدودیت منابع مواجه هستیم، لذا لزوم ایجاد و بکارگیري روشهایی که انواع محدودیتهاي منابع را در نظر بگیرند، مشخص است.
1-2 اهداف پژوهش
معمولا در مسئله زمانبندي پروژه با محدودیت منابع، هدف زمانبندي فعالیتها با توجه به روابط پیشنیازي و محدودیت منابع در کمترین زمان میباشد. در این تحقیق نیز، راهحلی جدید برای مسئله زمانبندی پروژه با منابع محدود ارایه میشود که از الگوریتم بهینهسازی مبتنی بر آموزش- یادگیری TLBO استفاده میشود. به علت کاربردهاي عملی فراوان و همچنین پیچیدگیهاي خاص، این مسئله بسیار مورد توجه محققین بوده است و در سالهاي اخیر تحقیقات بسیاري بر روي آن صورت گرفته است. در این تحقیقات معیارهایی براي تشخیص و تعیین مطلوبیت یک زمانبندي براي پروژههاي تحت بررسی بکار گرفته شده است. از جمله این معیارها نرخ موفقیت و میانگین زمان پردازش و میزان انحراف از پاسخ بهینه یا میزان انحراف از مسیر بحرانی پروژه است. در این پایان نامه معیارهای نرخ موفقیت و میزان انحراف از پاسخ بهینه یا میزان انحراف از مسیر بحرانی پروژه برای بررسی و مقایسه در نظر گرفته شده است. به علت اهمیت این مسئله محققین کتابخانههایی از مسایل نمونه را ایجاد کردهاند و در اختیار کاوشگران قرار دادهاند. براي حل این مسئله بصورت دقیق با استفاده از مدلهاي ریاضی تلاشهاي زیادي انجام گرفته است که با بزرگ شدن اندازه مسئله یعنی افزایش تعداد فعالیتها و منابع این الگوریتمها موثر نیستند. در حالتهای با پیچیدگی زیاد از پاسخهای مسئله زمانبندی پروژه بدون محدودیت منابع کمک گرفته میشود و این پاسخها به عنوان حدپایین برای الگوریتمها در حل مسئله زمانبندي پروژه با محدودیت منابع در نظر گرفته میشوند و مانند پاسخ بهینه نگریسته میشوند. همچنین طول مسیر بحرانی پروژه در حالت بدون محدودیت منابع نیز عامل دیگری است که میزان انحراف پاسخهای یافته شده در حالت محدودیت منابع از این مسیر بحرانی از فاکتورهای مطلوب بودن الگوریتم بکار گرفته شده است. در زمانبندي پروژه بدون در نظر گرفتن محدودیت منابع از روشهایی مانند CPM , PERT استفاده میشود. این روشها شبیه به هم هستند و تفاوتشان در زمان اجرای فعالیتهاست. هیچکدام از روشهای مذکور محدودیت منابع را در نظر نمیگیرند و به همین دلیل در حل مسئله زمانبندي پروژه با محدودیت منابع، قابل استفاده نیستند.
در سالهاي اخیر الگوریتمهاي فراابتکاری زیادي براي حل این مسئله پیشنهاد شده است. به علت پیچیدگی بالا، به دست آوردن جواب بهینه این مسئله با استفاده از روشهاي سنتی بهینهسازي، بسیار دشوار و یا حتی غیر ممکن است. بهینهسازی ریاضی و محاسباتی در مسایل مهندسی با مقیاس بزرگ، سختیهای زیادی را با همراه دارد و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد. بهمین دلیل راه حلهای جایگزین و متناوب را بصورت مشارکتی ایجاد کردهاند. روشهای سنتی مانند برنامهنویسی خطی، برنامهنویسی پویا و … هستند که غالبا در این مسایل با شکست روبرو می شوند یا دارای پاسخهای بهینه محلی هستند. این مسایل دارای متغیرهای خیلی زیادی هستند و توابع هدف غیر خطی دارند. برای حل و پوشش این مسایل الگوریتم های فراابتکاری جدیدی ارایه شده اند که پاسخهایی نزدیک به جواب بهینه را جستجو می کنند. این الگوریتمها در دسته های مختلفی دسته بندی میشوند که بستگی به معیار مورد نظر مانند مبتنی بر جمعیت، مبتنی بر تکرار و… دارند. در این پایان نامه الگوریتم فرا ابتکاري مبتنی بر آموزش- یادگیری یعنی 3TLBO براي حل این مسئله استفاده شده است. TLBO یکی از الگوریتمهای مبتنی بر جمعیت است که اخیرا معرفی شده است و فرایند آموزش و یادگیری در کلاس درس را شبیهسازی میکند. همچنین برای جلوگیری از محلی شدن پاسخها از رویکرد نخبهگرایی در این الگوریتم استفاده شدهاست.
الگوریتم مورد استفاده با بکارگیري عملیات فازهای خود به حل مسئله زمانبندي پروژه با محدودیت منابع میپردازد. به منظور بررسی کارایی الگوریتم و مقایسه آن با الگوریتمهاي دیگري که به حل این مسئله پرداختهاند، مسائل نمونه مختلف و شناخته شدهای که در این حوزه تعریف شدهاند، با الگوریتم پیشنهادي حل شدهاست. نتایج به دست آمده با بهترین الگوریتم هاي موجود در ادبیات موضوع مقایسه شدهاست. نتایج بدست آمده دلالت بر این دارد که الگوریتم مورد استفاده از کارایی مطلوب و قابل رقابتی در مقایسه با الگوریتمهاي دیگر برخوردار است و نتیجه بهتری از بیشتر آنها دارد.
1-3 ساختار پژوهش
در این پژوهش در ادامه یعنی در فصل دوم، به معرفی مسئله زمانبندی پروژه با منابع محدود میپردازیم و با فرمول های ریاضی آن را مدل میکنیم. سپس در فصل سوم الگوریتم TLBO را بررسی میکنیم. در فصل چهارم، رویکردهای سری و موازی و روشهای پسرو و پیشرو را برای زمانبندی اولیه با مثال تشریح میکنیم. سپس الگوریتم TLBO با رویکرد نخبهگرایانه را با مسئله زمانبندی پروژه با منابع محدود تطبیق میدهیم و بوسیله برنامهنویسی، مسئله را حل میکنیم. در فصل پنجم، مسایل نمونهای که با این الگوریتم حل شدهاند توضیح داده شدهاند. نتایج عددی بدست آمده را با توجه به پارامترهایی مانند اندازه جمعیت و حداکثر تعداد زمانبندیها بررسی مینماییم. در پایان نیز نتایج بدست آمده با الگوریتم TLBO در حل مسئله زمانبندی پروژه با منابع محدود با دیگر الگوریتمها مقایسه میگردد.
فصل دوم:
مروری بر ادبیات تحقیق و حل مسئله
2-1 مقدمه
دراین فصل از پایان نامه ادبیات موضوع را مشخص میکنیم و به تعریف مسئله زمانبندی پروژه با محدودیت منابع (RCPSP) میپردازیم. ابتدا زمانبندی پروژه را بررسی میکنیم و سپس مسئله زمانبندی پروژه با محدودیت منابع را به تفصیل تعریف میکنیم.
2- 2 زمانبندی پروژه
زمانبندي، يکي از مسائل مهم در مرحله برنامهريزي پروژه است. زمانبندي پروژه عبارت است از تعيين زمان شروع هر يک از فعاليت هاي پروژه با توجه به محدوديتها و به منظور رسيدن به يک يا چند هدف مشخص میباشد[1]. گاهی برنامه ريزي پروژه با برنامه زمانبندي پروژه معادل گرفته میشوند که این همارزی دقیق نیست. زمانبندي پروژه با توالی فعاليتها، طول عمليات و روابط آنها سروکار دارد، در صورتيکه برنامهريزي بستر بزرگتري بوده که برنامه زمانبندي جزیي از آن است. برنامه ريزي عبارت از تجهيز منابع و کليه سيستمهاي پروژه در جهت اجراي بموقع و طبق طرح و بودجه تعيين شده آن است. در این تحقیق زمانبندی پروژه بررسی میگردد. مهمترین اهداف زمانبندی پروژه عبارتند از[2]:
تعیین زمان شروع و پایان فعالیتها و مشخص کردن زمان پایان پروژه
تعیین میزان منابع در دسترس و منابع استفاده شده در هر لحظه از اجرای پروژه
ارزیابی تاثیر تغییر در ترتیب اجرای فعالیتها بر زمان تکمیل پروژه
تصمیم گیری و واکنش صحیح در مواردی که زمانبندی نشان میدهد، زمان پایان پروژه دیر است.
ارزیابی زیان ناشی از دیرکرد تکمیل پروژه
تعیین جریان نقدینگی پروژه
فرض بر این است که پروژه در حدی بزرگ است که میتوان آن را به چند فعالیت تقسیم کرد و روابط پیشنیازی بین فعالیتها برقرار است یعنی یک فعالیت زمانی شروع به اجرا میکند که فعالیتهای پیشنیاز آن اجرا شدهباشند. در دنیای واقعی پروژهها شامل صدها فعالیت هستند[2]. با استفاده از گراف (شبکه) میتوان فعالیتهای پروژه و روابط پیشنیازی آنها را نمایش داد. وزن هر یال زمان اجرای فعالیت انتهای یال را مشخص میکند. همچنین ممکن است هر فعالیت، محدودیتی به شکل زودترین زمان شروع یا دیرترین زمان پایان داشته باشد، یعنی این فعالیت باید در یک بازه زمانی مشخص انجام پذیرد. در مسائل زمانبندي در نظر گرفتن تمام محدودیتهایی که براي اجراي فعالیتها وجود دارند الزامی است. تابع هدف نیز در زمانبندی مهم است. کمترین زمان اتمام پروژه، کمترین زمان تاخیر، کمترین تعداد فعالیتهایی که بعد از زمان تعیین شده به پایان میرسند یا ترکیبی از این موارد، نمونههایی از تابع هدف هستند.
از مهمترین تکنیکهای زمانبندی که بطور گسترده استفاده شده است روش مسیر بحرانی (CPM)4 است. برنامههای کامپیوتری و الگوریتمهای زیادی برای زمانبندی به روش مسیر بحرانی موجود است. در این روش کمترین زمان تکمیل پروژه همراه با زمانهای ممکن شروع و پایان فعالیتهای پروژه محاسبه میگردد. مسیر بحرانی، مجموعه یا ترتیبی از فعالیتهاست که بیشترین زمان اجرا را خواهند داشت. طول زمان مسیر بحرانی، مجموع مدت زمانهای اجرای فعالیتهای این مسیر است. مسیر بحرانی را میتوان بعنوان طولانیترین مسیر ممکن در شبکه فعالیتهای پروژه تعریف کرد. مدت زمان اجرای فعالیتهای مسیر بحرانی، حداقل زمان لازم برای تکمیل پروژه را مشخص میکند. هر تاخیری در مسیر بحرانی منجر به افزایش زمان تکمیل پروژه میشود[2]. پروژه ممکن است چند مسیر بحرانی داشته باشد. در روش مسیر بحرانی محدودیت منابع را در نظر نمیگیریم. این روش را در مسائل زمانبندی پروژه بدون محدودیت منابع میتوان بکار برد. در روش مسیر بحرانی طول زمان اجرای هر فعالیت از قبل مشخص و بصورت ثابت در نظر گرفته میشود، در حالیکه در بیشتر پروژهها، اینگونه نیست. روش PERT 5روش دیگری است که مانند روش مسیر بحرانی است، با این تفاوت که طول زمان اجرای فعالیتها از قبل مشخص و ثابت نیست. در این روش کمترین مدت زمان و بیشترین مدت زمان انجام هر فعالیت تخمین زده میشود و زمان مورد انتظار محاسبه میشود. روش PERT یک روش احتمالی است. در این روش نیز محدودیت منابع در نظر گرفته نمیشود و مناسب مسائل زمانبندی پروژه بدون محدودیت منابع است. روشهای مذکور هر چند محدودیت منابع را رعایت نمیکنند ولی به معنی بدون استفاده بودن آنها در حالت محدودیت منابع نیز نیستند. مشکل تخصیص منابع وقتی بوجود میآید که منابع مورد نياز براي انجام هم‌زمان فعاليت‌های غیر وابسته را نتوان تامین کرد. در این وضعیت ناچاریم برخی فعالیتها را با تاخیر اجرا کنیم. بهتر است تاخیر را به فعالیتهایی دهیم که در مسیر بحرانی نیستند. همچنین میزان انحراف از مسیر بحرانی از معیارهای سنجش الگوریتمهای زمانبندی است.
2-3 زمان بندي پروژه با منابع محدود
مسئله زمان بندي پروژه با منابع محدود، يك مسئله کاملا سخت6 است و براي نخستين بار در سال 1963 مطرح شد. اين مسئله يكي از پيچيده‌ترين مسائل تحقيق در عمليات است كه در دهه‌هاي اخير پيشرفتهاي قابل توجهي در تدوين روشهاي حل دقيق و ابتكاري آن به وجود آمده و اخيرا روشهاي جديد بهينه‌سازي در حل آن به كار گرفته شدهاند. در اين مسئله، پروژه به

دسته بندی : No category

دیدگاهتان را بنویسید