تعدادي فعاليت تجزيه مي‌شود. اين فعاليتها به لحاظ روابط منطقي متفاوتي كه حاكم بر آنهاست با يكديگر ارتباط پيدا مي‌كنند و همچنین باعث ایجاد محدودیتهایی می گردند. یک نوع از این روابط، رابطه تقدم- تاخر است؛ یعنی اجرای برخی فعالیت ها، وابسته به اجرای چند فعالیت دیگر در پروژه است. یعنی برخی فعالیتها پیش نیاز برخی دیگر هستند. در این صورت میگوییم پروژه داراي محدودیتهاي تقدمی است. اما علاوه بر این محدودیتها، ممکن است محدودیتهایی تحت عنوان محدودیتهاي منابع نیز در پروژه وجود داشته باشند. منظور از منابع مواردی مانند ماشین آلات و مواد اولیه و نیروی انسانی و پول و سرمایه و …است. اين منابع غالباً به دو دسته تجديدشدني7 و تجديدنشدني8 تقسيم مي‌شوند. منابع تجدید نشدنی مانند سرمايه را پس از استفاده دیگر نمیتوان مجددا بکار برد ولی منابع تجدید شدنی مانند نيروي انساني و ماشینآلات قابل استفاده مجدد هستند. در این پایاننامه منابع تجدیدشدنی در نظر گرفتهشدهاند. هر فعالیت پروژه میتواند در چندین حالت مختلف اجرا شود که اجراي هر حالت به منابع معینی نیاز دارد. بنابراین در برنامهریزي پروژه علاوه بر اینکه باید به محدودیتهاي تقدمی توجه داشت، برنامه ریزي باید بهگونهاي انجام گیرد که با محدودیت منابع نیز سازگار باشد. در چنین مسائلی برنامه ریزي عمدتا اجراي فعالیتها به صورت پیوسته در نظر گرفته میشود. آن دسته از مسائل برنامهریزي پروژه که محدودیتهاي منابع در آنها وجود ندارد یا در نظر گرفته نمیشود به مسائل برنامه ریزي پروژه بدون محدودیت منابع و آن دسته که داراي محدودیت منابع میباشند و این محدودیتها در برنامهریزي پروژه در نظر گرفته میشوند به مسائل برنامه ریزي پروژه با محدودیت منابع معروفند. این مسئله بصورتهای مختلف و با فرضیات متفاوت بیان شده است. در برخی مسایل، فعالیتها برای اجرا یک حالت بیشتر ندارند که به آنها تک حالته9 میگویند و در برخی دیگر هر فعالیت چند سناریو برای اجرا دارد که به آن چندحالته10 میگویند. در برخی مسائل امکان قبضه کردن11 وجود دارد یعنی میتوان اجرای یک فعالیت را متوقف کرد و فعالیت دیگر با اولویت بالاتر را اجرا کرد. در برخی مسائل حتی روابط پیشنیازی نیز از ابتدا مشخص نیستند و در حین اجرا مشخص میشوند، همچنین مدت زمان اجرای فعالیتها نیز در برخی مسائل قطعی و ثابت نیستند و درحین اجرای پروژه یا بصورت تصادفی تعیین میشوند. در این پایان نامه مسئله زمانبندی با توجه به محدودیت منابع و تک حالته، بدون قبضه کردن، با روابط پیشنیازی و مدت اجرای معین فعالیتها بررسی میگردد.
مسئله زمانبندي پروژه با منابع محدود، با توجه به شرايط متفاوت، به صورتهاي مختلف مدلسازي مي‌شود. در اينجا فرض مي‌كنيم پروژه به صورت يك شبكه فعاليت است و مانند گراف G=(V, E) كه در آنV مجموعه گره ها و بيانگر فعاليتهاي پروژه و E مجموعه يالها و بيانگر روابط منطقي بين فعاليتهاست، تعريف شده باشد. مجموعه فعالیتهای پروژه را با N={0,1,2,…,n} نشان میدهیم. فعاليتها از 0 تا n شماره‌گذاري شده‌اند. فعاليتهاي 0 وn مجازي هستند و شروع و پايان پروژه را نشان مي‌دهند. زوج مرتب (i,j) نشان دهنده این خاصیت است که فعالیت i پیشنیاز فعالیت j میباشد، یعنی فعالیت i قبل از اجرای فعالیت j باید حتما اجرا شده باشد. مجموعه این زوج مرتبها را با A نشان میدهیم. مدت زمان اجرای فعالیت i را با di نشان میدهیم. مجموعه همه منابع تجدید شدنی را با R نمایش می دهیم. در این مجموعه K منبع متفاوت وجود دارد. ظرفیت منبع i را با Ri مشخص می کنیم.
Ri ∈ R+ ∪ {∞} ، این ظرفیت را در طول اجرای پروژه در هر واحد زمان می توان استفاده کرد. Ri=∞ یعنی منبع، ظرفیت نامحدود دارد و به هرمیزان قابل استفاده است. از آنجا که استفاده از هرواحد ظرفیت منبع دارای هزینه است، جهت کاهش هزینه باید استفاده از منابع را کمینه کنیم. میزان نیاز فعالیت i به منبع k ام را با rik مشخص میکنیم. rik ∈ R+، در زمان اجرای فعالیت i، میزان rik واحد از ظرفیت منبع k ام درگیر انجام فعالیت است که دیگر فعالیتها در زمان اجرای فعالیت i نمیتوانند از آن استفاده کنند. rik = 0 یعنی فعالیت i برای اجرا به منبع k ام نیاز ندارد. پس از اجرای کامل فعالیتi ، این میزان ظرفیت از منبع k ام آزاد میگردد. زمان شروع فعالیت i را Si در نظر میگیریم. از آنجا که هر فعالیت بطور پیوسته اجرا میگردد، زمان پایان فعالیت i، برابر با Si+ di میباشد. بنابراین میتوان گفت، فعالیت i در بازه[Si , Si+ di] اجرا میشود. میزان نیاز هر فعالیت به هر منبع از کل ظرفیت آن نباید تجاوز کند. یعنی برای همه فعالیتها و منابع رابطه زیر برقرار است:
rik ≤ Rk i ∈ N , k=1,2,…,K (2-1)
از آنجا که فعالیتهای 0 , n مجازی هستند و فقط شروع و پایان پروژه را مشخص می کنند، برای آنها روابط زیر را داریم:
هیچ فعالیتی قبل از فعالیت 0 اجرا نمیگردد. یعنی هیچ فعالیتی پیش نیاز فعالیت 0 نیست.
( i,0) ∉ A i=1,2,…,n (2-2)
فعالیت 0 زودتر از همه فعالیتها اجرا میگردد یعنی پیشنیاز همه فعالیتهاست.
( 0,i) ∈ A i=1,2,…,n (2-3)
فعالیت n پیشنیاز هیچ فعالیتی نیست.
( n ,i) ∉ A i=0,1,2,…,n-1 (2-4)
همه فعالیتها پیشنیاز فعالیت n هستند و قبل از فعالیت n انجام میگیرند.
( i,n) ∈ A i=0,1,2,…,n -1 (2-5)
زمان اجرای فعالیتهای 0 و n ،صفراست.
d0=dn=0 (2-6)
فعالیتهای 0 و n نیازی به هیچ منبعی ندارند.
r0k = rnk = 0 k=1,2,…,K (2-7)
مجموعه همه جایگشتهای تعریف شده برروی مجموعه فعالیتها (N) را π مینامیم. اگر روابط پیشنیازی و محدودیت منابع را در نظر نگیریم هر کدام از جایگشتهای عضو π میتواند یک ترتیب اجرای فعالیتها باشد و هر فعالیت میتواند قبل یا بعد از فعالیت دیگر باشد. ولی چون روابط پیشنیازی بین فعالیتها و همچنین محدودیت منابع وجود دارد، برخی جایگشتها با روابط پیشنیازی و محدودیت منابع سازگارند که هر یک از آنها را یک ترتیب ممکن میگوییم. مجموعه همه ترتیبهای ممکن را با F مشخص میکنیم. F زیر مجموعه π است. اگر f ∈ F یک جایگشت ممکن باشد، از طریق f می توان فعالیتها را به ترتیبی که در f است، زمانبندی کرد. اگر زمان شروع فعالیتها در f را به ترتیب فعالیتها،کنار هم قرار دهیم، تشکیل یک زمانبندی شدنی برای مسئله مورد نظر به ما میدهند که آن را با S=(S0,S1,…,Sn) مشخص میکنیم. همچنین t را بعنوان یک نقطه زمانی خاص و مشخص فرض میکنیم. با توجه به S و t و مجموعه فعالیتها (N)، مجموعه P(s,t) را بصورت زیر تعریف می کنیم:
P(S,t) = { i ∈ N | Si ≤ t Si+ di } (2-8)
P(S,t) مجموعه همۀ فعالیتهای در حال اجرای مسئله در زمان t طبق زمانبندی S است. حال تابع rk(S,t) را بدین صورت تعریف میکنیم:
rk(S,t) : [0,Sn] → R+ rk(S,t) = ∑_(i∈P(S,t) )▒r_ik k=1,2,…,K (2-9)
rk(S,t) میزان استفاده از منبع k ام در زمان t طبق زمانبندی S را مشخص میکند. با توجه به محدودیت ظرفیت منابع، داریم:
rk(S,t) ≤ Rk k=1,2,…,K 0 ≤ t ≤ Sn (2-10)
Sn زمان شروع فعالیت n یعنی فعالیت مجازی آخر است که در واقع زمان کل پروژه را مشخص میکند. برای تضمین شرط پیشنیازی نیز رابطه زیر را داریم:
Sh + dh ≤ Sj j∈ N (h,j) ∈ A (2-11)
همانگونه که قبلا گفته شد A مجموعه همه زوج فعالیت پیش نیاز و N مجموعه فعالیتهاست. این رابطه بیان میدارد که هر فعالیت مانند h که پیش نیاز فعالیت j است قبل از شروع فعالیت j باید پایان یابد.
اگرهمه زمانبندیهای سازگار با محدودیت منابع را SR و همه زمانبندیهایی که با پیشنیازیها سازگار باشند را ST بنامیم، آنگاه هر زمانبندی شدنی عضوی از SR ∩ ST است.
تابع هدف مسئله، کمینه کردن زمان پایان پروژه12 یعنی Sn است. شروع و پایان فعالیت مجازی n با هم برابرند. بنابراین مسئله زمانبندی پروژه با منابع محدود بصورت زیر قابل مدل کردن است:
Minimize Sn (2-12)
Subject to :
Si + di ≤ Sj j∈ N , (i,j) ∈ A (2-13)
∑_(i∈P(S,t) )▒r_ik ≤ Rk k=1,2,…,K , 0 ≤ t ≤ Sn (2-14)
در ادامه برای مسئله RCPSP مثالی میزنیم.
مثال 2-3-1
پروژهای را در نظر میگیریم که دارای 6 فعالیت اصلی و 2 فعالیت مجازی است. یک منبع با ظرفیت R=4 واحد نیز داریم. مجموعه روابط پیشنیازی بصورت زیر است:
A={(0,1),(0,2), (1,3) , (3,5) , (2,4) ,(4,6),(5,7),(6,7)}
رابطه پیشنیازی (1,3) یعنی فعالیت 1 پیشنیاز فعالیت 3 است. واضح است که در مجموعه A رابطه تراگذاری برقرار است، مثلا از روابط پیشنیازی (1,3),(3,5) نتیجه میگیریم که رابطه پیشنیازی (1,5) نیز برقرار است. پیشنیاز پیشنیاز هر فعالیت، پیشنیاز آن فعالیت نیز است. مدت اجرای هر فعالیت (di) و میزان نیاز هر فعالیت به منبع (ri1 ) در شکل زیر نشان داده شدهاست.
7
6
5
4
3
2
1
i
4
1
2
2
4
3
di
2
3
4
4
3
2
ri1
شکل2-1: مدت زمان و میزان منبع مورد نیاز فعالیتهای پروژه مثال 2-3-1 [3]
گراف متناظر با پروژه بالا در شکل 2-2 نمایش داده شده است. هر گره گراف معادل یک فعالیت است عدد بالای هر گره (فعالیت) مدت زمان آن فعالیت است و عدد پایین هر گره میزان منبع مورد نیاز آن فعالیت است.
شکل 2-2: گراف متناظر با پروژه مثال 2-3-1 [3]
یک زمانبندی شدنی که محدودیتهای منابع و پیشنیازی را رعایت کرده است در شکل 2-3 نمایش داده شدهاست. محور افقی زمان و محور عمودي میزان استفاده هر فعالیت از منبع مورد نظر را مشخص میکند. طبق زمانبندی انجام شده مدت اجرای پروژه 13 است، یعنی makespan=13 میباشد.
شکل 2-3: یک زمانبندی شدنی برای پروژه مثال 2-3-1 [3]
2-4 معیارهای مدل کردن مسئله زمان بندي پروژه با منابع محدود
در قسمت قبل، مدل مسئله زمان بندي پروژه با منابع محدود بیان شد. این مسئله داراي انواع گوناگونی است و در حالتهاي مختلفی مورد بررسی قرار گرفته است. مهمترین معیارهای این دستهبنديها در ادامه بررسی میگردند[4و5].
2-4-1 ماهيت فعاليت ها
يک دستهبندي کارا براي سهولت در مرور مدلهاي متنوع در اين زمينه، توجه به ماهيت فعاليتهاي فرض شده براي اين مدلهاست. اين دستهبندي شامل موارد زير است :
تك وضعيت / چند وضعيت بودن فعاليت: يك وضعيتي بودن فعاليت به

دسته بندی : No category

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