کارشناسی ارشددانلود *71- دانلود ریسرچ

فهرست تصاویر
TOC h z t "فهرست اشکال,1" شکل ‏21: مساله معیاری برای 5 کار و 5 ماشین5
شکل ‏21: رابطه تقذم برای n کار25
شکل ‏22: مساله 3 کار26
شکل ‏23: نمونه اول زمانبندی26
شکل ‏24: نمونه ای دیگر از زمانبندی26
شکل ‏25: قاعده جانسون27
شکل ‏26: مساله 3 کار و 3 ماشین30
شکل ‏27: نمودار گانت بر طبق ماشین30
شکل ‏28: نمودار گانت بر اساس کار31
شکل ‏29: تکنیک بکار برده شده برای مسائل job shop31
شکل ‏210: دسته بندی استراتژی‌های جستجو39
شکل ‏211: مراحل کلی الگوریتمهای تکاملی40
شکل ‏212: نمایش کروموزوم به صورت درختی43
شکل ‏213: احتمال انتخاب در روش چرخ گردان46
شکل ‏214: احتمال انتخاب در روش رتبه بندی47
شکل ‏215: انتخاب مسابقه‌ای48
شکل ‏216: عملگر تبادل تک نقطه ای49
شکل ‏217: عملگر تبادل دو نقطه ای50
شکل ‏218: عملگر معکوس سازی51
شکل ‏219: عملگر حذف و کپی51
شکل ‏220: عملگر حذف و تولید مجدد52
شکل ‏221: مراحل الگوریتم GA-ACO57
شکل ‏222: عملگر مبتنی بر کار58
شکل ‏223: عملگر جهش شیفتی58
شکل ‏224: یک کروموزوم نمونه در الگوریتم GA-Fuzzy59
شکل ‏225: یک کروموزوم نمونه در الگوریتم HGA59
شکل ‏226: فلوچارت الگوریتم HGA60
شکل ‏227: یک کروموزوم نمونه در الگوریتم GADG61
شکل ‏31: فلوچارت الگوریتم پیشنهادی65
شکل ‏32: یک کروموزوم نمونه66
شکل ‏33: نگهداری ماشین وابسته به سن ماشین67
شکل ‏34: یک کروموزوم نمونه با در نظر گرفتن نگهداری ماشین68
شکل ‏35: نمودار گانت شکل 3-468
شکل ‏36: ایجاد جمعیت اولیه با استفاده از ویژگی چند جمعیتی69
شکل ‏37: عملگر تبادل دو نقطه ای72
شکل ‏38: عملگر تبادل تک نقطه ای73
شکل ‏39: عملگر تبادل چند نقطه ای74
شکل ‏310: عملگر جهش دو نقطه ای77
شکل ‏41: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 182
شکل ‏42: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 382
شکل ‏43: نمودار بهترین شایستگی الگوریتم ها برای داده تست 483
شکل ‏44: پراکندگی جمعیت اولیه برای داده تست 283
شکل ‏45: پراکندگی جمعیت اولیه برای داده تست 484

فصل اول مقدمه و کلیات تحقیقدر این فصل ابتدا مسئله مورد نظر بیان گردیده و ضرورت و اهداف را دنبال مینمایم در ادامه پرسشهای موجود در مسئله را بررسی مینمایم و فرضیههای تحقیق را شرح میدهم سپس نوآوریهای تحقیق را ارائه مینمایم در پایان واژههای کلیدی تعریف شده و ساختار پایان نامه ذکر خواهد شد.
مقدمهمسئله زمانبندی سیستم های باز یکی از مهمترین مسائل زمانبندی در دنیای مهندسی و صنعت است. در این مسئله m ماشین و n کار وجود دارد. هرکار شامل تعداد معینی از عملیات است. هر عملیات دارای زمان از پیش تعیین شده ای برای پردازش بر روی ماشین متناظر خود می باشد. ترتیب پردازش این عملیات در زمان به انجام رسیدن همه کارها بسیار تاثیر گذار است. بنابراین هدف از حل این مسئله پیدا کردن ترتیب عملیاتی است که با کمترین مدت زمانبندی قابل پردازش باشد. در این راستا مقالات زیادی با استفاده از الگوریتم های ابتکاری مختلف ارائه شده است که از بین آنها الگوریتم ژنتیک یکی از بهترین ها، شناخته شده است. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی با در نظر گرفتن پارامتر نگهداری ماشین ها بر پایه الگوریتم ژنتیک با ویژگی چند جمعیتی ارائه شده است. نتایج تجربی نشان می دهد الگوریتم ارائه شده به جواب بهینه تری دست پیدا میکند [77].
بیان مسئلهمسئله زمانبندی سیستم باز یک مسئله زمانبندی مهم و جهانی است و این مسئله به طور وسیع در صنعت کاربرد دارد. این مسئله جزء مسائل سخت است. این مسئله شبیه به مسئله زمانبندی مغازه کارها است با این تفاوت که در هر کار هیچ اولویتی بین فرایند یا عملیات هر کار وجود ندارد. در مسئله زمانبندی سیستم باز فضای راه حل به طور قابل ملاحظهای بزرگتر از مسئله زمان بندی مغازه کارها است و به نظر میرسد که در کتاب ها و مقالات به آن کمتر توجه شده است. شرح مسئله سیستم باز توسط گراهام و همکارانش بدین صورت باشد: یک تعداد کار به تعداد n (J1,J2, … , Jn) وجود دارد که روی یک سلسله ماشین به تعداد m (M1,M2, … , Mm) قابل پردازش است، هر کار متشکل از m عملیات می باشد (Oij). که j=1 to m و i=1 to n و هر کدام از عملیات باید روی یک ماشین متفاوت برای یک زمان مشخص شده پردازش شوند. عملیات هر کار می تواند در هر ماشینی پردازش شود ولی در هر زمان نهایتا یک عمل روی هر ماشین می تواند پردازش شود و یک عمل از هر کار می تواند در یک زمان پردازش شود [77 ، 1].
هدف مسئله زمانبندی سیستم باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده است که زمان کلی اتمام کارها در کمترین زمان ممکن باشد. در ادامه به بیان چندین مثال که جز مسائل سیستم باز می باشد می پردازیم:
تعمیر کردن هواپیماهای بزرگ، که نیاز به تعمیر موتور و سیستم الکتریکی را دارد. این دو وظیفه (عملیات) ممکن است در هر ترتیبی انجام شود ولی این غیر ممکن است که این دو کار را با هم انجام دهیم. یا در مثالی دیگر یک گاراژ اتومبیل بزرگ با فروشگاه های اختصاصی را در نظر بگیرید. یک وسیله نقلیه ممکن است به کار های زیر نیاز داشته باشد: تعمیر انباره لوله اگزوز، میزان کردن چرخ ها و تنظیم موتور که سه عمل از یک کار ممکن است به هر ترتیبی انجام شوند. به هر حال، مغازه های سیستم اگزوز، میزان کردن چرخ ها، و تنظیم موتور در ساختمان های مختلف هستند و بنابراین انجام دو عمل در یک زمان امکان پذیر نیست. در مسئله زمانبندی سیستم باز ما فرض می کنیم که چندین کار از این قبیل کار ها و چندین وسیله نقلیه که نیاز به تعمیر دارند را داریم، موارد دیگر می تواند شامل: کنترل کیفیت مرکزی، انتساب کلاس، معاینه فنی خودرو، مخابره ماهواره ای و بسیاری از موارد دیگر شود [3]. در زیر یک مثال حل شده OSSP را مشاهده می کنید:
در جدول هر کار شامل دقیقا یک عملکرد برای هر دستگاه می شود. این معیارها به طور کامل توسط یک مجموع منظم از زمان های پردازش m برای هر کار تعریف شده اند. برای مثال، جدول 1-1 یک مسئله معیاری 5*5 (5 کار و 5 ماشین) را نشان می دهد.
جدول STYLEREF 1 s ‏1 SEQ جدول * ARABIC s 1 1: مساله معیاری برای 5 کار و 5 ماشین
ماشین: 5 4 3 2 1
کار 1: 44 85 31 66 64
کار 2: 18 14 68 69 7
کار 3: 90 1 60 70 74
کار 4: 13 76 98 45 54
کار 5: 91 15 10 45 80
در مثال بالا عملکرد 4 از کار 1 بایستی به ماشین 4 برای 85 واحد از زمان پردازش برود و عملکرد 1 از کار 1 بایستی به ماشین 1 برای 64 واحد از زمان پردازش اختصاص یابد بدون هیچ محدودیتی در ترتیب آن که کدام کارها در چه زمانی پردازش شوند. مسئله، ایجاد یک راه حل معتبر با زمان کلی اتمام کارهای حداقل است. شکل 1-1 یک برنامه زمان کلی اتمام کار حداقل300 را برای معیارهای ارائه شده در جدول 1-1 را نشان می دهد.

