اين معني است كه آن فعاليت را فقط مي توان با يک سناريو از نظر طول زمان اجرا و ميزان منابع مورد نیاز انجام داد. در حالت چند وضعيتي مي توان فعاليت را با تركيبهاي مختلفي از نظر طول زمان اجرا و ميزان منابع مورد نیاز به انجام رساند. مثلا یک فعالیت را با یک کارگر در 10 ساعت میتوان انجام داد، همان فعالیت را با دو کارگر در 5 ساعت میتوان انجام داد که دو سناریو برای این فعالیت وجود دارد.
قابلیت انقطاع فعاليت13 : اگر بتوان يک فعاليت را در حين اجرا متوقف کرد و در زمانی دیگر آن را ادامه داد به آن، فعالیت قابل انقطاع میگويند. در غير اين صورت اين فعاليت غير قابل انقطاع ميباشد. برای مثال این مسئله با قابلیت انقطاع بوسیله روش شاخه و کران حل شدهاست[6].
احتمالي /قطعي14 : درصورتیکه طول زمان اجرای فعالیتها غیرقطعی یا احتمالي باشد، مدل زمانبندی احتمالي خواهد بود.
2-4-2 نوع منبع
دستهبندي ديگر مدل زمانبندی براساس نوع منبع است که قبلا نیز بیان شدهاست. در اين دستهبندي منابع به دو دسته تجديدپذير و غيرتجديدپذير تقسيم ميشوند. اگر ميزان مشخصي از منبع به طور مداوم در طول اجرای فعالیتها موجود باشد، منبع تجديدپذير است (مانند ماشين آلات و نيروي انساني). اگر منبعی در اجرای فعالیتها مصرف شود و به پايان برسد منبع غيرتجديدپذير است (مانند بودجه و مواد اولیه). دسته دیگری از منابع نیز هستند که به آنها شبه تجدیدناپذیر گویند. منابع غیرتجدیدپذیری هستند که در پایان اجرای پروژه دوباره تجدید میشوند(مانند سرمایه). کمتر به این نوع منابع پرداخته شده است. گاهي اوقات يک منبع هم محدودیت از نظر ظرفیت در دسترس در طول اجرای پروژه دارد و هم مصرف منبع در واحد زمان سقف معيني دارد( مانند موادی که تاریخ انقضا دارند) که به آن منبع با محدودیت توام15 میگویند.
2-4-3 نوع روابط پيش نيازي
يکي از عوامل تعيين کننده در توسعه مدلهاي مسئله زمانبندی نوع روابط پيشنيازي است. در برخی مسایل فعالیت میتواند بدون تاخیر پس از فعالیت پیشنیازش شروع شود و در برخی مسائل با تاخیر زمانی16 پس از فعالیت پیشنیازش شروع میشود. تاخیر زمانی نیز میتواند حداکثر و حداقل داشته باشد. همچنین بین رابطه بین دو فعالیت پیشنیاز را براساس زمان شروع و رمان پایان هر یک میتوان در نظر گرفت که باعث ایجاد چهار نوع روابط بصورتهای start to start ، start to finish، finish to start و finish to finish میشود. این روابط به همراه تاخیر زمانی در روابط کلی پیشنیازی موسوم به GPR موجود است که همراه با روابط مربوط به زودترین زمان شروع هر فعالیت17 و مهلت زمانی18 مدلی موسوم به GRSPSP از مسائل زمانبندی با محدودیت منابع را ایجاد کردهاند. دمولیمستر19 و هروئلن20 روش کران و حل برای مسئله زمانبندی GRCPSP استفاده کردهاند[7]. همچنین اگر علاوه بر زمان تاخیر حداقلی، زمان تاخیر حداکثری نیز داشتهباشیم مسئله را RCPSP-GPR مینامند. در مسئله پایه زمانبندی با منابع محدود که در بخش 2-3 مطرح شد یک نوع روابط پیشنیازی داشتیم و تاخیر زمانی و مهلت زمانی نیز نداشتیم.
2-4-4 نوع تابع هدف
دستهبندي مسائل براساس تابع هدف با توجه به اهداف انجام پروژه اهمیت زیادی دارد. حداقل كردن طول زمان پروژه معمولا تابع هدف بیشتر مسائل زمانبندي پروژه است. با توجه به این تابع هدف، دو نوع دستهبندی مسایل زمانبندی زیر را داریم.
تابع هدف معمولي21: يك تابع غير نزولي از زمان اتمام فعاليتهاست. به اين معني كه هنگامي كه زمان اتمام فعاليتها افزايش يابد مقدار تابع هدف افزايش مييابد يا ثابت ميماند.حداقل كردن کل هزينههاي پروژه شامل جريمههاي ديركرد با توجه به زمانهاي تحويل فعاليتها يا پروژه ديگر تابع هدف معمولي است. اين تابع هدف براي مدل كردن مسئله زمانبندي پروژههاي چندگانه به كار ميرود كه در آن چندين پروژه بايد به صورت همزمان زمانبندي میشوند.
تابع هدف غير معمول22 :تابعی است که به تاخیر افتادن فعالیتها تابع هدف را بهبود میدهد. حداقل کردن وزنی زودکرد- دیرکرد فعالیتها نسبت به موعد تحویل، حداکثر کردن ارزش خالص فعلی23 نمونههایی از این نوع تابع هدف هستند. بعنوان نمونه، دمولیمستر الگوریتم کارایی، برای حل مسئله زمانبندی براساس تابع هدف حداکثر کردن ارزش خالص فعلی ارایه دادهاست[8].
2-4-5 تعداد تابع هدف
گاهي مدل داراي بيش از يک تابع هدف است. در موارد اندکي محققان براي حل مسئله زمان بندي پروژه با منابع محدود از چند تابع هدف استفاده کردهاند که تحت عناوینی مانند دوهدفه24 و چندهدفه25 از آنها یاد شدهاست.
2-4-6 تعداد پروژهها
مسئله زمانبندي پروژه با منابع محدود در حالت کلی برای اجرای یک پروژه بیان میشود. با توجه به غنی بودن ادبیات این مسئله، برای زمانبندی پروژههای یک یا چند سازمان بصورت یکپارچه، مدل مسئله زمان بندي چند پروژهای26 با منابع محدود نیز ایجاد شده است.
شکل 2-4: دستهبندیهای مختلف مسئله زمانبندی با محدودیت منابع[4]
در ادامه سه مدل معروف برای مسئله زمانبندی با محدودیت منابع را بررسی میکنیم.
2-5 مدل پریتسکر27
برای هر فعالیت دو زمان زودترین زمان پایان( EFT28 ) و دیرترین زمان پایان (29 LFT ) را میتوان در نظر گرفت که فعالیت در بازه بین این دو زمان، میتواند پایان یابد. در این مدل از متغیری بصورت صفر و یک برای تصمیمگیری استفاده میشود. Xi,t متغیر مورد نظر است که مشخص میکند، آیا فعالیت i در زمان t به اتمام میرسد یا نمیرسد. محاسبه EFT و LFT را از روشهای پیشرو و پسرو بدست میآید.
“X” _”i,t” ={█(1 if Activity i finish at time t@0 Othewiis )┤ (2-15)
زمان پایان فعالیت i از رابطه زیر بدست میآید.
∑_(t=EFTn+1)^(LFTn+1)▒〖t.”X” _”n+1,t” 〗 (2-16)
پریتسکر اولین مدل مسئله را با توجه به روابط بالا ارایهکرد[9].
■(min⁡∑_(t=EFTi)^LFTi▒〖t.”X” _(i,t) 〗 ) (2-17)
Subject to:
∑_(t=EFTi)^LFTi▒”X” _”i,t” =1 (2-18)
∑_(t=EFTi)^LFTi▒〖t.”X” _”i,t” ≤ 〗 ∑_(t=EFTi)^LFTi▒〖t.”X” _”j,t” -dj〗 for all (i,j) є A (2-19) ∑_”i=1″ ^”n” ▒〖∑_”q=max⁡{t,EFTi}” ^”min” ⁡{“t+di-1,LFTi” }▒〖” ” r_ik “.” “X” _”i,q” “≤ ” 〗 R_k 〗 k=1,2,…,m t=1,2,…,T (2-20) “X” _”i,t ” є { 0 , 1} i=1,2,…,n t=EFTi , …,LFTi (2-21)
تابع هدف حداقل کردن زمان پایان فعالیت نهایی است که در رابطه (2-17) آمدهاست. رابطه (2-18) مشخص میکند که هر فعالیت فقط یک زمان پایان دارد. رابطه (2-19) شرط پیشنیازی را بیان میدارد. رابطه (2-20) محدودیت منابع را در نظر میگیرد و رابطه (2-21) مشخص میکند که متغیر تصمیمگیری دودویی است.
2-6 مدل کلین30
در این مدل برای هر فعالیت دو زمان، زودترین زمان شروع ( EST31 ) و دیرترین زمان شروع (32LST) و زودترین زمان پایان ( EFT ) و دیرترین زمان پایان (LFT )در نظر گرفته میشود. در این مدل نیز از متغیری بصورت صفر و یک برای تصمیمگیری استفاده میشود. Xi,t متغیر مورد نظر است که مشخص میکند، آیا فعالیت i در زمان t یا قبل از آن به اتمام میرسد یا نمیرسد. برای اینکه محدودیت منابع بصورت صحیح بیان گردد، لازم است که بعضی از متغییرهای تصمیمگیری در خارج از بازه بین زودترین زمان شروع و دیرترین زمان پایان فعالیت مورد نظر تعریف شوند. همچنین بردار متغیرهاي تصمیمگیری براي یک فعالیت معین ابتدا شامل یک سري صفر و در ادامه شامل یک سري یک میشود. اگر فعالیت مورد نظر در یک دوره شروع شود، در آن دوره صفر به یک تبدیل میشود. رابطه (2-22) زمان شروع فعالیت i را نشان میدهد.
■(〖LFTi- 〗⁡∑_(t=ESTi+1 )^LFTi▒”X” _(i,t) ) (2-22)
کلین دومین مدل مسئله را بصورت زیر ارایه کرد[10].
■(〖min T- 〗⁡∑_(t=ESTn+1 )^LFTn▒”X” _(n,t) ) (2-23)
این رابطه تابع هدف که به حداقل رساندن زمان شروع فعالیت مجازی پایانی است را بیان میکند.
Subject to:
“X” _”i,t ” =0 i=1,2,…,n t= ESTi +1 -di , …, ESTi (2-24) “X” _”i,t ” ≤〖” X” 〗_”i,t+1 ” i=1,2,…,n t= ESTi +1 , …, LSTi – 1 (2-25) “X” _”i,t ” =1 i=1,2,…,n t= LSTi +1 – di , …, LFTi (2-26)
سه رابطه (2-10) و (2-11) و (2-12) مشخص میکنند که بردار متغییرهاي تصمیمگیری، براي یک فعالیت معین ابتدا شامل یک سري صفر و در ادامه شامل یک سري یک میشود.
“X” _j”,t ” ≤〖” X” 〗_”i,t ” -di for all (i ,j) є A t= ESTj +1 , …, LFTi – 1 (2-27)
∑_”i =1″ ^”n” ▒〖” ” r_ik “.” 〖”(X” 〗_(j, t ) “- ” “X” _”i,t ” “- di) ≤ ” 〗 R_k k =1,2,…,m t=1,2,…,T (2-28) “X” _”i,t ” є { 0 , 1} i=1,2,…,n t=ESTi +1 , …,LFTi (2-29)
رابطه (2-27) شرط پیشنیازی را مشخص میکند و رابطه (2-28) محدودیت منابع را ضمانت میکند. رابطه (2-29) مشخص میکند که متغیر تصمیمگیری دودویی است.
2-7 مدل آلوارز و تاماریت33
در این مدل براساس گرافی که فعالیتهای پروژه و روابط پیشنیازی را بیان میکند، گراف جدیدی بصورت G(N,A∩S) را تعریف میکند. مجموعه A شامل یالهای گراف فعالیتهاست که روابط پیشنیازی را مشخص میکنند. مجموعه A’ مجموعه روابط فعالیتهایی است که رابطه پیشنیازی بین آنها نیست و بازتاب دهنده ناسازگاریهای منابع است. زیر مجموعههایی از H’ که محدودیت منابع را رعایت میکنند با IS مشخص میکنیم. مجموعه Sزیر مجموعهای از IS است که طولانیترین مسیر در گراف G(N,A∩S) را به حداقل میرساند. بعبارت دیگر S مجموعه ای مینیمال است بطوریکه اگر یک فعالیت را جابجا میکنیم هنوز زیر مجموعه IS باقی بماند. انجام فعالیتها بصورت موازي، نیازمند به تعریف دستکم یک رابطه پیشنیازي بین زوج (i , j) میباشد، در نتیجه فعالیت i باید قبل از فعالیت j تمام شود. متغیر تصمیمگیری براساس پیشنیازی تعریف میشود و اگر فعالیت i پیشنیاز فعالیت j باشد، یک میشود و در غیر این صورت صفر میگردد. پایان فعالیت i نیز با متغیر fi مشخص نشان داده میشود.
سومین مدل بصورت زیر بیان میگردد[11].
Min fn (2-30)
این رابطه تابع هدف که به حداقل رساندن زمان پایان فعالیت پایانی است را بیان میکند.
Subject to:
“X” _”i,j ” =1; “X” _”j,i ” =0 for all (i,j) є A (2-31)
Xi,j + Xj,i ≤ 1 i, j = 1,2,…,n and i≠ j (2-32)
Xi,j + Xj,

دسته بندی : No category

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