حل مسئلة زمان­بندي پروژه همراه با منابع محدود بوسيلة سيستم ايمني مصنوعي

چكيده

در اين گزارش ، مسئلة زمان­بندي پروژه همراه با منابع محدود با هدف کاهش مدت زمان کل پروژه مورد بحث قرار مي­گيرد. به خاطر عموميت اين مسئله، براي آن کاربردهاي متنوعي در توليد، برنامه­ريزي توليد، مديريت پروژه و ... متصور است. همچنين بحث در مورد يک مسئلة پيچيدة محاسبــاتي معروف است و بـکارگيري روش­هاي ابتکاري و يا ابزارهاي بهينه­سازي بر پاية هوش مصنوعي در مورد آن، اين امر را گواهي مي­دهد.

در اين گزارش رويکرد سيستم ايمني مصنوعي براي مسئلة مذکور مورد بررسي قرار مي­گيرد و در انتها عملکرد الگوريتم پيشنهادي با عملکرد ديگر رويکردهاي موجود نظير الگوريتم ژنتيک، الگوريتم ژنتيک فازي و ... بر روي مجموعه­اي از داده­هاي معروف مسئله مقايسه مي شود.

كلمات كليدي

زمان­بندي پروژه، محدوديت تقدمی، محدوديت منبع، سيستم ايمني مصنوعي، فراجهش

Solving resource constrained project scheduling problem by artificial immune system

Reisi Nafchi  M.

Abstract

In this paper, resource-constrained project scheduling problem is discussed with an objective of minimizing the makespan of a project. Due to its universality, it has a variety of applications as in manufacturing, production planning, project management and elsewhere. It is a well known computationally complex problem, thus warrants the application of heuristics techniques or AI based optimization tools to achieve optimal or near optimal solution in real time. In this research, the artificial immune system approach is proposed to solve the aforementioned problem. Finally, performance of proposed algorithm is compared to the other approaches like, genetic algorithm, fuzzy genetic algorithm,  base on well-known data set of problem.

Keywords

Project scheduling, Precedence constraint, Resource constraint, Artificial immune system,

Hypermutation

1- مقدمه

در عصر جديد هر بنگاه اقتصادي خواهان زمان­بندي کارايي براي فعاليت­هاي خود به­منظور افزايش سوددهي است. مسئلة زمان­بندي پروژه همراه با منابع محدود ([1]RCPSP) شامل تخصيص تعدادي فعاليت يا کار به منبع يا منابعي با ظرفيت محدود و يک سري محدوديت­هاي زماني براي دستيابي به اهدافي از پيش تعيين شده است. براي مسئله اهداف  گوناگوني متصور است و نوع هدف به آرمان­هاي تصميم­گيرنده بستگي دارد. اما رايج­ترينِ اين اهداف يافتن کمترين مدت زمان کل پروژه (makespan) است. [1]

محدوديت­هاي زماني معمولاً شامل محدوديت­هاي تقدمي هستند که بطور ضمني دربردارندة اين مفهوم­اند که کارهاي معيني بايد قبل از شروع کارهاي ديگري تکميل شوند. يک محدوديت منبع نيز، مشخص مي­کند که هر فعاليت براي اجرا نيازمند چه ميزان استفاده از منابع است.

RCPSP به عنوان يک مسئلة به شدت NP-hard شناخته مي­شود.[4] از اين رو، الگوريتم­هاي ابتکاري و فرا ابتکاري مختلفي براي حل آن پيشنهاد شده است. در اين گزارش که پيکرة اصلي آن بر اساس [2] است، يک الگوريتم ايمني شناختي (Immunological algorithm) بر اساس سيستم ايمني مصنوعي (AIS[2]) براي حل RCPSP بررسي مي­شود.

