نشریه تخصصی مهندسی صنایع، دوره 48، سال 1393، ویژه نامه دهمین کنفرانس بین المللی مهندسی صنایع، از صفحه 45 تا 54
یک مدل ریاضی براي حل همزمان مسئله زمانبندي پروژه و تخصیص نیروي انسانی
عرفان مهمانچی*1و شهرام شادرخ2
کارشناسی ارشد مهندسی صنایع- دانشگاه صنعتی شریف
دانشیار دانشکده مهندسی صنایع- دانشگاه صنعتی شریف

چکیده
تخصیص نیروي انسانی به فعالیت هاي پروژه براي زمانبندي آن ها، یکی از نزدیک ترین حالات به شرایط واقعی مسائل زمانبندي است، اما با توجه به تازگی و تعلق این مسئله به دسته مسائل غیر چندجمله اي سخت، تا کنون روش هاي دقیق فقط قادر به حل مسائل با اندازه کوچک بوده اند. در این مسئله، منابع تجدیدپذیر از نوع ستادي بوده، به طوري که هر فرد با مهارت هاي چندگانه فقط قادر است، یکی از مهارت هاي مورد نیاز فعالیت ها را در زمان مشخص برآورده کند. در این مقاله، با تعریف مفهوم کارآیی براي اعضاي پروژه، یک مدل برنامه ریزي ریاضی براي حل همزمان دو مسئله بالا ارائه می شود. از آنجا که این مسئله جزو مسائل غیر چند جمله اي سخت طبقه بندي می شود، براي حل آن یک الگوریتم فراابتکاري تکامل دیفرانسیلی توسعه داده شده است. نتایج حاصل بیانگر کارآیی این الگوریتم فراابتکاري در حل همزمان دو مسئله زمانبندي پروژه و تخصیص نیروي انسانی است.

واژه هاي کلیدي: زمانبندي پروژه، تخصیص نیروي انسانی، کارآیی، الگوریتم فراابتکاري

مقدمه
Email: [email protected] 09122144450 :نویسنده مسئول: تلفن *

