جدول ۵-۵: تاثیر اندازه نخبه بر نرخ موفقیت الگوریتم TLBO ………………………………………..73
جدول ۵-۶: تاثیر اندازه نخبه بر درصد انحراف میانگین الگوریتم TLBO ……………………. 74
جدول ۵-۷: تاثیر روش زمانبندی بر الگوریتم TLBO برای مسائل J30 ………………………… 76
جدول ۵-۸: تاثیر روش زمانبندی بر الگوریتم TLBO برای مسائل J60 ………………………… 76
جدول ۵-۹: تاثیر روش زمانبندی بر الگوریتم TLBO برای مسائل J90 ………………………… 76
جدول ۵-۱۰: تاثیر روش زمانبندی بر الگوریتم TLBO برای مسائل J120 …………………… 76
جدول ۵-۱۱: تاثیر روش زمانبندی بر الگوریتم TLBO …………………………………………………. 77
جدول ۵-۱۲: مقایسه الگوریتمها برای مسائل J30 …………………………………………………………. 79
جدول ۵-۱۳: مقایسه الگوریتمها برای مسائل J60 …………………………………………………………. 80
جدول ۵-۱۴: مقایسه الگوریتمها برای مسائل J120 ……………………………………………………….. 81
فصل نخست:
مقدمه
۱-۱ مقدمه
امروزه، جهانی شدن تجارت، تغییرات سریع تکنولوژیک، بازارهای شدید رقابتی و رایزنی فشرده و قدرتمندانه شرکتها سازمانها و بنگاههای اقتصادی را وادار به تغییر سیستم مدیریتی خود مینماید، برای تطبیق و سازگاری با این تغییرات، مدیریت پروژه و پروژه محوری در مدیریت از اهمیت بالایی برای سازمانها برخوردار است. تولید کنندگان در بازار رقابتی امروز باید هزینه های تولید را تا حد امکان کاهش دهند تا بتوانند کالاهای خود را با قیمتی مناسب و قابل رقابت با دیگر رقبا به بازارها عرضه کنند. بنگاههای اقتصادی چارهای جز بالا بردن بهرهوری و انجام کارهای بیشتر و بهتر با صرف منابع و زمان کمتر ندارند. از همین جاست که مفاهیمی همچون پروژه، کنترل پروژه، زمانبندی پروژه و … مطرح شده اند.
دنیای ارتباطی امروز به کمک فناوری اطلاعات و اینترنت امکان مشارکت بیشتر بنگاههای اقتصادی را فراهم آورده است و این خود امکان تعریف پروژه هایی بزرگتر را تسهیل کردهاست. تاخیر در ساخت یا توزیع، گاهی به از دست رفتن یک بازار میانجامد و از این روست که حداقل کردن زمان انجام پروژه ها در کنار کیفیت و قیمت اهمیت بیشتری مییابد.
تاریخچه مدیریت پروژه در دنیای جدید به سالهای ابتدایی دهه ۱۹۰۰ میلادی باز میگردد؛ هنری گانت با توسعه نمودار میلهای ابداعی خود آغازگر حرکت پرشتاب بعدی طی سالهای دهه ۱۹۵۰ و ۱۹۶۰ میلادی در پروژههای نظامی و هوافضای آمریکا و سپس انگلستان گردید. هرچند نام پرآوازه هنری گانت به عنوان پدر تکنیکهای برنامهریزی و کنترل پروژه در تاریخ ثبت گردیده است لیکن سالهای دهه ۱۹۵۰ و ۱۹۶۰ به عنوان سالهای آغازین رشد و توسعه مدیریت پروژه در دنیای معاصر شناخته میشود. این سالها سرآغاز تکوین و توسعه بسیاری از روشها و دانشهای مربوط به مدیریت پروژه است که سالها بعد توسط نرمافزارهای مختلف عملیاتی و در پروژهها بکار گرفته شدند.
با توجه به همین مفاهیم، به دنبال طرح و زمانبندی برای انجام یک پروژه خواهیم بود که مسلما تاثیر بهسزایی در موفقیت پروژه و رسیدن به اهداف آن بازی خواهد کرد. این زمانبندی از طرفی باید با توجه به محدودیتهای منابع باشد و از طرف دیگر ممکن است به دلایل مختلف به دنبال حداقل کردن مدت زمان انجام پروژه باشیم و یا به دلایل اقتصادی به دنبال بیشینه کردن ارزش خالص فعلی پروژه باشیم.
یک پروژه مجموعهای از فعالیتهاست که برای دستیابی به منظور یا هدف خاصی انجام میگیرد. پروژهها شامل فعالیتهایی هستند که باید در تاریخهای معین، با هزینههایی معین و کیفیت تعیینشدهای به انجام رسند. بین این فعالیتها روابط پیشنیازی برقرار است و روابط تقدم- تاخر بین آنها وجود دارد، به این معنی که برخی فعالیتها وابسته به برخی دیگر هستند و برای اجرای یک فعالیت باید فعالیتهای پیشنیاز آن پایان یافته باشند یا حداقل تا مرحله لازم پیش رفته باشند. برنامه ریزی پروژه عبارت است از تعیین ترتیب زمانی یا برنامه زمانبندی جهت انجام فعالیتهای وابسته که تشکیل دهنده پروژه هستند. لازمه موفقیت هر پروژه، دستیابی توام به هر سه عامل زمان، هزینه و کیفیت معین است و خارج شدن هر یک از سه عامل مذکور از حدود تعیین شده، میتواند به انجام پروژهای ناموفق و غیراقتصادی منجر شود. از فاکتورهای مهم موثر در زمان و هزینه پروژه منابع مورد استفاده در پروژه از قبیل پول و مواد اولیه و تجهیزات و نیروی انسانی است. برخی منابع تجدیدپذیر هستند یعنی مصرفی نیستند و بارها میتوان از آنها استفاده کرد مانند نیروی انسانی و برخی دیگر مانند مواد خام مصرفی هستند و تجدیدناپذیر میباشند. معمولا این منابع محدود هستند و بین فعالیتها بصورت مشترک استفاده میشوند که این خود باعث ایجاد محدودیتی دیگر در اجرای فعالیتها و زمانبندی پروژه می شود. یک فعالیت برای اجرای خود باید تمام منابعش مهیا باشد تا به فعالیت اختصاص یابد. گاهی میتوان یک فعالیت را میتوان با تخصیص بخشی از منابع مورد نیازش، شروع کرد ولی برای خاتمه آن باید همه منابع مورد نیازش تامین شود. در اینجا فرض براین است که در ابتدای شروع هر فعالیت از پروژه همه منابع مورد نیازش به آن فعالیت تخصیص داده شود و پس از اجرای فعالیت، منابع باقیمانده آزاد گردند. منابع مورد نظر نیز تجدیدشدنی هستند.
بطورکلی انجام پروژه به پنج فاز تقسیم میشود. فاز اول، تعربف پروژه است که بر چگونگی پیدایش دید نسبت به پروژه و تعیین اهداف تاکید دارد. در این فاز، برخی عناصر کلیدی مجزا گردهم آمده و به تخمین اینکه پروژه چهچیز را باید ارائهدهد، می پردازد، فعالیتهای پروژه مشخص میگردد و اهداف کلی پروژه تعریف میشوند. فاز دوم، برنامهریزی پروژه است که شامل تعیین منابع لازم برای انجام پروژه، برنامهریزی، زمانبندی و تهیه بودجه پروژه است. در این مرحله اهداف به فعالیتهای ملموس تبدیل میگردند و گروههای کاری برای انجام این فعالیتها تشکیل می شود. در این مرحله است که محدوده پروژه واقعی می شود و توالی فعالیتها تعیین میشوند و زمانبندی موقت انجام میگیرد و برنامه تخصیص منابع به فعالیتها تهیه می شود. این تحقیق نیز در این فاز انجام میگیرد و به زمانبندی پروژه با توجه به محدودیت منابع می پردازد و در تلاش است تا با بهره گرفتن از روش های بهینه سازی و الگوریتمهای فراابتکاری[۱] بهترین توالی انجام فعالیتها را که کمترین زمان اجرا دارند را تعیین کند. فاز سوم، اجرای پروژه است که فعالیتهای هماهنگسازی و راهبری تیم پروژه بهسوی انجام موثر فعالیتهای پروژه را شامل می شود. نامین منابع مورد نیاز مانند پول، نیرویانسانی، تجهیزات در این مرحله انجام میگیرد. فاز چهارم، هدایت و کنترل پروژه است که در آن بر چگونگی انجام پروژه نظارت میشود. مرحله سوم و چهارم همزمان انجام میگیرند. تاکید این فاز بر روی چگونگی برخورد موثر مدیر با تاخیرات ناخواسته، تخطی از سقف بودجه یا تغییر محدوده پروژه است. ممکن است در این فاز پروژه دوباره برنامه ریزی و زمانبندی شود. آخرین فاز پروژه، بستن پروژه است؛ زمانی که بازتاب همه فعالیتها و تلاشهای انجامشده را میتوان دید بیشک مهمترین فاز پروژه ، بستن و اتمام آن است. فازهای دو تا چهار یعنی برنامهریزی، اجرا و کنترل در یک چرخه قرار دارند؛ این به دلیل ماهیت وابستگی درونی این فازها به یکدیگر است. مثلا گاهی لازم است تا برنامه پروژه با توجه به تجربیات بدستآمده در حین اجرا، یا بواسطه تغییرات پدیدآمده در طول پروژه، اصلاح شود و نتایج اصلاح مجددا برای اجرا ارسال گردد.
زمانبندی پروژه در صنعت و کارخانجات و حمل و نقل و فروش و پرداخت و … استفاده میگردد و کمتر سازمانی است که اهمیت آن را درک نکرده باشد. دستهای از مسائل برنامه ریزی پروژه که محدودیتهای منابع در آنها وجود ندارد یا در نظر گرفته نمی شود به مسائل برنامه ریزی پروژه بدون محدودیت منابع و آن دسته که دارای محدودیت منابع میباشند و این محدودیتها در برنامه ریزی پروژه در نظر گرفتهمیشوند به مسائل برنامه ریزی پروژه با محدودیت منابع[۲] معروفند. زمانبندی پروژه با در نظر گرفتن محدودیت منابع از جمله مسایل با ادبیات غنی در حوزه مسائل تحقیق در عملیات و مدیریت پروژه است. این مسئله با توجه به شرایط متفاوت کاربردی و صنعتی از نظر تابع هدف، خصوصیات فعالیت ها، منابع و روابط پیش نیازی بسیار متنوع اند و محققین همواره به دنبال ارائه راه حل های کاراتری برای حل این مسئله بوده اند. با توجه به اینکه در تمام سطوح پروژه با محدودیت منابع مواجه هستیم، لذا لزوم ایجاد و بکارگیری روشهایی که انواع محدودیتهای منابع را در نظر بگیرند، مشخص است.
۱-۲ اهداف پژوهش
معمولا در مسئله زمانبندی پروژه با محدودیت منابع، هدف زمانبندی فعالیتها با توجه به روابط پیشنیازی و محدودیت منابع در کمترین زمان میباشد. در این تحقیق نیز، راهحلی جدید برای مسئله زمانبندی پروژه با منابع محدود ارائه می شود که از الگوریتم بهینهسازی مبتنی بر آموزش- یادگیری TLBO استفاده می شود. به علت کاربردهای عملی فراوان و همچنین پیچیدگیهای خاص، این مسئله بسیار مورد توجه محققین بوده است و در سالهای اخیر تحقیقات بسیاری بر روی آن صورت گرفته است. در این تحقیقات معیارهایی برای تشخیص و تعیین مطلوبیت یک زمانبندی برای پروژه های تحت بررسی بکار گرفته شده است. از جمله این معیارها نرخ موفقیت و میانگین زمان پردازش و میزان انحراف از پاسخ بهینه یا میزان انحراف از مسیر بحرانی پروژه است. در این پایان نامه معیارهای نرخ موفقیت و میزان انحراف از پاسخ بهینه یا میزان انحراف از مسیر بحرانی پروژه برای بررسی و مقایسه در نظر گرفته شده است. به علت اهمیت این مسئله محققین کتابخانه هایی از مسایل نمونه را ایجاد کرده اند و در اختیار کاوشگران قرار دادهاند. برای حل این مسئله بصورت دقیق با بهره گرفتن از مدلهای ریاضی تلاشهای زیادی انجام گرفته است که با بزرگ شدن اندازه مسئله یعنی افزایش تعداد فعالیتها و منابع این الگوریتمها موثر نیستند. در حالتهای با پیچیدگی زیاد از پاسخهای مسئله زمانبندی پروژه بدون محدودیت منابع کمک گرفته می شود و این پاسخها به عنوان حدپایین برای الگوریتمها در حل مسئله زمانبندی پروژه با محدودیت منابع در نظر گرفته میشوند و مانند پاسخ بهینه نگریسته میشوند. همچنین طول مسیر بحرانی پروژه در حالت بدون محدودیت منابع نیز عامل دیگری است که میزان انحراف پاسخهای یافته شده در حالت محدودیت منابع از این مسیر بحرانی از فاکتورهای مطلوب بودن الگوریتم بکار گرفته شده است. در زمانبندی پروژه بدون در نظر گرفتن محدودیت منابع از روشهایی مانند CPM , PERT استفاده می شود. این روشها شبیه به هم هستند و تفاوتشان در زمان اجرای فعالیتهاست. هیچکدام از روش های مذکور محدودیت منابع را در نظر نمیگیرند و به همین دلیل در حل مسئله زمانبندی پروژه با محدودیت منابع، قابل استفاده نیستند.
در سالهای اخیر الگوریتمهای فراابتکاری زیادی برای حل این مسئله پیشنهاد شده است. به علت پیچیدگی بالا، به دست آوردن جواب بهینه این مسئله با بهره گرفتن از روشهای سنتی بهینهسازی، بسیار دشوار و یا حتی غیر ممکن است. بهینهسازی ریاضی و محاسباتی در مسایل مهندسی با مقیاس بزرگ، سختیهای زیادی را با همراه دارد و زمان حل آنها در این مسائل به صورت نمایی افزایش مییابد. بهمین دلیل راه حلهای جایگزین و متناوب را بصورت مشارکتی ایجاد کرده اند. روشهای سنتی مانند برنامهنویسی خطی، برنامهنویسی پویا و … هستند که غالبا در این مسایل با شکست روبرو می شوند یا دارای پاسخهای بهینه محلی هستند. این مسایل دارای متغیرهای خیلی زیادی هستند و توابع هدف غیر خطی دارند. برای حل و پوشش این مسایل الگوریتم های فراابتکاری جدیدی ارائه شده اند که پاسخهایی نزدیک به جواب بهینه را جستجو می کنند. این الگوریتمها در دسته های مختلفی دسته بندی میشوند که بستگی به معیار مورد نظر مانند مبتنی بر جمعیت، مبتنی بر تکرار و… دارند. در این پایان نامه الگوریتم فرا ابتکاری مبتنی بر آموزش- یادگیری یعنی [۳]TLBO برای حل این مسئله استفاده شده است. TLBO یکی از الگوریتمهای مبتنی بر جمعیت است که اخیرا معرفی شده است و فرایند آموزش و یادگیری در کلاس درس را شبیهسازی می کند. همچنین برای جلوگیری از محلی شدن پاسخها از رویکرد نخبهگرایی در این الگوریتم استفاده شدهاست.
الگوریتم مورد استفاده با بکارگیری عملیات فازهای خود به حل مسئله زمانبندی پروژه با محدودیت منابع می پردازد. به منظور بررسی کارایی الگوریتم و مقایسه آن با الگوریتمهای دیگری که به حل این مسئله پرداختهاند، مسائل نمونه مختلف و شناخته شدهای که در این حوزه تعریف شده اند، با الگوریتم پیشنهادی حل شدهاست. نتایج به دست آمده با بهترین الگوریتم های موجود در ادبیات موضوع مقایسه شدهاست. نتایج بدست آمده دلالت بر این دارد که الگوریتم مورد استفاده از کارایی مطلوب و قابل رقابتی در مقایسه با الگوریتمهای دیگر برخوردار است و نتیجه بهتری از بیشتر آنها دارد.
۱-۳ ساختار پژوهش
در این پژوهش در ادامه یعنی در فصل دوم، به معرفی مسئله زمانبندی پروژه با منابع محدود میپردازیم و با فرمول های ریاضی آن را مدل میکنیم. سپس در فصل سوم الگوریتم TLBO را بررسی میکنیم. در فصل چهارم، رویکردهای سری و موازی و روشهای پسرو و پیشرو را برای زمانبندی اولیه با مثال تشریح میکنیم. سپس الگوریتم TLBO با رویکرد نخبهگرایانه را با مسئله زمانبندی پروژه با منابع محدود تطبیق میدهیم و بوسیله برنامهنویسی، مسئله را حل میکنیم. در فصل پنجم، مسایل نمونه ای که با این الگوریتم حل شده اند توضیح داده شده اند. نتایج عددی بدست آمده را با توجه به پارامترهایی مانند اندازه جمعیت و حداکثر تعداد زمانبندیها بررسی مینماییم. در پایان نیز نتایج بدست آمده با الگوریتم TLBO در حل مسئله زمانبندی پروژه با منابع محدود با دیگر الگوریتمها مقایسه میگردد.
فصل دوم:
مروری بر ادبیات تحقیق و حل مسئله
۲-۱ مقدمه
دراین فصل از پایان نامه ادبیات موضوع را مشخص میکنیم و به تعریف مسئله زمانبندی پروژه با محدودیت منابع (RCPSP) میپردازیم. ابتدا زمانبندی پروژه را بررسی میکنیم و سپس مسئله زمانبندی پروژه با محدودیت منابع را به تفصیل تعریف میکنیم.
۲- ۲ زمانبندی پروژه
زمانبندی، یکی از مسائل مهم در مرحله برنامه ریزی پروژه است. زمانبندی پروژه عبارت است از تعیین زمان شروع هر یک از فعالیت های پروژه با توجه به محدودیتها و به منظور رسیدن به یک یا چند هدف مشخص میباشد[۱]. گاهی برنامه ریزی پروژه با برنامه زمانبندی پروژه معادل گرفته میشوند که این همارزی دقیق نیست. زمانبندی پروژه با توالی فعالیتها، طول عملیات و روابط آنها سروکار دارد، در صورتیکه برنامه ریزی بستر بزرگتری بوده که برنامه زمانبندی جزیی از آن است. برنامه ریزی عبارت از تجهیز منابع و کلیه سیستمهای پروژه در جهت اجرای بموقع و طبق طرح و بودجه تعیین شده آن است. در این تحقیق زمانبندی پروژه بررسی میگردد. مهمترین اهداف زمانبندی پروژه عبارتند از[۲]:
-
- تعیین زمان شروع و پایان فعالیتها و مشخص کردن زمان پایان پروژه
-
- تعیین میزان منابع در دسترس و منابع استفاده شده در هر لحظه از اجرای پروژه
-
- ارزیابی تاثیر تغییر در ترتیب اجرای فعالیتها بر زمان تکمیل پروژه
-
- تصمیم گیری و واکنش صحیح در مواردی که زمانبندی نشان میدهد، زمان پایان پروژه دیر است.
-
- ارزیابی زیان ناشی از دیرکرد تکمیل پروژه
-
- تعیین جریان نقدینگی پروژه
فرض بر این است که پروژه در حدی بزرگ است که میتوان آن را به چند فعالیت تقسیم کرد و روابط پیشنیازی بین فعالیتها برقرار است یعنی یک فعالیت زمانی شروع به اجرا می کند که فعالیتهای پیشنیاز آن اجرا شدهباشند. در دنیای واقعی پروژه ها شامل صدها فعالیت هستند[۲]. با بهره گرفتن از گراف (شبکه) میتوان فعالیتهای پروژه و روابط پیشنیازی آنها را نمایش داد. وزن هر یال زمان اجرای فعالیت انتهای یال را مشخص می کند. همچنین ممکن است هر فعالیت، محدودیتی به شکل زودترین زمان شروع یا دیرترین زمان پایان داشته باشد، یعنی این فعالیت باید در یک بازه زمانی مشخص انجام پذیرد. در مسائل زمانبندی در نظر گرفتن تمام محدودیتهایی که برای اجرای فعالیتها وجود دارند الزامی است. تابع هدف نیز در زمانبندی مهم است. کمترین زمان اتمام پروژه، کمترین زمان تاخیر، کمترین تعداد فعالیتهایی که بعد از زمان تعیین شده به پایان میرسند یا ترکیبی از این موارد، نمونههایی از تابع هدف هستند.
از مهمترین تکنیکهای زمانبندی که بطور گسترده استفاده شده است روش مسیر بحرانی (CPM)[4] است. برنامه های کامپیوتری و الگوریتمهای زیادی برای زمانبندی به روش مسیر بحرانی موجود است. در این روش کمترین زمان تکمیل پروژه همراه با زمان های ممکن شروع و پایان فعالیتهای پروژه محاسبه میگردد. مسیر بحرانی، مجموعه یا ترتیبی از فعالیتهاست که بیشترین زمان اجرا را خواهند داشت. طول زمان مسیر بحرانی، مجموع مدت زمانهای اجرای فعالیتهای این مسیر است. مسیر بحرانی را میتوان بعنوان طولانیترین مسیر ممکن در شبکه فعالیتهای پروژه تعریف کرد. مدت زمان اجرای فعالیتهای مسیر بحرانی، حداقل زمان لازم برای تکمیل پروژه را مشخص می کند. هر تاخیری در مسیر بحرانی منجر به افزایش زمان تکمیل پروژه می شود[۲]. پروژه ممکن است چند مسیر بحرانی داشته باشد. در روش مسیر بحرانی محدودیت منابع را در نظر نمیگیریم. این روش را در مسائل زمانبندی پروژه بدون محدودیت منابع میتوان بکار برد. در روش مسیر بحرانی طول زمان اجرای هر فعالیت از قبل مشخص و بصورت ثابت در نظر گرفته می شود، در حالیکه در بیشتر پروژه ها، اینگونه نیست. روش PERT [۵]روش دیگری است که مانند روش مسیر بحرانی است، با این تفاوت که طول زمان اجرای فعالیتها از قبل مشخص و ثابت نیست. در این روش کمترین مدت زمان و بیشترین مدت زمان انجام هر فعالیت تخمین زده می شود و زمان مورد انتظار محاسبه می شود. روش PERT یک روش احتمالی است. در این روش نیز محدودیت منابع در نظر گرفته نمی شود و مناسب مسائل زمانبندی پروژه بدون محدودیت منابع است. روشهای مذکور هر چند محدودیت منابع را رعایت نمیکنند ولی به معنی بدون استفاده بودن آنها در حالت محدودیت منابع نیز نیستند. مشکل تخصیص منابع وقتی بوجود می آید که منابع مورد نیاز برای انجام همزمان فعالیتهای غیر وابسته را نتوان تامین کرد. در این وضعیت ناچاریم برخی فعالیتها را با تاخیر اجرا کنیم. بهتر است تاخیر را به فعالیتهایی دهیم که در مسیر بحرانی نیستند. همچنین میزان انحراف از مسیر بحرانی از معیارهای سنجش الگوریتمهای زمانبندی است.
۲-۳ زمان بندی پروژه با منابع محدود
مسئله زمان بندی پروژه با منابع محدود، یک مسئله کاملا سخت[۶] است و برای نخستین بار در سال ۱۹۶۳ مطرح شد. این مسئله یکی از پیچیدهترین مسائل تحقیق در عملیات است که در دهه های اخیر پیشرفتهای قابل توجهی در تدوین روشهای حل دقیق و ابتکاری آن به وجود آمده و اخیرا روشهای جدید بهینهسازی در حل آن به کار گرفته شده اند. در این مسئله، پروژه به تعدادی فعالیت تجزیه میشود. این فعالیتها به لحاظ روابط منطقی متفاوتی که حاکم بر آنهاست با یکدیگر ارتباط پیدا میکنند و همچنین باعث ایجاد محدودیتهایی می گردند. یک نوع از این روابط، رابطه تقدم- تاخر است؛ یعنی اجرای برخی فعالیت ها، وابسته به اجرای چند فعالیت دیگر در پروژه است. یعنی برخی فعالیتها پیش نیاز برخی دیگر هستند. در این صورت میگوییم پروژه دارای محدودیتهای تقدمی است. اما علاوه بر این محدودیتها، ممکن است محدودیتهایی تحت عنوان محدودیتهای منابع نیز در پروژه وجود داشته باشند. منظور از منابع مواردی مانند ماشین آلات و مواد اولیه و نیروی انسانی و پول و سرمایه و …است. این منابع غالباً به دو دسته تجدیدشدنی[۷] و تجدیدنشدنی[۸] تقسیم میشوند. منابع تجدید نشدنی مانند سرمایه را پس از استفاده دیگر نمی توان مجددا بکار برد ولی منابع تجدید شدنی مانند نیروی انسانی و ماشینآلات قابل استفاده مجدد هستند. در این پایان نامه منابع تجدیدشدنی در نظر گرفتهشده اند. هر فعالیت پروژه می تواند در چندین حالت مختلف اجرا شود که اجرای هر حالت به منابع معینی نیاز دارد. بنابراین در برنامه ریزی پروژه علاوه بر اینکه باید به محدودیتهای تقدمی توجه داشت، برنامه ریزی باید بهگونه ای انجام گیرد که با محدودیت منابع نیز سازگار باشد. در چنین مسائلی برنامه ریزی عمدتا اجرای فعالیتها به صورت پیوسته در نظر گرفته می شود. آن دسته از مسائل برنامه ریزی پروژه که محدودیتهای منابع در آنها وجود ندارد یا در نظر گرفته نمی شود به مسائل برنامه ریزی پروژه بدون محدودیت منابع و آن دسته که دارای محدودیت منابع میباشند و این محدودیتها در برنامه ریزی پروژه در نظر گرفته میشوند به مسائل برنامه ریزی پروژه با محدودیت منابع معروفند. این مسئله بصورتهای مختلف و با فرضیات متفاوت بیان شده است. در برخی مسایل، فعالیتها برای اجرا یک حالت بیشتر ندارند که به آنها تک حالته[۹] میگویند و در برخی دیگر هر فعالیت چند سناریو برای اجرا دارد که به آن چندحالته[۱۰] میگویند. در برخی مسائل امکان قبضه کردن[۱۱] وجود دارد یعنی میتوان اجرای یک فعالیت را متوقف کرد و فعالیت دیگر با اولویت بالاتر را اجرا کرد. در برخی مسائل حتی روابط پیشنیازی نیز از ابتدا مشخص نیستند و در حین اجرا مشخص میشوند، همچنین مدت زمان اجرای فعالیتها نیز در برخی مسائل قطعی و ثابت نیستند و درحین اجرای پروژه یا بصورت تصادفی تعیین میشوند. در این پایان نامه مسئله زمانبندی با توجه به محدودیت منابع و تک حالته، بدون قبضه کردن، با روابط پیشنیازی و مدت اجرای معین فعالیتها بررسی میگردد.
مسئله زمانبندی پروژه با منابع محدود، با توجه به شرایط متفاوت، به صورتهای مختلف مدلسازی میشود. در اینجا فرض میکنیم پروژه به صورت یک شبکه فعالیت است و مانند گراف G=(V, E) که در آنV مجموعه گره ها و بیانگر فعالیتهای پروژه و E مجموعه یالها و بیانگر روابط منطقی بین فعالیتهاست، تعریف شده باشد. مجموعه فعالیتهای پروژه را با N={0,1,2,…,n} نشان میدهیم. فعالیتها از ۰ تا n شمارهگذاری شدهاند. فعالیتهای ۰ وn مجازی هستند و شروع و پایان پروژه را نشان میدهند. زوج مرتب (i,j) نشان دهنده این خاصیت است که فعالیت i پیشنیاز فعالیت j میباشد، یعنی فعالیت i قبل از اجرای فعالیت j باید حتما اجرا شده باشد. مجموعه این زوج مرتبها را با A نشان میدهیم. مدت زمان اجرای فعالیت i را با di نشان میدهیم. مجموعه همه منابع تجدید شدنی را با R نمایش می دهیم. در این مجموعه K منبع متفاوت وجود دارد. ظرفیت منبع i را با Ri مشخص می کنیم.
Ri ∈ ℝ+ ∪ {∞} ، این ظرفیت را در طول اجرای پروژه در هر واحد زمان می توان استفاده کرد. Ri=∞ یعنی منبع، ظرفیت نامحدود دارد و به هرمیزان قابل استفاده است. از آنجا که استفاده از هرواحد ظرفیت منبع دارای هزینه است، جهت کاهش هزینه باید استفاده از منابع را کمینه کنیم. میزان نیاز فعالیت i به منبع k ام را با rik مشخص میکنیم. rik ∈ ℝ+، در زمان اجرای فعالیت i، میزان rik واحد از ظرفیت منبع k ام درگیر انجام فعالیت است که دیگر فعالیتها در زمان اجرای فعالیت i نمی توانند از آن استفاده کنند. rik = ۰ یعنی فعالیت i برای اجرا به منبع k ام نیاز ندارد. پس از اجرای کامل فعالیتi ، این میزان ظرفیت از منبع k ام آزاد میگردد. زمان شروع فعالیت i را Si در نظر میگیریم. از آنجا که هر فعالیت بطور پیوسته اجرا میگردد، زمان پایان فعالیت i، برابر با Si+ di میباشد. بنابراین میتوان گفت، فعالیت i در بازه[Si , Si+ di] اجرا می شود. میزان نیاز هر فعالیت به هر منبع از کل ظرفیت آن نباید تجاوز کند. یعنی برای همه فعالیتها و منابع رابطه زیر برقرار است:
rik ≤ Rk i ∈ N , k=1,2,…,K (2-1)