رويکرد AIS پيش از اين براي حـل مسائل مختـــلف زمان­بندي مانند Job-shop ، Flow-shop ، single machine tardiness  بکار رفته است. اما اين گزارش رابطة AIS را با RCPSP مورد بررسي قرار مي­دهد. اخيراً تعدادي محقق سعي در حل RCPSP داشته­اند که از آن جمله مي­توان به Boctor، Chang، Herroelen & Demeulemeester، Salewski & Drexel، Schrage و Sprecher اشاره کرد.

همان­طور که ذکر شد محققان زيادي سعي در ارائة يک برنامة زماني کارا و مؤثر براي فعاليت­ها داشته­اند و در اکثر اين موارد معيار makespan مورد توجه بوده است. اما با وجود اين، اغلب به شرايط و محيط واقعي در اين پؤوهش­ها توجه نشده است. هدف اين گزارش بررسي کارهاي انجام شده در زمينة حل RCPSP تک حالته با هدف  کاهش makespan بوسيلة AIS است.

در ادامة گزارش و در بخش 2، مسئلة RCPS[3] با مدل رياضي آن توصيف شده است و سپس در بخش 3، رويکرد AIS مورد بررســي قرار مي­گيرد. بخش 4 نيز به تفصيل جنبه­هاي اجراي الگوريتم پيشنهادي را شرح مي­دهد. در بخش 5 هم نتايج محاسبات بر روي مجموعه­اي از داده­هاي معروف در اين رابطه و مقايسة آنها با ديگر رويکردهاي حل مسئلة مذکور آورده شده است.

شکل 1: رابطة تقدمي بين فعاليت­هاي مختلف

2- شرح مسئله

در اين گزارش، هدف اصلي کمينه کردن کل مدت زمان پروژه با در نظر گرفتن محدوديت­هاي زماني و محدوديت­هاي منابع است. بمنظور ساده­سازي حل، اين مسئله بصورت يک مسئلة فروشندة دوره­گرد (TSP[4]) با محدوديت­هاي تقدمي مدل شده است. در اين مدل مسـافت طي شده بين دو گره -  که گره­ها نمايندة فعاليت­ها هستند -  برابر با زمان اجراي گره­ها فرض شده است و روابط تقدمي رابطة بين دو فعاليت را از نظر پيش­نيازي يا پس­نيازي نشان مي­دهد.

براي مدل کردن و حل مسئله فرض­هاي زير مدنظر قرار مي­گيرند:

1. زمان اجراي هر فعاليت بايد از قبل معين باشد.
2. هر فعاليت نمي­تواند بدون تکميل فعاليت­هاي پيش­نياز آن اجرا شود.
3. حداکثر تعداد منابع در دسترس بايد ار قبل تعريف شده باشد. با وجود اين، تعداد منابع در دسترس بر اساس تکميل و زمان شروع فعاليت­ها تغيير خواهد کرد.
4. هيچ توقفي نبايد در هنگام اجراي فعاليت­ها صورت گيرد.
5. هر فعاليت تنها يک حالت براي اجرا دارد.

در اينجا يک مسئلة زمان­بندي پروژه شامل J فعاليت مختلف در نظر گرفته مي­شود. بدليل محدوديت­هاي فني، فعاليت­ها توسط تعدادي رابطة تقدمي به يکديگر متصل مي­شوند. اين روابط تقدمي نشان­گر اين هستند که يک فعاليت j نمي­تواند قبل از تکميل تمام پيش­نيازهاي آن آغاز شود.  روابط مذکور را همچنين مي­توان بوسيلة يک شبکة گرهي فاقد حلقه همانند شکل 1 نشان داد؛ که در آن فعاليت­هاي ابتدا و انتـــهاي شبکه فعاليت­هاي موهومي هستند.

شکل رياضي روابط تقدمي بين فعاليت­ها را مي­توان به صورت زير نشان داد:

بر اساس محدوديت منابع، در هر لحظه ميزان استفاده از يک منبع نمي­تواند از حداکثر مقدار آن فراتر رود. فرمول­بندي رياضي اين محدوديت نيز به صورت زير است:

3- روش حل بر پاية سيستم ايمني مصنوعي براي مسئلة RCPS

