مسئله زمانبندی سیستم های باز یکی از مهمترین مسائل زمانبندی در دنیای مهندسی و صنعت است. در این مسئله m ماشین و n کار وجود دارد. هرکار شامل تعداد معینی از عملیات است. هر عملیات دارای زمان از پیش تعیین شده ای برای پردازش[1] بر روی ماشین متناظر خود می باشد. ترتیب پردازش این عملیات در زمان به انجام رسیدن همه کارها بسیار تاثیر گذار است. بنابراین هدف از حل این مسئله پیدا کردن ترتیب عملیاتی است که با  کمترین مدت زمانبندی قابل پردازش باشد. در این راستا مقالات زیادی با استفاده از الگوریتم های ابتکاری[2] مختلف ارائه شده است که از بین آنها الگوریتم ژنتیک[3] یکی از بهترین ها، شناخته شده است. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی با در نظر گرفتن پارامتر نگهداری ماشین[4] ها بر پایه الگوریتم ژنتیک با ویژگی چند جمعیتی ارائه شده است. نتایج تجربی نشان می­ دهد­ الگوریتم ارائه شده به جواب بهینه تری دست پیدا می­کند [77].

1-2   بیان مسئله

هدف مسئله زمانبندی سیستم باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده است که زمان کلی اتمام کارها در کمترین زمان ممکن باشد. در ادامه به بیان چندین مثال که جز مسائل  سیستم باز می باشد می پردازیم:

تعمیر کردن هواپیماهای بزرگ، که نیاز به تعمیر موتور و سیستم الکتریکی را دارد. این دو وظیفه (عملیات) ممکن است در هر ترتیبی انجام شود ولی این غیر ممکن است که این دو کار را با هم انجام دهیم. یا در مثالی دیگر یک گاراژ اتومبیل بزرگ با فروشگاه های اختصاصی را در نظر بگیرید. یک وسیله نقلیه ممکن است به کار های زیر نیاز داشته باشد: تعمیر انباره لوله اگزوز، میزان کردن چرخ ها و تنظیم موتور که سه عمل از یک کار ممکن است به هر ترتیبی انجام شوند. به هر حال، مغازه های سیستم اگزوز، میزان کردن چرخ ها، و تنظیم موتور در ساختمان های مختلف هستند و بنابراین انجام دو عمل در یک زمان امکان پذیر نیست. در مسئله زمانبندی سیستم باز ما فرض می کنیم که چندین کار از این قبیل کار ها و چندین وسیله نقلیه که نیاز به تعمیر دارند را داریم، موارد دیگر می تواند شامل: کنترل کیفیت مرکزی، انتساب کلاس، معاینه فنی خودرو، مخابره ماهواره ای و بسیاری از موارد دیگر شود [3].

در زیر یک مثال حل شده OSSP را مشاهده می کنید:

در جدول هر کار شامل دقیقا یک عملکرد  برای هر دستگاه می شود. این معیارها به طور کامل توسط یک مجموع منظم از زمان های پردازش m برای هر کار تعریف شده اند. برای مثال، جدول  1-1 یک مسئله معیاری 5*5 (5 کار و 5 ماشین) را نشان می دهد.

1-1   ضرورت تحقیق

با توجه به پیشرفت در محیط های تولید امروزی و افزایش سطح تولید و اهمیت سرعت در تولید که باعث کاهش هزینه ها و افزایش بهره وری خواهد شد نیاز به سیستم هایی که بتواند در کمترین زمان ممکن بهترین راه حل ها را در کمترین زمان برای اختصاص منابع تولیدی یا خدماتی به کارهایی که بایستی انجام شوند به شدت ضروری به نظر می رسد.

خرید متن کامل این پایان نامه در سایت nefo.ir

مساله زمانبندی سیستم باز از رده مسایل سخت[1] است و برای حل این مساله از روشهای ابتکاری استفاده می شود. تاکنون روشهای ابتکاری زیادی برای حل مساله زمانبندی سیستم های باز توسعه یافتند [4].

1-2   اهداف تحقیق

فرایند بهتر نمودن هر چیز را بهینه سازی می­گویند. مسائلی مانند سیستم باز به دلیل بزرگ بودن فضای جستجو امکان استفاده از روشهای جستجوی معمول را ندارند. اعمال اینگونه تکنیکها برای حل چنین مسائلی گاهی به زمانی بیش از عمر یک انسان نیاز دارند. به همین دلیل تکنیکهای بهینه سازی با این ویژگی اصلی که هدف رسیدن به جواب بهینه یا نزدیک به جواب بهینه است، مطرح شدند. الگوریتم ژنتیک یکی از مناسب­ترین و کاربردی­ترین روشهای حل مسئله سیستم باز است.

در مساله سیستم باز می توان به دو صورت سیستم های زمانبندی را بهینه کرد. بهینه کردن زمان برای رسیدن به پاسخ بهینه در روشهای قبلی و یا بهینه تر کردن زمان کلی زمانبندی برای این مساله که ما در این مقاله به دنبال بهینه تر کردن زمانبندی این مساله هستیم.

1-3   نوآوری تحقیق

1-4   پرسشهای اصلی تحقیق

• آیا به جواب های بهبود یافته برای مسئله سیستم باز لازم داریم؟

• آیا نگهداری ماشین را در مسئله سیستم باز می توان در نظر گرفت؟

• و اینکه آیا می توان در این مسئله به شکل هدفمند به جواب های بهتری رسید؟

1-5   فرضیه های تحقیق

تعمیم تئوری بهینه‌سازی و تکنیک‌های فرمول‌بندی بخش بزرگی از ریاضیات کاربردی را شکل می‌دهد. تحقیق در عملیات، برنامه ریزی با اعداد صحیح و مختلط، مدل‌های شبکه‌ای، تئوری کنترل، برنامه‌ریزی غیرخطی، نظریه صف و برنامه ریزی پویا برخی شاخه‌های ریاضیات کاربردی مرتبط با بهینه‌سازی هستند که امروزه در مدیریت و اقتصاد کاربرد وسیعی دارند. بنابراین با توجه به نیازهای جدید و گاهی تغییر نیازها به هر چه نزدیکتر بودن جواب به جواب بهینه نیاز داریم.

در سطح تولید ماشین ها به نگهداری نیازمندند این مساله به طور مستقیم روی دسترس پذیری ماشین، نرخ تولید، نرخ استفاده و غیره تاثیر گذار است. اگر در زمانبندی مسئله سیستم باز نگهداری در نظر گرفته نشود در عمل ما دچار وقفه هایی می شویم که در نظر گرفته نشده اند بنابراین با در نظر گرفتن نگهداری در زمانبندی، قابلیت اطمینان سیستم افزایش می یابد. می توان با تنوع بخشیدن و جستجوی چند وجهی در کروموزوم­ها در الگوریتم ژنتیک به شکل هدفمند به دنبال جواب های متقاعد کننده بود .

1-6   زمینه های کاربردی