شکل STYLEREF 1 s ‏1 SEQ شکل * ARABIC s 1 1: زمانبندی بهینه برای مساله معیاری 5*5
ضرورت تحقیقبا توجه به پیشرفت در محیط های تولید امروزی و افزایش سطح تولید و اهمیت سرعت در تولید که باعث کاهش هزینه ها و افزایش بهره وری خواهد شد نیاز به سیستم هایی که بتواند در کمترین زمان ممکن بهترین راه حل ها را در کمترین زمان برای اختصاص منابع تولیدی یا خدماتی به کارهایی که بایستی انجام شوند به شدت ضروری به نظر می رسد.
مساله زمانبندی سیستم باز از رده مسایل سخت است و برای حل این مساله از روشهای ابتکاری استفاده می شود. تاکنون روشهای ابتکاری زیادی برای حل مساله زمانبندی سیستم های باز توسعه یافتند [4].
اهداف تحقیقفرایند بهتر نمودن هر چیز را بهینه سازی میگویند. مسائلی مانند سیستم باز به دلیل بزرگ بودن فضای جستجو امکان استفاده از روشهای جستجوی معمول را ندارند. اعمال اینگونه تکنیکها برای حل چنین مسائلی گاهی به زمانی بیش از عمر یک انسان نیاز دارند. به همین دلیل تکنیکهای بهینه سازی با این ویژگی اصلی که هدف رسیدن به جواب بهینه یا نزدیک به جواب بهینه است، مطرح شدند. الگوریتم ژنتیک یکی از مناسبترین و کاربردیترین روشهای حل مسئله سیستم باز است.
در مساله سیستم باز می توان به دو صورت سیستم های زمانبندی را بهینه کرد. بهینه کردن زمان برای رسیدن به پاسخ بهینه در روشهای قبلی و یا بهینه تر کردن زمان کلی زمانبندی برای این مساله که ما در این مقاله به دنبال بهینه تر کردن زمانبندی این مساله هستیم.
نوآوری تحقیقهزینه‌های نگهداری و تعمیرات، در مجموع، بخش عمده‌ای از هزینه‌های تولید را در بر می‌گیرد. با توجه به نوع صنعت مورد بررسی، این هزینه چیزی حدود ۱۵ تا ۶۰ درصد هزینه محصول تولید شده را در بر می‌گیرد. تحقیقات نشان داده‌است که حدود ۳۳ سنت از هر دلار که برای فعالیت‌های نگهداری و تعمیرات هزینه می‌شود، مربوط به فعالیت‌های غیر ضروری در حوزه نگهداری و تعمیرات می‌باشد این در حالی است که صنایع آمریکا سالانه حدود ۲۰۰ میلیارد دلار برای نگهداری و تعمیرات تجهیزات خود هزینه می‌نمایند. این بدان معنی است که مدیریت صحیح فرآیند نگهداری و تعمیرات، سالانه ۶۰ میلیارد دلار صرفه جویی در این حوزه را به همراه خواهد داشت. ژاپنی‌ها با درک اهمیت ویژه‌ای که در مدیریت فرآیند نگهداری و تعمیرات در سیستم‌های تولیدی احساس می‌کردند، اقدام به طراحی سیستم‌های مختلف نگهداری و تعمیرات، از جمله نگهداری و تعمیرات بهره ور فراگیر نمودند و آن را به عنوان یکی از زیر سیستم‌های سه گانه تولید ناب به جهان معرفی نمودند.
پرسشهای اصلی تحقیقآیا به جواب های بهبود یافته برای مسئله سیستم باز لازم داریم؟
آیا نگهداری ماشین را در مسئله سیستم باز می توان در نظر گرفت؟
و اینکه آیا می توان در این مسئله به شکل هدفمند به جواب های بهتری رسید؟
فرضیه های تحقیقتعمیم تئوری بهینه‌سازی و تکنیک‌های فرمول‌بندی بخش بزرگی از ریاضیات کاربردی را شکل می‌دهد. تحقیق در عملیات، برنامه ریزی با اعداد صحیح و مختلط، مدل‌های شبکه‌ای، تئوری کنترل، برنامه‌ریزی غیرخطی، نظریه صف و برنامه ریزی پویا برخی شاخه‌های ریاضیات کاربردی مرتبط با بهینه‌سازی هستند که امروزه در مدیریت و اقتصاد کاربرد وسیعی دارند. بنابراین با توجه به نیازهای جدید و گاهی تغییر نیازها به هر چه نزدیکتر بودن جواب به جواب بهینه نیاز داریم.
در سطح تولید ماشین ها به نگهداری نیازمندند این مساله به طور مستقیم روی دسترس پذیری ماشین، نرخ تولید، نرخ استفاده و غیره تاثیر گذار است. اگر در زمانبندی مسئله سیستم باز نگهداری در نظر گرفته نشود در عمل ما دچار وقفه هایی می شویم که در نظر گرفته نشده اند بنابراین با در نظر گرفتن نگهداری در زمانبندی، قابلیت اطمینان سیستم افزایش می یابد. می توان با تنوع بخشیدن و جستجوی چند وجهی در کروموزومها در الگوریتم ژنتیک به شکل هدفمند به دنبال جواب های متقاعد کننده بود [73 ،74].
زمینه های کاربردیزمانبندی به عنوان یک فرآیند تصمیم سازی نقش مهمی در اکثر سیستم های ساخت و تولید و نیز اکثر محیط های پردازش اطلاعات بازی می کند. همچنین زمابندی در بسیاری از سیستم های حمل و نقل و توزیع و دیگر انواع صنایع خدماتی از اهمیت بسزایی برخوردار است. زمانبندی میتواند شامل بازه وسیعی از فعالیت ها باشد. روش های ساده ممکن است منجر به نتایج خوبی نشود و تحلیل گری که از تکنیک های دیگر آگاه نباشد ممکن است حتی تصور کند که روش های موجود میتوانند بهبود یابند. از طرف دیگر روش های پیچیده و ریاضی نیازمند دانش جامع و اساسی میباشند، بنابراین نمی توان چنین تخصصی را از هر فردی که کار زمانبندی را انجام می دهد، انتظار داشته باشیم. از آنجایی که اینگونه تکنیک ها به دلیل پیچیدگی و نیز دشواری ریاضیاتی اغلب در کسب و کار همچنان بلا استفاده مانده اند، برای مدیران داشتن اطمینان کافی به استفاده از این روشها جهت به کار گیری آنها و نیز اطمینان به نتایج آنها دشوار است. در ادامه مثالهایی به منظور بیان نمودن نقش زمانبندی در صنعت ارائه داده شده است.
تخصیص گیت در یک فرودگاهپایانه خط هوایی در یک فرودگاه بزرگ را در نظر بگیرید که روزانه صدها هواپیما در آن فرود آمده و یا از آن پرواز میکنند. گیت ها و هواپیماها مشابه نیستند. بعضی از این گیتها به گونهای هستند که هواپیماهای بزرگ به راحتی می توانند از آنها استفاده کنند. هواپیماها مطابق با زمانبندی معین بلند میشوند و فرود میآیند. البته زمانبندی تا حدودی تصادفی است که ممکن است مرتبط با آب و هوا یا ناشی از وقایع پیشبینی نشده در دیگر فرودگاه ها باشد. در مدتی که یک هواپیما، یک گیت را اشغال می کند، مسافرانی که میآیند باید منتظر بمانند، هواپیما باید سرویس شود و مسافران رسیده باید پیاده شوند. مدت زمان خروج زمانبندی شده می تواند به عنوان زمان تحویل در نطر گرفته شود و عملکرد فرودگاه بر طبق آن اندازه گیری شود. اگر از قبل مشخص شده باشد که هواپیما به دلیل ازدحام پیش بینی شده، در زمان ورود زمان بندی شده اش، نمی تواند در فرودگاه بعدی فرود بیاید، آنگاه هواپیما پرواز نمی کند. اگر به یک هواپیما اجازه بلند شدن داده نشود، طبق قواعد معمول مسافران به جای هواپیما در پایانه می مانند. اگر پروازی به تاخیر بیفتد هواپیما ممکن است برای مدت بیشتری در گیت باقی مانده و از استفاده سایر هواپیماها از آن گیت جلوگیری کند.
هدف زمانبندی، تخصیص هواپیماها به گیت ها به گونه ای است که در عین بهینه کردن تعدادی از اهداف، تخصیص ها از نظر عملی موجه باشند. این به معنی تخصیص هواپیماها به گیت های مناسب، که در زمان ورود مربوطه در دسترس هستند، است. اهداف شامل کمینه کردن کار پرسنل خط هوایی و تاخیرهای هواپیماها است. در چنین حالتی گیت ها، منابع و جابجایی و سرویس هواپیماها، فعالیت محسوب می شوند. ورود یک هواپیما به یک گیت نمایانگر زمان تکمیل فعالیت است.
زمانبندی در یک واحد پردازش مرکزیکارهای زمانبندی در یک واحد پردازش مرکزی یکی از وظایف سیستم عامل یک کامپیوتر چندکاره، زمانبندی زمانی است که واحد پردازش مرکزی به برنامه های مختلفی که باید اجرا شوند، اختصاص می دهد. زمان های پردازش دقیق معمولا از پیش معلوم نیستند. البته توزیع این زمان های پردازش تصادفی، ممکن است از پیش معلوم نباشد. البته توزیع این زمان های پردازش تصادفی، ممکن است از پیش معلوم باشد (شامل میانگین و واریانس زمان ها). به علاوه معمولا هر فعالیت سطح اولویت مشخصی دارد (سیستم عامل معمولا به کاربر اجازه می دهد تا سطح اولویت یا وزن هر فعالیت را مشخص کنند). در چنین حالتی، هدف کمینه کردن مجموع انتظاری زمان های تکمیل وزنی همه فعالیت ها است.
برای اجتناب از حالتی که فعالیت های نسبتا کوتاه برای فعالیت هایی که اولویت بالاتری دارند، مدت طولانی منتظر می مانند، سیستم عامل هر فعالیت را به بخش های کوچکی تقسیم می کند. سیستم عامل این بخش ها را در واحد پردازش مرکزی به گردش در می آورد، به طوری که در هر بازه زمانی مشخص، این واحد مدت زمانی را به هر فعالیت اختصاص می دهد. به این ترتیب اگر به طور اتفاقی زمان پردازش یک فعالیت خیلی کوتاه باشد، آن فعالیت قادر خواهد بود نسبتا سریع سیستم را ترک کند.
در اینجا هر وقفه در پردازش یک فعالیت به عنوان یک قطع کار در نظر گرفته می شود. واضح است که سیاست بهینه در چنین محیطی استفاده زیادی از این قطع کارها می کند. ممکن است آنقدر واضح نباشد که زمانبندی چه تاثیری روی اهداف مورد نظر دارد. آیا صرف وقت و انرژی جهت پیدا کردن یک زمانبندی خوب که به جای انتخاب یک زمانبندی تصادفی ایجاد شده منطقی بنظر میرسد؟ در عمل، اغلب معلوم می شود که انتخاب زمانبندی حقیقتا تاثیر بسزایی روی عملکرد سیستم دارد و صرف انرژی و زمان جهت یافتن یک زمانبندی مناسب منطقی است.
زمانبندی از نقطه نظر فنی و اجرا می تواند کاری بسیار سخت باشد. انواع مشکلاتی که زمانبندی از نظر فنی با آن مواجه است، مشابه با مشکلاتی است که در بهینه سازی ترکیبیاتی و مدل سازی تصادفی با آن ها روبرو هستیم. مشکلات اجرایی از نوع کاملا متفاوتی هستند. این مشکلات ممکن است به دقت مدلی که برای تحلیل مساله زمانبندی حقیقی از آن استفاده شده و نیز اعتبار داده های ورودی مورد نیاز بستگی داشته باشند.
زمانبندی در پالایشگاه نفتیک پالایشگاه نفت خام به اپراتورهای تمام وقت در روز و هفته نیاز داشته و ضروری است که با یک سیستم سه شیفته، که در آن اپراتورها همیشه حداقل دو روز متوالی تعطیلی دارند و هر سومین آخر هفته را تعطیل می باشند، کار کند. زمانبندی برای سه ماه در یک بازه زمانی بسط می یابد و لذا هر کارمند می تواند برای روزهای تعطیل و شیفت کاری برنامه ریزی کند. در واقع وجود یک برنامه زمانبندی شفاف و منصفانه برای کارکنان ضروری است.
کارخانه تولید پاکت کاغذیکارخانه ای که پاکت کاغذی برای سیمان، ذغال چوب، غذای حیوانات و ... تولید می کند را در نظر بگیرید. مواد اولیه برای چنین عملیاتی رول های کاغذ هستند. فرآیند تولید، شامل سه مرحله است: چاپ لگو، چسباندن لبه های کاغذ و دوختن یک یا هر دو انتهای پاکت. هر مرحله شامل تعدادی ماشین است که لزوما مشابه نیستند. ماشین ها در هر مرحله ممکن است از نظر سرعت عمل، تعداد رنگی که می توانند چاپ کنند یا اندازه پاکتی که می توانند تولید کنند، متفاوتند. هر سفارش تولید، در بر گیرنده مقدار معینی از یک پاکت خاص است که باید در موعد مقرر تولید و ارسال شوند. زمان فرآیند برای عملیاتهای مختلف، با اندازه سفارش متناسب است. تحویل دیرتر از موعد، جریمه ای به شکل از دست دادن اعتبار را در بر دارد که مقدار این جریمه به اهمیت سفارش یا مشتری و میزان تاخیر در تحویل بستگی دارد. یکی از اهداف سیستم زمانبندی به حداقل رساندن مجموع این جرائم است.
زمانی که تولید یک ماشین از یک نوع پاکت به نوع دیگر پاکت، تغییر می کند، به یک آماده سازی احتیاج دارد. طول زمان آماده سازی روی ماشین به شباهت های بین دو سفارش متوالی بستگی دارد (تعداد رنگ های مشترک، تفاوت در اندازه پاکت ها و ...). یک هدف مهم سیستم زمانبندی، به حداقل رساندن زمان کل صرف شده برای آماده سازی است.
کارخانه تولید تجهیزات لامپ های صنعتییک تولید کننده تجهیزات لامپ های صنعتی از خط مونتاژ کنترل شده ای به وسیله اپراتورها استفاده می کند. بر اساس تولید معمول که در راستای خط مونتاژ در جریان است، اپراتورها یک مجموعه تعریف شده از وظایف را دارا می باشند. برای هر تولید شرکت امیدوار به استفاده از زمانهای از پیش تعیین شده ای برای توسعه ایستگاه های کاری و تخصیص وظایف به این ایستگاه ها برای رسیدن به سطح تولید مناسب و کارایی مطلوب می باشد. حال این نکته مطرح است که خط مونتاژ چگونه می تواند برای تغییرات یا اصطلاحات تولید به منظور دست یابی به سطوح تولید مورد نظر و افزایش کارایی اصلاح شود.
سفارش هایی که به جایگاه تولید رسیده اند باید به کارهایی با موعد تحویل مربوطه تبدیل شوند. این کارها اغلب باید بر روی ماشین ها در قالب یک توالی از پیش تعیین شده پردازش شوند. هنگامی که کار هایی با اولویت بالا آماده پردازش در سیستم باشند و ماشین خاصی مشغول به کار باشد، با توجه به این نکته که کار های دارای اولویت بالا باید بلافاصله پردازش شوند، بریدگی در سیستم رخ خواهد داد. رویدادهای غیر قابل پیش بینی در کارگاه مانند خرابی ماشین و زمان های بیش از انتظار طولانی شده نیز باید مورد توجه قرار گیرد، به این سبب که می توانند تاثیر به سزایی بر روی زمانبندی داشته باشند. ایجاد زمانبندی دقیق کارهایی که قرار است پردازش شوند منجر به حفظ کارایی و کنترل عملیات می شود. کارگاه تنها قسمت تاثیر گذار بر روی فرآیند زمانبندی نمی باشد. در واقع، فرآیند زمانبندی تحت تاثیر فرآیند برنامه ریزی تولید قرار دارد که برنامه ریزی میان مدت تا بلند مدت را برای کل سازمان بر عهده دارد. هدف فرآیند برنامه ریزی تولید، بهینه کردن محصول کلی شرکت، تخصیص بلند مدت منابع بر اساس سطوح موجودی و پیش بینی تقاضا و نیازمندی های منابع است. تصمیماتی که در سطوح بالای برنامه ریزی گرفته می شوند به طور مستقیم بر فرآیند زمانبندی موثر می باشند [3].
اهمیت زمانبندی با معیارهای متمرکز بر دیرکرد از آن جهت مورد توجه است که در محیط کسب و کار حاضر، رقابت تولیدی از طریق قابلیت آن ها برای تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می شود. شرکت های تولیدی در تلاش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به هنگام، تکنولوژی گروهی و مدیریت کیفیت جامع به دست آورند. برای مثال، در سیستم های تولید به هنگام، کارها نباید زودتر و نه دیرتر تکمیل شوند، چرا که به هزینه های زودکرد و دیرکرد منجر می شود. در یک بازار رقابتی، دیر کرد کارها با توجه به موعد تحویل آن ها به عنوان یک مقیاس عملکرد بسیار مهم برای محیط های تولیدی متنوع، مطرح است. از دیگر زمینه های کاربردی الگوریتم پیشنهادی می توان به:
زمانبندی کارها در سیستم های چند پردازنده ای
زمانبندی تخلیه و بارگیری بار در بنادر
زمانبندی حرکت تاکسی های بی سیم در داخل شهر
زمانبندی سرویس به مشتری در فروشگاه های بزرگ
اشاره کرد.
تعریف کلمات کلیدیمسئله زمانبندی سیستمهای باز: در مباحث تئوریک علوم کامپیوتر مسئله زمانبندی سیستم باز یک مسئله زمانبندی می باشد که در آن یک مجموعه از کارها باید زمان مشخصی را در یک ایستگاه کاری (ماشین) دلخواه پردازش شود و هدف مشخص شدن زمان هایی است که هر تمامی کارها بایستی در هر ایستگاه کاری پردازش شود [77 ، 4].
الگوریتم ژنتیک: تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند. این الگوریتم برای اولین بار توسط جان هلند معرفی شد [77 ، 8 ، 19].
در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. مختصراً گفته می‌شود که الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند.مسئله‌ای که باید حل شود ورودی است و راه‌حلها طبق یک الگو کد گذاری می‌شوند که تابع شایستگی نام دارد هر راه حل کاندید را ارزیابی می‌کند که اکثر آنها به صورت تصادفی انتخاب می‌شوند.
نگهداری ماشین: عبارت استراتژی نگهداری و تعمیرات معمولاً به عنوان مجموعه خط مشی‌ها و مفاهیم نگهداری و تعمیرات تفسیر شده ‌است اما از دیدگاه کلان تر این خط مشی‌های نگهداری و تعمیرات و مفاهیم، یکی از چند مولفه اصلی استراتژی نگهداری و تعمیرات را شکل می‌دهند. سایر مولفه‌های ساختاری در تعریف استراتژی نگهداری و تعمیرات عبارت است از ظرفیت نگهداری و تعمیرات، تجهیزات و تسهیلات نگهداری و تعمیرات، تکنولوژی نگهداری و تعمیرات و یکپارچه سازی افقی. در ادبیات این حوزه، استراتژی نگهداری و تعمیرات، به عنوان یک الگوی منسجم و جدا نشدنی و یکپارچه ساز تصمیم‌ها در عناصر استراتژی‌های متفاوت در تجانس با تولید، شرکت و استراتژی‌های سطح کسب و کار معرفی می‌شود. استراتژی نگهداری و تعمیرات اهداف سازمان را آشکار می‌سازد و طبیعت کارکردهای اقتصادی و غیر اقتصادی را که قصد دارد برای سازمان به شکل یکپارچه انجام دهد، تعریف می‌کند. با این تفاسیر ارتباط میان کسب و کار و استراتژی‌های نگهداری و تعمیرات را از طریق چارچوب زنجیره ارزش معروف پورتر به خوبی می‌توان درک نمود [73].
زمان تکمیل کل کارها: در تولید اختلاف بین زمان شروع و پایان یک رشته کار یا وظیفه میباشد.
ساختار پایان نامهدر ادامه بحث در فصل دوم ادبیات و پیشینه تحقیق بیان شده و در فصل سوم روش تحقیق ارائه میگردد در ادامه در فصل چهارم محاصبات و یافته های تحقیق برای حل این مساله شرح داده شده، سرانجام در فصل پنجم نتیجه گیری و پیشنهادها بیان شده است.
فصل دوم ادبیات و پیشینه تحقیقمقدمه

