مقاله مرور و طبقه بندی مدلهای زمانبندی پروﮊه با در نظر گرفتن محدودیت منابع

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

مرور و طبقه بندی مدلهای زمانبندی پروﮊه با در نظر گرفتن محدودیت منابع
چکیده :
زمانبندی پروﮊه با در نظر گرفتن محدودیت منابع یا RCPSP دارای ادبیاتی غنی است . این دسته مسائل در مهندسی صنایع به دو دلیل مورد توجه قرار گرفته اند : اول اینکه با توجه به شرایط متفاوت کاربردی و صنعتی از نظر تابع هدف , خصوصیات فعالیتها , منابع و نوع روابط پیش نیازی بسیار متنوعند و دوم اینکه با توجه به NP-hard بودنشان محققین همواره به دنبال ارائه راه حلهای کاراتری برای حل این دسته از مسائل بوده اند .
با توجه به گستردگی و تنوع این دسته مسائل دراین مقاله به دسته بندی مدلهای زمانبندی پروﮊه با در نظر گرفتن محدودیت منابع بر اساس نوع تابع هدف, خصوصیات فعالیتها , منابع , نوع روابط پیش نیازی و سایر پارامترهای مطرح شده در مقاله و راه حلهای ارائه شده برای آنها پرداخته شده است . در این تحقیق علاوه بر مشخص شدن ویژگیهای مدلهای توسعه یافته و نقاطی که در آن خلا تحقیقاتی وجود دارد , دست اندرکاران اجرای پروﮊه ها در سازمانهای مختلف می توانند با توجه به شرایط سازمانی , نوع منابع و خصوصیات تکنولوﮊیک فعالیتهای سازمانشان اقدام به انتخاب مدل مناسب برای پروﮊه هایشان کنند.
کلمات کلیدی
زمانبندی پروﮊه , محدودیت منابع , فعالیتهای تک وضعیتی , فعالیتهای چند وضعیتی , منابع تجدیدپذیر , منابع غیر تجدیدپذیر