3-1- سيستم ايمني مصنوعي (AIS):

طبيعت و بطور خاص سيستم­هاي بيولوژيکي هميشه بدليل پيچيدگي، انعطاف­پذيري و فلسفة کارکردي آنها براي کارشناسان سحرآميز بوده­اند. سيستم­ عصبي، الهام­بخشِ تکامل تدريجي شبکه­هاي عصبي مصنوعي است و در حالتي مشابه سيستم ايمني، موجب پيدايش يک سيستم ايمني مصنوعي (AIS) شده است. بر طبق نظر Castero & Zuben، AIS را مي­توان به عنوان چکيدة سيستم­هاي محاسباتي الهام گرفته شده از نظرية ايمونولوژي (Immunology) و اجزاي آن دانست. [3]

براي فهم بيشتر اين موضوع، تعداي عبارات بيولوژيکي اوليه در زير توصيف شده­اند:

سلول­هاي ايمني: سلول­هاي B و سلول­هاي T، دو گروه بزرگ از سلول­هاي ايمني هستند. اين سلول­ها در شناسايي الگوهاي آنتي­ژني در محدوده­اي تقريباً بي حد و حصر کمک مي­کنند.

آنتي­ژن­ها (Ag):  اينها عوامل بيماري­زا هستند. دو نوع آنتي­ژن خودي و غير خودي وجود دارد. آنتي­ژن­هاي غير خودي عوامل بيماري­زا بوده در حالي که آنتي­ژن­هاي خودي براي بدن بي­ضرر­اند.

آنتي­بادي­ها (Ab):  آنتي­بادي مولکولي است که بوسيلة يک سلول B در واکنش به يک آنتي­ژن توليد مي­شود و داراي خاصيت ويژه­اي است که با آنتي­ژن ترکيب شده و موجب تغيير شکل آن مي­شود.

3-2- نظرية انتخاب همزادي (Clonal selection):

هنگامي که يک سلول B با يک الگوي آنتي­ژني غير خودي با آستانة ميل ترکيبي (affinity) مناسب مواجه مي­شود، تکثير شده و به سلول­هاي عمل­کننده و سلول­هاي حافظـــه مشتق مي­شود. بر اساس نظرية انتخاب همزادي، آنتي­ژن سلول B را تحريک مي­کند که پس از تکثير به سلول  ترشحي با آنتي­­بادي نهايي تکامل مي­يابد. تکثير سلول­هاي ايمني يک فرآيند غيرجنسي و صرفاً تقسيم سلولي است. اين سلول­ها خودشان را براي توليد همزادها تقسيم مي­کنند. همزادها تحت يک فرآيند فراجهشي (Hypermutation) قرار مي­گيرند که منجر به توليد سلول­هاي B با گيرنده­هاي آنتي­ژني داراي ميل ترکيبي بالا با آنتي­ژن مذکور مي­شود. فرآيند انتخاب همزادي بطور خلاصه در شکل 2 نشان داده مي­شود.

شکل 2: فرآيند انتخاب همزادي، تکثير و بلوغ ميل ترکيبي

صرف­نظر از تکثير و مشتق شدن به سلول­هاي پلاسما، سلول­هاي B مي­توانند به سلول­هاي حافظة داراي عمر طولاني مشتق شوند. در طي تکامل سيستم ايمني اين امکان وجود دارد که سلول­هاي ايمني در طول حيات خود با يک آنتي­ژن خاص به­دفعات برخورد کنند، بنابراين سلول­هاي حافظة داراي عمر طولاني مي­توانند در واکنش­هاي آتي کمک کنند. حضور اين سلول­هاي حافظه در اولين مواجهه با بيماري، اثربخشي واکنش ايمني به مواجهة دوم را افزايش مي­دهد و اين به تضمين سرعت و دقتِ واکنش ايمني کمک کرده و به طور پي­در­پي آن را قوي­تر مي­کند.

