بخشی از مقاله
چکیده
مسئله ي زمان بندي یکی از مسائل مهم و پر کاربرد در طراحی پردازنده هاي چند هستهاي و پردازش موازي محسوب می شود. به همین دلیل، در سالیان اخیر تحقیقات گستردهاي در ارتباط با این مسئله انجام شده است. به طور کلی، زمان بندي به معناي یافتن زمان مناسب جهت رخدادن یک رویداد میباشد. برخی از مسائل زمان بندي مانند JSP از دسته مسائل NP hard محسوب می شوند. این مقاله با ارائه ي روشی ترکیبی به حل مسئلهي JSP در پردازنده هاي چند هسته اي می پردازد.
جهت ارزیابی روش پیشنهادي مدت زمان اجراي تمامی کارها، میزان مصرف انرژي و تاخیر اندازه گیري شده است. بررسی نتایج حاصل از شبیه سازي نشان می دهد، الگوریتم معرفی شده به صورت موثري مدت زمان اجراي کارها را کاهش می دهد. ضمنا، مصرف انرژي در روش پیشنهادي در مقایسه با روشهاي حریصانه تفاوت معنی داري ایجاد نکرده است. همچنین، در مواردي از نظر میزان تاخیر در اجراي کارها موثرتر عمل میکند.
-1 مقدمه
مسئله ي زمان بندي یکی از مسائل مهم و پر کاربرد در حوزه هاي مختلفی از جمله طراحی پردازندههاي چند هسته اي، پردازش موازي، سیستم هاي توزیع شده است. به طور کلی، زمان بندي به معناي یافتن زمان و توالی مناسب جهت رخدادن یک رویداد می باشد. به عبارت دیگر، زمان بندي شامل تعیین ترتیب و تخصیص فعالیت هایی است که باید توسط گروهی محدود از منابع پردازش شوند. با توجه به کاربردهاي گسترده ي زمان بندي در طراحی سیستمهاي سخت افزاري و صنایع مختلف، در طول سالیان اخیر تحقیقات گسترده اي در ارتباط با این مسئله انجام شده است. در سیستم عامل، زمان بندي از طریق دسترسی پردازنده ها یا نخها به منابع سیستم انجام می شود.
همچنین، یکی از مسائل مهم و رایج در سیتم هاي محاسباتی همگن و ناهمگن - گرید - [1]، معماري هاي چند هسته اي و موازي [2]، طراحی 1 NOCها، 2MPSOCها[3] و غیره محسوب میشود. مسئله ي زمان بندي قابلیت گسترش و تبدیل به مسائل متفاوت را دارد. انواع متفاوت این مسئله open shop scheduling، flow shop scheduling و job shop scheduling می باشند. در این مقاله سعی در بهبود عملکرد مسئلهي JSP از جهت زمان اجرا خواهیم داشت. بعلاوه، میزان مصرف انرژي نیز در این مقاله مورد بررسی قرار گرفته است.
مسئلهي JSP شامل گروهی متفاوت از کارهایی است که باید توسط ماشینهاي متفاوتی پردازش شوند. به عبارت دیگر، یک کار شامل لیستی مرتب از عملیات هایی است که هر کدام با توجه به ظرفیت ماشینهاي موجود و زمان پردازشی خود، پردازش می شوند. این مسئله محدودیتهایی در اجراي کارها توسط ماشین ها دارد.[4] معمولا تعداد کارها بیشتر از تعداد ماشین ها است. هر کار شامل چندین عملیات است که باید طبق ترتیب معین شده، توسط ماشین ها پردازش شوند.
میان عملیات هاي کارهاي متفاوت تقدم یا تاخري وجود ندارد. پردازش کارها توسط ماشین ها قبضه اي می باشد. به این معنی که اگر ماشینی در حال اجراي کاري است، نمی تواند آن را متوقف کرده و عمل دیگري را پردازش کند. هر ماشین در هر زمان تنها قادر به اجراي یک کار است و هر کار در هر زمان تنها توسط یک ماشین اجرا خواهد شد. این مقاله، از یک تعریف ریاضی ساده جهت معرفی و توصیف مسئله استفاده کرده است.
اگر مسئله ي فروشنده ي دورهگرد3 را به عنوان یک مسئله ي NP بشناسیم، بنابراین می توان به صراحت گفت که مسئلهي JSP یک مسئله ي NP سخت محسوب می شود. زیرا مسئلهي TSP نمونه اي خاص از مسئله ي JSP با یک ماشین - فروشنده - و n کار - شهرها - است .[4] الگوریتمهاي حریصانه، از روش هاي حل مسائل NP محسوب می شوند. این الگوریتم ها با صرف زمان کمتري نسبت به روش هاي دیگر، توانسته اند پاسخهاي مناسبی را تولید نمایند.
به عنوان مثال مقاله ي [5] با ارائه ي روشهاي Greedy min و Greedy max به حل مسئله ي زمان بندي در حوزه ي محاسبات گرید پرداخته است. این الگوریتم ها در برخی دیتاست ها باعث ایجاد قحطی زدگی در اجراي کارها می شود. جهت رفع مشکل قحطی زدگی، می توان با ارائه ي یک روش ترکیبی از مزایاي روش هاي حریصانه بهره جست. در مقاله ي پیشرو، روش جدیدي مبتنی بر روش هاي Greedy min و Greedy max جهت کاهش زمان کل زمان بندي ارائه شده است. ساختار کلی مقاله به این شکل است: بخش2 تحقیقات مرتبط حول مسئلهي JSP، بخش3 شرح الگوریتم پیشنهادي و بخش4 شامل نتایج پیاده سازي و مقایسات خواهد بود.
-2 تحقیقات مرتبط
مسئلهي JSP در سال 1963 با طرح مثالی با 10 کار و 10 ماشین توسط Fisher و Thompson ارائه شد. طی 50 سال گذشته روش هاي گوناگونی جهت حل و بهینه سازي این مسئله ارائه شده است. همانگونه که ذکر شد، مسئلهي JSP از دسته مسائل NP محسوب می شود. بنابراین از روشهاي حل مسائل NP جهت حل این مسئله استفاده می گردد. این روشها به چهار بخش کلی تقسیم شدهاند: - i - الگوریتم هاي دقیق - ii - الگوریتمهاي ابتکاري - iii - الگورتیم هاي هوش جمعی و - iv - الگوریتمهاي حریصانه. در حل مسائل بهینه سازي، الگوریتم هاي دقیق قادر به یافتن جواب بهینه به صورت دقیق می باشند. امروزه کمتر از الگوریتم هاي دقیق استفاده میشود.
زیرا این الگوریتم ها زمان زیادي را صرف محاسبات، درحل مسائل بهینه سازي میکنند. الگوریتم هاي انشعاب و محدودسازي، ازدسته الگوریتمهاي دقیق محسوب می شوند. اساس کار این دسته از الگوریتمها بررسی تمامی پاسخهاي ممکن جهت حل یک مسئله ي بهینه سازي است.[4] الگوریتمی که توسط McMahon و Florian در سال 1975 ارائه شد، براي سال هاي زیادي کارآ ترین الگوریتم محسوب می شد6]، .[7
الگوریتمهاي ابتکاري4 یا هیوریستیک، به دسته اي از راهحل ها گفته می شود که به دنبال جوابی معقول و قابل قبول براي یک مسئله دشوار می گردند که الزاماً بهترین جواب براي آن مسئله نیست. هیوریستیکها با کاهش زمان محاسبات، داراي نقشی اثر بخش در حل چنین مسائلی خواهند بود. الگوریتم هاي ابتکاري همه منظوره مانند جستجوي تابو5 و شبیه سازي تبرید6 به منظور حل مسئلهي JSP استفاده شده است. [6] قابل ذکر است، که تا به امروز الگوریتم ابتکاري با کارآیی تضمین شده، ارائه نشده است.[8]
الگوریتم هاي هوش جمعی از دسته روش هاي تقریبی در حل مسائل بهینه سازي محسوب می شوند. با استفاده از این الگوریتم ها پاسخهایی یافت می شود که تقریبا به جواب نهایی مسئله نزدیک تر است.[9] تلاشهاي اولیه جهت ارائهي روشی قدرتمند و عمومی به منظور حل مسائل بهینه سازي، با معرفی روش هایی از الگوریتم ژنتیک توسط Aarts در سال 1994، Nakano و Yamada در سال هاي 1991 و 1992 آغاز شد.[10] روش هایی که معرفی شد، هریک بهینه سازي هاي قابل قبولی را در حل مسئلهي JSP با شرایط و پیشفرض هاي متفاوت بدست آوردهاند.
روش حریصانه یکی از روش هاي مشهور و پرکاربرد در طراحی الگوریتمها محسوب می شود که با ساختاري ساده در حل بسیاري از مسائل استفاده می شود. این روش اغلب در حل مسائل بهینه سازي استفاده شده و در پاره اي مواقع جایگزین مناسبی براي روش هایی مانند برنامه ریزي پویا است. در حالت کلی این روش سرعت و مرتبه اجرایی بهتري نسبت به روش هاي مشابه خود دارد. اما متناسب با مساله، ممکن است به یک جواب بهینه سراسري ختم نشود.
در این مقاله، با بررسی روش هاي حریصانه به حل و بهینه سازي مسئلهي JSP خواهیم پرداخت. تا به امروز، الگوریتم هاي حریصانه و حریصانه ي ابتکاري زیادي جهت حل مسائل بهینه سازي به خصوص مسئله ي JSP ارائه شده است. به طور مثال Adams، Balas و Zawack در سال 1988، Sadeh در سال 1991، Dauzere-peres و Lasserre در سال 1993، Balas و Vazacopoulos
در سال 1995و . . .[4]. در مقاله ي [5] با استفاده از تکنیکهاي حریصانه و با معرفی چندین الگوریتم حریصانه ي ساده به حل مسائل زمانبندي در فضاي محاسباتی گرید پرداخته است. از جمله ي این الگوریتم ها، Greedy min و greedy max می باشد. در این مقاله، ابتدا با پیاده سازي الگوریتمهاي Greedy min و greedy max براي حل یک مسئلهي JSP، با تلفیق روش هاي فوق الگوریتمی جهت حل این مسئله معرفی خواهد شد.
-3 روش پیشنهادي
در این مقاله با ارائه ي یک الگوریتم ترکیبی، به حل مسئله ي JSP خواهیم پرداخت. این روش با توجه به شرایط مسئله یکی از الگوریتم هاي Greedy max یا Greedy min را به کار خواهد گرفت. همانگونه که ذکر شد الگوریتم هاي Greedy min و Greedy max از دسته الگوریتم هاي حریصانه در حل مسائل بهینه سازي محسوب می گردند. در الگوریتم - Greedy max - Greedy min انتخاب کار یا عملیات بعدي بر اساس زمان اجراي هر کار یا عملیات انجام می گردد.
در هر بار اجراي حلقه ي اصلی الگوریتم - Greedy max - Greedy min براي مسئلهي JSP، شماري عملیات آماده ي اجرا میباشند که تعداد این عملیات ها معمولا بیش از تعداد ماشین ها است. هریک از عملیات ها تنها توسط یک ماشین قابل اجرا می باشد. هر ماشین باید عملیات مربوط به خود را پردازش کند. اگر در یک زمان چند عملیات به یک ماشین محول شود، ماشین، عملیاتی که کمترین - بیشترین - زمان اجرا را دارد براي پردازش انتخاب خواهد کرد. با توجه به زمان مصرفی این الگوریتم ها می توان گفت، پاسخ نسبتا خوبی بدست می دهند اما امکان ایجاد گرسنگی براي اجراي برخی کارها را به وجود میآورد.
با معرفی روش زیر میتوان گفت امکان ایجاد قحطی در اجراي کارها با استفاده از این نوع الگوریتم هاي حریصانه کاهش پیدا خواهد کرد. در دیتاست هاي مورد استفاده جهت حل مسئلهي JSP، کمترین و بیشترین زمان لازم جهت اجراي عملیاتها مشخص می باشد. کمترین زمان اجرا با minproc و بیشرین زمان اجرا با maxproc نشان داده می شود. در هر بار اجراي حلقه ي اصلی این الگوریتم، تعدادي عملیات آماده ي اجرا میباشند.
آرایهي var شامل زمان اجراي این عملیات ها میباشد. maxvar بیشترین مقدار آرایهي var و minvar کمترین مقدار آرایه ي var را نشان میدهند. همچنین ave1 میانگین maxproc و minproc ، و ave2 میانگین عناصر آرایهي var را نشان میدهند. هر ماشین باید عملیات مربوط به خود را پردازش کند. اگر در یک زمان چند عملیات به یک ماشین محول شود، ماشین مورد نظر به شیوه ي زیر عمل خواهد کرد:
اگر در میان عملیاتهاي آماده ي اجرا، عملیاتی با بیشینه زمان اجرا وجود داشت، ۰ f lag = خواهد بود.
اگر در میان عملیات هاي آمادهي اجرا، عملیاتی با کمینه زمان اجرا وجود داشت، ۱ f lag = خواهد بود.
اگر در میان عملیاتهاي آماده ي اجرا، عملیاتی با بیشینه زمان اجرا و کمینه زمان اجرا وجود نداشت، ۲ f lag = خواهد بود.
اگر در میان عملیات هاي آماده ي اجرا، هم عملیات هایی با بیشینه
زمان اجرا و هم عملیات هایی با کمینه زمان اجرا وجود داشت، ۲ f lag = خواهد بود. در الگوریتم 1 نحوه ي عملکرد الگوریتم پیشنهادي قابل مشاهده است. به این ترتیب می توان گفت، امکان اجرا نشدن یک کار به دلیل پایین - بالا - بودن زمان اجراي اولین عملیاتش کاهش پیدا خواهد کرد. در بخش بعدي با توجه به نتایج پیاده سازي به بررسی و ارزیابی الگوریتم پیشنهادي خواهیم پرداخت.