یکی از مهم ترین شاخه هاي حوزه دانشی زمانبندي پروژه ،مسئله زمانبندي با منابع محدود است که با نام RCPSP1 نیز شناخته می شود. این مسئله با توجه با ماهیت غیر چندجمله اي سختی2 که دارد، یکی از دشوارترین و پیچیده ترین مسائل تحقیق در عملیات به شمار می رود. با گسترش RCPSP یک فعالیت میتواند از چندین راه یا حالت انجام پذیرد که هر یک از این حالات، منعکس کننده ترکیبی از زمان لازم و منابع مورد نیاز براي انجام فعالیت مورد نظر هستند [1]. این مفهوم جدید سبب توسعه یکی از عمومی ترین حالت هاي مسائل زمان بندي با عنوان زمانبندي پروژه با منابع محدود چند حالته یا MRCPSP3 شده است که بسیاري از مسائل واقعی را با استفاده از آن میتوان مدل سازي کرد. با این حال MRCPSP به عنوان مسئله اي مهم و سخت شناخته شده است، زیرا بلازویک و همکاران [2] اثبات کرده اند که RCPSP یک مسئله NP-hard است و در نتیجه حالت عمومی تر آن یعنی MRCPSP نیز یک مسئله NP-hard خواهد بود. جامع ترین مطالعه و دسته بندي در زمینه مسئله زمانبندي پروژه با منابع محدود و زیرشاخه هاي گسترش یافته آن را می توان در [1،3] جستجو کرد. در طی سال هاي اخیر، نسخه جدیدي از مسئله MRCPSP در ادبیات مطرح شده است که شامل حل همزمان دو مسئله زمانبندي پروژه و تخصیص نیروي انسانی است که گاهی با نام مسئله زمانبندي پروژه چندمهارته یا MSPSP4 نیز شناخته می شود. این مسئله در حالت استاندارد عبارت است از تعیین یک زمانبندي شدنی براي فعالیت ها با توجه به روابط پیش نیازي و محدودیت منابع که فقط از نوع نیروي انسانی با مهارت هاي چندگانه در نظر گرفته می شوند. در این مسئله هر فعالیت به تعدادي نیروي انسانی براي انجام هر یک از مهارت هاي خود نیاز دارد که باید توسط زیرمجموعه اي از اعضاي پروژه که از تخصص لازم براي انجام مهارت برخوردارند، برآورده شود. علاوه بر این، افراد نمی توانند در زمان واحد روي دو فعالیت یا حتی دو مهارت اشتغال داشته باشند و در صورت اختصاص به یک مهارت تا اتمام کامل فعالیت در اختیار آن خواهند بود. نتایج گذشته حاکی از آن است که چند مهارته بودن باعث افزایش بهره وري، کیفیت و پیوستگی کار میشود و به مدیران انعطافپذیري بیشتري در تخصیص کارها می بخشد.
در این مسئله، با توجه به نیاز فعالیت ها به مهارت هاي مختلف و همچنین تخصص اعضاي پروژه در مهارت هاي گوناگون، بدیهی به نظر می رسد که می توان هر فعالیت را با تعداد حالات متنوعی از نظر تخصیص نیروي انسانی انجام داد که امکان دارد تعداد آن ها فقط براي یک فعالیت به بیش از چند 10 حالت برسد. در نتیجه در مقایسه با MRCPSP این مسئله پیچیدگی به مراتب بالاتري دارد.
با توجه به این موضوع، حل همزمان زمانبندي پروژه و تخصیص نیروي انسانی حتی در اندازههاي متوسط نیز توسط روش هاي ارایه شده براي RCPSP و MRCPSP که اکثراً بر اساس شمارش کامل هستند، قابل حل نیست
.[4،5]
MSPSP مسئله جدیدي در حوزه زمانبندي پروژه به شماره می رود، به طوري که حتی در جامع ترین هندبوك هاي زمانبندي پروژه مانند [3] نیز نامی از این مسئله برده نشده است. بلنگوئز در خلاصه رساله دکتراي خود، روش هاي حل MSPSP را در سه دسته کلی روش هاي حدود پایین، شاخه و کران و ابتکاري و فراابتکاري تقسیم بندي کرده است [5]. البته به این دسته بندي می توان روش برنامه ریزي آرمانی را نیز اضافه کرد [6،7]. از آنجا که استفاده از برنامه ریزي محدودیت ها و صفحات برش براي یافتن حدهاي مناسب براي مسئله MSPSP دشوار و زمان بر است، بلنگوئز و نرون [4] با چندسطحی در نظر گرفتن هر مهارت، روش حد پایینی را براي حل MSPSP ارائه دادند که می تواند به عنوان یک روش کارآ براي استفاده در هر گره روش شاخه و کران مورد استفاده قرار بگیرد. تحقیقات دیگري نیز بر همین مبنا و با استفاده از روش حد پایین انجام شده است که براي نمونه به کار نرون و همکاران [8] می توان اشاره کرد.
در مورد روش هاي شاخه و کران نیز می توان از کار بلنگوئز و نرون [9] در سال 2007 نام برد. کاظمی پور و همکاران [10] نیز یک مدل MINLP را براي حل مسئله MSPSP ارائه دادند، اما از آنجا که حل این مسئله در ابعاد واقعی، بسیار زمان بر بود، نویسندگان با ارائه یک الگوریتم شبیه سازي تبرید اقدام به حل مسئله کردند. در مورد سایر روش هاي فراابتکاري به کار رفته در حل MSPSP نیز می توان به روش جستجوي ممنوع اشاره کرد که همراه با یک جستجوي محلی قوي توسط کادرو و ناجید [11] در سال 2006 مورد استفاده قرار گرفت. آنها براي اثبات کارآیی الگوریتم خود، یک حد پایین براي مسئله نیزیافتند و به مقایسه الگوریتم خود با این حد یافت شدهپرداختند.
بسیاري از تحقیقات، اگر چه به حل همزمان دو مسئله زمانبندي پروژه و تخصیص نیروي انسانی پرداخته اند، اما با تکمهارته فرض کردن نیروي انسانی، حالت بسیار ساده اي از زمانبندي پروژه چندمهارته را بررسی کردهاند. به عنوان نمونه آلفارز و بیلی [12] با هدف زمانبندي پروژه و حداقل کردن هزینه آن، مسئله تخصیص نیروي انسانی تک مهارته را در مطالعات خود گنجانده اند و براي آن یک مدل ریاضی به همراه حل فراابتکاري با استفاده از برنامه ریزي پویا ارائه کرده اند. تحقیق وو و سان [13] نیز مثال دیگري از نوع تک مهارته به شمار می رود.
در تحقیق پیش رو، در ابتدا با در نظر گرفتن محدودیت هاي کاربردي به دنبال تعریف گسترشی از مسئله MSPSP هستیم تا بدین ترتیب آن را هر چه بیشتر به شرایط دنیاي واقعی نزدیک کنیم. بدین منظور بر خلاف آنچه که اغلب در ادبیات مسئله مطرح شده است، فرض می شود مهارت افراد فقط به دو سطح تخصص و تخصصنداشتن براي انجام مهارت خلاصه نمی شود و با در نظر گرفتن توانایی افراد در مهارت هاي مختلف، کارآیی آن ها را در هر مهارت به صورت عددي حقیقی در بازه [1،0] تعریف میشود. با بهره بردن از این ویژگی و از آنجا که منابع مورد استفاده در مسئله MSPSP از نوع نیروي انسانی هستند و یادگیري و فراموشی جزو جدایی ناپذیري از مهارت هاي انسانی است، عامل منحنی یادگیري و فراموشی نیز به شرایط مسئله اضافه می شود. در این حالت به ازاي هر واحد زمانی اشتغال افراد در مهارتی (یادگیري) کارآ یی آن ها در آن مهارت به صورت نمایی افزایش یافته و در صورت اشتغال نیافتن در آن، کارآیی آنها با ضریب کمتري نسبت با حالت یادگیري کاهش می یابد. با توجه به این فرض، بیشینه کردن کارآیی افراد در پایان پروژه، علاوه بر در نظر گرفتن تابع هدف متداول یعنی کمینه سازي زمان اجراي پروژه به عنوان هدف ثانویه به مسئله افزوده می شود.
از تحقیقاتی که به تأثیر »یادگیري« و »یادگیري و فراموشی« در حل همزمان مسائل زمانبندي پروژه و تخصیص نیروي انسانی پرداخته اند، می توان به مطالعات وو و سان [13] و همچنین گاتجاهار و همکاران [14] اشاره کرد. اگر چه تحقیق وو و سان جزو مسائل تک مهارته طبق بندي می شود، اما آن ها اولین کسانی بودند که در سال 2006 بحث تأثیر یادگیري (بدون در نظر گرفتن فراموشی) را وارد ادبیات موضوع مسئله زمانبندي و تخصیص افراد کردند. اما گاتجاهار و همکاران در سال 2008 این بار مسئله اي را در نظر گرفتند که تأثیر یادگیري و فراموشی را همزمان روي مهارت افراد در مسئله MSPSP بررسی می کرد، ولی آن ها نیز مانند وو و سان، با در نظر گرفتن بازه زمانی براي انجام فعالیت ها به ساده سازي مسئله پرداختند و علاوه بر آن، شرط پیوسته بودن فعالیت ها را نیز در مدل خود رعایت نکردند. به همین دلیل این دو مطالعه تفاوت هاي اصلی با مسئله مورد نظر این تحقیق دارند.
حاصل مسئله مطرح شده در این مقاله، یک مدل برنامه ریزي عدد صحیح مختلط غیرخطی است که با توجه به NP-hard بودن مسئله MSPSP و امکان نداشتن حل دقیق آن در ابعاد واقعی و در مدت زمان قابل قبول، راهی جز استفاده از الگوریتم ها فراابتکاري براي این دسته از مثال ها امکان پذیر نیست. بنابراین با استفاده از مقادیر حل دقیق مسئله براي مثال هاي با ابعاد کوچک در [15،16]، الگوریتم فراابتکاري تکامل دیفرانسیلی (DE)5 را براي مسئله مطرح شده در این مقاله گسترش می دهیم.
از جدیدترین تحقیقاتی که از الگوریتم تکامل دیفرانسیلی براي حل دسته مسائل زمانبندي پروژه با منابع محدود استفاده کرده اند، می توان به تلاش هاي داماك و همکاران [17] در سال 2009 براي حل MRCPSP اشاره کرد. نتایج تحقیقات آن ها، نشان دهنده کارآیی DE براي حل مسئله استاندارد MRCPSP در مقایسه با نتایج ثبت شده در کتابخانه زمانبندي پروژه [18] است. کاظمی پور [6] نیز در رساله دکتراي خود نشان داده است که الگوریتم تکامل دیفرانسیلی در مقایسه با سه الگوریتم فرا ابتکاري جستجوي ممنوع، شبیه سازي تبرید و جستجوي پراکنده از کارآیی بیشتري در حل MSPSP و حالت سبد پروژه آن برخوردار است.

