چکیده:
مسئله زمانبندی پروژه با منابع محدود و چندمهارته یکی از مسائل کاربردی تحقیق در عملیات است. در این نوع مسئله، کارکنان چندمهارته در طول انجام فعالیتهای پروژه موردنیاز هستند. میزان دسترسی به کارکنان در طول افق برنامهریزی پروژه، به دلایل وجود تعطیلات رسمی، تعطیلات آخر هفته، بیماری یا مرگ ثابت نیست. بنابراین در این مقاله، یک مدل ریاضی برای مسئله زمانبندی پروژه چندمهارته پیشنهاد میشود که در آن میزان دسترسی به منابع، متغیر و وابسته به زمان است. ارتباط بین فعالیتها در مدل پیشنهادی از نوع تعمیمیافته در نظر گرفتهشده است. هدف مدل پیشنهادی، کمینهسازی زمان تکمیل پروژه است. بهمنظور حل مدل پیشنهادی که ازجمله مسائل NP-Hard است، یک الگوریتم فراابتکاری مبتنی بر روش جستجوی هارمونی (HS) توسعه داده شده است. در جهت افزایش تنوع جوابها و کاهش احتمال گرفتارشدن الگوریتم پیشنهادی در بهینه محلی، دو عملگر تقاطع و جهش جدید برای این الگوریتم طراحی شده است. کارایی الگوریتم پیشنهادی در حل چند مسئله نمونه، نسبت به دو الگوریتم بهینهسازی ازدحام ذرات (PSO) و ژنتیک (GA) موردمقایسه قرار گرفته است. نتایج، نشان از برتری الگوریتم پیشنهادی ازنظر شاخصهای کیفیت جواب و زمان حل مسئله دارد.
In this paper, we address the multi-skilled RCPSP with time-dependent resource capacities and generalized precedence relations between activities. In this problem, a set of multi-skilled workforces are required to execute project activities. Each worker is able to perform several skills. The availability of workforces is time-dependent due to holidays, weekends, sicknesses, etc. Therefore, in this study, a mathematical formulation is proposed for the multi-skilled RCPSP with time-dependent resource availabilities. The objective function of the model is minimization of project completion time. The proposed model in this study is an NP-Hard problem in the strong sense. Hence, we develop a new meta-heuristic algorithm based on harmony search algorithm to solve the proposed model. New crossover and mutation operators have been designed for the proposed method to produce diverse solutions and to prevent the proposed algorithm from converging to a local optima. Hence, the proposed method not only uses the common procedure in harmony search algorithm, but also it employs the proposed crossover and mutation operators to explore solution space more accurately. The generated solutions are all combined and the harmony memory is updated. The effectiveness of this method has been compared to particle swarm optimization (PSO) and genetic algorithm (GA) in solving 30 test problems. The results show that the proposed method has been superior in terms of multiple performance measures.
خلاصه ماشینی:
مسئله RCPSP، يک مسئله بهينه سـازي ترکيبي است که هدف آن زمان بندي مجموعه اي از فعاليت هاي مرتبط به هم ، با توجه بـه محدوديت دسترسي به منابع و روابط پيش نيازي است ؛ به طوريکه زمان تکميل پـروژه ٢ کمينه گردد [١].
به عنوان نمونه ، در مسـئله RCPSP کلاسـيک ، فـرض بـر ايـن است که ميزان دسترسي به منابع در هر دوره زماني ثابت است [٤]؛ اين در حالي اسـت که در دنياي واقعـي، ظرفيـت منـابع در طـول زمـان بـه دليـل وجـود تعطـيلات رسـمي، تعطيلات آخر هفته ، خرابي ماشين آلات و تجهيزات ، بيماري کارکنان ، عمليات نگهـداري و تعميرات ، متغير است [٥].
Multi-skilled resource-constrained project scheduling problem (MSRCPSP) فعاليت ها و يافتن بهترين ترکيب نيروي کـار چندمهارتـه بـراي انجـام فعاليـت هـا اسـت .
در ايـن مقالـه ، يـک مـدل رياضي براي RCPSP چندمهارته ارائه خواهد شد که در آن سـطح دسترسـي بـه منـابع متغير و وابسته به زمان بوده و روابط پيش نيازي تعميم يافته بين فعاليت ها وجـود دارد.
Multi-mode RCPSP (MRCPSP) (به تصویر صفحه مراجعه شود) ٣- مدل رياضي MSRCPSPTRC-GPR ١-٣- مفروضات مدل براي نمايش ساختار پروژه از شبکه هاي گرهـي١ (AON) شـامل يـک شـبکه جهـت دار (G)V, A استفاده شده که V (مجموعه گره ها) نشان دهنده فعاليت هاي پروژه است و A نشانگر مجموعه اي از کمـان هـا اسـت .
(به تصویر صفحه مراجعه شود) شکل ٦ اثر مولفه هاي مدل بر زمان تکميل پروژه ٦- نتيجه گيري و پيشنهادها در اين مقاله ، يک مدل رياضي براي مسئله زمان بنـدي پـروژه چندمهارتـه بـا ظرفيـت متغير از منابع محدود و روابط پيش نيازي تعميم يافته بين فعاليت ها (-MSRCPSPTRC GPR) ارائه شد.