بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه راه حلي بر پايه الگوريتم جستجوي هارموني براي مسئله زمانبندي در ماشينهاي موازي مستقل براساس معيار کمترين تاخير و زودرسي کارها
چکيده
در اين مقاله راه حلي کارا براي مسئله زمانبندي ,در ماشينهاي موازي با معيـار کمينـه سـازي تـاخير (Tardiness) و زودرسـي (Earliness) کارها ارائه شده است .راه حل بر پايه زمانبندي تصادفي (Stochastic) و با استفاده از الگوريتم جستجوي هـارموني (Harmony Search Algorithm) است . روش جديد ارايه شده بر پايه ترکيب دو الگوريتم جسـتجوي هـارموني بهبـود يافتـه (Improved Harmony Search) و الگوريتم جستجوي هارموني مرسوم اسـت . در ايـن الگـوريتم از دو نـرخ تنظـيم ( Pitch Adjustment Rate) متفاوت به جهت جستجوي سريعتردر دو فضاي گسسته و پيوسته جوابها به صورت همزمان استفاده شده است .از اين جهت ترکيب دو نوع الگوريتم ياد شده و جستجوي همزمان دو فضاي گسسته و پيوسته در نوع خود بديع است .نتـايج شبيه سازي حاکي از بدست آوردن زمانبنديهايي با کمينه معيار بهتر,در تمام نمونه ها,نسـبت بـه شـبيه سـازيهاي انجـام شـد باالگوريتمهاي ژنتيک (GA) و ژنتيک -کوانتم (QGSA)است .
کلمات کليدي
زمانبندي ماشينهاي موازي (Parallel Machine Scheduling) ,الگوريتم جستجوي هارموني (Harmony Search),تـاخير و زودرسـي کارها (Earliness-Tardiness)
۱-مقدمه
زمانبندي ماشينهاي موازي از جمله مسائل زمانبندي است که در صنايع و بويژه خط مونتاژ کاربردزيادي دارد.در حال حاضراين مسئله يکي از مسائل باز و مورد تحقيق در زمينه تحقيق در عمليات يا OR است .ثابت شده اين مسئله جزو مسائل NP-HARD مي باشد[١].تاکنون روشهاي بسياري براي حل مسئله زمانبندي ماشينهاي موازي ارائه شده است که از جمله آنها مي توان به روشهاي اکتشافي و فوق اکتشافي از جمله روشهاي شاخه و حد[٢] ,جستجوي ممنوعه [٣] ,الگوريتم ژنتيک [٤]و شبيه سازي سرمايش [٥]اشاره کرد.اخيرا روشهاي ترکيبي از جمله کوانتم - ژنتيک نيز در مرجع [٦] مورد استفاده قرار گرفته شده است .در اين مقاله سعي شده با روشي متفاوت و با استفاده ,ترکيبي از الگوريتمهاي جستجوي هارموني (يا به اختصار HS),راه حلي نزديک به بهينه براي مسئله بدست آيد.اين الگوريتم داراي پيچيدگي پياده سازي بسيار کمي ميباشد و پياده سازي آن ساده است .اين الگوريتم تا به حال بر روي مسائل زيادي با موفقيت امتحان شده است [٧,٨]. الگوريتم ياد شده علاوه بر مزاياي بالا پيچيدگي زماني کمتري دارد چرا که با توجه به شکل ۱تنها داراي دو حلقه اصلي و تودر تو در ساختار خود است .همچنين بر خلاف الگوريتمهاي مرسوم بر پايه جمعيت ,که در هر بار تکرار,iteration, تعدادي جواب براي مساله ارايه مي دهند, مانند الگوريتم تکاملي ژنتيک و الگوريتمهاي بر پايه ازدحام ذرات ,تنها يک جواب در هر تکرار بدست مي ايد.
۲- توصيف مسئله
در اين مسئله nتعداد کار که هر کدام داراي پارامتر هاي :
Rj -: زمان آزاد سازي يا آماده بودن کار,در اين مسئله زمان آزاد سازي تمام کارها ۰در نظر گرفته شده است .
Dj - : زمان سررسيد کار
Pj - : زمان پردازش کار jام
Cj - : زمان اتمام کار jام
Tj -: تاخير کار jام .
Ej -: زودرسي کار jام .
هستند,بر روي m تعداد ماشين موازي با شرايط زير :
يک ماشين در هر زمان فقط يک کار را مي تواند انجام دهد.
ماشينها از هم مستقلند.
ماشينها از لحاظ سرعت و ديگر ويژگيها يکسان هستند.
ماشينها بدون وقفه کار مي کنند.
به گونه اي زمانبندي مي شوند تا تابع هدف يا برازش راکمينه سازند[٦].
- : ميزان زودرسي تمام کارها
- : ميزان تاخير تمام کارها از موعد مقررشان
۳-الگوريتم جستجوي هارموني ( Harmony (Search Algorithm
الگوريتم جستجوي هارموني يا Harmony Search الگوريتمي است فوق اکتشافي ,داراي زمينه تصادفي (Stochastic) که از تقليد فرايند اجراي موسيقي (Jazz) الهام گرفته شده است [٧] . اين الگوريتم داراي مفهومي ساده و به راحتي قابل پياده سازي است .اين الگوريتم در ابتدا براي محيطهاي گسسته طراحي شده و سپس در روند توسعه خود براي محيطهاي پيوسته نيز پياده شد[٩].مراحل و فازهاي اين الگوريتم در شک ۱نمايش داده شده است .اين مراحل به قرار زيرند[٧] :
i. مرحله مقدار دهي اوليه مسئله و پارامتر هاي الگوريتم
ii. مقدار دهي اوليه حافظه (Harmony Memory) iii. ايجاد يا اجراي (Improvise) يک هارموني
iv. بروز رساني حافظه
v. چک کردن شرط پايان
اين پنج گام به شرح زير هستند.
۳-۱-مرحله مقدار دهي اوليه مسئله و پارامتر هاي الگوريتم
هدف از اين مرحله فرموله کردن مسئله است . بطور کلي مي توان مسائل بهينه سازي رابه صورت رياضي و بصورت تابع هدف و توابع قيوددرنظر گرفت .
ai,bi ضرايب جريمه توابع قيود تساوي و عدم تساوي هستند.
عمومابسيار مشکل است که اين ضرائب محاسبه شونددر حالي که مسئله به اين پارامترهاوابسته است . پارامترهايHS نيز در اين گام تعيين مي شوند. اندازه حافظه هارموني (HMS) يا تعداد بردارهاي جواب در حافظه هارموني , احتمال انتخاب از حافظه (HMCR) ,احتمال تنظيم کوک(PAR) وتعدادبهبود (NI) وشرط پايان پارامتر هاي الگوريتم اند. حافظه هارموني (HM)شامل همه بردارهاي راه حل ذخيره شده است . اين بردارها همان مجموعه ژنتيک در الگوريتم ژنتيک است .
۳-۲- مقدار دهي اوليه ماتريس هارموني Harmony Memory
در اين قسمت ماتريس هارموني با تعدادي هارموني Harmony (هر هارموني معادل يک جواب براي مسئله است ) که بصورت تصادفي مقدار دهي شده اند پر مي شود. يک هارموني شامل بردار متغييرهاي تصادفي و جواب تابع هدف است .براي همگرايي بهتر مي توان هارمونيهاي تصادفي بيش از اندازه ماتريس هارموني ايجاد کرد و انگاه از بين آنها و بر اساس مقدار تابع هدف از بين آنها انتخاب کرد.معمولا بعد از مقداردهي به متغيير هاي تصادفي و محاسبه تابع هدف هر هارموني ,در ماتريس هارموني ,ماتريس بترتيب غير نزولي و بر اساس مقدار تابع هدف مرتب مي شود.
هر رکورد اين ماتريس يک هارموني و تعداد کل رکوردهاي اينما ريس به نام HMS يا Harmony Memory Size خوانده مي شود.مـات يس HM محلي است که قرار است بهترين هارموني هادر آن باقي بمانند.
۳-۳-اجراي يک هارموني جديد
بعد از مرحله پر کردن ماتريس هارموني (HM),نوبت به توليد يک هارموني مي رسد. توليد مقادير جديد هارموني به پيشرفت و بهبود (Improvisation) معروف است .بردار هارموني جديد بر اساس سه قاعده زير بنا مي شود:
درنظر گرفتن حافظه
تنظيم کوک(pitch)
انتخاب مقاديرتصادفي
در حافظه مقادير اولين متغير هاي تصميم گيري در دامنه مي آيند. مقادير ديگر متغيرها به همين شيوه بدست آمده است . HMCR بين صفرو يک تغيير مي کند و ميزان انتخاب يک مقدار از ساير مقادير ذخيره شده در HM را نشان مي دهد. (HMCR-1) ميزان انتخاب تصادفي يک مقدر از دامنه ممکن متغيرمطابق فرم (۴) است .
جايي که ()rand يک عدد تصادفي بين صفر و يک و Xi ميزان محدوده ممکن مقادير تصميم گيري است بدين ترتيب
که براي مثال يک HMCR با ٨۵% نشان دهنده اين است که HS مقدار متغير تصميم گيري را از مقادير قبلي ذخيره شده درHM با ٨۵% احتمال بدست مي آيد. هر جزء بدست آمده با حافظه مد نظر باز تنظيم ميشود اين عملکرد با استفاده از پارامتر PAR (ميزان تنظيم کوک ) و در فضاي پيوسته مطابق (۵ ) انجام مي شود..
bw پهناي باند فاصله دلخواه است و جهت پيشرفت کارايي HSبکارگرفته مي شود. مرجع [۱۰] الگوريتم جستجوي هارموني بهبود يافته را با متغير بودن PAR و bw در نظر مي گيرد.در اين روش PAR و bw بصورت (۶)بدست مي آيند:
پهناي باند براي هر تکرار است .
مراجع [١١,١٢]روش هاي آماري جديدي رابراي متغير هاي گسسته وپيوسته بر اساس الگوريتم جستجوي هارموني جهت بهينه سازي انجام مي دهند . در فضاي گسسته فرايند تنظيم کوک با استفاده از مفهوم همسايگي , پارامتر و به صورت (٧)انجام مي پذيرد:
