کار ۳:

۹۰

۱

۶۰

۷۰

۷۴

کار ۴:

۱۳

۷۶

۹۸

۴۵

۵۴

کار ۵:

۹۱

۱۵

۱۰

۴۵

۸۰

در مثال بالا عملکرد ۴ از کار ۱ بایستی به ماشین ۴ برای ۸۵ واحد از زمان پردازش برود و عملکرد ۱ از کار ۱ بایستی به ماشین ۱ برای ۶۴ واحد از زمان پردازش اختصاص یابد بدون هیچ محدودیتی در ترتیب آن که کدام کارها در چه زمانی پردازش شوند. مسئله، ایجاد یک راه حل معتبر با زمان کلی اتمام کارهای حداقل است. شکل ۱-۱ یک برنامه زمان کلی اتمام کار حداقل۳۰۰ را برای معیارهای ارائه شده در جدول ۱-۱ را نشان می دهد.

شکل ‏۱‑۱: زمانبندی بهینه برای مساله معیاری ۵*۵
ضرورت تحقیق
با توجه به پیشرفت در محیط های تولید امروزی و افزایش سطح تولید و اهمیت سرعت در تولید که باعث کاهش هزینه ها و افزایش بهره وری خواهد شد نیاز به سیستم هایی که بتواند در کمترین زمان ممکن بهترین راه حل ها را در کمترین زمان برای اختصاص منابع تولیدی یا خدماتی به کارهایی که بایستی انجام شوند به شدت ضروری به نظر می رسد.
مساله زمانبندی سیستم باز از رده مسایل سخت^[۱۲] است و برای حل این مساله از روش های ابتکاری استفاده می شود. تاکنون روش های ابتکاری زیادی برای حل مساله زمانبندی سیستم های باز توسعه یافتند [۴].
اهداف تحقیق
فرایند بهتر نمودن هر چیز را بهینه سازی^[۱۳] می­گویند. مسائلی مانند سیستم باز به دلیل بزرگ بودن فضای جستجو امکان استفاده از روش های جستجوی معمول را ندارند. اعمال اینگونه تکنیکها برای حل چنین مسائلی گاهی به زمانی بیش از عمر یک انسان نیاز دارند. به همین دلیل تکنیکهای بهینه سازی با این ویژگی اصلی که هدف رسیدن به جواب بهینه یا نزدیک به جواب بهینه است، مطرح شدند. الگوریتم ژنتیک یکی از مناسب­ترین و کاربردی­ترین روش های حل مسئله سیستم باز است.
در مساله سیستم باز می توان به دو صورت سیستم های زمانبندی را بهینه کرد. بهینه کردن زمان برای رسیدن به پاسخ بهینه در روش های قبلی و یا بهینه تر کردن زمان کلی زمانبندی برای این مساله که ما در این مقاله به دنبال بهینه تر کردن زمانبندی این مساله هستیم.
نوآوری تحقیق
هزینه‌های نگهداری و تعمیرات، در مجموع، بخش عمده‌ای از هزینه‌های تولید را در بر می‌گیرد. با توجه به نوع صنعت مورد بررسی، این هزینه چیزی حدود ۱۵ تا ۶۰ درصد هزینه محصول تولید شده را در بر می‌گیرد. تحقیقات نشان داده‌است که حدود ۳۳ سنت از هر دلار که برای فعالیت‌های نگهداری و تعمیرات هزینه می‌شود، مربوط به فعالیت‌های غیر ضروری در حوزه نگهداری و تعمیرات می‌باشد این در حالی است که صنایع آمریکا سالانه حدود ۲۰۰ میلیارد دلار برای نگهداری و تعمیرات تجهیزات خود هزینه می‌نمایند. این بدان معنی است که مدیریت صحیح فرایند نگهداری و تعمیرات، سالانه ۶۰ میلیارد دلار صرفه جویی در این حوزه را به همراه خواهد داشت. ژاپنی‌ها با درک اهمیت ویژه‌ای که در مدیریت فرایند نگهداری و تعمیرات در سیستم‌های تولیدی احساس می‌کردند، اقدام به طراحی سیستم‌های مختلف نگهداری و تعمیرات، از جمله نگهداری و تعمیرات بهره ور فراگیر^[۱۴] نمودند و آن را به عنوان یکی از زیر سیستم‌های سه گانه تولید ناب به جهان معرفی نمودند.
پرسشهای اصلی تحقیق

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

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

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

فرضیه های تحقیق
تعمیم تئوری بهینه‌سازی و تکنیک‌های فرمول‌بندی بخش بزرگی از ریاضیات کاربردی را شکل می‌دهد. تحقیق در عملیات، برنامه ریزی با اعداد صحیح و مختلط، مدل‌های شبکه‌ای، تئوری کنترل، برنامه‌ریزی غیرخطی، نظریه صف و برنامه ریزی پویا برخی شاخه‌های ریاضیات کاربردی مرتبط با بهینه‌سازی هستند که امروزه در مدیریت و اقتصاد کاربرد وسیعی دارند. بنابراین با توجه به نیازهای جدید و گاهی تغییر نیازها به هر چه نزدیکتر بودن جواب به جواب بهینه نیاز داریم.
در سطح تولید ماشین ها به نگهداری نیازمندند این مساله به طور مستقیم روی دسترس پذیری ماشین، نرخ تولید، نرخ استفاده و غیره تاثیر گذار است. اگر در زمانبندی مسئله سیستم باز نگهداری در نظر گرفته نشود در عمل ما دچار وقفه هایی می شویم که در نظر گرفته نشده اند بنابراین با در نظر گرفتن نگهداری در زمانبندی، قابلیت اطمینان سیستم افزایش می یابد. می توان با تنوع بخشیدن و جستجوی چند وجهی در کروموزوم­ها در الگوریتم ژنتیک به شکل هدفمند به دنبال جواب های متقاعد کننده بود [۷۳ ،۷۴].
زمینه های کاربردی
زمانبندی به عنوان یک فرایند تصمیم سازی^[۱۵] نقش مهمی در اکثر سیستم های ساخت و تولید و نیز اکثر محیط های پردازش اطلاعات بازی می کند. همچنین زمابندی در بسیاری از سیستم های حمل و نقل و توزیع و دیگر انواع صنایع خدماتی از اهمیت بسزایی برخوردار است. زمانبندی می ­تواند شامل بازه وسیعی از فعالیت ها باشد. روش های ساده ممکن است منجر به نتایج خوبی نشود و تحلیل گری که از تکنیک های دیگر آگاه نباشد ممکن است حتی تصور کند که روش های موجود می­توانند بهبود یابند. از طرف دیگر روش های پیچیده و ریاضی نیازمند دانش جامع و اساسی می­باشند، بنابراین نمی توان چنین تخصصی را از هر فردی که کار زمانبندی را انجام می دهد، انتظار داشته باشیم. از آنجایی که اینگونه تکنیک ها به دلیل پیچیدگی و نیز دشواری ریاضیاتی اغلب در کسب و کار همچنان بلا استفاده مانده اند، برای مدیران داشتن اطمینان کافی به استفاده از این روش­ها جهت به کار گیری آن­ها و نیز اطمینان به نتایج آن­ها دشوار است. در ادامه مثال­هایی به منظور بیان نمودن نقش زمان­بندی در صنعت ارائه داده شده است.
تخصیص گیت در یک فرودگاه
پایانه خط هوایی در یک فرودگاه بزرگ را در نظر بگیرید که روزانه صدها هواپیما در آن فرود آمده و یا از آن پرواز می­ کنند. گیت ها و هواپیماها مشابه نیستند. بعضی از این گیت­ها به گونه ­ای هستند که هواپیماهای بزرگ به راحتی می توانند از آن­ها استفاده کنند. هواپیماها مطابق با زمانبندی معین بلند می­شوند و فرود می­آیند. البته زمانبندی تا حدودی تصادفی است که ممکن است مرتبط با آب و هوا یا ناشی از وقایع پیش ­بینی نشده در دیگر فرودگاه ها باشد. در مدتی که یک هواپیما، یک گیت را اشغال می کند، مسافرانی که می­آیند باید منتظر بمانند، هواپیما باید سرویس شود و مسافران رسیده باید پیاده شوند. مدت زمان خروج زمانبندی شده می تواند به عنوان زمان تحویل در نطر گرفته شود و عملکرد فرودگاه بر طبق آن اندازه گیری شود. اگر از قبل مشخص شده باشد که هواپیما به دلیل ازدحام پیش بینی شده، در زمان ورود زمان بندی شده اش، نمی تواند در فرودگاه بعدی فرود بیاید، آنگاه هواپیما پرواز نمی کند. اگر به یک هواپیما اجازه بلند شدن داده نشود، طبق قواعد معمول مسافران به جای هواپیما در پایانه می مانند. اگر پروازی به تاخیر بیفتد هواپیما ممکن است برای مدت بیشتری در گیت باقی مانده و از استفاده سایر هواپیماها از آن گیت جلوگیری کند.
هدف زمانبندی، تخصیص هواپیماها به گیت ها به گونه ای است که در عین بهینه کردن تعدادی از اهداف، تخصیص ها از نظر عملی موجه باشند. این به معنی تخصیص هواپیماها به گیت های مناسب، که در زمان ورود مربوطه در دسترس هستند، است. اهداف شامل کمینه کردن کار پرسنل خط هوایی و تاخیرهای هواپیماها است. در چنین حالتی گیت ها، منابع و جابجایی و سرویس هواپیماها، فعالیت محسوب می شوند. ورود یک هواپیما به یک گیت نمایانگر زمان تکمیل فعالیت است.
زمانبندی در یک واحد پردازش مرکزی
کارهای زمانبندی در یک واحد پردازش مرکزی^[۱۶] یکی از وظایف سیستم عامل یک کامپیوتر چندکاره، زمانبندی زمانی است که واحد پردازش مرکزی به برنامه های مختلفی که باید اجرا شوند، اختصاص می دهد. زمان های پردازش دقیق معمولا از پیش معلوم نیستند. البته توزیع این زمان های پردازش تصادفی، ممکن است از پیش معلوم نباشد. البته توزیع این زمان های پردازش تصادفی، ممکن است از پیش معلوم باشد (شامل میانگین و واریانس زمان ها). به علاوه معمولا هر فعالیت سطح اولویت مشخصی دارد (سیستم عامل معمولا به کاربر اجازه می دهد تا سطح اولویت یا وزن هر فعالیت را مشخص کنند). در چنین حالتی، هدف کمینه کردن مجموع انتظاری زمان های تکمیل وزنی همه فعالیت ها است.
برای اجتناب از حالتی که فعالیت های نسبتا کوتاه برای فعالیت هایی که اولویت بالاتری دارند، مدت طولانی منتظر می مانند، سیستم عامل هر فعالیت را به بخش های کوچکی تقسیم می کند. سیستم عامل این بخش ها را در واحد پردازش مرکزی به گردش در می آورد، به طوری که در هر بازه زمانی مشخص، این واحد مدت زمانی را به هر فعالیت اختصاص می دهد. به این ترتیب اگر به طور اتفاقی زمان پردازش یک فعالیت خیلی کوتاه باشد، آن فعالیت قادر خواهد بود نسبتا سریع سیستم را ترک کند.
در اینجا هر وقفه در پردازش یک فعالیت به عنوان یک قطع کار^[۱۷] در نظر گرفته می شود. واضح است که سیاست بهینه در چنین محیطی استفاده زیادی از این قطع کارها می کند. ممکن است آنقدر واضح نباشد که زمانبندی چه تاثیری روی اهداف مورد نظر دارد. آیا صرف وقت و انرژی جهت پیدا کردن یک زمانبندی خوب که به جای انتخاب یک زمانبندی تصادفی ایجاد شده منطقی بنظر می­رسد؟ در عمل، اغلب معلوم می شود که انتخاب زمانبندی حقیقتا تاثیر بسزایی روی عملکرد سیستم دارد و صرف انرژی و زمان جهت یافتن یک زمانبندی مناسب منطقی است.
زمانبندی از نقطه نظر فنی و اجرا می تواند کاری بسیار سخت باشد. انواع مشکلاتی که زمانبندی از نظر فنی با آن مواجه است، مشابه با مشکلاتی است که در بهینه سازی ترکیبیاتی^[۱۸] و مدل سازی تصادفی با آن ها روبرو هستیم. مشکلات اجرایی از نوع کاملا متفاوتی هستند. این مشکلات ممکن است به دقت مدلی که برای تحلیل مساله زمانبندی حقیقی از آن استفاده شده و نیز اعتبار داده های ورودی مورد نیاز بستگی داشته باشند.
زمانبندی در پالایشگاه نفت
یک پالایشگاه نفت خام به اپراتورهای تمام وقت در روز و هفته نیاز داشته و ضروری است که با یک سیستم سه شیفته، که در آن اپراتورها همیشه حداقل دو روز متوالی تعطیلی دارند و هر سومین آخر هفته را تعطیل می باشند، کار کند. زمانبندی برای سه ماه در یک بازه زمانی بسط می یابد و لذا هر کارمند می تواند برای روزهای تعطیل و شیفت کاری برنامه ریزی کند. در واقع وجود یک برنامه زمانبندی شفاف و منصفانه برای کارکنان ضروری است.