عنوان پایان‌نامه
کمیته سازی همزمان مجموع وزن دار دیرکردها و میزان مصرف انرژی در مسئله زمان بندی کارگاه مرحله ای انعطاف پذیر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: 3150;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 72345
- تاریخ دفاع
- ۲۹ دی ۱۳۹۴
- دانشجو
- محدثه عباس زاده
- استاد راهنما
- محمد مهدی نصیری خونساری
- چکیده
- در میان مسائل زمانبندی، کارگاه مرحله‌ای به‌عنوان یکی از تعمیم‌های کارگاه مخلوط تعریف می‌شود. در این نوع از کارگاه‌ها هر کار شامل مراحلی است که باید با توجه به یک برنامه از پیش تعیین‌شده از تمامی آن‌ها عبور کند و هر یک از این مراحل شامل عمل‌هایی است که هریک به هر ترتیب نسبی دلخواهی می‌توانند مورد پردازش قرار گیرند. درواقع اگر به هر مرحله این مسئله به‌صورت مجزا نگاه کنیم مسئله‌ای از نوع کارگاه باز خواهیم داشت و اگر در هر مرحله فقط یک عملیات وجود داشته باشد با یک مسئله کار کارگاهی روبه‌رو خواهیم بود. یک کارگاه انعطاف‌پذیر نیز شامل بخش‌های متفاوتی است که حداقل دریکی از این بخش‌ها دو ماشین یا بیشتر وجود داشته باشند به‌طوری‌که عمل یکسانی را بر روی کارها انجام دهند. با توجه به اینکه، مسئله زمانبندی مرحله‌ای منعطف یک مدل جدید از مسئله زمانبندی ماشین‌های موازی است، تاکنون توسعه خاصی بر روی مدل مسئله و همچنین روش های حل آن انجام نشده است. در این تحقیق، مسئله زمانبندی مرحله‌ای منعطف با دو هدف کمینه کردن میزان مصرف انرژی و کمینه کردن مجموع دیرکردهای عملیات مورد بررسی قرارگرفته است. در این مسئله روابط پیش نیازی به‌صورت پایان-شروع با تأخیر زمانی صفر در نظر گرفته‌شده است. همچنین، فعالیت ها قابلیت انقطاع ندارند و زمانی که آغاز می شوند تا زمان خاتمه ادامه می یابند، هر کار به چند مرحله تقسیم شده است و در هر مرحله چندین عملیات قرار دارند. با توجه به اینکه اهداف پروژه دارای تناقض هستند، مسئله زمانبندی مرحله‌ای منعطف دارای یک جواب مشخص نخواهد بود بلکه دارای یک مجموعه از جواب است که هرکدام می توانند جواب مسئله محسوب شوند. به دلیل پیچیدگی مسئله ذکرشده، برای حل مسئله، دو الگوریتم بهینه سازی چند هدفه الگوریتم ژنتیک مرتب‌سازی نامغلوب-2 و الگوریتم تکاملی مبتنی بر قوت پارتو-2 مورداستفاده قرار گرفته است. با توجه به اینکه مسئله دارای دو هدف می‌باشد، برای مقایسه و ارزیابی نتایج به‌دست‌آمده از الگوریتم ها از پنج معیار ارزیابی استفاده‌شده است. مقایسه نتایج به‌دست‌آمده از حل 15 مسئله با اندازه های کوچک، متوسط و بزرگ نشان داده‌خواهد شد. واژه‌های کلیدی: زمانبندی، کارگاه مرحله‌ای انعطاف پذیر، چند هدفه، الگوریتم ژنتیک مرتب‌سازی نامغلوب-2، الگوریتم تکاملی مبتنی بر قوت پارتو-2
- Abstract
- the stage shop problem is defined as a generalization of the mixed shop and a special case of the general shop problem. In a stage shop, each job has several stages of operations. A stage is a subset of operations of a job that can be processed in any arbitrary relative order. If a stage includes all operations of a job, the job is like an open shop job in the mixed shop problem. The stages of a job (like the operations of a job in a job shop) should be processed in a predetermined order. Therefore, if each stage of a job includes only one operation, the job is like a job shop job in a mixed shop problem. A flexible shop includes different parts that at least in two of these parts two or more machines exist which do the same oprations on the jobs. As the flexible stage shop problem is a new model of parallel machines scheduling problems, there hasn’t been any special extention on it or on the methods of its solvations. In this research, a flexible stage shop with two objects of minimization of energy consumption and minimization of total weighted tardiness has been considered. In this problem prerequisite relatives has been assumed as finish-start with zero delay time, there is no opration which can be stopped, and all oprations will be continued from the strat to finish. Each job will be divided in to the different stages and there will be different oprations in each stage. As the objects of the project are in contradiction, the flexible stage shop problem doesn’t have a significate answer, it will have a set of answers that each of them can be counted as the final answer. For complexity of the problem, two multi-objective optimization algorithems NSGA-II and SPEA-II have been used. As the problem have two objects, for comparison and evaluation of the achived answers from the algorithems, five evaluation criterias have been used. The comparison of the achived answers will be shown from the solvation of the fifteen problems with small, medium, and large sizes. Keywords: scheduling, flexible stage shop, multi-objective, NSGA-II, SPEA-II
