بخشی از مقاله
چکیده
یکی از مسائل مهم در بحث زمانبندی، مساله کارگاه باز می باشد. این مساله به دلیل دارا بودن فضای جستجوی گسترده از رده مسائل سخت می باشد. تاکنون الگوریتم های مختلفی برای حل این مساله پیشنهاد شده است. در این تحقیق برای حل مساله زمانبندی کارگاه باز از ترکیب الگوریتم ژنتیک و الگوریتم جستجوی گرانشی استفاده شده است. برای نشان دادن کارایی، سنجش بر روی داده های استاندارد صورت گرفته و الگوریتم پیشنهادی با الگوریتم ژنتیک مقایسه شده است. نتایج تجربی نشان می دهد الگوریتم پیشنهادی در همه موارد جواب بهتری داده است.
-1 مقدمه
زمانبندی موثر و مناسب منابع، استفاده درست از منابع و در نتیجه افزایش کارایی را به دنبال دارد. یکی از مسائل زمانبندی، کارگاه باز است، کارگاه باز شامل n کار و m ماشین است و هر کار نیز از m عملیات تشکیل شده که باید در ماشین متناظر خود اجرا شود. کارگاه باز به دلیل داشتن فضای پاسخ گسترده از جمله مسائل سخت است. جهت حل مسائل کارگاه باز محققین الگوریتم های مختلفی ارائه نمودند.
- Gonzalez and Sahni,1976 - مسئله زمانبندی سیستم باز را ابتدا در سال 1976 به عنوان مدلی برای کاربردهای جهان واقعی مطرح کردند. آنها الگوریتم زمانی خطی برای دو ماشین به صورت مسئله زمانبندی قطعی و غیر قطعی ارائه داده اند. - Pinedo,1995 - یک قانون ساده دیگری از توزیع را بنام longest Atternate processing Time - LAPT - ارائه داد که این مسئله را برای دو ماشین در زمان چند جمله ای حل می کند. همچنین نشان داد که برایM>=3 مسئله زمانبندی سیستم باز، NP کامل می باشد. - Liaw and Chen , 2005 - مساله زمانبندی کارگاه باز دو ماشینه و بدون زمان توقف و انتظار را با هدف کمینه سازی زمان تکمیل کل برنامه مورد بررسی قرار دادند.
- Senthilkumar and Shahabudeen , 2006 - الگوریتم ژنتیکی را برای مساله زمانبندی کارگاه باز با هدف کمینه سازی زمان تکمیل کل برنامه، توسعه دادند. - Sha and Hsu , 2008 - یک الگوریتم انبوه ذرات جدید را برای مساله زمانبندی کارگاه باز با هدف کمینه سازی زمان تکمیل کل برنامه ارائه دادند. - Andresen et al, 2008 - الگوریتمی بر مبنای شبیه سازی تبرید و الگوریتم ژنتیک برای کمینه سازی میانگین زمان جریان ساخت در مساله زمانبندی کارگاه باز ارائه نمودند.
- Seraj and Tavakkoli-Moghaddam , 2009 - یک مدل ریاضی برنامه ریزی عدد صحیح مختلط دو هدفه برای مسئله زمانبندی در محیط کارگاه باز ارائه داده اند که هدف آن کاهش میانگین دیرکرد کارها و میانگین زمان تکمیل کارها است. - Naderi et al, 2011 - مدلی مبتنی بر زمان آماده سازی وابسته برای مسئله کار گاه باز ارایه داده اند که موتور جستجوی محلی استفاده شده برای حل این مسئله SA بوده است.
- Barzegar et al, 2012 - به حل مسئله کارگاه باز با استفاده از یک الگوریتم ژنتیک ترکیبی به منظور کاهش حداکثر زمان تکمیل کار پرداخته اند. - Ghoonodi, 2015 - به حل مساله زمانبندی کارگاه باز با استفاده از الگوریتم ژنتیک پرداخت. در این مقاله الگوریتمی ترکیبی بر مبنای الگوریتم ژنتیک و الگوریتم جستجوی گرانشی برای زمانبندی کارگاه باز با هدف کاهش حداکثر زمان تکمیل کارها ارائه شده است مسأله زمانبندی سیستم های باز شامل m ماشین و n کار است.
هر کار شامل m عملیات است که باید در ماشین متناظر خود اجرا شود. هر ماشین میتواند حداکثر یک عمل را در یک زمان پردازش کند و هر کار می تواند حداکثر به وسیله یک ماشین در هر زمان پردازش شود. همچنین در زمانبندی سیستمهای باز ترتیب پردازش عملیات کارها مهم نیست. مثال: جدول1 یک سیستم تولید باز نمونه 3*3 را نشان میدهد به عبارت دیگر در این سیستم 3 کار وجود دارد که هر کار دارای 3 عملیات است بنابراین در این سیستم 3 ماشین وجود دارد.
در سیستم نمونه جدول 1 عملیات1 از کار 1 بایستی در ماشین1 به مدت 7 واحد زمانی پردازش شود و عملیات2 از کار 1 باید در ماشین 2 به مدت 2 واحد زمانی پردازش شود. در مساله زمانبندی سیستمهای باز هدف ایجاد یک برنامه زمانبندی برای انجام تمام عملیات کارها به نحوی است که زمان انجام کل عملیات کارها حداقل شود. شکل 1 نمودار گانت یک زمانبندی امکان پذیر را برای سیستم نمونه جدول 1 نشان می دهد.