تعریف مسئله
از یک منظر، مسئله MSPSP را می توان ترکیبی از دو مسئله زمانبندي پروژه و تخصیص افراد در نظر گرفت که براي حل آن هر دو زیرمسئله را باید به طور همزمان در نظر داشت، زیرا حل جداگانه هر یک لزوماً به حل بهینهMSPSP منجر نخواهد شد. از منظري دیگر هر مسئلهMSPSP را می توان متشکل از سه مجموعه فعالیت ها ،افراد و مهارت ها دانست که در آن هر فعالیت براي اجرایی شدن به یک یا چند مهارت نیاز دارد که توسط نیروي انسانی در اختیار پروژه باید برآورده شوند. علاوه بر موارد اشاره شده، در این مقاله با استفاده از مفهوم یادگیري و فراموشی شرایطی را در نظر می گیریم که با انجام هر مهارت، کارآیی فرد در آن مهارت به ازاي هر واحد زمانی افزایش و در صورت اشتغال نداشتن در آن به هر دلیلی مانند مرخصی، تخصیص نیافتن و یا اشتغال در مهارت دیگر، کارآیی وي کاهش خواهد یافت.
براي شرح مدل ریاضی، پروژه اي را در نظر بگیرید که از مجموعه اي از فعالیت ها { .…,1} ∈ j تشکیل شده است و هر فعالیت به یک یا چند مهارت { ,…,1} ∈ نیاز دارد. تعداد کارمند مورد نیاز براي انجام هر یک از مهارت هاي فعالیت با yjk نمایش داده می شود که بسته به حداقل کارآیی مورد نیاز فعالیت در مهارت مربوطه ،zjk، توسط زیرمجموعه اي از کارمندان { .… ,1} ∈ برآورده می شود. در این مدل، متغیر تصمیم xijkt برابر یک خواهد بود، اگر فرد i روي مهارت k فعالیت j در دوره زمانی t کار کند و در غیر این صورت برابر صفر خواهد بود. مقدار یک را خواهد گرفت، اگر فعالیت j در زمان t و یا قبل از آن شروع شده باشد و در غیر این صورت صفر خواهد بود.
همچنین برابر یک خواهد بود، اگر این فعالیت در زمان t هنوز تمام نشده باشد. متغیر باینري نیز بیانگر تخصیص فرد i به مهارت k فعالیت j است. همچنین Sikt مقدار کارآیی فرد i در مهارت k در زمان t پروژه را نشان می دهد که بسته به تعداد دفعات انجام مهارت توسط فرد و با توجه به ضرایب یادگیري و فراموشی تعیین شده براي مهارت مقدار آن در بازه [1،0] تغییر پیدا می کند. نیز میزان کارآیی فرد در مهارت مربوطه درست در زمان پایان پروژه است که مقدار آن از Sikt به دست می آید. مدل ریاضی مسئله گسترش یافته MSPSP را به صورت روابط (1) الی (17) می توان بیان کرد:
. −
s.t.
≤ ∀ , ∀
(3)
≥ ∀ , ∀
(4)
≤ ∀ , ∀
(5)
≥ ∀ , ∀
≤ 1 − , ∀ ,: ≤, ( ,) ∈ (6)
(7)
≥− 1 −
−1 − ∀ , ∀ ,∀
(8)
≤+ 1 −
+1 − ∀ , ∀ ,∀
(9)
≥−1 − ∀ ,∀ , ∀
(10)
≤+1 − ∀ ,∀ , ∀
(11)
−≤ 0 ∀ ,∀ , ∀
(12)
= ∀ ,∀
(13)
≤ 1 ∀ , ∀

