نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 استادیار، دانشکده مهندسی صنایع، دانشگاه جامع امام حسین (ع)
2 کارشناس ارشد، دانشکده مهندسی صنایع، دانشگاه جامع امام حسین (ع)
3 دانشجوی دکتری، دانشکده مهندسی صنایع، دانشگاه آزاد اسلامی واحد تهران جنوب
چکیده
کلیدواژه‌ها
عنوان مقاله [English]
نویسندگان [English]
This research studies resource constrained project scheduling problem in a part of a refinery construction project in real world. In real world, most of the activities are new and we have problems such as activity duration uncertainty. This problem causes a change in a project makespan. The RCPSP is NP-hard. Hence, we proposed an optimization method based on simulated annealing to solve the RCPS Problem. In this paper, Fuzzy sets theory is used to represent this activity duration uncertainty. Used schedule generation scheme, in the proposed simulated annealing algorithm, is a fuzzy parallel scheduling generation method. Proposed algorithm generates the minimum project makespan while considers renewable resource-constrained and activity precedence and also has ability to perform with fuzzy numbers for presenting project details such as start and final time of activities and project whole time with fuzzy numbers. Finally, the results of the algorithm will be evaluated and it will be represented that the proposed algorithm is very efficient and can be used by managers and scheduling programmers in real projects.
کلیدواژه‌ها [English]
1- مقدمه
مساله زمانبندی پروژه عبارت از تعیین زمان انجام فعالیتهای یک پروژه، با توجه به محدودیتهای حاکم بر آن، برای رسیدن به یک هدف معین است. این هدف ممکن است جنبه مالی، زمانی و یا کیفی داشته باشد. در فعالیتهای واقعی، دو مقوله مهم وجود دارد: حداقل کردنزمان اتمام پروژه(با توجه به ضرورت نیاز به استفاده از محصول پروژه) و محدودیت منابع. بر همین اساس، موضوع زمان بندی پروژه و به تبع آن زمانبندی بهینه پروژه بدلیل صرفهجوی اقتصادی، استفاده بهینه از منابع و تکمیل پروژه در بهترین زمان ممکن (زمان بهینه) جهت ارائه خدمات حاصل از پروژه دارای اهمیت زیادی میباشد.
در جهان واقعی، به دلیل تغییرات محیط بیرونی (مانند: آب و هوا، کمبود فضا، حوادث طبیعی و غیر تکراری بودن یا عدم مواجهه مدیران پروژه با فعالیت مشابه در تجربیات قبلی) عدم قطعیت در تعیین مدت زمان فعالیتهای پروژه وجود دارد که این عدم قطعیت در فعالیتهای پروژه احداث پالایشگاه بسیار پررنگتر است. بنابراین این عدم قطعیت بایستی در مسائل زمانبندی پروژه در نظر گرفته شده و مدیریت شود. برای مواجهه با این عدم قطعیت، دو متدولوژی وجود دارد: رویکرد فازی و رویکرد احتمالی. رویکرد اول (تئوری فازی) برای نشان دادن عدم قطعیت در فعالیتهای دنیای واقعی، به دلایل زیر دارای کارایی بیشتری میباشد((فورتمپس[1]، 1996)،(پان[2] و همکاران، 2003)، (اشتهاردیان و همکاران، 1387)) : الف- نیاز کمتر رویکرد فازی به اطلاعات در مقایسه با رویکرد احتمالی. ب- عدم دسترسی و یا کمبود اطلاعات فعالیتهای گذشته و مشابه در برآوردها توسط افراد خبره. ج- سهولت حل روشهای فازی. د- حجم کمتر محاسبات نسبت به روشهای احتمالی. و عدم نیاز به مفروضاتی که در رویکرد احتمالی وجود دارد. بر همین اساس در این تحقیق، زمان انجام فعالیتها به صورت عدد فازی ذوزنقهای در نظر گرفته شده است که به وسیله مصاحبه با خبرگان درگیر در پروژه و بر اساس نظرات آنها برآورد میگردند.
برخی از محققان مطالعاتی روی مساله زمانبندی پروژه تحت محدودیت منابع و عدم قطعیت زمان فعالیتها داشتهاند که طی بررسیهای انجام شده در ادامه چند تحقیق مرتبط انجام شده آورده میشود.
ایشی و همکاران از روش زمان بندی پیشرو برای حل زمانبندی مساله استفاده کردند. آنها برای سادگی استفاده از اعداد فازی از روش α- برش فازی استفاده کرده و یک زمان تکمیل پروژه به صورت بازه بسته [a, b] ارائه کردند(ایشی و همکاران، 1998).
جویت وانگ یک مفهوم ریسک زمان بندی را پیشنهاد کردند و یک الگوریتم ژنتیک با استفاده از قانون اولویت برای حل مساله با هدف حداکثر کردن نیرومندی و استحکام زمانبندی ارائه دادند (وانگ و همکاران، 2002). باسکار و همکاران در مقاله ای یک روش ابتکاری برای حل مساله RSPS تحت زمان فازی فعالیتها ارائه کردند. آنها روش مبنی بر قانون اولویت را برای نمایش حل استفاده کردند و روش تولید زمان بندی موازی را برای حل مساله بکار بردند(باسکار و همکاران، 2011).
لیو[3] و وانگ[4] یک چهارچوب شامل الگوریتم ژنتیک ترکیب با تابو، برای حل مساله زمانبندی تحت محدودیت منابع و رویکرد فازی ارائه کردند که منجر به یک حل بهینه تقریبی میشد (لیو و وانگ، 1992). سلطانی وحاجی یک روش زمانبندی پروژه با استفاده از تئوری اعداد فازی ارائه کردند که در آن محدودیت منابع را در نظر نگرفتند (سلطانی و حاجی، 2007).
با توجه به اینکه مساله RCPSP، بعنوان یک مساله NP-hard شناخته شده است (بلاژوویچ، 1983). درنتیجه استفاده از روشهای دقیق و نرمافزارهای مدیریت پروژه برای حل این مساله در ابعاد بزرگ توجیهپذیر نبوده و بشدت کارایی خود را از دست میدهند. لذا برای حل این مسائل از روشهای ابتکاری و فراابتکاری کمک رفته میشود. که نمونههایی در بالا ذکر شد.
هدف این مقاله توسعه الگوریتم شبیه‌سازی تبرید ترکیب با تئوری مجموعههای فازی برای زمانبندی پروژه تحت محدودیت منابع و عدم قطعیت زمان فعالیتها میباشد که الگوریتمی کارا بوده و قابل استفاده توسط مدیران و برنامهریزان پروژه در فعالیتهای واقعی میباشد. در این الگوریتم، طول فعالیتها با استفاده از اعداد فازی ذوزنقهای نمایش داده شده است. الگوریتم پیشنهادی، حداقل زمان تکمیل پروژه را با در نظر گرفتن محدودیت منابع اقتصادی و نیروی انسانی تولید میکند و این قابلیت را دارد که با اعداد فازی اجرا شده و جزئیات پروژه شامل زمان شروع، زمان پایان فعالیتها و زمان تکمیل پروژه را بصورت اعداد فازی ارائه میکند.
در ادامه، ابتدا عدم قطعیت فازی، شرح مساله زمانبندی و الگوریتم پیشنهادی شبیه سازی تبرید تشریح می گردد و سپس، اطلاعات بخش نصب سازههای فلزی از پروژه احداث پالایشگاه آورده شده و با استفاده از الگوریتم پیشنهادی شبیه‌سازی تبرید ترکیبی با مجموعههای فازی حل میشود. در نهایت برای اعتبارسنجی الگوریتم پیشنهادی، چند مساله نمونه در ابعاد کوچک را با استفاده از الگوریتم پیشنهادی حل کرده و با حل توسط نرمافزار GAMS مورد مقایسه قرار خواهیم داد.
2- عدم قطعیت فازی
2-1- تئوری مجموعههای فازی
در ریاضیات کلاسیک مجموعه ها دارای مرزهای مشخص و روشن هستند. تعلق یک عضو به یک مجموعه بصورت صریح بوده و یک عضو می تواند به یک مجموعه تعلق داشته باشد و یا به آن تعلق نداشته باشد. در دنیای پیرامون ما برخی از مجموعهها نظیر مجموعه افراد قد بلند وجود دارند که دارای مرزهای مشخص نیستند. بنابراین تعریف چنین مجموعه هایی در ریاضیات کلاسیک امکان پذیر نیست. برای حل این مشکل مجموعه های فازی تعریف شده اند. در نظریه فازی یک مجموعه فازی صورت تعمیم یافته یک مجموعه کلاسیک است که اجازه می دهد هر عضو مجموعه، مقدار تعلقی را بین صفر و یک اختیار نماید. به عبارت دیگر، در یک مجموعه کلاسیک، هر عضو می تواند مقدار تعلقی برابر صفر یا یک داشته باشد. در حالی که در یک مجموعه فازی، تابع تعلق بصورت یک تابع پیوسته در محدوده صفر و یک می باشد. حداکثر مقدار تابع تعلق یک مجموعه فازی را ارتفاع آن مجموعه گویند. به یک مجموعه فازی که ارتفاع آن برابر یک میباشد مجموعه فازی طبیعی گفته می شود.
بنابراین مجموعه فازیA در فضای جهانی U را میتوان به صورت زوجهای مرتبی از X و مقدار تابع تعلق آن (x)µ مطابق رابطه (1) نمایش داد.
(1)
در این رابطه نشاندهنده تابع تعلق(عضویت) یا درجه عضویت مجموعه A میباشد. به طوریکه برد این تابع شامل اعداد حقیقی غیر منفی در فاصله بسته [0,1] می باشد. چنانچه مقدار تابع تعلق برای یک عضو مجموعه برابر صفر باشد، آن عضو مجموعه به صورت مطلق به آن مجموعه تعلق نداشته و اگر مقدار تابع تعلق برای یک عضو مجموعه برابر یک باشد، آن عضو به صورت مطلق به مجموعه تعلق دارد. این درجه عضویت اصل بنیادی مجموعههای فازی محسوب می گردد و هیچ روش قطعی برای تعیین تابع عضویت وجود ندارد و برای اعداد فازی شکل های مختلفی متصور است. لذا تعیین شکل و تابع عضویت بیش از همه یک مقوله حسی و تجربی میباشد که توسط فرد خبره تعیین میشود. انجام محاسبات با اعداد فازی به دلیل ساختار خاص آنها بسیار زمانبر و پیچیده میباشد برای تسهیل و کاربردی نمودن اعدا فازی، اعداد فازی خاصی معمولا به کار گرفته میشوند. این اعداد خاص معمولا به صورت اعداد زنگولهای[5]، مثلثی[6]، ذوزنقهای[7] هستند(غضنفری و همکاران، 2009). در این تحقیق، از اعداد فازی ذوزنقهای استفاده میگردد که در ادامه توضیح داده میشود.
2-2- حساب فازی
برای اعدا فازی نیز همانند اعداد حقیقی میتوان عملگرهای جمع، تفریق، ضرب، تقسیم، ماکسیمم، مینیمم، اشتراک و ... را تعریف نمود که در اینجا بر حسب کاربرد و نیاز فقط عملگرهای جمع، تفریق، ماکسیمم و مینیمم معرفی میگردد (غضنفری و رضایی، 1385).
الف- جمع اعداد فازی ذوزنقهای
از مجموع دو عدد فازی ذوزنقهای (a, b, c, d)= و (a', b', c', d') = عدد فازی جدید + = حاصل میشود که تابع عضویت آن به صورت زیر به دست میآید:
(2)
و مجموعه فازی به صورت زیر به دست میآید:
(3)
ب- تفریق دو عدد فازی
از تفریق دو عدد فازی ذوزنقهای (a, b, c, d)= و (a', b', c', d') = عدد فازی جدید - = به دست میآید که تابع عضویت آن به صورت زیر میباشد:
(4)
که مجموعه فازی بهصورت زیر تعریف می شود:
(5)
ج- ماکسیمم و مینیمم دو عدد فاز
ماکسیمم و مینیمم دو عدد فازی ذوزنقهای (a, b, c, d)= و (a', b', c', d') = بهصورت زیر معرفی میگردند:
(6)
2-3- مقایسه (رتبهبندی) اعداد فازی
با توجه به برسی ادبیات مرتبط، رتبه بندی نوع دوم (استفاده از روابط فازی) بر دو گونه است رتبهبندی ضعیف و رتبهبندی قوی اعدا فازی که در ادامه بهطور مختصر تشریح میگردند.
2-3-1- رتبهبندی قوی اعداد فازی[8] (SCR)
در حالت رتبهبندی قوی اعداد فازی، برای مقایسه دو عدد فازی و رابطه زیر را وجود دارد (لین و همکاران، 2007).
2-3-2- رتبهبندی ضعیف اعداد فازی[9] (WCR)
الف. رتبهبندی با استفاده از مقدار انتگرال
رویکرد مقدار انتگرال که توسط چن برای مقایسه دو عدد فازی توسعه داده شد، بهصورت زیر توصیف میشود (پان وهمکاران، 2004).
فرض کنید عدد فازی داده شده است. توابع و بترتیب توابع معکوس تابع چپ و راست عدد فازی فرض میشوند. مقدار انتگرال چپ و راست عدد فازی بهصورت زیر تعریف میشوند.
(7)
(8)
سپس مقدار انتگرال کل عدد فازی به صورت مجموع وزن داده شده از توابع و به صورت زیر تعریف میشود.
(9)
به طوریکه ، اندیس خوشبینی میباشد که توسط مدیران پروژه تعریف میشود. اگر باشد، فرمول(9) بهصورت زیر تعریف میشود.
(10)
جایکه ، و سطوح -برش از به صورت مجموعه زیر تعریف میشود.
(11)
و در نهایت برای دو عدد فازی و داریم:
(12)
ب. رتبهبندی اعداد فازی با استفاده از رویکرد فاصله‌ای
چنگ یک روش مبتنی بر فاصله را برای مقایسه دو عدد فازی مبنی بر فاصله بین مرکز مختصاد و مرکز جرم عدد فازی را توسعه داد(چنگ، 1998). فرض کنید که ᵋ عددی خیلی کوچک، تقریبا معادل با صفر باشد. برای محاسبه مرکز جرم عدد فاز به صورت زیر عمل میکنیم (پان وهمکاران، 2004).
(13)
(14)
که برای عدد فازی ذوزنقهای، فرمولهای فوق را به صورت ساده شده مطابق روابط زیر میتوان نوشت:
(15)
(16)
و با استفاده از معادلههای فوق، فاصله عدد فازی از مرکز مختصاد به صورت زیر محاسبه میشود
(17)
و در نهایت برای مقایسه دو عدد فازی و به روش فاصله‌ای خواهیم داشت:
3- تشریح مساله
مساله برنامهریزی (زمانبندی) پروژه با منابع محدود را با توجه به شرایط متفاوت، میتوان به صورتهای مختلفی مدلسازی کرد. شبکه‌های پروژه[10] که نشاندهنده پروژه خواهند بود، به دو شکل، فعالیت بر روی گره‌ها[11] (AOA) و فعالیتها بر روی کمان‌ها[12] (AON)، نشان داده میشوند. در این مقاله فرض میگردد که شبکه پروژه به صورت فعالیت بر روی گره (AON)، مانند گراف G(V, E) است که در آن V مجموعهی گره‌ها، و بیانگر فعالیتهای پروژه بوده و E مجموعه یالای[13]گراف و بیانگر رابطه منطقی پایان به شروع بدون تأخیر زمانی بین فعالیتها (روابط پیشنیازی بین فعالیتها) میباشد. روابط پیشنیازی از نوع پایان به شروع[14] در نظر گرفته شده است. محدودیت های روابط پیش نیازی بیان میکنند که هیچ فعالیتی را نمیتوان در زمانt زمانبندی کرد مگر آن که تا زمان t، تمام پیش نیازهای آن اتمام یافته باشند. فرض شده است که تمام فعالیتها در زمان صفر آماده هستند و نیز زمان آماده سازی برای فعالیتها متصور نیست و جزئی از زمان انجام فعالیت در نظر گرفته شده است. مابین فعالیتها اولویت وجود ندارد. به عبارت دیگر هیچ فعالیتی بر فعالیت دیگر ارجحیت ندارد. هر فعالیتی که آغاز میشود باید بدون وقفه تا انتها انجام شود و قطع فعالیتها جایز نیست. منابع به صورت تجدیدپذیر درنظر گرفته شدهاند. به این معنی که هر منبع در هر پریود زمانی دارای سقف استفاده مشخصی است و بیش از آن نمیتوان از آن منبع استفاده کرد و منابع در ابتدای هر پریود زمانی کاملا در دسترس هستند. با توجه به این مفروضات، مدل ریاضی مساله بهصورت زیر ارائه میشود.
پارامترهای مورد استفاده در مدل، بهصورت تعریف شدهاند.
V: مجموعه رأسهای گراف (گره‌ها)
J={0,1,…,n+1}: مجموعه فعالیتهای پروژه
: مدت زمان انجام فعالیت j که بهصورت عدد فازی ذوزنقهای میباشد.
: زودترین زمان شروع فعالیت j که به صورت عدد فازی ذوزنقهای میباشد.
: زودترین زمان پایان فعالیت j که بهصورت عدد فازی ذوزنقهای میباشد.
: مجموعه فعالیتهایی که در دوره t، در حال انجام هستند و از آنها به عنوان مجموعه فعالیتهای فعال[15] یاد میشود.
P(j) : مجموعه فعالیتهای پیشنیاز فعالیت j
Q(J): مجموعه کل فعالیتهای پسنیاز فعالیتj
: حداکثرمقدار موجود از منبع نوع K
: مقدار لازم از منبع نوع Kبرای انجام فعالیت i
T: حداکثر مدت زمان تکمیل پروژه
R : تعداد منابع تجدیدپذیر
در مدل برنامه ریزی بالا، رابطه (21) تابع هدف نشان دهنده کمینهسازی زمان اتمام فعالیت n+1 میباشد. در واقع، زمان اتمام این فعالیت برابر است با زمان اتمام همه فعالیتهای پروژه که برابر با زمان اتمام پروژه[16] خواهد بود. محدودیتهای مسئله عبارتند از: محدودیت (22) بیان کننده زمان شروع پروژه میباشد. محدودیت (23) مربوط به روابط تقدمی و تأخری (بدون تأخیر زمانی) بین فعالیتهای پروژه میباشد. بدین ترتیب که هیچ فعالیتی نمی تواند زودتر از اتمام تمامی فعالیتهای پیش نیازی خود شروع شود. محدودیت (24) مربوط به منابع در دسترس برای انجام فعالیت ها در بازههای زمانی افق برنامهریزی پروژه میباشد. محدودیت (25) و (26) بیان کننده این مفهوم هستند که فعالیتهای صفر و n+1، فعالیتهای مجازی پروژه (با زمان انجام صفر) هستند و محدودیت (27) و (28) بیان میکند که فعالیتهای پروژه بدون انقطاع میباشند. محدودیت (29) بیانگر این مطلب است که زمان شروع فعالیت فعالیت jام بزرگتر یا مساوی با بیشترین زمان اتمام فعالیتهای پیشنیازی خودش میباشد این یعنی اینکه فعالیت jام زمانی شروع میشود که تمام فعالیتهای پیشنیازیش تمام شده باشند.
4- الگوریتم شبیه‌سازی تبرید فازی پیشنهادی
استفاده از فرآیند سرمایش در مباحث بهینهسازی، اولین بار توسط کرک پاتریک[17] در سال ۱۹۸۰ تحت عنوان شبیه‌سازی تبرید[18] (SA) پیشنهاد شد (پاتریک، 1980). این روش با استفاده از قواعد علم فیزیک آماری به وجود آمده و به دنبال یافتن راهی برای استفاده از این قواعد در بستر بهینه سازی ترکیبی[19] میباشد. فرآیند این الگوریتم همانند شکلگیری کریستالهای فلز گداخته در حین خنک شدن است. شبیه‌سازی تبرید، الگوریتمی است که بوسیله حرکت تدریجی از یک جواب قابل قبول به جواب دیگر، به سمت بهینه کردن تابع هدف می رود. در شبیه‌سازی تبرید در هر تکرار، تفاوت بین مقدار تابع هدف به ازای جواب داوطلب و میزان تابع هدف به ازای جواب جاری محاسبه می شود ، اگر این تفاوت مطلوب بود، جواب داوطلب پذیرفته می شود و جایگشت دیگری انتخاب می شود. تا این قسمت از فرآیند، همانند الگوریتمهای بهبود دهنده محلی میباشد. ولی آنچه متفاوت است اینکه در الگوریتم شبیه سازی تبرید اگر δ مطلوب نبود، جواب داوطلب حتما رد نمیشود بلکه با احتمالی از پیش تعیین شده، ممکن است پذیرفته می شود. به این ترتیب، شبیه‌سازی تبرید، علاوه بر حرکت در یک سراشیبی، ممکن است در یک مسیر سربالایی هم حرکت کند و با این فرآیند الگوریتم شبیه سازی تبرید امکان فرار از دام بهینه های محلی را فراهم میآورد (کومار، 2008).
احتمال پذیرش «جواب غیر بهبود دهنده» به عواملی بستگی دارد که عبارت از موارد زیر است.
الف. درجه نزدیکی جواب داوطلب به جواب بهینه جاری.
ب. درجه حرارت مساله
توجه به این دو عامل، احتمال پذیرفتن جوابی که بهبود دهنده نیست) با افزایش فاصله از بهینه جاری) کاهش مییابد و هر چه درجه حرارت مساله پایینتر باشد، باید با احتمال کمتری جواب نامطلوب را بپذیریم تاهنگامی که به یک مرحله فریز شده برسیم جواب جدید را امتحان می کنیم. مشخصات یک مرحله فریز شده عبارتند از: تعداد جواب های امتحان شده در یک دما از حد مورد نظر گذشته باشد و یا اینکه تعداد از پیش تعیین شده ای از جوابها چک شوند بدون اینکه هیچ یک از آنها شرایط پذیرش را داشته باشند. پارامترهای کنترلی SA، شامل حداکثر تکرار جواب در هر درجه حرارت (معیار خروج از حلقه درونی)، حداکثر دفعات تغییر درجه حرارت (معیار خروج از حلقه بیرونی)، دمای اولیه، دمای نهایی و ضریب سردی است که بر اساس تحقیق دانشپایه (1390) به ترتیب برابر100، 100، 5، صفر و 95/0 انتخاب میشود.
در شکل (1) گامهای اساسی الگوریتم پیشنهادی آورده شده است پارامترهای به کار رفته در این فلوچارت، به صورت زیر تعریف میشود: T0 درجه حرارت اولیه، a ضریب سردی، K شمارنده تغییر درجه حرارت، Kn تعداد مجاز تغییر درجه حرارت (معیار خروج از حلقه بیرونی یا توقف الگوریتم)، L شمارنده تکرار همسایگی در هر درجه حرارت، Ln تعداد تکرار همسایگی در هر درجه حرارت (معیار خروج از حلقه درونی)، Z جواب شدنی، F(Z) مقدار تابع هدف به ازای جواب شدنی Z و ZBest بهترین جواب شناخته شده است. در ادامه، استخوانبندی الگوریتم SA، شامل نحوه نمایش جواب، تولید جواب اولیه، نحوه تولید جواب همسایه به طور مختصر شرح داده میشوند.
4-1- نحوه نمایش جواب
در تمام الگوریتمهای فراابتکاری، به دلیل نیاز به حل شدنی در شروع کار، لازم است حل شدنی بر طبق ساختار مشخصی ذخیره گردد که به این ساختار، نحوه نمایش جواب میگویند. یک حل شدنی برای مسأله مورد نظر، در شکل (2) نشان داده شده است. این شکل یک ماتریس یک بعدی با ابعاد 1×n است و این سطر ترتیب فعالیتها را بگونه‌ای نشان نشان میدهد که از چپ به راست، فعالیتها به ترتیب در اولویت اجرا هستند.
4-2- تولید جواب اولیه
در مساله زمانبندی پروژه، برای تولید جواب اولیه از روشی استفاده میشود که آن را روش تولید زمانبندی مینامند. این روش نقش بسیار مهمی در اکثر روشهای ابتکاری و فراابتکاری و حل این مساله ایفا میکند. این روش یک فهرست نمایش مانند لیست فعالیت، کلید تصادفی یا نمایش قانون اولویت[20] را گرفته و آن را به یک برنامه زمانبندی تبدیل میکند. دو نوع مختلف از این روش وجود دارد؛ برنامه تولید زمانبندی سری[21] و برنامه تولید زمانبندی موازی[22]. در این تحقیق، با توجه به مطالعات انجام شده توسط مسیج وهمکاران (2002)، از روش زمانبندی موازی که کارایی بهتری دارد، استفاده میگردد. همچنین براساس تحقیق کولیش (1996)، برای تبدیل یک شکل نمایش جواب به یک زمانبندی شدنی، در اینجا از یک روش زمانبندی موازی فازی استفاده شده است که روش زمانبندی موازی آن از مرجع (کولیش و همکاران، 1996) گرفته شده و فازی شده است.
شکل (1): فلوچارت SA پیشنهادی
شکل (2): نحوه نمایش جواب
شبه کد برنامه تولید زمانبندی موازی (PSS) در شکل (3) آمده است:
شکل(3) شبه کد برنامه تولید زمانبندی موازی
برخی پارامترهای مورد استفاده در این شبهکد، به شرح زیر میباشند:
An:مجموعه فعالیتهای که تا زمان زمانبندی شدهاند ولی هنوز تکمیل نشدهاند و به مجموعه فعال معروف میباشند.
Cn: مجموعه فعالیتهای که تا زمانبه اتمام رسیده‌اند.
Dn: مجموعه فعالیتهایی که پیش نیازهای آنها تا زمان به اتمام رسیده‌اند. یعنی پیش نیازهای آنها در مجموعه قرار دارند.
: قانون اولویت فعالیت ها را نمایش میدهد.
4-3- تولید جواب همسایه
در این بخش، تولید جواب همسایه از جواب جاری تشریح میگردد. برای تولید جواب همسایه) بعد از تولید جواب اولیه)، یک فعالیت به تصادف انتخاب می شود. زودترین زمان آغاز آن و همچنین دیرترین زمان اتمام آن با توجه به توالی فعالیتها در جواب جاری به دست می آید. سپس یکی از مکان‌های ممکنه (بعد از نزدیک‌ترین پیشنیاز و قبل از نزدیک‌ترین پسنیاز) زمانبندی میشود. برای توضیح بیشتر، فرض کنید که جواب اولیه‌ای توسط الگوریتم به صورت شکل (4) تولید شده است. کار 7 را در نظر بگیرید. تنها پیشنیاز این فعالیت، فعالیت 5 بوده است. پس کار 7 میتواند بلافاصله بعد از کار 5 آغاز شود. همانگونه که در شکل (4) نشان داده شده است فعالیت 7 به بعد از کار 5 انتقال داده شده است.
5- اجرای الگوریتم پیشنهادی
برای نشان دادن جواب ارائه شده توسط الگوریتم طراحی شده، بخش نصب سازههای فلزی شامل 35 فعالیت، یک پروژه احداث پالایشگاه در دنیای واقعی بهعنوان مساله نمونه این تحقیق انتخاب شد. دادههای مورد نیاز برای زمانبندی این بخش از پروژه، از خبرگان پروژه احصاء شد که این اطلاعات در جدول(1) به پیوست آورده شده است. فعالیتهای S و E فعالیتهای شروع و پایان پروژه میباشند که به صورت مجازی تعریف شدهاند.
شکل(4): روش تولید جواب همسایه
در این مساله، زمان فعالیتها بهصورت اعداد فازی ذوزنقهای در نظر گرفته شده که توسط افراد خبره برآورد شدهاند و به اینصورت تعریف شدهاند که به طور مثال، برای عدد فازی ذوزنقهای ، با احتمال زیاد زمان انجام فعالیت j در بازه [b, c] قرار دارد و در بهترین حالت زمان انجام این فعالیت برابر با a، و در بدترین حالت زمان انجام فعالیت برابر با d خواهد بود. منابع تجدیدپذیر برای این مساله به دو دسته نیروی انسانی و ماشینآلات تقسیم میشوند و مقدار موجود از این منابع به ترتیب 150 نفر و 100 دستگاه میباشد.
شکل(5): گراف روابط پیشنیازی مساله نمونه
. جدول (2): زمان نهایی شروع فعالیتها
|
فعالیت |
زمان شروع بهینه فعالیت |
فعالیت |
زمان شروع بهینه فعالیت |
|
1 |
(3 2 1 0) |
20 |
(728 704 673 649) |
|
2 |
(3 2 1 0) |
21 |
(745 720 687 661) |
|
3 |
(49 47 46 43) |
22 |
(763 737 700 673) |
|
4 |
(3 2 1 0) |
23 |
(680 659 630 609) |
|
5 |
(49 47 46 43) |
24 |
(694 672 646 627) |
|
6 |
(554 540 552 509) |
25 |
(728 704 674 653) |
|
7 |
(17 16 14 12) |
26 |
(755 750 717 693) |
|
8 |
(49 47 46 43) |
27 |
(1389 1349 1277 1236) |
|
9 |
(69 63 59 53) |
28 |
(811 748 744 716) |
|
10 |
(554 540 522 509) |
29 |
(811 748 744 716) |
|
11 |
(20 18 15 12) |
30 |
(859 829 787 756) |
|
12 |
(586 571ذ549 535) |
31 |
(1454 1412 1335 1293) |
|
13 |
(633 617 592 576) |
32 |
(1369 1349 1277 1236) |
|
14 |
(554 540 522 509) |
33 |
(1369 1349 1277 1236) |
|
15 |
(603 578 566 551) |
34 |
(729 706 673 640) |
|
16 |
(662 643 616 597) |
35 |
(680 659 630 609) |
|
17 |
(619 601 579 564) |
36 |
(1472 1329 1348 1305) |
|
18 |
(666 646 623 606) |
37 |
(1424 1379 1306 1263) |
|
19 |
(104 95 87 79) |
- |
|
در جدول (1) اطلاعات پروژه شامل پیشنیازهای فعالیتها به همراه میزان استفاده هر فعالیت از دو منبع درنظر گرفته شده است. مدل ریاضی ارائه شده در این مقاله، با استفاده از الگوریتمSA پیشنهادی، در محیط نرمافزار MATLAB نسخه 2009 کدنویسی شده است و در یک کامپیوتر پنتیوم 4 با 2.4 گیگا هرتز، اجرا شده است. جواب نهایی تولید شده توسط الگوریتم، در جدول (2) نشان داده شده است. در این جدول زمان آغاز فعالیتها به عنوان جواب نهایی تولید شده، ارائه شده است. همانطور که مشاهده میشود زمانهای شروع به صورت عدد فازی ذوزنقهای میباشند که از جمع زمانهای شروع با زمان انجام فعالیتها، زمان پایان هر فعالیت بهصورت عدد فازی ذوزنقهای به دست میآید.
با استفاده از نتایج به دست آمده برای فعالیت مجازی 37 در جدول (2) مشاهده میگردد که زمان تکمیل بهینه پروژه توسط الگوریتم برابر (1424 1379 1306 1263) است که برابر زمان شروع فعالیت 37ام بعلاوه زمان انجام این فعالیت میباشد که به صورت عدد فازی ذوزنقهای بیان شده است.
5-1- اعتبارسنجی الگوریتم پیشنهادی
به منظور اثبات کارایی الگوریتم پیشنهادی، نتایج حل این الگوریتم با نتایج حل بوسیله نرمافزار GAMS که یک نرمافزار بهینهسازی دقیق میباشد، مقایسه میشوند. البته پروژه مورد بررسی در این تحقیق، یک پروژه از مسائل دنیای واقعی میباشد که هماکنون در حال اجرا میباشد. پس از تکمیل پروژه، نتایج حاصله از اجرای پروژه میتواند با نتایج ارائه شده توسط الگوریتم پیشنهادی مقایسه گردد اما در تحقیق حاضر، برای اثبات کارایی الگوریتم پیشنهادی، چند مساله نمونه در ابعاد کوچک که شامل زیر مجموعههایی از مساله واقعی تحقیق میباشند را در نظر گرفته و با الگوریتم پیشنهادی و نرمافزار GAMS، حل نموده و نتایج مورد مقایسه و ارزیابی قرار خواهند گرفت. همان گونه که از جدول مشاهده میگردد نتایج بهدست آمده با استفاده از الگوریتم پیشنهادی بهصورت عدد فازی ذوزنقهای میباشند که برای ایجاد حالت مقایسه ایی نتایج، از روش رتبهبندی فاصله‌ای اعداد فازی، با استفاده روابط (15)، (16) و (17)، کمک گرفته شده است. در جدول (3) جزئیات حل مسائل نمونه در ابعاد کوچک بوسیله نرمافزار GAMS و الگوریتم پیشنهادی آورده شده است.
جدول (3): مقایسه نتایج الگوریتم SA پیشنهادی با نرمافزار GAMS در ابعاد کوچک
|
درصد انحراف |
GAMS |
SA |
روش حل شماره مساله |
|
|
21/1 |
85 |
9686/83 = (112 91 74 58) |
مقدار بهینه |
8=j |
|
|
782/17 |
870865/0 |
زمان اجرا (ثانیه) |
|
|
17/0 |
0/586 |
585 = (616 596 574 554) |
مقدار بهینه |
10=j |
|
|
624/212 |
5014/0 |
زمان اجرا (ثانیه) |
|
|
29/0 |
617 |
2107/615= (650 628 603 580) |
مقدار بهینه |
14=j |
|
|
697/473 |
580649/0 |
زمان اجرا (ثانیه) |
|
|
73/2 |
83 |
2705/85 = (120 91 73 55) |
مقدار بهینه |
16=j |
|
|
791/835 |
618776/0 |
زمان اجرا (ثانیه) |
|
|
786/3 |
649 |
214/645 |
مقدار بهینه |
j= 18 |
|
|
432/1432 |
037/1 |
زمان اجرا (ثانیه) |
|
|
637/1 |
میانگین انحراف |
|
||
شکل (6): زمان حل مسائل نمونه در الگوریتم پیشنهادی و نرمافزار GAMS
از نتایج به دست آمده در جدول (3) مشاهده میگردد که میانگین درصد اختلاف جواب الگوریتم پیشنهادی با الگوریتم دقیق، 63/1٪ میباشد. همچنین مطابق نتایج جدول (3) و شکل (6) زمان رسیدن به جواب در الگوریتم پیشنهادی تقریبأ ثابت بوده ولی در نرمافزار GAMS بهصورت تابع درجه دو افزایش مییابد و این نشان میدهد که الگوریتم پیشنهادی یک الگوریتم همگرا به جواب بهینه و کارا میباشد.
6- نتیجه گیری
در این مقاله، یک مدل فازی برای مساله زمانبندی پروژه تحت عدم قطعیت فعالیتها و محدودیت منابع ارائه گردید و چون مساله RSPS در گروه مسایل سخت دستهبندی میشود، استفاده از روشهای کلاسیک بهینه سازی جهت دستیابی به جوابهای بهینه سراسری یا موضعی، امری زمانبر بوده و از پیچیدگی زمان محاسباتی برخوردار میباشد. لذا جهت حل این مساله از الگوریتم فراابتکاری شبیه‌سازی تبرید ترکیبی با دادههای فازی کمک گرفته شد. هدف این الگوریتم، حداقل کردن زمان تکمیل پروژه است و این الگوریتم قادر است ضمن استفاده مستقیم از اعدا فازی، زمان شروع و زمان تکمیل پروژه را بهصورت عدد فازی ارائه کند. در این تحقیق، از نظریه مجموعه های فازی برای نمایش عدم قطعیت زمان فعالیتها استفاده شده است. در الگوریتم پیشنهادی برای تولید برنامه زمانبندی، از روش تولید زمانبندی موازی فازی استفاده شده است. برای مقایسه اعداد فازی مورد استفاده در الگوریتم پیشنهادی، از روش رتبهبندی فاصله‌ای استفاده شده است. یک مساله نمونه در دنیای واقعی با استفاده ازالگوریتم پیشنهادی زمانبندی شد. در نهایت برای سنجش کارایی الگوریتم پیشنهادی، نتایج حل 5 مساله نمونه در ابعاد کوچک را با نتایج حل نرمافزار بهینهسازی GAMS مقایسه کردیم و مشاهده نمودیم که الگوریتم پیشنهادی جوابهای با میانگین انحراف 63/1٪ از جوابهای دقیق تولید میکند و این در حالی است که زمان حل برای نرمافزار دقیق (با افزایش ابعاد مساله)، بهصورت نمایی افزایش مییابد درصورتی که زمان حل الگوریتم پیشنهادی به صورت تقریبا ثابت و کمتر از 2 ثانیه میباشد و این نشان میدهد که الگوریتم پیشنهادی همگرا بوده و قابلیت رسیدن به جواب بهینه را دارد. از آنجاکه الگوریتم پیشنهادی، قابلیت حل مسائل با داده های غیر قطعی را دارد و کارایی آن اثبات شد، الگوریتمی کابردی بوده و بهسادگی قابل استفاده برای مدیران پروژه در فعالیتهای جهان واقعی میباشد.
جدول (1): اطلاعات هر فعالیت شامل زمان انجام، منابع مورد نیاز و فعالیتهای پیشنیاز هر فعالیت
|
منابع مورد نیاز |
فعالیت پیشنیاز |
مدت فعالیت |
کد فعالیت |
نام فعالیت |
|
|
- |
- |
- |
(0 0 0 0) |
1 |
شروع |
|
23 |
20 |
1 |
(17 16 14 12) |
2 |
Arr.on SITE STEEL STRUCTURE CDU Unit 01 |
|
30 |
41 |
1 |
(49 46 43 41) |
3 |
ERECT.MED.-HEAVY STR-01-004 up to First Level |
|
23 |
27 |
2 |
(35 31 28 26) |
4 |
MEDIUM-HEAVY STR. STR-51-002 up to First Level |
|
29 |
33 |
2 |
(17 16 14 12) |
5 |
Arr.on SITE STEEL STRUCTURE CDU Unit 51 |
|
34 |
38 |
2 |
(65 62 58 55) |
6 |
ERECT.MED.-HEAVY STR-01-002 up to Intemed.Level |
|
22 |
32 |
2 |
(27 26 23 22) |
7 |
ERECT.MED.-HEAVY STR-01-005 up to Top |
|
15 |
23 |
2 |
(17 16 14 12) |
8 |
ERECT.MED.-HEAVY STR-01-006 up to TOP |
|
18 |
34 |
2 |
(35 31 28 26) |
9 |
ERECT.MED.-HEAVY STR-01-002 up to First Level |
|
19 |
36 |
2 |
(33 31 28 27) |
10 |
ERECT.MED.-HEAVY PR-01-003 to Closed Blowdown |
|
47 |
59 |
4 |
(65 62 58 55) |
11 |
MEDIUM-HEAVY STR-51-002 up to Intemediate Level |
|
38 |
44 |
4و5 |
(49 46 43 41) |
12 |
MEDIUM-HEAVY STR. STR-51-004 up to First Level |
|
18 |
39 |
5 و 12 |
(27 26 24 21) |
13 |
MEDIUM-HEAVY STR.STR-51-005 up to First Level |
|
26 |
37 |
5 |
(49 46 43 41) |
14 |
MEDIUM-HEAVY STR-51-003 up to Intemediate Level |
|
16 |
21 |
5 |
(17 16 14 12) |
15 |
MEDIUM-HEAVY STR. STR-51-006 up to TOP |
|
25 |
29 |
5 |
(17 16 14 12) |
16 |
Arr.on SITE STEEL STRUCTURE CDU Unit 71. |
|
40 |
39 |
6 |
(49 46 43 41) |
17 |
ERECT.MED.-HEAVY STR-01-003 up to Intemed.Level |
|
34 |
55 |
2 و 3 و 9 |
(27 26 24 21) |
18 |
ERECT.MED.-HEAVY STR-01-005 up to First Level |
|
78 |
97 |
2 و 7 و 8 |
(450 445 435 428) |
19 |
ERECT.MEDIUM-HEAVY STR. CDU Unit 01 |
|
14 |
34 |
13و 14و 15 |
(17 16 14 12) |
20 |
MEDIUM-HEAVY STR. STR-51-002 up to TOP
|
|
16 |
12 |
11و 20 |
(18 17 14 12) |
21 |
ERECT.MEDIUM-HEAVY STR. CDU Unit 51 |
|
45 |
23 |
20و 13 |
(49 47 43 42) |
22 |
MEDIUM-HEAVY STR. STR-51-004 up to Top |
|
21 |
19 |
16 |
(49 47 44 42) |
23 |
MEDIUM-HEAVY STR-71-003 up to Intemediate Level |
ادامه جدول (1)
|
منابع مورد نیاز |
فعالیتهای پیشنیاز |
مدت فعالیت |
کد فعالیت |
نام فعالیت |
|
|
23 |
34 |
16 |
(35 31 28 26) |
24 |
MEDIUM-HEAVY STR. STR-71-002 up to First Level |
|
13 |
23 |
16و 24 |
(49 47 43 40) |
25 |
MEDIUM-HEAVY STR. STR-71-004 up to First Level |
|
23 |
27 |
16و 25 |
(29 26 23 20) |
26 |
MEDIUM-HEAVY STR.STR-71-005 up to First Level |
|
34 |
43 |
25 |
(65 62 58 57) |
27 |
MEDIUM-HEAVY STR-71-002 up to Intemediate Level |
|
13 |
23 |
24 |
(49 47 43 40) |
28 |
MEDIUM-HEAVY STR. STR-71-004 up to Top |
|
12 |
18 |
20و 22 |
(29 26 23 20) |
29 |
MEDIUM-HEAVY STR. STR-51-005 up to Top |
|
79 |
120 |
23و24و25و26 |
(525 520 490 480) |
30 |
ERECT.MEDIUM-HEAVY STRUCT.ST.CDU Unit 71 |
|
12 |
23 |
27و 30 |
(18 17 14 12) |
31 |
MEDIUM-HEAVY STR.STR-71-002 up to TOP |
|
22 |
36 |
26و 28و 30 |
(28 26 24 22) |
32 |
MEDIUM-HEAVY STR. STR-71-005 up to Top |
|
21 |
19 |
23و 30 |
(32 30 29 27) |
33 |
MEDIUM-HEAVY STR. STR-71-003 up to Top |
|
28 |
21 |
17و 19 |
(32 30 29 27) |
34 |
ERECT.MED.-HEAVY STR-01-003 up to Top |
|
45 |
65 |
3و 19 |
(49 47 43 40) |
35 |
ERECT.MED.-HEAVY STR-01-004 up to Top |
|
76 |
95 |
30 |
(247 245 237 233) |
36 |
OTHER MEDIUM-HEAVY STR. U71 CDU-3 |
|
- |
- |
21و28و32و33و 34و35و26 |
(0 0 0 0 ) |
37 |
پایان |
[1] Fortemps
[2] Pan
[3] Liuo
[4] Wang
[5] bell
[6] Triangle
[7] Trapozedial
[8] Weak Comparison rule
[9] Strong Comparison rule
[10] Project networks
[11] Activity – on – node
[12] Activity – on – arc
[13] Arc
[14] Finish to Start
[15] Active set at time t
[16] makespan
[17] Kirkpatrick
[18] Simulated Annealing
[19] Combinatorial Optimization
[20] priority rule
[21] Serial Scheduling Generation Scheme
[22] Parallel Scheduling Generation Scheme
)