هر چند در گذشته توجه کمتری نسبت به مسائل کارگاه باز شده اما به نظر می رسد، در سالهای اخیر، مسائل زمانبندی کارگاه باز مورد توجه محققان بسیاری قرار گرفته است. با این حال، مسائل کارگاه باز در مقایسه با سایر مسائل زمانبندی سهم بسیار کمی از ادبیات موضوع را به خود اختصاص داده اند. تمامی کارهای انجام شده در حقیقت تلاشی برای در نظر گرفتن ویژگی ها و شرایط واقعی در حوزه مسائل زمانبندی بوده است. در این پایان نامه قصد داریم تا مسائل زمانبندی در محیط کارگاه باز را مورد بررسی قرار دهیم و برای حل آن از روشهای فرا ابتکاری استفاده نماییم. در ادامه مروری بر تعاریف اولیه مسائل زمانبندی کرده و همچنین مطالبی در مورد معیارها و محدودیتهای موجود در مسائل زمانبندی سیستمهای باز را مورد تجزیه و تحلیل قرار میدهیم.
تعریف مربوط به زمانبندی
زمانبندی نوعی تصمیمگیری است و فرآیندی است که در جریان برنامه زمانی تعیین میشود. در واقع زمانبندی تخصیص منابع در طول زمان برای مجموعه ای از وظایف است. با توجه به این زاویه دید، بیشتر آموخته های ما در مورد زمانبندی را می توان در مورد تصمیم گیری های دیگر نیز به کار گرفت. زمانبندی مبحثی نظری است که مجموعه ای از اصول، مدل ها، روش ها و نتایج منطقی را در بر می گیرد و بینشی عمیق را در مورد برنامه تخصیص عملیات فراهم می آورد. زمانبندی به تخصیص منابع محدود به وظایف مورد انجام، در طی زمان می پردازد. زمانبندی فرآیند تصمیم گیری است که یک یا چند هدف بهینه سازی را شامل می شود. منابع و وظایف ممکن است صورت های مختلفی داشته باشند. منابع ممکن است ماشین ها در یک کارگاه، باند پرواز در یک فرودگاه، کارگردان در یک سایت ساخت وساز، واحدهای پردازش در محیط محاسباتی و غیره باشند. وظایف می توانند شامل یک عملیات فرآیند تولید، فرود یا بلند شدن در یک باند پرواز، مراحل مختلف موجود در یک پروژه ساخت، اجرای برنامه های کامپیوتری و غیره باشند. هر وظیفه می تواند سطوح اولویت متفاوتی داشته باشد مانند زودترین زمان ممکن برای شروع و یا بر اساس موعد تحویل و غیره. تابع هدف نیز می تواند به فرم های مختلفی باشد و یا در حالت دیگر، می تواند کمینه سازی تعداد کارهایی باشد که زمان اتمام کارها برای آخرین وظیفه باشد و یا در حالت دیگر، می تواند کمینه سازی تعداد کارهایی باشد که زمان اتمام آن ها بعد از موعد تحویل است. زمانبندی یک فرآیند تصمیم گیری است که در اکثر سیستم های ساخت و تولید و محیط های پردازش اطلاعات موجود است. همچنین، زمانبندی در حمل و نقل، برنامه زمانی توزیع و سایر صنایع خدماتی دارای کاربرد می باشد ]2،3[.
اگر بخواهیم تعریف دیگری از زمانبندی ارائه کنیم که در برگیرنده زوایای دیگری باشد، این تعریف می تواند به این گونه بیان شود که زمانبندی عمل تعیین اولویت ها و یا مرتب نمودن فعالیت ها برای برآورده نمودن الزامات مشخص، محدودیت ها و یا اهداف است. از آنجایی که همچنان زمان یک منبع محدودکننده می باشد، ما نیاز داریم تا به طور خودآگاه یا ناخودآگاه فعالیت هایمان را برای بهره برداری بهینه از این منبع محدود زمانبندی کنیم. با توسعه صنعتی، مساله محدودیت منابع بحرانی تر شده است. در حال حاضر ماشین ها، نیروی کار، تسهیلات نیز علاوه بر زمان به عنوان منابع بحرانی در فعالیت های تولیدی و خدماتی شناخته می شوند. زمانبندی این منابع به افزایش کارایی و بهره برداری از ظرفیت، کاهش زمان مورد نیاز برای تکمیل کارها و نهایتا افزایش سوددهی یک سازمان می انجامد. زمانبندی موثر منابعی همچون ماشین و نیروی انسانی، در محیط به شدت رقابتی امروز الزامی است.
در بیشتر موارد، عمل زمانبندی کارها پس از حل برخی مسائل مربوط به برنامه ریزی اصولی مورد توجه قرار می گیرد. باید همواره این نکته را مد نظر داشت که تصمیمات مربوط به زمانبندی اهمیت کمتری نسبت به مجموعه وسیع تری از تصمیمات مدیریتی دارند. برای مثال، در حل مسائل مربوط به ساخت، مسائل اساسی مدیریتی مربوط به انتخاب محصولی که باید ساخته شود و تعیین میزان تولید هر محصول اولویت دارد. بعد از به کارگیری بررسی بازار و تحلیل های اقتصادی برای حل این گونه مسائل، برنامه ریزی تکنولوژیکی بر روی این مساله که محصول چگونه باید ساخته شود متمرکز می شود. بعد از این که جواب این سوالات مربوط به برنامه ریزی داده شد و در دسترس بودن منابع نیز مورد بررسی قرار گرفت، آنگاه می توان به مسائل زمانبندی به طور مناسب توجه نمود. در واقع زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه می کند.
زمانبندی از دیدگاهی دیگرزمانبندی، تخصیص منابع درطول زمان برای مجموعه ای از وظایف است. این تعریف نسبتا کلی واژه، دو مفهوم مختلف دارد. اولا زمانبندی نوعی تصمیم گیری است و فرایندی است که در جریان آن برنامه زمانی را تعیین می کند. از این لحاظ بیشتر آموخته های ما در مورد زمانبندی را می توان در مورد تصمیم گیری های دیگر نیز بکار بست، لذا این مبحث ارزش علمی عام دارد. ثانیا زمانبندی مبحثی نظری است که مجموعه ای اصول، مدل ها، روش ها و نتایج منطقی را در برمی گیرد، که برای ما بینشی عمیق در مورد عمل زمانبندی به همراه دارد که می توان در مورد سایر نظریه ها به کار برد و بنابراین ارزش مفهومی عام دارد.
عناصر مهم مدلهای زمانبندی کارها و منابع اند. در نوشتار های مربوط به زمانبندی، منابع نوعا بر حسب قابلیت های کمی و کیفی خود مشخص می شوند، به طوری که هر مدل نشان دهنده نوع و میزان هر منبع است. هر کار مشخص بر حسب اطلاعاتی از قبیل منبع مورد نیاز، مدت انجام آن کار، زمانی که انجام آن را می توان شروع کرد و زمان تحویل توصیف می شود. به علاوه مجموعه ای از کارها بعضا می توان بر حسب محدودیت های تکنولوژیکی (روابط تقدمی) که در مورد عناصر متشکله آن صدق می کند بیان کرد [17].
تئوری زمانبندی همچنین شامل شیوه های متنوع و مختلف است که در حل مسائل زمانبندی مفید واقع می شود. در واقع، حوزه زمانبندی به صورت نقطه کانونی ایجاد، بکارگیری و ارزیابی روش های ترکیبی ، شیوه های شبیه سازی، روش های شبکه ای و رویکرد های ابتکاری حل مسائل در آمده است. انتخاب شیوه مناسب به پیچیدگی مساله، طبیعت مدل و انتخاب معیار کارایی و عوامل دیگر بستگی دارد. در خیلی از حالات بهتر است چند شیوه به عنوان گزینه های مختلف برخورد به مساله در نظر گرفته شود. به همین دلیل نظریه زمانبندی شاید به همان اندازه که به امر بررسی روشها بپردازد به بررسی مدل ها نیز توجه دارد [18].
برای رده بندی مدل های عمده زمانبندی لازم است ترکیب منابع و رفتار کارها مشخص شود. برای نمونه یک مدل ممکن است یک یا چند نوع منبع داشته باشد. اگر یک نوع منبع داشته باشد کارهای مربوطه احتمالا یک مرحله ای است، در حالی که اگر چند منبع داشته باشد کارها معمولا چند مرحله ای انجام می شود و در هر دو حالت منابع را می توان به صورت یک مجموعه واحد یا موازی در نظر گرفت. به علاوه، اگر مجموعه کارهای در دسترس برای زمانبندی در طول زمان تغییر نکند سیستم، ایستا نامیده می شود، در مقابل اگر یک کار جدید به مجموعه کارها در طول زمان افزده شود سیستم پویا نامیده می شود.
نظریه زمانبندینظریه زمانبندی اصولا با مدل های ریاضی سر وکار دارد و بین کار زمانبندی و توسعه مدلهای زمانبندی رابطه برقرار می نماید و به طور پیوسته آن ها را با مسائل نظری و عملی زمانبندی محک می زند.
در این زمینه دیدگاه نظری اغلب به صورت رویکردی کمی است و سعی آن، دست یافتن به ساختار مساله در قالب شکل فشرده ریاضی است. این رویکرد کمی با تفسیر اهداف تصمیم گیری در قالب یک تابع هدف صریح و بیان موانع تصمیم گیری به صورت محدودیت های صریح شروع میشود. حل هر مسئله زمانبندی برابر پاسخگویی به این دو سوال است :
کدام منبع برای انجام هر وظیفه تخصیص داده خواهد شد ؟
هر وظیفه در چه وقت انجام خواهد شد ؟
به عبارت دیگر، وظیفه ی اصلی مسائل زمانبندی به تصمیم گیری در مورد تخصیص منابع و توالی عملیات منحصر می شود. تئوری زمانبندی شامل شیوه های متنوع و مختلفی است که در حل مسائل زمانبندی مفید واقع گردد. در واقع حوزه زمانبندی، به یک نقطه کانونی برای ایجاد، به کارکیری و ارزیابی روش های حل مسائل تبدیل شده است. این روش ها عبارتند از: رویکردهای ترکیبی، شیوه های شبیه سازی، روش های شبکه ای و رویکردهای ابتکاری. انتخاب شیوه مناسب به پیچیدگی مساله، طبیعت مدل، انتخاب معیار کارایی و عوامل مرتبط دیگر بستگی دارد [39،40].
مروری بر مدل های زمانبندی
عملکرد سیستم های تولیدی و خدماتی با معیارهای بسیاری مانند تعداد ماشین ها، سطح اتوماسیون، ویژگی های مربوط به ساختار مورد نظر، نوع سیستم حمل و نقل و غیره تعیین می شود. تفاوت در این معیارها تعداد بسیار زیادی از مدلی های زمانبندی را به وجود می آورد. پارامترهایی که در زیر بیان می شوند در طول این فصل مورد استفاده قرار خواهند گرفت.
چارچوب و نمادها
تعداد کارها برابر با n و تعداد ماشین ها برابر با m در نظر گرفته شده است. اندیس های i وj به کارهای i ام و j ام اشاره دارند و اندیس هایk و l به ماشین های k و l اشاره دارند. پارامترهای زیر مرتبط با کار i ام می باشند:
زمان پردازش(Pik) : بیان کننده مدت زمانی است که کار i ام باید بر روی ماشین k ام سپری کند.
زمان آماده به کار بودن (ri) : زمانی که کار i وارد سیستم می شود و به عبارت دیگر زود ترین زمانی که پردازش کار i می تواند آغاز شود.
موعد تحویل (di) : زمانی است که در آن، کار طبق قرار قبلی باید به مشتری تحویل داده شود. تکمیل کار بعد از موعد تحوید با جریمه همراه خواهد بود.
وزن (wi) : وزن کار بیان کننده اولویت آن می باشد. وزن کار در حقیقت بیان کننده میزان اهمیت آن در ارتباط با دیگر کارها در سیستم می باشد. درحالی که می تواند مشخص کننده هزینه نگهداری کار در سیستم نیز باشد. داده های اشاره شده از نوع ایستا می باشند به این معنی که به زمانبندی بستگی ندارند. نقطه مقابل داده های دینامیک هستند که از قبل مشخص نبوده و وابسته به زمانبندی می باشند.
زمان تکمیل کار (Cik) : مدت زمانی است که کار i بر روی ماشین k تکمیل شده است.
ترکیب ماشین ها (محیط های کار)مدل های زمانبندی معمولا از طریق ترکیب ماشین ها، محدودیت ها و توابع هدف مشخص می شوند. پارامترهای متعددی در تعریف مسائل زمانبندی و طبقه بندی آن ها مطرح هستند. از این رو لازم است که ابتدا پارامترهایی را که به نوعی در طبقه بندی مسائل دخیل هستند، مشخص نماییم. در ذیل فهرستی از این پارامترها گرد آوری شده اند.
تابع هدف (مانند حداقل کردن زمان اتمام کل کارها، حداقل کردن حداکثر زمان دیرکردها)
زمان های آماده سازی (وابسته یا مستقل از توالی عملیات)
افق برنامه ریزی (کوتاه مدت – بلند مدت – میان مدت )
تعداد مراحل تولید (یک مرحله ای - چند مرحله ای)
روش تولید(سری - مونتاژ -کلی)
محدودیت ظرفیت یا منابع (محدود- نامحدود)
تعداد و شرح تقاضای هر یک از محصولات
نرخ تقاضا (یکنواخت - پویا و احتمالی)
کمبود موجودی (قابل جبران، غیر قابل جبران)
هزینه نگهداری و متغیر تولید
متغیر تصمیم گیری (تعیین زمان شروع عملیات)
مسائل زمانبندی را به کمک سه پارامتر α | β | γ دسته بندی می کنند . پارامتر α نشان دهنده محیط های کار و یا ترکیب ماشین ها است. پارامتر β بیان کننده محدودیت های مربوط به کارهاست و پارامتر γ نشان دهنده معیارهای بهینگی و اهداف مساله می باشد. در جدول ذیل برخی از محیط های کار در مسائل زمانبندی به ازای پارامتر α نشان داده شده است.
جدول STYLEREF 1 s ‏2 SEQ جدول * ARABIC s 1 1: نمایش برخی از محیط های مختلف کار در مسائل زمانبندی با پارامتر αمحبط زمانبندی کارها پارامنر α
مساله تک ماشینه 1
مساله ماشین های موازی با m ماشین P m
مساله گردش ماشین با m ماشین F m
مساله کار کارگاهی با m ماشین J m
مساله کارگاه باز با m ماشین  O m
مدل های تک ماشینه
در این مسائل تنها یک ماشین موجود است و کارها نیاز به دریافت خدمت از این ماشین دارند. در هر زمان یک کار به وسیله ماشین پردازش می شود. هر کار یک زمان پردازش و یک موعد تحویل دارد و ممکن است مشخصه های دیگری مانند اولویت، بریدگی و یا زمان حمل نیز در این مساله مطرح باشد. همچنین ممکن است یک تابع جریمه برای کارهایی که از موعد تحویل انحراف دارند، در مدل مورد استفاده قرار بگیرد. در این مسائل متداول ترین هدف ، ترتیب دهی کارها روی ماشین به منظور حداقل کردن جریمه دیر کرد است. سیستم های تولیدی بسیاری از نوع سیستم های تولیدی تک ماشینه می باشند. به عنوان مثال، اگر در محیطی که شامل چندین ماشین است، گلوگاهی رخ دهد آنگاه توالی کارها در گلوگاه به طور کلی بیان کننده عملکرد کلی سیستم خواهد بود. در این حالت تمامی عملیات پس از زمانبندی گلوگاه زمانبندی خواهند شد. چنین رویکردی دلالت بر در نظر گرفتن مساله اصلی به صورت مساله تک ماشین دارد. مدل های تک ماشین همچنین در رویکرد های تجزیه کاربرد دارند که در آن مسائل زمانبندی در محیط های پیچیده به چندین مساله زمانبندی تک ماشین تبدیل می شوند. مدل های تک ماشین با محدودیت ها و توابع هدف مختلفی در نظرگرفته شده اند. نتایج به دست آمده منجر به ایجاد مجموعه ای از قواعد گردیده است که نتیجه آن ها ایجاد جواب بهینه در محیط های تک ماشینه می باشد. برای مثال قانون زود ترین موعد تحویل که کارها را به ترتیب صعودی موعد تحویل زمانبندی می کند منجر به حداقل شدن حداکثر دیرکرد در میان تمام کارها می شود. قانون کمترین زمان پردازش که کارها را به ترتیب صعودی زمان پردازش زمانبندی می کند منجر به حداقل شدن تعداد کارهای در انتظار پردازش می شود.
مدل های ماشین موازی
در این مدل ها تعدادی ماشین مشابه در دسترس بوده و کارها می تواند روی هر کدام از آن ها پردازش شود. کارها می توانند بین خود وابستگی داشته باشند، به این معنی که در یک توالی، کار بعدی نمی تواند پردازش شود مگر آن که کار قبلی کاملا پردازش شده باشد. هدف این مسائل میتواند کمینه سازی حداکثر زمان تکمیل کارها باشد. ماشین های موازی تعمیمی بر مدل های تک ماشین می باشند. بسیاری از محیط های تولیدی از چندین مرحله یا مرکز کاری تشکیل شده اند درحالی که هر یک از آن ها دارای چندین ماشین به صورت موازی می باشند. ماشین های موجود در یک مرکز کاری می توانند یکسان باشند. در این حالت هر لحظه که کار وارد سیستم شود امکان پردازش آن بر روی هر یک از ماشین های در دسترس فراهم خواهد بود. مدل های ماشین های موازی نیز مانند مدل های تک ماشین از این جهت دارای اهمیت می باشند که اگر در سیستم های تولید چند مرحله ای یک مرکز کاری خاص به صورت گلوگاه عملی کند، آنگاه زمانبندی در مرکز کاری مورد نظر تعیین کننده عملکرد کلی سیستم خواهد بود. در این صورت گلوگاه می تواند به صورت مجموعه ای از ماشین های موازی در نظر گرفته شده و به تنهایی به صورت یک مساله مجزا مورد تجزیه و تحلیل قرارگرفته شود. در بعضی از موارد ماشین های موازی ممکن است یکسان نباشند. در واقع در این حالت برخی از ماشین ها قدیمی تر از بقیه هستند و با سرعت پایین تری عمل می کنند و یا ممکن است ماشینی بهتر نگهداری شده باشد و بتواند کار را باکیفیت بالاتری انجام دهد. در این صورت برخی از کارها ممکن است بر روی هر یک از m ماشین موازی پردازش شوند درحالی که بقیه ممکن است تنها بر روی مجموعه خاصی از m ماشین پردازش کردند.
مدل های جریان کارگاهی
در این مدل ها کارها روی چندین ماشین در یک توالی یکسان پردازش می شوند. زمان پردازش هر کار روی هر ماشین ممکن است متفاوت باشد. هدف می تواند حداقل کردن زمان مورد نیاز برای تکمیل همه کارها باشد که حداکثر زمان تکمیل کارها (زمان ساخت) نامیده می شود. در بسیاری از محیط های تولیدی یا مونتاژ، کارها دارای چندین عملیات می باشند که معمولا باید بر روی چندین ماشین مختلف پردازش شوند. اگر مسیر همه کارها یکسان باشد (یعنی همه کارها ماشینهای یکسانی را در ترتیب یکسانی بازدید کنند)، چنین محیطی به عنوان محیط جریان کارگاهی در نظر گرفته می شود. در این محیط ماشین ها پشت سرهم قرارگرفته اند و هنگامی که زمان پردازش کاری بر روی ماشین خاصی تکمیل می شود وارد صف ماشین بعدی می گردد. ترتیب کارها از ماشینی به ماشین دیگر ممکن است متفاوت باشد به این سبب که کارها میان ماشین ها ممکن است دوباره مرتب شوند. با این وجود، اگر سیستم حمل ونقل مواد، کارها را از یک ماشین به ماشین بعدی منتقل کند، در این صورت توالی یکسانی از کارها در کل سیستم برقرار خواهد بود. در برخی از سیستم های جریان کارگاهی، هنگامی که کاری به پردازش بر روی ماشین خاصی نیاز نداشته باشد، از ماشین مورد نظر عبور کرده و جلوتر از کارهایی که پردازش شده اند و یا منتظر پردازش در آن مرحله هستند قرار می گیرد. برخی از سیستم های جریان کارگاهی در چنین حالتی امکان عبور کردن کار از ماشین را نمی دهند. مدل جریان کارگاهی انعطاف پذیر تعمیمی بر مدل جریان کارگاهی میباشد که از چندین مرحله به صورت سری تشکیل شده و هر مرحله دارای تعدادی ماشین به صورت موازی می باشد. کارها در هر مرحله بر روی یکی از ماشین های موازی پردازش می شوند.
این مسئله یک مدل چند ماشینی است که به صورت سری در یک کارگاه وجود دارند. فرض سری بودن ماشین آلات ، به دنبال خود فرض چند مرحله ای بودن کار ها را ایجاب می کند. این نکته بدین معناست که بین هر کار و هر یک از عملیات تشکیل دهنده فرآیند آن تفاوت قائل شویم [46،47].
کار ها به صورت مجموعه ای از عملیات در نظر گرفته می شود که ساختار تقدمی خاص دارد، به ویژه هر یک از عملیات به جز مورد اول دقیقا یک مورد عملیات مقدم مستقیم و هر یک از عملیات بجز مورد آخر دقیقا یک مورد فعالیت موخر مستقیم دارد . این رابطه تقدم برای کار i در شکل 2-1 نشان داده شده است.
475488020320im
00im
40316151949450033870901949450024739601949450096202519494500213995020320I2
00I2
62801520320i1
00i1

شکل STYLEREF 1 s ‏2 SEQ شکل * ARABIC s 1 1: رابطه تقذم برای n کارمسائل جریان کارگاهی یک کلاس مشخص از مسائل زمانبندی کارگاهی هستند . که در آن n کار (i=1,..,n) وجود دارد که باید به شرح زیر روی m ماشین انجام شوند (j=1,…,m). کار A عبارت است از m عمل ، j امین عمل از هر کار باید روی ماشین j پردازش شود و زمان پردازش Pij را دارا می باشد . کار A می تواند فقط روی ماشین j شروع شود اگر عمل های آن روی ماشین (j-1) تکمیل شده باشند و اگر ماشین j بیکار باشد. زمان تکمیل شدن کار i، هنگامی است که زمان آخرین عمل Ci تکمیل شود. این مسئله در مقالات (مجلات) مشخص شده است و به صورت α|β|γ ثبت است . یک مثال از Flow Shop با سه کار و با داده های به شرح زیر را در شکل2-2 مشاهده می کنید :
شکل STYLEREF 1 s ‏2 SEQ شکل * ARABIC s 1 2: مساله 3 کارشکل 2-3 و شکل 2-4 دو زمانبندی امکان پذیر را برای این مثال نشان می دهند . ملاحظه میکنید که هر دو زمانبندی ترتیبی از کارهای مختلف بر روی ماشین ها هستند . برای مورد اول ما Cmax=9 و 18=Ci∑ را داریم . در مورد دوم ما Cmax=8 و Ci=21∑ را داریم. ملاحظه می کنید که در نمونه اول Ci∑ نسبت به Cmax بهتر است در حالی که این در نمونه دوم بر عکس می باشد. این مثال به این نکته اشاره دارد که اسباب خیلی زیاد به تابع هدف وابسطه اند.
شکل STYLEREF 1 s ‏2 SEQ شکل * ARABIC s 1 3: نمونه اول زمانبندی شکل STYLEREF 1 s ‏2 SEQ شکل * ARABIC s 1 4: نمونه ای دیگر از زمانبندیدر برخی از مقالات با کمی تغییر در مساله جریان کارگاهی تعاریف دیگری نیز مطرح شده، در ادامه به ارائه یکی از این تعاریف می پردازیم:
در ساخت و مونتاژ وسائل زیادی، تعدادی از عملیات در هر کار باید انجام شود. اغلب این عملیات باید در همه کارها به همان ترتیب که اشاره شده پردازش شوند. این ماشین های فرضی به صورت سری تنظیم شده اند، و محیط به عنوان جریان کارگاهی ارجاع داده شده است. با فرض زمانبندی مسائل جریان کارگاهی کلاسیک که هر کار فقط یک بار هر ماشین را ملاقات می کند گاهی اوقات در عمل نقض شده است. یک نمونه جدید از کارگاه صنعتی ، کار بازگشتی است که کار ماشین های معین را بیش از یک بار ملاقات می کند .
در شکل 2-5 قاعده جانسون برای مسئله Flow shop را مشاهده می کنید:
شکل STYLEREF 1 s ‏2 SEQ شکل * ARABIC s 1 5: قاعده جانسونمدل های کار کارگاهی
یکی از پر کاربردترین سیستم های تولیدی است که دارای کاربردهای فراوانی در دنیای واقعی است. ماشین های مختلفی در کارگاه وجود دارند و یک کار ممکن است نیاز به چندین یا همه ماشینها با توالی خاصی داشته باشد. تنها محدودیتی که در این مدل ها وجود دارد این است که یک کار نمی تواند بیش از یک بار از ماشین استفاده کند. هدف این مدل ها می تواند کمینه سازی حداکثر زمان تکمیل کارها یا حداقل جریمه دیرکرد باشد. در کارگاه های چند عملیاتی، کارها اغلب دارای مسیرهای مختلفی می باشند. چنین محیطی بیان کننده کار کارگاهی می باشد که در واقع تعمیمی از مدل جریان کارگاهی است. در حقیقت مدل جریان کارگاهی مدل کار کارگاهی است که در آن هر کار مسیر یکسانی دارد. ساده ترین مدل کارگاهی فرض می کند که هر کار حداکثر یک بار بر روی ماشین خاصی پردازش می شود. درحالی که در مدل هایی ممکن است که یک کار چند بار در مسیرش در طول سیستم بر روی ماشینی خاص پردازش شود. چنین محیطهایی مقید به گردش کاری مجدد هستند که به طور قابل ملاحظه ای پیچیدگی مدل را افزایش میدهند. تعمیمی از مدل کار کارگاهی مدل کار کارگاهی انعطاف پذیر است که برای پردازش کارها دارای چندین ماشین به صورت موازی می باشد.
مساله زمانبندی کار کارگاهی یکی از مشهورتر ین و پیچیده ترین مسایل زمانبندی است که پیداکردن جو اب بهینه برای آن از مرتبه سخت است . هدف مسائل برنامه ریزی کارگاهی تخصیص m ایستگاه به n کار می باشد. در اینجا سه دیدیگاه سنتی برای حل این نوع از مسایل وجود دارد: قانون اولویت ، بهینه سازی ترکیبی و تحلیل با محدودیت. کارگاه یک سیستم تولیدی با ظرفیت تولید محصول با تعداد متغیر کار و زمان فعالیت متفاوت برای هر کار است .فعالیت متفاوت در محصول و ایستگاه نیازمند پردازش هر مرحله از تولید می باشد که پیداکردن زمانبندی مناسب اغلب خیلی سخت است. روش های حل سنتی معمولا مساله را در مقیاس کوچک و پارامتر های مشخص و قطعی حل می کنند .صنعت امروزی فارغ از قطعیت و خواص محصولات غیر قابل پیش بینی است. متغییر های غیر قطعی و محدودیت های ناشی از آن در حل مبتنی به نگاه سنتی وجود ندارند.
مسله زمانبندی کار کارگاهی با مجموعه ای از کارها J={J1,J2,…,Jn} و مجموعه ای از منابع R={R1,R2,…,Rn} نمایش داده می شود. هر کار Ji شامل مجموعه ای از فعالیت ها T={T1,T2,…,Tn} که باید بین زمان آماده و زمان انجام انجام شوند. انجام هر فعالیت Ti نیازمند استفاده از مجموعه منابعR (Rki) در فاصله زمانی (dUki) می باشد. زمان شروع stki برای فعالیت Tki از موقعی است که شروع به استفاده از منابع Rki بکند [42،43،44،45].
به بیان دیگری از مسئله زمانبندی کار کارگاهی از دیدگاه محققین دیگر می پردازیم، آنها در ارائه تعریفی از مسله زمانبندی کار کارگاهی کلاسیک ایستا و معمولی که n کار و m ماشین را شامل میشوند ضوابط و محدودیت های ذیل را مطرح کردند:
هیچ ماشینی نمی تواند بیش از یک کار را در یک زمان انجام دهد.
هر کار توسط هر ماشین فقط یک مرتبه ویزیت می شود. یعنی دوبار ویزیت نمی شود.
هر ماشین فقط یک مدل از کارها را می تواند انجام دهد.
سیستم نمی تواند مقطوع باشد زیرا هر عملیات از هر کار حتما بایستی اتمام یابد.
هیچ ماشینی نمی تواند یک کار را متوقف کند و کار دیگری را شروع کند قبل از آنکه کار قبلی به پایان برسد.
قبلا زمان پردازش برای هر عملیات Oji در ماشین مخصوص m با Tjim مشخص شده است، در اینجا j و i ایندکس هایی از کارها و عملیات ها هستند.
از قبل ترتیبی از ماشین ها برای هر کار بایستی محیا شود.
ماشین ها در هر زمان قابل دسترس می باشند.

Related posts: