بخشی از مقاله
*** این مقاله شامل تعدادی فرمول میباشد که در سایت قابل نمایش نیست ***
حداقل کردن مصرف انرژی ماشینها و مجموع وزنی اتمام کارها در زمانبندی ماشینهای موازی نامرتبط
چکیده
در مسائل زمانبندی کلاسیک تنها بر روی تخصیص و توالی کارها برای بهینه سازییک تابع خاص که بنمیمم کردن زمان تکمیلیا دیر کردها، تمرکز شده است اما با توجه به نگرانیهای زیست محیطی، مصرف انرژی یکی از فاکتورهای مهم سیستمهای با عملکرد بالا محسوب میشود. در این مقاله مسأله زمانبندی ماشینهای موازی نامرتبط با هدف حداقل کردن همزمان مصرف انرژی ماشینها و مجموع وزنی زمان تکمیل کارها را مورد بررسی قرار میدهیم. برای هر ماشین سطوح مختلفی از سرعت در نظر گرفته شده است و مصرف انرژی هر ماشین متناسب با سرعت آن ماشین می باشد. بالا رفتن سرعت ماشین اگرچه باعث کاهش زمان تکمیل کارها می شود اما مصرف انرژی را نیز بالا می برد. در چنین شرایطی هدف مسأله یافتن همزمان توالی بهینه کارها و تعیین سرعت مناسب انجام هر کار روی هر ماشین جهت حداقل کردن جریمه های مربوط به مصرف انرژی و زمان تکمیل کارهاست. با ارائه نحوه نمایش جواب، برای حل مسأله فوق دو الگوریتم فراابتکاری بر پایه الگوریتم ژنتیک و روش بهینه سازی ازدحام ذرات پیشنهاد شده و در نهایت کارایی الگوریتمها مقایسه و نتایج بدست آمده مورد بررسی قرار گرفته است.
کلمات کلیدی:توالی عملیات، زمانبندی ماشینهای موازی نامرتبط، مصرف انرژی، الگوریتمهای فراابتکاری
۱. مقدمه
در پژوهش های زمانبندی کلاسیک غالبا سرعت پردازش ماشین آلات ثابت فرض می شود، این در حالی است که در واقعیت در بسیاری از موارد سرعت ماشینها قابل تنظیم است. کاملا مشخص است که هر چه سرعت پردازنده یا یک ماشین بیشتر باشد از نظر زمان پردازش مسلما عملکرد بهتری خواهد داشت. از طرفی هرچه سرعت پردازنده ماشین بیشتر باشد نه تنها انرژی بیشتری مصرف می کند بلکه گرمای بیشتری نیز تولید می کند که برای خنک کردن پردازنده یا ماشین می بایست از وسایلی مانند فن و غیره استفاده کرد که خود سبب مصرف بیشتر انرژی می شود. طبق تحقیقاتی که در ایالات متحده آمریکا انجام شده است مصرف انرژی در سال ۲۰۰۷ به میزان 7.2 بیلیون دلار بوده که به نسبت سال ۲۰۰۰ دو برابر افزایش داشته است، از اینرو روشهای صرفه جویی در انرژی در تحقیقات مورد توجه محققان قرار گرفته است. پیش از این ثابت شده است که تنظیم سرعت پردازنده با فداکردن زمان اتمام کار می تواند یکی از رویکردهای مهم و مؤثر در صرفه جویی انرژی باشد[۲]. ایده اصلی تنظیم سرعت پردازنده توسط مقیاس گذاری ولتاژ پویا (DVS) پشتیبانی میشود که ماشینها مجهز به تجهیزاتی با توانایی تغییر حالت محاسباتی خود در پردازشگرهای کامپیوتری (CPU)هستند. نمونه آنها را می توان در ۳۱, ۴] مشاهده کرد. لذا با امکان تغییر سرعت پردازنده ماشینها، بسیاری از مسائل زمانبندی کلاسیک می تواند دوباره مورد بحث قرار گیرد[۱]. اخیرا کارهایی که در این زمینه انجام شده میتوان به موارد زیر اشاره داشت. شروف و همکاران (۲۰۱۳) [۵] مسأله زمانبندی تک ماشین با هدف حداقل کردن مصرف انرژی در هر دوره را در حالیکه هزینه مصرف انرژی بصورت متغیر در نظر گرفته شود را بررسی کردند. آنها هچنینیک الگوریتم فراابتکاری بر پایه الگوریتم ژنتیک برای حل مسأله خود ارائه دادند. لو و همکاران (۲۰۱۳) [۶] مسأله زمانبندی جریان کاری را با تعریف تابع بهره وری تولید بعنوان تابع هدف و نیز با در نظر گرفتن هزینه مصرف برق ماشینها بررسی کردند. و برای حل مسأله مورد نظر از الگوریتم فراابتکاری مورچگان بهره گرفتند. روژیکی و وگلارز(۲۰۱۴) [۷] مسأله زمانبندی کارهای قابل انقطاع در ماشینهای موازییکسان با کم مصرف انرژی ماشینها را بررسی کردند و برای حل دقیق مسأله یک الگوریتم ریاضی جدید پیشنهاد دادند. فانگ و لین (۲۰۱۳) [۱] مسأله زمانبندی ماشینهای موازییکسان با فرض مجاز بودن تنظیم سرعت ماشينها و با هدف حداقل کردن جریمه دیرکرد و مصرف انرژی ماشینها بررسی شده و پس از مدلسازی مسأله، برای حل مسأله یک الگوریتم فراابتکاری بر پایه روش بهینه سازی ازدحام ذرات داده است. از آنجا که مسائل دنیای واقعی در سایز بزرگ هستند، بهینه سازی در مقیاس بزرگ یکی از زمینه های مورد علاقه در سالهای اخیر بوده است، از طرفی مسئله زمانبندی ماشینهای موازی با هدف مجموع وزنی زمان تکمیل کارها در ساده ترین حالت دو ماشین موازییکسان NP - Hard است [۸]. لذا استفاده از الگوریتمهای فراابتکاری در این زمینه میتواند رویکرد مناسبی باشد. آنگینولفی و پاولسی یک الگوریتم فراابتکاری ترکیبی از TS ، SA و VNS برای مسأله ماشینهای موازی با هدف حداقل کردن مجموع دیر کردها ارائه کردند. پیرو و رزی(۲۰۱۰) [۱۰] الگوریتم جستجوی محلی حریصانه را برای مسأله زمانبندی ماشینهای موازی نامرتبط با هدف حداقل کردن بیشترین زمان تکمیل کارها پیشنهاد دادند. بندی اها پرایا و باتاچرایا(۲۰۱۳) [۱۱] یک الگوریتم ژنتیک چند هدفه اصلاح شده را برای حل مسأله زمانبندی ماشینهای موازی با هدف حداقل کردن همزمان مجموع دیرکردها و بیشترین زمان تکمیل کارها ارائه دادند. کیوانفر و همکاران (۲۰۱۴) [۱۲] یک الگوریتم ابتکاری و نیز الگوریتم ژنتیک را برای مسأله حداقل کردن مجموع زود کردها و دیر کردها در زمانبندی ماشینهای موازی نامرتبط پیشنهاد دادند. فرانسیسکو (۲۰۱۳) [۸] یک الگوریتم فراابتکاری بر پایه جستجوی حریصانه برای مسأله زمانبندی ماشینهای موازی نامرتبط ارائه دادند، آنها ادعا کردند که الگوریتم ارائه شده قادر به حل مسأله با بیش از هزار کار و پنجاه ماشین با خطای بسیار کم است. در اینجا نیز از مدل ارائه شده مقاله "یک الگوریتم حریصانه تکرار شونده برای مسأله زمانبندی ماشینهای موازی نامرتبط در مقیاس بزرگ برای حداقل کردن مجموع وزنی اتمام کارها استفاده شده است. در این مقاله مسأله کمینه کردن همزمان مجموع وزنی اتمام کارها و مصرف انرژی ماشینها در مسأله زمانبندی ماشینهای موازی را بررسی خواهیم کرد. براییافتن توالی بهینه و تعیین سرعت بهینه کارها روی ماشینها براساس نحوه کدینگ نمایش جواب دو الگوریتم ژنتیک و روش بهینه سازی ازدحام ذرات را برای حل مسأله پیشنهاد و در نهایت نتایج را مقایسه خواهیم کرد. در ادامه در قسمت ۲ تعریفی از مسأله و شرایط آن بیان می شود، در قسمت ۳ روش حل پیشنهادی و معرفی مختصری از الگوریتم های پیشنهادی می پردازیم، در قسمت ۴ آزمایشات محاسباتی تدوین و تحلیل حساسیت و کارایی الگوریتمها برسی و مقایسه میشود. در پایان در قسمت ۵ نتیجه گیری و زمینه های تحقیقاتی آینده آورده شده است.
۲. تعریف مسأله و مدل سازی شرح کلی مسأله زمانبندی ارائه شده به صورت زیر است. n کار وجود دارد که باید روی m ماشین موازی پردازش شوند. ماشینها نامرتبط در نظر گرفته شده اند به این معنی که زمان پردازش هر کار روی هر ماشین متفاوت است. هر ماشین قادر است برای انجام هر کار روی سطوح سرعت متفاوتی تنظیم شود. سطوح سرعت ماشینها می تواند متفاوت باشد و هر سطح سرعت برای هر ماشین نیز هزینه انرژی در واحد زمان مشخصی دارد. وجود کارهای ناتمام در کارخانه از ابتدای ورود تا لحظه اتمام آن کار می تواند هزینه های گوناگونی اعم از نگهداری، سرمایه در گردش و تلف کردن زمان ماشین در لحظه ساخت و غیره، در پی داشته باشد از طرفی در بسیاری مواقع به دلیل بالا بودن هزینه های انرژی مصرفی ماشینیکی از رویکردها در جهت کاهش مصرف انرژی کم کردن یا متعادل کردن سرعت ماشین و به تأخیر انداختن اتمام کارها باشد. لذا در این تحقيق هدف یافتن تخصیص و توالی بهینه کارها روی ماشینها و نیز تعیینیا تنظیم بهینه سرعت هر ماشین برای انجام هر کار جهت حداقل کردن همزمان مجموع وزنی زمان اتمام کارها و هزینه های مصرف انرژی ماشینها می باشد. اندیسها و پارامترها اندیس کارها
تابع هدف(۱) حداقل کردن مجموع وزنی اتمام کارها و کل هزینه مصرف انرژی ماشینها برای انجام کارها را نشان میدهد. عبارت (۲) نحوه محاسبه زمان تکمیل کار در تابع هدف اول را نشان میدهد. که زمان اتمام کار ز از جمع زمان آن کار با زمان اتمام کل کارهایی که قبل از آن انجام شده است بدست می آید. محدودیت (۳) تضمین می کند که هر کار همزمان روی چند ماشین و نیز با سرعتهای متفاوت انجام نشود، بعبارتی هر کار براییک بار و تنها روییک ماشین و در یک سطح سرعت می تواند انجام شود. محدودیت (۴) بیانگر این است که هر نوبت یا مکان توالی برای هر ماشین حداکثر می تواند به یک کار با یک سرعت مشخص اختصاص یابد. عبارت (۵) نشان دهنده باینری بودن متغیر تصمیم مسأله می باشد.
٣. روش حل پیشنهادی مسأله زمانبندی ماشینهای موازی با هدف مجموع وزنی زمان تکمیل کارها حتی در ساده ترین حالت دو ماشین موازی مشابه NP - Hard است [۸]. بنابراین برای حل مسأله، استفاده از الگوریتمهای فراابتکاری کارآمد می تواند رویکرد مناسبی باشد. در ادامه پس از شرح نحوه نمایش جواب، برای حل مسأله فوق در مقیاس بزرگ، دو الگوریتم فراابتکاری بر پایه الگوریتم ژنتیک و روش بهینه سازی اردحام ذرات پیشنهاد شده و در نهایت کارایی الگوریتمها مقایسه و نتایج بدست آمده مورد بررسی قرار گرفته است.
۲۰۳. روش بهینه سازی ازدحام ذرات روش بهینه سازی ازدحام ذرات (PSO) یک روش تکاملی است که در سال (۱۹۹۵) توسط Eberhart & Kenedy معرفی شد ، که مفهوم اصلی آن از رفتار اجتماعی حیوانات الهام گرفته است. زنبورها و پرندگان وحیواناتی که دسته جمعی حرکت می کنند تجربیات خود را از جستجوی غذا با هم مبادله می کنند. بهمین دلیل است که وقتی زنبورها و پرندگان برای غذا پرواز می کنند کوتاهترین مسیر یا راه کارآمدی را بکار می برند. در PSO هر ذره با توجه به اطلاعات تصمیم و ارزش برازندگی آن که نشان از عملکرد آن ذره دارد جا داده می شود. سپس موقعیت هر ذره در فضا در هر تکرار براساس تجربیات آن ذره و همچنین بر اساس بهترین ذره بروز می شود[13]
. 1.2.3ایجاد جمعیت جواب اولیه متداولترین روش برای تولید جمعیت جواب اولیه، تولید جمعیت تصادفی به دلیل سرعت اجرا و نیز ایجاد تنوع در جوابها است. بنابراین در این قسمت به تعداد جمعیت در نظر گرفته شده، جواب تصادفی در بازه (1-m , 0) که m برابر تعداد ماشینهاست) تولید می کنیم و مقدار تابع هدف را نیز برای هر یک از آنها حساب می کنیم.
۲ . ۲ . ۳ . ارزیابی تابع ارزش برازندگی هر ذره(پاسخ) برابر Fiکه مقدار تابع هدف و برابر هزینه های بدست آمده برای اتمام کارها و انرژی مصرفی ماشینها برای ذره (متغیر پاسخ) i است.
۳ . ۲ . ۳ . به روز آوری سرعت و موقعیت ذرات
در تکرار t موقعیت و سرعت هر ذره بصورت زیر بدست می آید
۳ . ۳. الگوریتم ژنتیک الگوریتم ژنتیک به عنوان یک تکنیک بهینه سازی برای بسیاری از مسائل پیچیده توجه بسیاری را به خود جلب کرده است و بطور موفقیت آمیزی در بسیاری از شاخه های مهندسی صنایع از جمله توالی عملیات و زمانبندی، مکان یابی، جانمایی، طراحی قابلیت اطمینان، حمل ونقل و غیره بکار گرفته شده است. فرم کاربردی الگوریتم ژنتیک برای اولین بار توسط گلدبرگ در سال ۱۹۸۹ ارائه شده است. الگوریتم ژنتیک با یک جمعیت تصادفی اولیه از حلهای مسأله شروع میشود. هر کروموزوم در جمعیت معرف یک پاسخ شدنی برای مسأله مورد نظر است. کروموزوم ها از طریقیک تولیدمثل موفق تکامل پیدا می کنند. پس از هر تولید مثل، کروموزومها بوسیله اندازه گیری تابع برازندگی ارزیابی می شوند و هر کروموزوم که برازندگی بهتری داشت احتمال بیشتری برای انتخاب جهت تولید فرزند از طریق عملگرهای تقاطع یا جهش دارد. عملگر تقاطع، دو کروموزوم را جهت بوجود آوردن فرزند ادغام می کنددرنتیجه هر فرزند خصوصیات والدینش را به ارث می برد. عملگر جهش برای جلوگیری از همگرایی زودرس یک تغییر تصادفی خود به خودی را در ژنها بوجود می آورد [13]. |
۱ . ۳ . ۳ .ایجاد جمعیت جواب اولیه در این قسمت نیز از روش تولید جمعیت تصادفی بهره میگیریم. به تعداد جمعیت در نظر گرفته شده، طبق نحوه نمایش جواب شرح داده شده جواب تصادفی تولید می کنیم و مقدار تابع هدف را نیز برای هر یک از آنها حساب می کنیم.