−) ∀
همچنین در این مدل، E مجموعه روابط پیش نیازي فعالیت ها ،dj مدت زمان فعالیت j و M یک عدد مثبت بزرگ است.
طبق تعریفی که از مسئله مورد بررسی شد، هدف، حداقل کردن زمان اتمام پروژه ضمن حداکثرکردن کارآیی افراد در مهارت هاي مختلف در پایان پروژه با توجه به درجه اهمیت مهارتها () است، زیرا براي بسیاري ازسازمان هاي پروژه محور، یکی از نکات پر اهمیت، افزایشتوانایی نیروي انسانی براي انجام پروژه هاي مشابه بعدي و همچنین بهبود کیفیت کار است. این دو هدف را در رابطه (1) و به صورت یک عبارت با اضافه کردن مجموع کارآیی افراد با ضریب منفی به رابطه حداقل کردن زمان محاسبه می شود. باید توجه داشت براي آنکه کل تابع هدف معنی دار باشد، مقدار باید طوري تعیین شود که متناسب با زمان باشد. براي تعیین زمان شروع هر فعالیت از روابط (2) و (3) و براي تعیین زمان پایان آن از (4) و (5) استفاده میشود. با دانستن زمان شروع و پایان فعالیت ها، می توان روابط پیش نیازي بین آنها را با استفاده از رابطه (6) لحاظ کرد [14]. همچنین براي آنکه با شروع یک فعالیت، همه مهارتهاي آن به طور همزمان آغاز شوند و فعالیت منقطع نباشد، از روابط (7) و (8) استفاده می شود. روابط (9) و (10) سبب می شوند تا اگر فرد i به فعالیت j اختصاص پیدا کرد، به طور دقیق برابر مدت زمان فعالیت (dj) مشغول انجام آن باشد و در این بازه زمانی به فعالیت دیگري تخصیص پیدا نکند. با استفاده از رابطه (11) اطمینان حاصل می شود که اگر فردي براي انجام هیچ یک از مهارت هاي مورد نیاز، فعالیتی اختصاص پیدا نکرد (0=Cijk) متغیر xijkt مربوط به آن نمیتواند در هیچ زمانی مقدار یک بگیرد. تساوي (12) سبب می شود تا به طور دقیق به تعداد مورد نیاز یک فعالیت در یک مهارت به آن نیروي انسانی تخصیص داده شود. با استفاده از (13) میتوان اطمینان حاصل کرد که هر فردي در هر زمانی حداکثر می تواند روي یک فعالیت و آن هم فقط روي یک مهارت کار کند. براي پیاده سازي تأثیر یادگیري و فراموشی بر کارآیی افراد با توسعه منحنی یادگیري نمایی که توسط مازور و هستیه [19] ارائه شد ه و گسترش آن با در نظر گرفتن تأثیر فراموشی، رابطه اي همانند (14) به دست می آید که در آن Sikt کارآیی مهارت k فرد i در زمان Sik0 ،t کارآیی اولیه فرد و و ضرایب یادگیري و فراموشی هستند.
از آنجا که یکی از اهداف، حداکثرکردن کارآیی در زمان پایان پروژه است و از سویی دیگر زمان دقیق پایان پروژه مشخص نیست، پس باید با اضافه کردن رابطه (15) شرایطی را فراهم کنیم تا بتوان کارآیی افراد را به طور دقیق در زمان پایان پروژه به دست آورد. همچنین براي آنکه افراد تخصیص یافته به مهارت یک فعالیت، حداقل کارآیی مورد نیاز آن فعالیت در زمان تخصیص را داشته باشند، از رابطه (16) استفاده می شود. در نهایت (17) نیز نوع متغیرها و مقادیر ممکن براي آن ها را نمایش می دهد.
مجموعه روابط (1) الی (17) یک مدل برنامه ریزي عدد صحیح غیر خطی را براي مسئله ایجاد می کنند.
حل مسئله
دانستن این موضوع که حل همزمان زمانبندي پروژه و تخصیص نیروي انسانی یک مسئله NP-hard است، باعث میشود تا جز مسائل با ابعاد کوچک از حل بهینه مثالهاي با ابعاد واقعی صرف نظر کنیم. از این رو، در این بخش ضمن توسعه الگوریتم فراابتکاري تکامل دیفرانسیلی براي حل مسئله MSPSP مورد بحث در این مقاله ،به بررسی کارآیی آن در مقایسه با نتایج حاصل از حل دقیق به دست آمده براي مثال هاي در ابعاد کوچک که آن ها را در [15،16] می توان جستجو کرد و همچنین مثال هاي تصادفی تولید شده در ابعاد بزرگ می پردازیم.
در MSPSP براي یافتن جواب بهینه باید دو مسئله زمانبندي و تخصیص افراد را به طور همزمان در نظر گرفت. بدین منظور در این تحقیق براي نمایش جواب در الگوریتم هاي فرا ابتکاري از دو ساختار استفاده می شود.
ساختار اول، مطابق جدول (1)، شامل یک بردار است که اندازه آن برابر تعداد فعالیت هاي پروژه و عناصر نظیر هر فعالیت بیانگر اولویت انجام آن ها در طرح زمانبندي سري رو به جلو هستند. مطابق جدول (2) ساختار دوم متشکل از یک ماتریس سه بعدي است که بعد اول آن مربوط به فعالیت هاي مسئله، بعد دوم برابر تعداد کارمندان و بعد سوم براي مهارت هاي مورد نیاز انجام فعالیت ها است.
عناصر این ماتریس نیز بیانگر اولویت فرد مربوطه براي انجام مهارت مورد نیاز فعالیت متناظر با آن عنصر است.
لازم به ذکر است که مقادیر عناصر این دو ساختار در DE به طور تصادفی تولید می شوند.

