بخشی از مقاله
چکیده
مسأله زمانبندی پروژه با منابع محدود و شناسایی حالت اجرا، شکل عمومیتری از مسألهی زمانبندی پروژه با منابع محدود و اجرای چند حالته است. این مسأله زمانی مطرح میشود که برخی از فعالیتهای پروژه دارای وابستگی هستند. در این مسأله تمامی فعالیتهای پروژه به چند زیرمجموعهی مستقل از هم تقسیمبندی میشوند که تمامی فعالیتهای هر زیرمجموعه باید در یک حالت یکسان اجرا شوند. این مقاله مسألهی زمانبندی پروژه با منابع محدود و شناسایی حالت اجرا را، با هدف کمینهسازی ارزش زمانی هزینهی اجرای فعالیتهای پروژه مورد بررسی قرار میدهد.
با توجه به ادبیات اندک در زمینهی مسألهی مورد بررسی، تا کنون مدلی برای لحاظ کردن ارزش زمانی پول در مسألهی زمانبندی با منابع محدود و شناسایی حالت اجرا مطرح نشده است و این موضوع تا کنون مورد بررسی قرار نگرفته است و از جمله نوآوری های مقاله به شمار میرود. در ادامه برای مدل پیشنهادی یک مثال عددی ارائه شده است و با حل آن اثر در نظر گرفتن ارزش زمانی هزینههای اجرای فعالیتها نشان داده شده است. با توجه به NP-Hard بودن مسأله، برای حل آن، از یک الگوریتم فراابتکاری آشوبی استفاده شده است.
کلمات کلیدی:زمان بندی پروژه; محدودیت منابع; شناسایی حالت اجرا; ارزش زمانی پول; الگوریتم فراابتکاری.
مقدمه
مسأله شناسایی حالت اجرا در واقع نسخهی کلیتری از مسئله زمانبندی پروژه با منابع محدود و اجرای چند حالته میباشد. مسألهی استاندارد شامل انتخاب حالت اجرای یک فعالیت است، به گونه ای که محدودیت های روابط پیشنیازی و منابع رعایت شوند و زمان اجرای پروژه کمینه سازی شود. در مسئله ی چندحالته تمام حالات تخصیصیافته به گروهها مستقل از هم هستند. به گونهای که انتخاب یک حالت برای یکی از فعالیتهای پروژه، ضرورتی را برای انتخاب حالتی خاص برای فعالیتی دیگر ایجاد نمیکند.
در عمل ممکن است شرایطی رخ دهد که در آن حالت، اجرای برخی از فعالیتها با هم وابستگی داشته باشند، به طوریکه اجرای یک فعالیت در یک حالت، فعالیتی دیگر را ملزم به اجرا در حالتی خاص نماید. سالفسکی و همکاران مجموعه فعالیتهای پروژه را به زیرمجموعه هایی مستقل از هم تقسیم بندی کردند به طوریکه تمام فعالیت های تشکیل دهندهی یک زیر مجموعه باید در یک حالت خاص اجرا شوند و به این ترتیب مدل زمانبندی پروژه با منابع محدود و شناسایی حالت اجرا را معرفی کردند.
این مسأله تحت تاثیر شرایط دنیای واقعی برای مواقعی که چند فعالیت باید از یک طریق اجرا شوند، یعنی، با تخصیص منابع یکسان به آن ها، بوجود آمده است. ادبیات مرتبط با مسأله شناسایی حالت اجرا و روشهای حل آن اندک هستند. سال فسکی و همکاران یک روش نمونهبرداری تصادفی ارائه کردند که روشی دو مرحلهای است. در مرحلهی اول از مقادیر اولویت برای تخصیص حالات اجرایی به زیرمجموعه ها استفاده می شود و در مرحلهی دوم با استفاده از طرح زمانبندی موازی مبتنی بر اولویت، یک زمانبندی ایجاد میشود. افشار نجفی و همکاران یک روش شاخه و کران برای حل مسألهی زمانبندی پروژه با منابع محدود و با شناسایی حالت اجرا، پیشنهاد کردند.
افشار نجفی و همکاران یک الگوری تم ژنتیک برای این مسأله ارائه کردند. مانند بسیاری از روشهای فراابتکاری، فرآیند پردازش قبل از فرایند اصلی الگوریتم اجرا میشود. یک جواب توسط یک لیست فعالیت و یک لیست کاهشیافته ی تخصیص فعالیت - با اندازهای برابر با تعداد فعالیتها و تعداد زیرمجموعهها - تولید میشود. رحیمی و همکاران سه روش فراابتکاری برای مسأله ی مورد بررسی، پیشنهاد کردند: الگوریتم رقابت استعماری، شبیه سازی تبرید و تکامل تفاضلی. مفهوم ارزش زمانی پول به عنوان یکی از اصول مالی تلقی می گردد و دارای کارکردهایی در مدیریت مالی می باشد.
بنا به تعریف، ارزش زمانی پول عبارت است از این که یک واحد پول در امروز ارزش بیشتری از یک واحد پول در آینده دارد که در این تعریف پول به عنوان مقیاس اندازه گیری بکار گرفته شده است. مطالعات مختلفی در زمینه ی زمان بندی پروژه و ارزش زمانی پول صورت گرفته است. لیمان و ون هوک بر روی مسائل زمان بندی پروژه با منابع محدود تک حالته و چندحالته همراه با جریانهای نقدی تنزیلیافته کار کردند. آنها از یک تکنیک جدید برای زمان بندی پروژه استفاده کردند که فعالیت ها را به ترتیب بهبود ارزش زمانی پول زمانبندی میکند. سابل و همکاران زمان بندی پروژه را با مدت زمان اجرای تصادفی فعالیتها به منظور بیشینهسازی ارزش خالص فعلی پروژه مورد بررسی قرار دادند.
وایسمن و همکاران بر روی بیشینه سازی ارزش خالص فعلی در زمان بندی پروژه در شرایط عدم قطعیت مطالعه کردند. کریمرز و همکاران زمان بندی شبکه های مارکوفی پرت را به منظور بیشینه سازی ارزش خالص فعلی بررسی کردند. با توجه به ادبیات اندک در زمینه مسأله ی مورد بررسی، تا کنون مدلی برای لحاظ کردن ارزش زمانی پول در مسألهی زمانبندی با منابع محدود و شناسایی حالت اجرا مطرح نشده است که در این مقاله به معرفی این مدل خواهیم پرداخت.
در ادامه در بخش دوم، مدل پیشنهادی معرفی می شود. در بخش سوم، روش حل مدل با الگوریتم فراابتکاری آشوبی بهینه سازی ازدحام ذرات بیان میشود و در بخش چهارم، یک مثال عددی برای ارزیابی اثر در نظر گرفتن ارزش زمانی پول در مدل، ارائه خواهد شد. و در نهایت در بخش انتهایی نتایج حاصل از در نظر گرفتن ارزش زمانی پول ارائه خواهد شد.
مدل پیشنهادی
مسأله ی زمانبندی پروژه با منابع محدود و شناسایی حالت اجرا و با در نظر گرفتن ارزش زمانی پول - هزینهی اجرای فعالیتها - شامل زمان بندی فعالیت های پروژه به منظور کمینه سازی ارزش فعلی هزینه های اجرای فعالیتهای پروژه، است. در مسأله، مجموعهی فعالیتهای پروژه به تعداد U زیرمجموعه ی مستقل از هم تقسیم بندی میشود به طوری که تمام فعالیتهای تشکیلدهندهی یک زیر مجموعه باید در یک حالت اجرا شوند. هزینهی اجرای فعالیتها به صورت تصادفی تولید می شود و هزینهی اجرای هر فعالیت پس از تکمیل شدن آن پرداخت می شود.
لازم به ذکر است که هزینهی حالات اجرای مختلف یک فعالیت بر اساس مدت زمان اجرای آن، مرتب میشود. به طوریکه حالتی که مدت زمان بیشتری برای اجرا نیاز دارد، دارای هزینه کمتر و حالتی که دارای کمترین زمان اجرا در بین حالات اجرای یک فعالیت است، دارای بیشترین هزینهی اجرا می باشد. پارامترها و محدودیتهای مدل در ادامه بیان میشوند.
روش حل
به علت کاربرد ساده و قابلیت بالای گریز از بهینهی محلی، آشوب یک تکنیک نوین بهینه سازی است و الگوریتمهای بهینه سازی مبتنی بر آشوب توجه زیادی را به خود جلب کرده است. آشوب یک رفتار قطعی شبه تصادفی کراندار است که تکرار در آن وجود ندارد و همگرا نیز نمیشود. سیستمهای سادهای وجود دارند که قابلیت ایجاد رفتارهای آشوبی دارند از جملهی آنها میتوان به نگاشت های آشوبی تک بعدی از جمله نگاشت لاجستیک، نگاشت تنت، نگاشت سینوسی، نگاشت گوسی و... اشاره کرد.در این مقاله از الگوریتم بهینه سازی ازدحام ذرات آشوبی و با استفاده از نگاشت لاجستیک به منظور حل مثال عددی استفاده شده است.
