عنوان پایان‌نامه
زمانتندی کارهای رو به زوال
- رشته تحصیلی
- مهندسی سیستم های اقتصادی - اجتماعی
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس 2 فنی شماره ثبت: 1469;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 39978
- تاریخ دفاع
- ۲۹ بهمن ۱۳۷۸
- دانشجو
- جلیل لایق
- استاد راهنما
- محسن صادق عمل نیک, فریبرز جولای
- چکیده
- در این پایان نامه دو مدل از مسائل زمانبندی کارهای رو به زوال در نظر گرفته شده است. تابع هدف هر دو مدل کمینه کردن مجموع وزنی زمان تکمیل می باشد. همچنین اثباتی برای NP-hard بودن هر دو مدل وجود دارد. در مدل اول زمان پردازش تابع افزایشی خطی از زمان شروع فرایند می باشد. در حیطه زمانبندی مدل اول را به صورت نشان می دهند. برای حل این مدل چندین الگوریتم ممتیکی ارائه شده است، که با آنالیز واریانس بهترین آنها انتخاب شده است. و در انتها الگوریتم پیشنهادی با بهترین الگوریتم موجود مقایسه شده است. در مدل دوم زمان پردازش یک تابع پله ای از زمان شروع فرایند می باشد. بر خلاف مدل قبلی در این مدل زمان تحویل کار مطرح می باشد و در تمامی کارها زمان تحویل یکسان می باشد. شیوه نمایش این مدل به صورت می باشد. جهت حل این مدل پیچیده یک الگوریتم ممتیک پیشنهاد شده است. در فصل اول پایان نامه مطالبی جهت آشنایی کلی با مسائل زمانبندی آورده شده است. در فصل دوم شرحی از مسائل زمانبندی رو به زوال به همراه مرور ادبیات گفته شده است. از آنجا که حل مسائل در این پژوهش به کمک الگوریتم ممتیک می باشد، در فصل سوم توضیحات از الگوریتم ممتیک مخصوصاً کاربرد آن در مسائل زمانبندی آورده شده است. توسعه مدل در فصول چهارم و پنجم آمده است. این دو فصل به گونه ای نگارش شده اند که به صورت مستقل قابل بررسی باشد، به عبارت دیگر تعاریف مورد نیاز هر فصل در فصل مربوطه گفته شده است. فصل ششم هم نتیجه گیری و پیشنهاداتی برای پژوهش های آینده می باشد.
- Abstract
- In this thesis, we consider two cases of deteriorating scheduling problems. Goal functions of both are minimizing total weighted completion time. Also there are two proofs which both of them are NP-hard. In a first case, Jobs processing times is increasing linear function of start times. In the field of scheduling; shows the first case. We present some new dominance properties for this NP-hard problem, and then a memetic algorithm which using these properties is developed. The results of computational experiments show the good performance of the proposed algorithm. And at the end, we compare our algorithm with the best existing heuristic algorithm. In the second model, we consider minimizing total weighted completion time criteria on a single machine. Jobs processing times is step function of its starting time and a due date that is common to all jobs. In the field of scheduling; shows the second case. We present some new dominance properties for this NP-hard problem, and then a memetic algorithm which using these properties is developed. We compared the solutions of the memetic algorithm with optimal solutions obtained from complete enumeration. In the first section some general information about scheduling is presented. In section two the literature review and deterioration scheduling problems are described. Because our problems are solved by memetic algorithm, the memetic algorithm and its usage in the field of scheduling is described in section three. Model extensions are explained in the section four and five. The conclusions are in section six.