جدول 1: نحوه نمایش اولویت انجام فعالیت ها
فعالیت 1 2 3 4 5 6 7 8 9 10
اولویت 5 4 10 1 8 6 9 3 2 7

الگوریتم تکامل دیفرانسیلی توسعه یافته
الگوریتم تکامل دیفرانسیلی با کمک عملیاتی که توسط استورن و پرایس در سال 1997 [20 ] معرفی شد، به مرحله اجرا درآمد. براي توسعه الگوریتم تکامل دیفرانسیلی در حل مسئله MSPSP، این روش را مطابق با نظریه استورن و پرایس طبق مراحل زیر اجرا می کنیم تا در بخش نتایج محاسباتی به بررسی کارآیی آن بپردازیم.

ایجاد جمعیت اولیه6
در این تحقیق از طرح زمانبندي سري و لیست اولویت تصادفی مطابق ساختار اول و ماتریس تصادفی تخصیص افراد مطابق ساختار دوم براي ایجاد جواب هاي اولیه ،، استفاده می شود. اندیسهاي g و i به ترتیب، نسل و جمعیتی را که بردار به آنها تعلق دارد، نشان میدهند. به طوري که 1[-i∈[0,NP و در آن Np نشان دهنده اندازه جمعیت است. مراحل اصلی الگوریتم DE را در چهار فاز جهش، جابه جایی و انتخاب می توان به صورت زیر بیان کرد که باید براي هر عضو جمعیت و به تعداد از پیش تعیین شده اي براي کل جمعیت تکرار شوند.

جهش7
مشابه الگوریتم ژنتیک، الگوریتم تکامل دیفرانسیلی نیز از دو والد و − ( و دو جواب غیر همسان هستند که به طور تصادفی انتخاب شده اند) براي ایجاد فرزند استفاده میکند. بدین منظور از بردار , که درایههاي آن یک عدد تصادفی در بازه [1،0] هستند، استفاده میشود. j نیز اندیس هر یک از عناصر موجود در بردار جواب است. رابطه (18) نشان میدهد که چگونه سه جواب مختلف با یکدیگر ترکیب می شوند تا بردار جهش یافتهي ایجاد شود. در این رابطه عامل A یک عدد مثبت از قبل انتخابشده است که نرخ تکامل جمعیت را تحت کنترل دارد:
, =,i +×,,1 −,2 (18)

جدول 2: نحوه نمایش اولویت تخصیص نیروي انسانی براي انجام مهارت هاي مورد نیاز هر فعالیت
فعالیت مهارت اول مهارت دوم کارمند 1 کارمند 2 کارمند 3 کارمند 4 کارمند 1 کارمند 2 کارمند 3 کارمند 4
1 2 4 1 3 1 4 3 2
2 4 2 1 3 2 1 3 4
3 4 3 1 2 1 4 2 3
4 1 2 3 4 4 1 2 3
5 1 2 4 3 2 3 1 4
6 1 4 2 3 1 2 3 4
7 1 3 2 4 4 2 3 1
8 2 3 4 1 3 4 2 1
9 4 3 2 1 3 1 4 2
2 4 3 1 4 2 3 1
10

جابه جایی8
-299718-154684

38374334246627

با ساخته شدن بردار جهش، آن را با جواب ترکیب کرده و سپس عملیات جابهجایی توسط روش تکامل دیفرانسیلی روي آن ها انجام میگیرد. در نتیجه آن بردار آزمایشی , با اعمال فرآیند رابطه (19) حاصل می شود:
, ( , ≤ =)
, =, ℎ (19)
براي تعیین عناصر موجود در ,، چنانچه عدد تصادفی , کوچک تر یا مساوي با مقدار عامل جابه جایی 1[,0]∈Cr باشد، مقدار عنصر متناظر از بردار جهشی به ارث برده میشود، در غیر این صورت عامل بالا از جواب فعلی ( ) کپی خواهد شد.
انتخاب
در گام انتخاب، مطابق رابطه (20) بردار آزمایشی بر مبناي مقدار تابع هدف با مقایسه میشود. هر یک از این دو جواب که برازندگی بهتري داشته باشد، به عنوان جواب جدید به جمعیت نسل بعد انتقال می یابد و دیگري حذف می شود [17]:

= (20)
براي استفاده از این الگوریتم توسعه یافته در حل مسئله MSPSP هر دو ساختار اولویت انجام فعالیت ها و ماتریس تخصیص اولویت افراد باید طی مراحل بالا و به
طور همزمان براي یافتن یک جواب شدنی جدید محاسبه
شوند. در شکل (1) مراحل الگوریتم فراابتکاري DE شکل 1: مراحل الگوریتم تکامل دیفرانسیلی نمایش داده شده است.
نتایج محاسباتی
پارامترهاي موجود در یک الگوریتم فراابتکاري بر عملکرد آن تأثیر مستقیم میگذارند. انتخاب مقادیر درست براي این پارامترها باعث گسترش جستجو و جلوگیري از همگرایی زودرس میشود. در این میان، هر یک از این پارامترها، مقادیر مختلفی میتوانند به خود بگیرند. سطوح ممکن براي مقادیر این پارامترها را گاهی می توان مطابق با استفاده از ادبیات موضوع و یا ویژگی هاي مسئله تعیین کرد. الگوریتم تکامل دیفرانسیلی مورد استفاده در این مقاله نیز داراي چهار پارامتر اندازه جمعیت NP، عامل مقیاس A، عامل جابهجایی براي بردار اولویت فعالیت ها Cra و عامل جابه جایی براي ماتریس اولویت تخصیص کارمندان Crs است. براي تعیین کارآیی الگوریتم تکامل دیفرانسیلی در حل مسئله MSPSP توصیف شده در این مقاله، ابتدا مقادیر این پارامترها با استفاده از روش تاگوچی (آرایه 25L) به صورت ,9.0=NP =100, A 2.0=Cra=0.3, Crs تعیین شد. سپس با به دست آوردن نتایج الگوریتم DE در حل هشت مثال در ابعاد کوچک که مقادیر حاصل از حل دقیق آن ها با استفاده از نرم افزار CPLEX در [15،16] موجود است، کارآیی آن ها مطابق جدول (3) مورد ارزیابی قرار گرفت. لازم به ذکر است که الگوریتم با استفاده از نرم افزار MATLAB(R2009a) در یک کامپیوتر شخصی با 4 گیگابایت رم و 13,2 گیگاهرتز سی پی یو کد شده است.
همان طور که در جدول (3) مشاهده می شود ،الگوریتم تکامل دیفرانسیلی، هم از نظر کیفیت جواب ها و هم از نظر زمان محاسباتی کارآیی مناسبی دارد. اما از آنجا که امکان حل دقیق این مسئله در ابعاد بزرگ وجود ندارد ،در نتیجه براي مقایسه و تعیین کارآیی الگوریتم بالا از 30 مثال که به طور تصادفی ایجاد شده اند، استفاده شد.
در تولید این مثال ها براي رعایت پیچیدگی ها و پوشش مطلوب فضاي مسئله و نبود تولید مثا ل هاي با ویژگی هاي یکسان، از نرم افزارProGen [18] براي تولید شبکه پروژه ها استفاده شده است.
همچنین در انتخاب بازه هر پارامتر از جنبه تعداد فعالیت ها، مهارت ها، کارکنان و… سعی شده است تا بر اساس ادبیات موضوع [4،6،13] حداکثر بازه ممکن در نظر گرفته شود. از هر دسته تعداد فعالیت 10,20,30,50,70 و 90 تایی پنچ مثال تولید و هر مثال براي سه مرتبه الگوریتم تکامل دیفرانسیلی اجرا شد (در مجموع 90 اجرا). مقدار تابع هدف یافت شده توسط الگوریتم به همراه میانگین زمان محاسباتی براي هر مثال در جدول (4) نمایش داده شده است.
جدول 3: بررسی کارآیی DE در مثال هاي کوچک
DE

CPLEX

)
مهارت
،
کارمند
،
فعالیت
(

مثال
انحراف

زمان

)
(
s

انحراف
زمان

)
h
(

DE

CPLEX

)

مهارت



قیمت: تومان


دیدگاهتان را بنویسید