زمان‏بندی پروژه با داده‌های فازی با استفاده از الگوریتم شبیه‌سازی تبرید

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 و Z_Best بهترین جواب شناخته شده ‏است. در ادامه، استخوان‏بندی الگوریتم SA، شامل نحوه نمایش جواب، تولید جواب اولیه، نحوه تولید جواب همسایه به طور مختصر شرح داده می‏شوند.

4-1- نحوه نمایش جواب

در تمام الگوریتم‏های فراابتکاری، به دلیل نیاز به حل شدنی در شروع کار، لازم است حل شدنی بر طبق ساختار مشخصی ذخیره گردد که به این ساختار، نحوه نمایش جواب می‏گویند. یک حل شدنی برای مسأله مورد نظر، در شکل (2) نشان داده شده است. این شکل یک ماتریس یک بعدی با ابعاد 1×n  است و این سطر ترتیب فعالیت‏ها را بگونه‌ای نشان نشان می‏دهد که از چپ به راست،  فعالیت‏ها به ترتیب در اولویت اجرا هستند.

4-2- تولید جواب اولیه

در مساله زمان­بندی پروژه، برای تولید جواب اولیه از روشی استفاده می­شود که آن ­را روش تولید زمان­بندی می­نامند. این روش نقش بسیار مهمی در اکثر روش­های ابتکاری و فراابتکاری و حل این مساله ایفا می­کند. این روش یک فهرست نمایش  مانند لیست فعالیت، کلید تصادفی یا نمایش قانون اولویت[20] را گرفته و آن­ را به یک برنامه زمان­بندی تبدیل می­کند. دو نوع مختلف از این روش وجود دارد؛ برنامه تولید زمان­بندی سری[21] و برنامه تولید زمان­بندی موازی[22]. در این تحقیق، با توجه به مطالعات انجام شده توسط مسیج وهمکاران (2002)، از روش زمان­بندی موازی که کارایی بهتری دارد، استفاده می­گردد. همچنین براساس تحقیق کولیش (1996)، برای تبدیل یک شکل نمایش جواب به یک زمان­بندی شدنی، در اینجا از یک روش زمان­بندی موازی فازی استفاده شده است که روش زمان­بندی موازی آن از مرجع (کولیش و همکاران، 1996) گرفته شده و فازی شده است.

 شکل (1): فلوچارت SA پیشنهادی

شکل (2): نحوه نمایش جواب

شبه کد برنامه تولید زمان‏بندی موازی (PSS) در شکل (3) آمده است:

شکل(3) شبه کد برنامه تولید زمان‏بندی موازی

     برخی پارامترهای مورد استفاده در این شبه­کد، به شرح زیر می‏باشند:

A_n:مجموعه  فعالیت‏های که تا زمان زمان‏بندی شده‏اند ولی هنوز تکمیل نشده‏اند و به مجموعه فعال معروف می‏باشند.

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) اطلاعات پروژه شامل پیشنیازهای فعالیت‏ها به همراه میزان استفاده هر فعالیت از دو منبع درنظر گرفته شده است. مدل ریاضی ارائه شده در این مقاله، با استفاده از الگوریتم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 در ابعاد کوچک

شکل (6): زمان حل مسائل نمونه در الگوریتم پیشنهادی و نرم‏افزار GAMS