فراجهش و تصحيح گيرنده دو خاصيت قابل توجه در سيستم ايمني هستند. آنها در تکامل فرزندان، به عنوان آنتي­بادي­هاي حاضر در واکنشِ حافظه، که بايد داراي ميل ترکيبي بيشتري از آنها که در واکنـــــش اوليه بوده­اند باشند، کمک مي­کنند. فراجهش بسيار شبيه به عملگر جهش در الگوريتم ژنتيک است، از آن رو که هر دو تغييرات تصادفي را براي متنوع ساختن فضاي جستجو معرفي مي­کنند. اما تفاوت آنها در نرخ تعديل نهفته است که بستگي به ميل ترکيبي آنتي­ژني دارد.

بطور کلي آنتي­بادي­هاي پَست (داراي ميل ترکيبي آنتي­ژني پايين) در يک نرخ بيشتر در مقايسه با آنتي­بادي­هاي داراي ميل ترکيبي آنتي­ژني بالا، فراجهش پيدا مي­کنند. اين پديده به عنوان تصحيح گيرنده شناخته مي­شود و فراجهش را اداره مي­کند. کار اصلي فراجهش هدايت به سمت بهينة محلي است، در حالي که تصحيح گيرنده به خروج از آن کمک مي­کند.

3-3- مراحل کلي AIS :

گام 1:  تابع هدف مخصوص مسئله را تعريف و پارامترهاي الگوريتم را معين کنيد.

 iter=0 قرار دهيد. (شمارنده­اي براي تعداد تکرارها) جواب­هاي تصادفي امکان­پذير اوليه را توليد کنيد. (در اينجا جواب همان عدد اولويت عمليات مربوط به هر فعاليت است)

گام 2 :   يک آنتي­ژن را بطور تصادفي انتخاب کرده و در معرض تمام آنتي­بادي­ها قرار دهيد.

ميل ترکيبي همة آنتي­ژن­ها را محاسبه کنيد و بردار ميل ترکيبي (Af) را بسازيد. (در مورد کار ما، براي محاسبة ميل ترکيبي، اولين زمان­بندي بهينه/نزديک بهينة فعاليت­ها را مطابق بخش 3.4 تعيين کرده و مقدار makespan آن محاسبه مي­گردد.)

گام 3 :   آنتي­بادي­هاي با بالاترين ميل ترکيبي Pc را انتخاب کنيد.

    مجموعة همزادها را براي آنتي­بادي­هاي منتخب توليد نماييد.

گام 4 :   براي هر همزاد توليد شده عمل جهش معکوس (قسمتي از رشتة همزاد را انتخاب کرده و معکوس کنيد) را با يک احتمالي انجام داده و ميل ترکيبي جواب جديد را محاسبه کنيد. اگر ميل ترکيبي جواب جديد از ميل ترکيبي همزاد بزرگتر است آنگاه همزاد را برابر با جواب جديد قرار داده و در غير اين صورت عمل تغيير جفتي را انجام دهيد. (دو مکان را انتخاب کرده و اجزاي آنها را جابجا کنيد) ميل ترکيبي جواب جديد را محاسبه کنيد، اگر بزرگ­تر از ميل ترکيبي همزاد بود آنگاه همزاد را برابر با جواب جديد قرار داده و در غير اين صورت همزاد را تغيير ندهيد.

گام 5 :   ساکنين جديد جامعه (يعني همزادها) را در معرض آنتي­ژن­ها قرار دهيد. امکان­پذيري را کنترل کرده و ميل ترکيبي را محاسبه نماييد.

گام 6 :   آنتي­بادي­هاي با کمترين ميل ترکيبي Ps را با بهترين همزادهاي Ps تعويض کنيد.

