بخشی از مقاله
چکیده
این مقاله به مطالعه یک طرح تقریب کارا بر روی مسأله زمانبندی کارها روی تک ماشین با محدودیت دسترسی ماشین در یک بازه مشخص و با هدف مینیمم سازی ماکزیمم زمان تحویل کارها میپردازد. طرح های تقریب با زمان چندجمله ای که بر اساس مقایسه جواب الگوریتم مطرح شده برای حل مسأله با جواب بهینه بنا شده اند، معیاری برای سنجش کارایی الگوریتم حل یک مسأله خاص هستند. در این مطالعه یک طرح تقریب کارای بهبود یافته با زمان چند جملهای ارائه شده است. این طرح که بر اساس الگوریتم برنامه ریزی پویا بنا شده است، پیچیدگی زمانی کمتری نسبت به طرح های تقریب پژوهشهای قبلی دارد.
-1 مقدمه
مسائل زمانبندی به دلیل کاربرد فراوان در صنعت، تولید، مدیریت و سایر حوزه ها مورد توجه محققان قرار دارند. شروع این تحقیقات در دهه پنجاه با انگیزه کاربردی بودن این مسائل در زمینههای علوم کامپیوتر، بهینه سازی ترکیبیاتی، تحقیق در عملیات و مدیریت بوده است. این مسائل در رده مسائل -NP سخت مسائل بهینه سازی ترکیبیاتی و علوم کامپیوتر قرار می گیرند، از این رو پیدا کردن جواب بهینه دقیق برای آنها در زمان اجرای معقول - زمان چند جمله ای - امکان پذیر نیست. مسأله زمانبندی در یک بازه غیرقابل دسترس در مطالعات و ادبیات مربوطه بر اساس توابع هدف مختلف مورد بررسی قرار گرفته است.
برای نمونه میتوان به مراجع [1-8]، اشاره کرد. محققین این حوزه همواره تلاش دارند با رویکردهای مناسب روش های کارایی برای حل این مسائل ارائه کنند. یکی از این رویکردها ارائه راه حلهای تقریبی و نزدیک به جواب بهینه است. رویکردی که به لحاظ زمان اجرا سریع تر و در حین حال جواب های با کیفیتی را ارائه میکند. روش های تقریب در تمامی مسائل بهینه سازی، نظریه گراف و کلیه مسائل الگوریتم محور استفاده می شوند و به طور معمول به صورت الگوریتم های تقریب1، APX و طرح تقریب با زمان چند جمله ای2، PTAS و طرح تقریب با زمان کاملا چند جمله ای3، FPTAS مطرح میشوند.
اساس این طرح ها بر مبنای مقایسه جواب الگوریتم ابتکاری مطرح شده و جواب بهینه مسأله مورد نظر است. رویکرد یافتن طرح تقریب مناسب، برای سنجش کارایی الگوریتم-های حل مسائل بهینهسازی ترکیبیاتی استفاده میشود. از میان پژوهشهای مختلف که از این معیار استفاده کردهاند، میتوان به مراجع [9-15] اشاره کرد. در مسأله مطالعه شده در این پژوهش، مجموعهای از کارهای غیر وابسته وجود دارد که بایستی روی یک تک ماشین تحت قید یک بازه ثابت غیرقابل دسترس به منظور مینیمم سازی ماکزیمم زمان تحویل اجرا شوند.
این مسأله در ادبیات مختلف مورد مطالعه قرار گرفته است در سال 1982 قانون جکسون بر اساس ترتیب نزولی زمان های تحویل کارها تعریف شد - یعنی - 1 ≥ 2 ≥ ⋯ ≥ و نشان داده شد این قانون منجر به حل بهینه مسأله می شود اما زمانی که محدودیت هایی از قبیل بازه دسترسی ماشین به مسأله اضافه می شود این مسأله در دسته مسائل -NPسخت قرار میگیرد و حل بهینه مسأله در زمان چند جمله ای امکان پذیر نیست.
لی [16] قانون جکسون را ارائه کرد و نشان داد خطای جواب بدست آمده از بکارگیری این قانون نسبت به جواب بهینه از مقدار max{ } تجاوز نمی کند. - زمان اجرای کار ام است - . لی [16 ] ثابت کرد مسأله زمانبندی روی یک تک ماشین تحت بازه ثابت غیر قابل دسترسی و تابع هدف مینیمم سازی ماکزیمم تأخیر یک مسأله -NP سخت است.
قاسم و ها آوی [17 ] مسأله را با زمان های دسترسی هر کار در نظر گرفتند و نشان دادند قانون جکسون کران بدترین حالت با مقدار 2 را برای این مسأله دارد. یان و همکاران [ 18] طرح تقریبی با زمان اجرای چند جمله ای - - PTAS برای این مسأله پیدا کردند. قاسم [ 19 ] یک طرح تقریبی قویا ً چند جمله ای FPTAS برای این مسأله مطرح کرد.
مقاله به صورت زیر بخش بندی میشود:
بخش دوم این مقاله به تعریف مسأله اختصاص دارد. بخش سوم به ساده سازی ورودی مساأله می پردازد. بخش چهارم طرح تقریب بر اساس الگوریتم برنامه ریزی پویا روی مسأله مورد نظر را مطرح میکند و در بخش آخر نتایج ارائه میشود.
-2 فرمول بندی مسأله
میخواهیم مجموعه ای از کار = {1,2, … , } را بر روی یک تک ماشین که در بازه [ 1, 2 ] در دسترس نیست، زمانبندی کنیم به طوری که هر کار - 1 ≤ ≤ - زمان اجرای و زمان تحویل را دارد. ماشین در هر زمان حداکثر یک کار می تواند انجام دهد و همه کارها در زمان شروع به کار ماشین آماده برای اجرا می باشند.
-3 ساده سازی ورودی مسأله
پیدا کردن یک طرح تقریب برای یک مسأله بهینه سازی از رده -NP سخت به چگونگی طراحی و آنالیز الگوریتم تقریب مربوط میشود. به عبارتی ساختار این الگوریتم را باید به گونهای بهبود داد تا منجر به یک طرح تقریب شود. راهکارهای رسیدن به یک طرح تقریب با زمان اجرای چند جمله ای، متفاوت هستند. تغییر در ساختار الگوریتم یکی از این روشها است. این تغییر در ساختار به دقت مورد نظر در تقریب وابسته است و تغییر در ساختار باید به گونهای باشد که زمانی که به صفر نزدیک می شود میزان این تغییرات نیز کاهش یابد و به عبارتی از بین برود.
این مرحله از ساده سازی برای به دست آوردن نمونه جدید در زمان - - انجام می شود. دومین مرحله ساده سازی ورودی به این صورت است که مجموعه کارها را به زیر مجموعه های ′ تقسیم می کنیم. سپس کارهای کوچک - کارهایی که طول اجرای کمتر از ⁄2 دارند - در هر یک از این زیر مجموعه ها را با هم ترکیب می کنیم تا کارهای بزرگ به دست آوریم. در پایان تمامی کارها بر اساس ترتیب جکسون مجددا اندیس گذاری می شوند. نمونه به دست آمده از ساده سازی مرحله دوم را با ′′ نمایش میدهیم و جواب به دست آمده بر اساس ترتیب جکسون برای این نمونه را با - ′′ - نمایش میدهیم.
-4 برنامه ریزی پویا برای طرح تقریب با زمان بهبود یافته
یکی از راهکارهای دیگر برای یافتن طرح تقریب، تکنیک اصلاح ساختار اجرای الگوریتم است. ایده این روش بدین صورت است که یک الگوریتم دقیق اما با سرعت کند که برای حل مسأله مطرح شده است را به گونه ای اصلاح کنیم تا مقداری از داده های ورودی حذف شود و داده های کمتری برای پردازش باقی ماند تا سرعت الگوریتم بالا رود. در ادامه با بهکارگیری رویکرد برنامه ریزی پویا که توسط قاسم[19 ] مطرح شده است، طرح تقریب جدید را ارائه میکنیم.
