بخشی از مقاله
چکیده:
در این پژوهش به بررسی مسألهی زمانبندی ماشینهای موازی غیرمرتبط با در نظرگرفتن محدودیت دسترسی به ماشین و محدودیتهای پردازش پرداخته میشود. در نظر گرفتن محدودیت دسترسی به ماشین در کنار محدودیتهای قابلیت ماشین و زمانهای آمادهسازی وابسته به توالی و نوع ماشین، نوآوری این مقاله محسوب میشود زیرا در پژوهشهای انجام شده در حوزهی زمانبندی ماشینهای موازی تا به کنون، این محدودیتها با هم در یک مسأله لحاظ نشدهاند و در اغلب موارد محدودیت دسترسی به ماشین به شیوههای مختلف، تنها محدودیت مسأله بوده است. هدف از این مسأله، تعیین رویکرد تخصیص کارها به ماشینها و زمانبندی کارها روی هر ماشین در جهت کمینه کردن دامنه عملیات است. برای حل این مسأله در اندازههای کوچک، یک مدل ریاضی غیرخطی آمیخته ارائه شده است سپس نمودی از مسأله، ارائه و مدل ریاضی آن با استفاده از یک نرم افزارهای بهینهسازی - GAMS - حل شده و مقدار بهینه تابع هدف آن گزارش شده است.
کلمات کلیدی:زمانبندی ماشینهای موازی; محدودیت دسترسی به ماشین; مدل ریاضی غیرخطی آمیخته
-1 مقدمه :
زمانبندی یک فرایند تصمیم سازی است که در بسیاری از صنایع خدماتی و تولیدی استفاده میشود. زمانبندی با تخصیص منابع به فعالیتها در بازههای زمانی داده شده، سروکار داشته و هدف آن بهینهسازی یک یا چند هدف تعیین شده است. دراین پژوهش، مسألهی زمانبندی ماشینهای موازی غیرمرتبط با در نظرگرفتن زمانهای آمادهسازی وابسته به توالی کارها و نوع ماشین، محدودیت دسترسی به ماشین و محدودیتهای قابلیت ماشین با تابع هدف کمینه کردن دامنهی عملیات مورد بررسی قرار میگیرد. منظور از ماشینهای موازی غیرمرتبط این است که تعدادی ماشین به صورت موازی و با سرعتهای متفاوت وجود دارند. اگر ماشین i توانایی پردازش کار jرا داشته باشد، آن را با سرعت انجام میدهد و زمان که کار j روی ماشین i صرف میکند برابر با است.
محدودیت دسترسی به ماشینها را میتوان به دو صورت در نظر گرفت. در حالت اول یک ماشین از ابتدای دوره زمانبندی در دسترس نباشد یعنی زمان دسترسی به ماشین صفر نبوده و این میتواند به این دلیل باشد که پردازش کارهای دوره قبلی زمانبندی روی این ماشین به پایان نرسیده در نتیجه ماشین در ابتدای دوره فعلی در دسترس نیست و با تاخیر در دسترس قرار میگیرد. در حالت دوم، یک ماشین در یک دوره زمانی نیازمند فعالیتهای نگهداری و تعمیرات میباشد و در آن زمانها ماشین در دسترس نیست. البته حالت دوم نیز به دو حالت دیگر تقسیم میشود که زمانهای نگهداری و تعمیرات از ابتدا به صورت قطعی، مشخص است یا به صورت احتمالی در نظر گرفته میشوند.
در مسأله زمانبندی که در این پژوهش مورد بررسی قرار میگیرد، هر ماشین ممکن است در زمانهای خاصی در دسترس فاروقی، مهدوی، برزنجه، امینی/ زمانبندی ماشینهای موازی غیرمرتبط با در نظر گرفتن محدودیت دسترسی به ماشین و محدودیتهای پردازشنباشند. همچنین محدودیتهای قابلیت ماشین که در این مسأله مطرح شده، این مفهوم را بیان میکند که بعضی از ماشینها توانایی پردازش بعضی از کارها را ندارند.در ادبیات زمانبندی، مسأله زمانبندی ماشینهای موازی مورد توجه بسیاری از پژوهشگران قرار گرفته و کارهای متعددی در این زمینه انجام شده است. در این بخش سعی بر این است که به مرور تحقیقاتی در حوزه زمانبندی ماشینهای موازی پرداخته شود که محدودیت دسترسی به ماشینها وجود داشته باشد.
یک مسأله زمانبندی با سهگانه | | توصیف می شود. فیلد محیط ماشین را توصیف میکند و فقط شامل یک ورودی میباشد. فیلد جزئیات ویژگیهای فرایند و محدودیتها را دربر میگیرد و ممکن است بدون ورودی یا با یک یا چند ورودی باشد. فیلد هدفی را که باید کمینه شود، توصیف میکند. در زیر عبارتهایی که در این پژوهش برای هر فیلد مسأله استفاده شده، توضیح داده میشود.در ادامه به بررسی مطالعاتی که در حوزه زمانبندی ماشینهای موازی با در نظر گرفتن محدودیت دسترسی به ماشینها به انجام رسیده، پرداخته میشود.مکنافتن[16] مسأله زمانبندی ماشینهای موازی زمانی که همه ماشینها در یک بازه زمانی مشابه در دسترس هستند را بررسی کرد و یک الگوریتم چندجملهای را با m-1 وقفه برای ایجاد یک زمانبندی موجه جهت کمینه کردن دامنه عملیات پیشنهاد کرد.
اشمیت[10]همین مسأله را زمانی که ماشینها در بازههای متفاوتی در دسترس هستند، بررسی کرد. لی[6] برای حل مسأله | − | ازالگوریتم طولانی ترین زمان پردازش تغییر یافته - MLPT - استفاده کرد. لی و لیمان[7] مسأله را در حالتی که یک ماشین اززمان صفر تا نقطه زمانی ثابتی در دسترس و بعد از آن قادر به پردازش هیچ کاری نبود را بررسی کردند. آنها اثبات کردند که این مسأله NP-hard است و یک الگوریتم برنامهریزی پویای شبه چندجملهای و همچنین یک روش ابتکاری بر مبنای کوتاهترین زمان پردازش راارایه کردند. موشیو[11] مسأله را با این فرض که یکی از ماشینها در بازه خاصی در دسترس باشد، بررسی کرد.
او نشان دادکه الگوریتم کوتاهترین زمان پردازش برای حالت m ماشین هنگامی که تعداد کارها بالا میرود، بهینه است. سورش و چادهوری[18] مسأله | − | را در حالی که ماشین دارای چندین دوره در دسترس نبودن است، بررسی کردند و از یک الگوریتم ابتکاری برای حل مسأله استفاده کردند. آنها دوره در دسترس نبودن یک ماشین را به عنوان کاری که تنها بر روی آن ماشین انجام میشود درنظر گرفته و سپس مسأله را به صورت برنامهریزی خطی فرموله و به وسیله الگوریتم ژنتیک حل کردند. لی[8] مسأله | − | را یررسی کرد. او در این تحقیق بیشتر به بررسی مسأله ماشینهای موازی یکسان با این فرض که حداقل یک ماشین همواره در دسترس و هر کدام از ماشینهای دیگر یک دوره در دسترس نباشند، پرداخت و نشان داد که الگوریتم طولانیترین زمان پردازش دارای خطای نسبی بزرگ حتی برای حالتی که تعداد ماشینها برابر 2 است، میباشد.
همچنین زمانی که تابع هدف مسأله مجموع وزنی زمانهای تکمیل کار بود، لی[8] نشان داد که این مسأله NP-hard بوده و یک الگوریتم برنامهریزی پویا را برای حل آن پیشنهاد داد. هوانگ و
چانگ[12] الگوریتم طولانیترین زمان پردازش را برای مسألهای که هر ماشین دارای یک بازه در دسترس نبودن باشد را با تابع هدف کمینه کردن دامنه عملیات بررسی کردند. بلازویچ و همکاران[14] مسألهای را با عملیات زمانبندی وقفهدار بر روی ماشینهای موازی در دسترس در بازههای مشخص با توابع هدف کمینه کردن دامنه عملیات بررسی کردند. آنها الگوهای دردسترس بودن را شبیه شیوه سانلاویل و اشمیت[9] طبقهبندی کردند. در آن تحقیق آنها نشان دادند مسأله با یک الگوی پلکانی از در دسترس بودن، به شدت NP-hard است.
لیائو و همکاران[4] مسأله 2| − | که یکی از ماشینها در بازههایی از زمان در دسترس نیست را بررسی کردند. آنها دوره در دسترس نبودن را به عنوان یک کار مجازی در نظر گرفته و سپس الگوریتم TMO را برای حل مسأله به کار بردند. لیائو وهمکاران[4] مسأله 2| − | که یکی از دو ماشین در طول دوره برنامهریزی در دسترس نیست را بررسی کردند. آنها مسأله را به 4 زیرمسأله تقسیم کردند و برای حل هر مسأله یک الگوریتم چندجملهای بهینه ارائه دادند. قربی و هائوری[1] مسأله را در نظر گرفته و یک الگوریتم شاخه و کران دقیق برای حل آن ارائه دادند. هوانگ و همکاران[13] الگوریتم
طولانیترین زمان پردازش را برای مسألهای که هر ماشین دارای یک بازه در دسترس نبودن باشد را با تابع هدف کمینه کردن دامنه عملیات بررسی کردند. لین و لیائو[3] مسأله 2| − | را در حالتی که هر دو ماشین در بازههای مشخصی از زمان در دسترس نبودند، بررسی کردند. آنها فرض کردند طول بازههای در دسترس نبودن یکسان است و براساس اینکه کمترین مقدار تابع هدف در کدامدوره رخ میدهد، مسأله را به موارد مختلفی تقسیمبندی کردند و الگوریتمی را بر مبنای جستجوی الفبایی برای حل بهینه هر بخش توسعه دادند.
-2 فرموله کردن مسأله
در این بخش برای مسأله زمانبندی ماشینهای موازی غیرمرتبط با در نظرگرفتن زمانهای آمادهسازی وابسته به توالی کارها و نوع ماشین، محدودیت دسترسی به ماشین و محدودیتهای قابلیت ماشین با تابع هدف کمینه کردن دامنهی عملیات، یک مدل MINLP ارائه میشود که به سادگی قابلیت خطیسازی داشته و با خطی کردن محدودیت 6، به یک مدل MIP تبدیل میشود. در این مدل برای در نظر گرفتن محدودیت دسترسی به ماشین از مفهوم کارهای مجازی استفاده میشود به این صورت که بازههای عدم دسترسی به ماشین به عنوان کارهای مجازی در نظر گرفته میشود که فقط بر روی آن ماشین پردازش میشوند و زمان پردازش این کارها برابر با مدت زمان در دسترس نبودن ماشین است بنابراین کارهای تخصیص یافته به هر ماشین باید در بین این کارهای مجازی پردازش شوند.
-1-2 نمادها
اندیسها :
i و j و : s اندیس مربوط به کار : k اندیس مربوط به ماشین
b و : l اندیس مربوط به بازههای در دسترس نبودن ماشین - کارهای مجازی - پارامترها :
: برابر یک است اگر ماشین k قابلیت پردازش کار i را دارد و در غیر این صورت صفر است. : زمان پردازش کار i بر روی ماشین k
: زمان در دسترس قرار گرفتن ماشین k ام
: زمان آمادهسازی کار j روی ماشین k اگر کار j بعد از کار i پردازش شود.
: زمان شروع کار مجازی b ام روی ماشین k ام - زمان شروع بازه عدم دسترسی b ام روی ماشین k ام - : زمان پایان کار مجازی b ام روی ماشین k ام - زمان پایان بازه عدم دسترسی b ام روی ماشین k ام -