مقدمه
زمانبندی پروﮊه با در نظر گرفتن محدودیت منابع ( RCPSP ) عبارت است از زمانبندی فعالیتهای پروﮊه با توجه به روابط پیش نیازی و محدودیت منابع. از آنجا که در CPM/PERT منابع در زمانبندی دخیل نیستند برای زمانبندی پروﮊه ها به طورکلی به دو صورت عمل می شود .
در روش اول ابتدا برنامه زمانبندی فقط با در نظر گرفتن روابط پیش نیازی تعیین شده ( با روش . (CPM/PERT سپس با وارد کردن منابع , میزان مصرف منابع در دوره های زمانی و نحوه توزیع آتها درطول برنامه بدست می آید با توجه به این اطلاعات اقدام به تامین منابع یا برون سپاری کارها با هدف تحقق برنامه صورت می گیرد .در صورت وجود محدودیت در سطوح منابع اقدام به تسطیح منابع می گردد. تسطیح منابع ممکن است منجر به طولانی تر شدن زمان پروﮊه گردد.
در روش دوم زمانبندی , در واقع تعیین برنامه با توجه همزمان به پیش نیازی ها و سطح منابع صورت می گیرد . در واقع محاسبات شبکه بر ارضاﺀ محدودیتها ی منابع اولویت ندارد بلکه به صورت همزمان در نظر گرفته می شوند . در این روش هدف در اغلب اوقات حداقل کردن makespan است.
این هدف با استفاده از الگوریتمهای بهینه پیگیری می شود. در روش اول زمانبندی بهینه نیست بلکه قابل قبول است ولی به علت سهولت محاسباتی این روش بیشتر مورد استفاده قرار می گیرد و نرم افزارهای تجاری این روش را پوشش می دهند . مدلهایی که برای تهیه زمانبندی به روش دوم توسعه داده شده اند در ادبیات به RCPSP مشهور هستند .
در این مقاله به منظور آسان سازی تشخیص و تطبیق پروﮊه های صنعتی و سازمانی با مدلهای موجود به جمع آوری و دسته بندی این مدلها پرداخته و روشهای حل آنها مورد اشاره قرار گرفته است.
محدوده مدلهای مورد بررسی
هدف از زمانبندی و توالی عملیات , تخصیص بهینه منابع محدود در طول زمان می باشد. زمانبندی (scheduling) در واقع تعیین فعالیتهایی است که باید در یک زمان مشخص انجام شوند و توالی عملیات (sequencing) ترتیب انجام فعالیتهایی که باید اجرا شوند را مشخص می کند.
تخصیص منابع محدود در طول زمان موضوع تحقیقاتی بسیار گسترده ای از اوایل شروع تحقیق در عملیات در اواسط دهه پنجاه بـوده اسـت. تئـوری زمانبندی و توالی عملیات بیش از هر زمینه دیگری در تحقیق در عملیات و مدیریت عملیات دارای انواع مختلف مسائل می باشد.

بیشتر مدلهای زمانبندی در صنایع تولیدی تعریف شده اند به همین دلیل به طور سنتی برروی زمانبندی کار روی ماشین آلات متمرکـز بـوده انـد و پارامترهای مساله قطعی بوده اند . دراین مسائل در اکثرقریب به اتقاق مواقع منبع ماشین بوده و طبیعتا در یک زمان مشخص قادر به انجـام یـک کـار بوده است.
در طول سالهای بعد بسیاری از فرضیات محدود کننده مربوط به زمانبندی ماشین آلات تولیدی آزاد شدند. استفاده فعالیت از چند منبع در زمان واحد به جای استفاده فعالیت از یک منبع در زمان واحد امکان پذیر می باشد . هر منبع می تواند در زمان واحد به چند فعالیت سرویس دهد به جای اینکه منبع در زمان واحد به یک فعالیت سرویس دهد. روابط FS.SS.SF.FF با lag های غیر صفر حداقلی و حداکثری قابل تعریفند و مسائل محدود به روابط از نوع FS و با lag صفرنیست. هر منبع ظرفیت مشخصی دارد و هر فعالیت در حین اجرا به میزان مشخصی از چندین منبع نیازمند است .
منابع دارای ظرفیت محدود در هر پریود زمانی و یا در کل افق زمانبندی می باشند .
با توجه به مطالب گفته شده مساله زمانبندی پروﮊه ها در حالت محدودیت منابع مطرح می شود که عبارت است از زمانبندی فعالیتهای پروﮊه با توجه به محدودیتهای پیش نیازی و محدودیت منابع . این زمینه زمانبندی نیز دارای مسائل و مدلهای متنوعی است.[9]
زمانبندی و توالی عملیات به معنی مصطلح خود در ادبیات تحت عنوان کلی machine scheduling یادشده است و زیرمجموعه ای از مسائل RCPSP تلقی شده است.[9]

معیارهای دسته بندی مدلها
١- ماهیت فعالیت ها
یک دسته بندی کارا برای سهولت در مرور مدلهای متنوع در این زمینه توجه به ماهیت فعالیتهای فرض شده برای این مدلهاست . این دسته بندی شامل موارد زیر است :

تک وضعیت / چند وضعیت بودن فعالیت (Single-mode/multi-mode)
اگر یک فعالیت یک وضعیتی باشد به این معنی است که آن فعالیت را فقط می توان به یک صورت با یک سناریو (از نظر مدت زمان انجام , میزان مصرف منابع و هزینه) انجام داد.در حالت چند وضعیتی می توان فعالیت را با ترکیبهای مختلفی از زمان , هزینه و منبع به انجام رساند . بنابراین در این حالت موازنه trade off ممکن می باشد. باید به این نکته توجه کرد که در این جا یک فعالیت خود می تواند یک پروﮊه باشد.

قابلیت انقطاع فعالیت (preemptive/non preemptive)
اگر بتوان یک فعالیت را در حین انجام متوقف و در آینده ادامه داد به آن قابل انقطاع گویند. ودر غیر این صورت ای فعالیت غیر قابل انقطاع می باشد.
احتمالی /قطعی (stochastic/deterministic)
درصورت احتمالی بودن زمان انجام فعالیت ها مدل احتمالی خواهد بود.
٢- نوع منبع

دسته بندی کارای دیگری که برای تشخیص نوع مدل مورد نیاز از اهمیت برخوردار است , دسته بندی نوع منابع مورد نیاز برا اجرای فعالیتهاست. .
در این دسته بندی منابع به دو دسته تجدید پذیرrenewable یا غیر تجدید پذیر nonrenewable تقسیم می شوند .
منابع تجدید پذیر به این صورت تعریف می شوند : اگر میزان مشخصی از منبع به طور مداوم در طول افق برنامه ریزی موجود باشد ماننـد ماشـین آلات و نیروی انسانی. اما اگر میزان مشخصی از منبع برای کل افق برنامه ریزی در نظر گرفته شود و در اثر مصرف به پایان برسد مانند :بودجه , مواد به این منابع , منابع غیر تجدید پذیر گویند .
منابع شبه (غیر) تجدید پذیر : منابع غیر تجدید پذیری هستند که در بازه ای از افق برنا مه ریزی مقدار مشخص دارند اما در پایان بازه تجدید می شوند. ( به ندرت در ادبیات مورد استفاده قرار گرفته اند)
گاهی اوقات یک منبع دارای هر دونوع محدودیت فوق به صورت توام است .در این حالت هم حجم کل منبع در دسترس در افق برنامه ریزی محدود است و هم مصرف منبع در واحد زمان سقف معینی دارد این نوع منابع را دارای محدودیت توام (doubly-constrained) گویند.

٣- نوع روابط پیش نیازی
یکی از عوامل تعیین کننده در توسعه مدل های RCPSP توجه به نوع روابط پیش نیازی است .در نوع پیش نیازی که در ادبیات به CPM/PERT معروف است , روابط محدود به رابطه از نوع FS با lag زمانی صفر می باشد. در پیش نیازی مفروض در GPR انواع پیش نیازها به صورت FF, SF, SS, FS همراه با Lag زمانی موجود می باشد (در کتابهای کنترل پروﮊه به PN مشهور است ) . همچنین deadline و اولین زمان ممکن برای شروع کاردر صورت وجود در مدل وارد می شود. این نوع مسائل را GRCPSP می نامند . اگر علاوه بر lag حداقلی , lag حداکثری هم وجود داشته باشد مساله را RCPSP-GPR می نامند. تعریف lag حداکثری همزمان با ارائه مدل مربوطه مطرح می گردد.

٤- نوع تابع هدف
دسته بندی مسائل براین اساس با توجه به اهداف سازمان مجری پروﮊه و اولویتهای آن حائز اهمیت است معمولاﹶ هدف اکثر مسائل زمانبندی پروﮊه حداقل کردن طول زمان پروﮊه Makespan می باشد. حداقل کردن طول زمان پروﮊه نوعی تابع هدف معمولی regular می باشد.
یک تابع هدف معمولی (regular) یک تابع غیر نزولی از زمان اتمام فعالیتهاست . به این معنی که هنگامی که زمان اتمام فعالیتها افزایش می یابد مقدار تابع هدف افزایش می یابد یا ثابت می ماند.

دیگر توابع هدف معمولی عبارتند از حداقل کردن کل هزینه های پروﮊه شامل جریمه های دیر کرد با توجه به زمان های تحویل فعالیت ها یا پروﮊه . این تابع هدف معمولاﹶ برای مدل کردن مساله زمان بندی پروﮊه های چند گانه به کار می رود که در آن چندین پروﮊه باید به صورت همزمان زمانبندی شوند.

یک تابع هدف غیر معمول (non-regular) تابعی است که در آن به تاخیر افتادن فعالیتها ممکن است به بهبود تابع هدف بیانجامد .حتی اگر این تاخیر در اثر محدودیتهای پیش نیازی یا منابع نباشد. توابع هدف غیر معمول عبارتند از حداقل کردن وزنی زودکرد- دیرکرد فعالیتها (پروﮊه) نسبت به موعدهای تحویل و حداکثر کردن ارزش خالص فعلی . (NPV) همچنین در بخشی از ادبیات تسطیح منبع (resource leveling) هم به عنوان یک تابع هدف غیر معمول ذکر شده است.

٥- تعداد تابع هدف
گاهی مدل دارای بیش از یک تابع هدف است . در موارد اندکی محققان برای حل RCPSP با بیش از یک تابع هدف کار کرده اند. که تحت عناوین دو هدفه (bi-objective) و چند هدفه (multi-objective) از آن یاد شده است.

٦- تعداد پروﮊه ها
در سازمانها ممکن است برای زمانبندی پروﮊه ها به صورت یکپارچه بخواهیم از مدلهای RCPSP استفاده کنیم که برای زمانبندی در حالت چند پروﮊه ای (multi-project) توسعه داده شده اند.

روشها و رویکردهای حل
۱)روشهای حل بهینه
مسائل RCPSP به عنوان حالت کلی مسائل توالی عملیات از نوع مسائل NP-hard می باشند. روشهای حل بهینه ای که درادبیات مورد استفاده قرار گرفته اند [9] عبارتند از برنامه ریزی ریاضی(صفرویک ) و روشهای شمارش ضمنی یعنی برنامه ریزی پویا و شاخه و کران .در دهه اخیر پیشرفت زیادی در حل این مسائل با استفاده از روشهای بهینه صورت گرفته است که بر روی دو مجموعه مساله تست شده اند. این دو مجموعه عبارتند از:
مجموعه ۰۱۱ مسئله طراحی شده توسط ”پترسون“ و مجموعه ۰۸۴ مساله توسط ”کلیش ” .الگوریتمها بر اساس اینکه چند مساله را در چه مدت زمانی حل می کنند ارزیابی می شوند. . [9] مجموعه مسائل پترسون شامل ۰۱۱ مساله نمونه است که توسط پترسون طراحی شده است که مسائل مجموعه بین ۷ تا ۰۵ فعالیت و ۱ تا ۳ منبع تجدید پذیر دارند در طول دهه های گذسته این مجموعه معیاری برای سنجش اعتبار و توانایی رویه های بهینه و نزدیک به بهینه بوده است. در سال ۵۹ کلیش اعتبار مجموعه پترسون را مورد سوال قرار داد که منجر به توسعه ProGen گردید. یک نرم افزار تولید کننده شبکه که قادر به تولید نمونه مسائل RCPSP با پارامترهای از پیش تعیین شده است .(با ۰۳ نوع فعالیت و ۴ نوع منبع تجدید پذیر

۲) روشهای حل ابتکاری و فوق ابتکاری
از آنجا که مسائل RCPSP دستهای از مسائل مشکل را در حوزه پزوهش عملیاتی شامل میشود اخیرا بستر مناسبی برای پیاده سازی آخرین تکنیکهای بهینه سازی گردیده است. در[1-3] به معرفی , دسته بندی و مقایسه روشهای ابتکاری و فوق ابتکاری برای حل این گونه مسائل پرداخته شده است . به طور کلی می توان روشهای فوق را به صورت شکل ۲ دسته بندی کرد.

مدل پایه RCPSP
فرض می کنیم که یک پروﮊه با یک شبکه AON (فعالیت بر روی گره ها) تعریف شود بـه صـورت G(V,E) کـه در آن V مجموعـه گـره هـا کـه نماینده فعالیتها می باشد و E مجموعه کمانها که روابط پیش نیازی را به صورت FS با Lag به میزان ۰ مشخص می کنند می باشد. فعالیتها از ۱ تـا n شماره گذاری شده اند. فعالیتهای فرضی ۱ و n فعالیتهای شروع و پایان پروﮊه با مدت زمان صفر هستند. فعالیتهـا بایـد بـدون انقطـاع انجـام شـوند .
میزان طول فعالیت با و زمان شروع آن با Si و زمان پایان آن با fi مشخص می شود. به تعداد K نوع منبع تجدیـد پـذیر مفـروض
است به طوری که میزان ثابت نیازمندی فعالیت i از منبع k می باشد و ak میزان ثابت در دسـترس از منبـع نـوع k می باشد.
مساله RCPSP به صورت زیر مدل می شود : [46 [

H مجموعه از جفت فعالیتهایی است که دارای روابط پیش نیازی هستند و St مجموعه ای از فعالیتها است که در بازه زمانی قـرار دارند به طوری که

مدل RCPSP با قابلیت انقطاع
در RCPSP پایه فرض بر این است که فعالیتی که آغاز می شود باید بدون قطع شدن تا پایان ادامه یابد. در عمل ممکـن اسـت بتـوان فعـالیتی را قطع و پس از مدتی ادامه داد. همچنین این کار ممکن است در حالت محدود یت منابع به زودتر خاتمه یافتن کل پروﮊه بیانجامد. این فـرض پیچیـدگی مساله را افزایش می دهد.
با این فرض فعالیتها می توانند در مقـاطع صـحیح از زمـان قطـع شـوند در ایـن صـورت طـول فعالیـت di را مـی تـوان بـه قـسمت هـای صـحیح j  1,2,...,di افراز کرد. به این صورت به هر طول زمانی j از فعالیت i یک عدد صحیح که مبـین زمـان پایـان آن بخـش اسـت بـه صـورت fij

اختصاص می دهیم.
متغیر fio زودترین زمانی را نشان می دهد که فعالیت i می تواند شروع شود از آنجا که فقط رابطه FS با lag زمانی صفر مجاز هستند fio برابـر دیرترین زمان پایان همه پیش نیازهای فعالیت i هستند. یک فعالیت به مجموعه St از فعالیتهای در حـال انجـام در بـازه ]t − 1,t] تعلـق دارد اگـر یکی از واحدهای زمان اش j  1,2....,di در زمان t تمام شود . fij  t این مساله به صورت زیر مدل می گردد : [46 ]

این مساله در [17] توسط رویه شاخه و کران حل شده است.
مدل RCPSP تحت روابط پیش نیازی عمومی (GRCPSP)
تحقیقات زیادی برای زمانبندی در حالت روابط کلی پیش نیازی GPR انجام شده است. مدل موجـود در ادبیـات بـه صـورت زیـر توسـعه داده شـده است : [46 ]