iter=iter+1  قرار داده، اگر (iter

3-4- زمان­بندي عملياتِ فعاليت :

در اين گزارش يک الگوريتم جستجوي ترکيبي بر پاية AIS با ويژگي­هاي آميخته با گراف جهت­دار و روش­هاي کوتاه جانمايي براي توليد يک زمان­بندي امکان­پذير بهينه/نزديک بهينه، توسعه داده شده است. در يک گراف جهت­دار، رئوس نشان­دهندة فعاليت­ها هستند در حالي که کمان­ها نشان­دهندة روابط تقدمي بين فعاليت­هاي مختلف­اند. کمان جهت­دار از گراف جهت­دار را مي­توان با mi , e_mj> نشان داد؛ که رأس e_mi بايد قبل از رأس e_mj تکميل شود. الگوريتم جستجو (AIS) اولين بار براي انتصاب يک عدد اولــويتِ ثابت نظير هر رأسِ گراف جهت­دار اجرا مي­شود، سپس روش کوتاه جانمايي براي توليد يک زمان­بندي اماکن­پذيرِ واحد مطابق با اعداد اولويت منصوب شده بکار مي­رود.

يک گراف جهت­دار از يک فرآيند توليد که در دو کارگاه اجرا شده، در شکل 3 نشان داده مي­شود.

شکل 3: گراف جهت­دارِ يک فرآيند توليد همراه با روابط تقدمي

رأس e₁₁ به عنوان اولين فعاليت انتخاب شده است، زيرا هيچ کمان مقدمي براي آن وجود ندارد و نيز داراي عدد اولويت بالاتري در مقايسه با رئوس e₁₂ و e₁₃ است. رأس e₁₁ را به عنوان اولين فعاليت انتخاب کرده و کمان­هاي متصل به e₁₁ را

شکل 4: کدگذاري آنتي­بادي

حذف کنيد. اين روند تکرار مي­شود تا اينکه همة رئوس انتخاب شوند. در آخر، يک توالي امکان­پذير واحد به صورت زير بدست مي­آيد:

{e₁₁ , e₁₃ , e₂₁ , e₂₃ , e₂₂ , e₁₂ , e₁₄ , e₁₅ , e₂₄ , e₂₆ , e₂₅}

4- اجراي رويکرد AIS براي حل مسئلة RCPS

همان­طور که پيش از اين بحث شد، هدف از حل مسئلة RCPS ، زمان­بندي فعاليت­ها است، بطوري که محدوديت­هاي تقدمي و منبعي برآورده شده و makespan کمينه شود.

4-1- تعريف مسئله

براي نشان دادن کارآيي و قدرت مدل پيشنهاد شده و نيز کيفيت رويکرد جواب بر پاية سيستم ايمني پيشنهادي، يک مثال توضيحي از [4] ذکر مي­شود. در اين مسئله يک پروژه با 27 فعاليت زمان­بندي مي­شود. اين زمان­بندي بايد بگونه­اي باشد که مدت زمان کل پروژه را کمينه کند. اطلاعات مربوط به هر فعاليت در جدول 1 آمده است. روابط تقدمي نيز در شکل 1 نشان داده مي­شود.

از روي شکل مي­توان ديد که کدام فعاليت پيش­نياز و کدام فعاليت پس­نياز است. فعاليت­هاي 1 و 27 فعاليت­هاي موهومی هستند.

4-2- الگوي کدگذاري

مبحث کليدي در اجراي رويکرد AIS، کدگذاري آنتي­بادي يک جواب و نحوة نمايش آن است. در طول دو دهة گذشته، روش­هاي کدگذاري رشته­اي مختلفي  مانند کدگذاري حقيقي، عدد صحيح، جايگشت، ماتريس و ... توسعه داده شده­اند. در اين گزارش از الگوي کدگذاري عدد صحيح استفاده مي­شود. براي مثال جواب اولية مسئله­اي با 10 فعاليت در شکل 4 آمده است. در آنتي­بادي نشان داده شده در اين مثال هر جزء نمايانگر اولويت هر فعاليت است، مثلاً اولويت عملياتِ فعاليت­هاي اول و دوم و چهارم به ترتيب برابر است با 6، 5 و 2.

4-3- جمعيت اوليه

رويکرد AIS پيشنـهاد شده بر روي يک آنتي­بادي از رشته­هاي تکي عمل مي­کند. چندين محقق هر دو روش تصادفي و ابتکاري را براي توليد جواب اوليه بکار برده­اند. نتايج آزمايشات نشان­دهندة اين است که عملکرد رويکرد AIS با جواب­هاي ابتدايي تصادفي بهتر از جواب­هاي از قبل انتخاب شده است. همچنين مشاهده شده است که جواب­هاي اولية تصادفي به طور کارا، فضاي جستجو را متنوع ساخته و بطور همزمان زمان محاسبات را کاهش مي­دهد.[5] اين دليل اصلي براي توليد تصادفي يک جواب اوليه در اين گزارش است. براي همين در آغاز به تعداد n عدد آنتي­بادي بطور تصادفي توليد مي­شود.

جدول 1: مجموعه داده­هاي مسئلة اول

4-4- محاسبه زيبندگي (Fitness)

بعد از مراحل آغازين، مقدار زيبندگي هر آنتي­بادي بر اساس تابع هدف مخصوص مسئله ارزيابي مي­شود. در اينجا هدف اصلي توليدِ يک زمان­بندي کارا از فعاليت­ها با کمترين مقدار makespan است، بطوري که همة محدوديت­هاي فني در نظر گرفته شوند.

شکل 5: آنتي­بادي اوليه

4-5- تکثير و بلوغ ميل ترکيبي

50 درصد از بهتـرين آنتي­بادي­هاي موجود براي تکثير ثبت­نام مي­شوند. در اينجا آنتي­بادي­ها در تقابل با هم نمايندگان خود را انتخاب مي­کنند. تعداد کل همزادهاي توليد شده از معادلة (3) تبعيت خواهد کرد:

سپس مرحلة بلوغ ميل ترکيبي انجام مي­شود. الگوريتم ما يک روية قطعي براي يافتن نرخ فراجهش دارد، که به صورت معادلة (4) است:

فراجهش تغييرات تصادفي را ارائه مي­دهد و تفاوت آن با فرآيند جهش طبيعي در درجة تعديل نهفته است. تصحيح گيرنده (درجه­اي که يک آنتي­بادي به بهترين نوع خود شباهت دارد) فراجهش را اداره کرده و قدرتي براي خروج از بهينه­هاي محلي ارائه مي­کند. از معادلة (4) بديهي است که آنتي­بادي­هاي با ميل ترکيبي پايين در يک نرخ بيشتري از آنتي­بادي­هاي با ميل ترکيبي بالاتر، فراجهش مي­يابند. الگوريتم حاضر بر اساس اين قوانين و اصول، آنتي­بادي­هاي فراجهش يافته را توليد مي­کند. شکل 5 يک آنتي­بادي اوليه را نشــان داده و شکل 6 همان آنتي­بادي را بعد از فراجهش نشان مي­دهد.

در آخر، مجموعه­اي از جواب­هاي فراجهش يافته تشکيل شده و مقدار زيبندگي آنها ارزيابي مي­شود. سپس تعداد ثابتي (d) از بهترين آنتي­بادي­ها براي توليدات بعدي انتخاب مي­گردند. در اينجا d يک پارامتر تنظيم است.

4-6- پارامتر تنظيم

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

با وجود موارد ذکر شده، رويکرد AIS سه پارامتر تعريف شده توسط کاربر دارد که عبارتند از: n (تعداد آنتي­بادي­هايي که بايد براي همزادي انتخاب شوند)، N_c  (تعداد همزادهاي توليد شده) و d (تعداد آنتي­بادي­هاي با ميل ترکيبي پايين که بايد تعويض گردند). اينها به طور عمده بر سرعت همگرايي، پيچيدگي محاسبات و توانايي الگوريتم براي اجراي جستجوهاي چند­شرطي اثر مي­گذارند.

شکل 7: ميانگين ميل ترکيبي جمعيت بعد از همگرايي

4-6-1-                       پارامتر n

در اين گزارش 50 درصد از بهترين آنتي­بادي­ها براي همزادي انتخاب شدند. با اينکه پارامتر n بطور قوي بر تعدادِ توليدات اثر ندارد، اما بطور مؤثري بر اندازة جمعيت تأثيرگذار است؛ و مقدار بزرگتر n به­معني هزينة محاسباتي بيشتر براي اجراي الگوريتم است. به همين دليل 50 درصد بنظر مناسب­تر و اقتصادي­تر است. همچنين ميانگين ميل ترکيبي جمعيت با افزايش n ، افزايش مي­يابد. اين امر در شکل 7 نشان داده شده است.

4-6-2-                       پارامتر Nc

بر روي اين پارامتر آناليز حساسيت صورت گرفته است. در هنگام ارزيابي عملکرد N_c ، مقدار n برابر 10 و d نيز صفر بوده است. چندين آزمايش بر روي N_c   از 0 تا 100 و در گام­هاي 20تايي و  از 100 تا 500 در گام­هاي 50تايي انجام شده و نمودار مربوطه در برابر تعداد توليدات، در شکل 8 رسم گرديده است. در اين شکل به سادگي مي­توان ديد که با مقدار بيشتر N_c

شکل 6: آنتي­بادي بلوغ يافته

، همگرايي سريع­تري برحسب تعداد توليدات رخ مي­دهد. با وجود اين، زمان محاسبات بازاي تعداد توليدات بصورت خطي با N_c  و در يک دامنة منطقي افزايش مي­يابد.

شکل 8: رابطة بين Nc و تعداد توليدات

4-6-3-                       پارامتر d

تعداد آنتي­بادي­هاي با ميل ترکيبي پايين که بايد تعويض گردند بطور زيادي بر حفظ تنوع در جمعيت مؤثر است. اين امر در جستجوي نواحي جديد کمک شاياني مي­کند. براي n=10 ، الگوريتم به­ازاي d=0,1,2,3,4 اجرا مي­شود، و بطور متناظر 0، 10، 20، 30 و 40 درصد از جمعيت در هر بار توليد تعويض خواهند شد. همان­طور که مقدار d افزايش مي­يابد الگوريتم به جواب بهينه نزديک و نزديک­تر مي­شود. در اين گزارش مقدار پارامتر d در عدد 1 تنظيم شده است.

5- نتايج محاسبات

براي اثبات کارآييِ ابتکار ارائه شده بر پاية AIS، مطالعات گسترده­اي بر روي مجموعة داده­هاي معروف RCPSP انجام شده است. ويژگي­هاي اصلي الگوريتم پيشنهاد شده عبارتند از:

1- ماهيت احتمالي الگوريتم به خروج آن از بهينه­هاي محلي کمک مي­کند.

2- رويه­هاي قطعي براي يافتن نرخ فراجهش به الگوريتم در دستيابي سريع­تر به جواب بهينه کمک مي­کند.

3- زمان محاسباتي مورد نياز براي محاسبة جواب بهينه بطور قابل توجهي با بکار بردن يادگيري حافظه، کاهش مي­يابد.

تجزيه و تحليل عميقي بر روي مسئله­اي که در بخش 4.1 ذکر شد، با استفاده از AIS انجام شده است. با بکارگيري رويکرد AIS براي اين ممسئله بهترين مقدار makespan برابر 64 بدست آمد.(جدول 2) در رابطه با اين مسئله مقايسه­اي بين رويکرد AIS با ديگر رويکردهاي موجود در ادبيات موضوع انجام شده که در شکل 9 نتايج آن نشان داده شده است.

شکل 9: مطالعة مقايسه­اي از AIS ارائه شده با ديگر رويکردهاي موجود

در شکل 9 واضح است که الگوريتم AIS بر همة روش­هاي موجود برتري دارد بغير از روش الگوريتم ژنتيک فازي (FGA[5]) که نتيجه در مورد هر دو روش يکسان است. با وجود اين، رويکرد AIS در تعداد کمتري از توليدات نسبت به الگوريتم ژنتيک فازي به جواب مي­رسد. الگوريتم AIS جواب را در 52 تکرار و FGA همان جواب را در 100 تکرار بدســت مي­آورد. همچنين زمان صرف شده براي رسيدن به جواب مذکور براي AIS برابر 0.41185 ثانيه و براي FGA 0.934066 ثانيه است. با توجه به موارد ياد شده مي­توان گفت، بر اساس معيار makespan الگوريتم AIS با رويکرد FGA برابر و بر اساس زمان محاسبات برتر از آن است. روند همگرايي رويکرد AIS در شکل 10 نشان داده مي­شود.

شکل 10: همگرايي makespan  با تعداد توليدات

چند گزينة ديگر با مقدار makespan  برابر 64 در جدول 3 نشان داده مي­شود. اين گزينه­ها از اين نظر داراي اهميت هستند که در صورت اجرايي نبودن يکي مي­توان از ديگري استفاده نمود.

جدول 2: برنامة زماني بهينة توليد شده توسط AIS براي مسئلة اول

نتايج مطالعات صورت گرفته بر روي مجموعة نمونة ProGen از PSPLIB [6] در جدول 4 خلاصه شده است. در اين جدول ميانگين درصدِ انحراف از makespan بهينه، براي مجموعة نمونة ProGen با 30 فعاليت بعد از 1000 و 5000 تکرار مشاهده مي­شود.

الگوريتم ارائه شده بر پاية AIS در C++ کدنويسي شده و بر روي يک کامپيوتر Pentium IV با  1.8 GHz CPUاجرا گرديده است.

6- نتيجه

در اين گزارش مسئلة زمان­بندي پروژه همراه با منابع محدود مورد بررسي قرار گرفت. هدف اصلي کمينه کردن مدت زمان کل پروژه با در نظر گرفتن چند معيار، (مانند انتخاب فعاليت و اولويت آن) در عين برآورده شدن محدوديت­هاي تقدمي و منبعي  بود. بررسي ادبيات موضوع آشکار مي­کند که اين مسئله از لحاظ محاسباتي پيچيده و ذاتاً NP-hard است. به همين دليل دست­يابي به جواب بهينه تحت يک جستجوي جامع در دنياي واقعي قابل اجرا نبوده و بنابراين استفاده از يک روش جستجوي تصادفي ضروري است. برخي از کارهاي صورت گرفته در گذشته، مدت زمان کل پروژه را کمينه کرده­اند، اما جواب آنها غير واقي بوده است زيرا بيش از يک محدوديتِ حداکثر منبع در دسترس را نقض کرده­اند. عملکرد الگوريتم AIS ارائه شده بر روي مسئله­اي که در ادبيات موضوع آمده است حاکي از اين است که اين الگوريتم در مقايسه با الگوريتم ژنتيک (GA[6])، الگوريتم ژنتيک فازي (FGA)، حداقلِ ديرترين زمان پايان ([7]LFT)، بيشترين استفاده از منابع (GRU[8])، کوتاه­ترين عمليات آتي (SIO[9])، حداقل شناوري کار (MINSLK[10])، روش زمان­بندي منابع (RSM[11])، انتخاب تصادفي کارها (RAN[12])، حداکثر کارهاي ممکن ([13]MJP)، برتر است.

اين موضوع داراي دامنه­اي وسيع جهت کارهاي آتي است. در آينده مي­توان توابع هدف ديگري چون تابع هزينة موجودي، ميانگين زمان در جريان، تابع ارزش فعلي خالص و... را مورد مطالعه قرار داد و از روش­هاي ديگري چون الگوريتم مورچگان، شبيه­سازي سرد شدن فلزات و ... استفاده کرد.

جدول 3: چند گزينة ديگر براي زمان­بندي بهينة بدست آمده بوسياة AIS براي مسئلة اول

جدول 4: ميانگين انحراف (%) از makespan بهينه براي مجموعه داده­هاي ProGen براي 30 فعاليت

7- مراجع