عنوان پایان‌نامه
ارایه الگوریتم برنامه ریزی پویا برای زمانبندی تک ماشین با فرض رذ کارها در فضای قطعی وفازی
- رشته تحصیلی
- مهندسی صنایع
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس 2 فنی شماره ثبت: 1898;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 47853
- تاریخ دفاع
- ۲۶ دی ۱۳۸۹
- دانشجو
- علیرضا شامخی امیری
- استاد راهنما
- فریبرز جولای
- چکیده
- در دو دهه گذشته، کارهای تحقیقاتی زیادی در مسائل مرتبط با زمانبندی ماشین ها انجام گرفته است. فرض کلاسیکی که در بسیاری از این تحقیقات وجود دارد این است که همه کارهای پیشنهادی حتما باید زمانبندی شوند. اگر چه در دنیای واقعی می‌توان مسئله را در سطح بالاتری حل کرد و آن اینکه تعدادی از کارهای پیشنهادی را "رد" و از فرآیند تصمیم گیری حذف کرد. به این معنی که تصمیم‌گیرنده با حذف بعضی از کارهای پیشنهادی، زیرمجموعه‌ای از کارها را به گونه ای زمانبندی کند که سود حاصل از اجرای آنها ماکزیمم شود. بدیهی است برای تصمیم‌گیری در مورد رد یا قبول یک کار، هزینه جریمه برای آن در نظر گرفته می‌شود. به این سطح تصمیم‌گیری در مسائل زمانبندی، زمانبندی به در نظر گرفتن رد کارها گفته می‌شود. در این پایان‌نامه دو سری از مسائل با فرض رد کارها مورد توجه قرار گرفته است: 1. مسائل زمان بندی تک-کاشین با فرض ردکارها با در نظر گرفتن فرض اثریادگیری: در این تحقیق، توابع هدف مختلفی برای زمانبندی تک-ماشین مورد بررسی قرار گرفت. برای هرکدام از شاخص‌های مورد بررسی ضمن بررسی پیچیدگی مسئله، الگوریتم برنامه ریزی پویای مناسب ارائه شده است. 2. مسئله زمان بندی تک-ماشین با فرض ردکارها در فضای فازی: برای این مسئله نیز یک الگوریتم برنامه ریزی پویا ارائه شده است. برای مناسب سازی الگوریتم برنامه ریزی پویا برای فضای فازی، دست به تعریف معیاری برای مقایسه اعداد فازی زدیم و از آن در ساختار الگوریتم بهره گرفته ایم. نوآوری ما در این تحقیق شامل اثبات سختی مسئله و ارائه الگوریتم برنامه‌ریزی پویای مناسب برای حل آن است. علت انتخاب الگوریتم برنامه‌ریزی پویا به جای برنامه‌ریزی ریاضی، امکانی است که این روش در بهره‌گیری از خواص برجستگی مسئله به ما می‌دهد. در این صورت می‌توانیم مسئله را در زمانی شبه‌چندجمله‌ای حل کنیم. در حل مسئله فازی نیز به ارائه مقیاسی مناسب برای مقایسه اعداد فازی و استفاده از آن در الگوریتم برنامه‌ریزی پویا دقت ویژه‌ای شده است.
- Abstract
- In last two decades, there are so many researches in the field of machine scheduling. A classic consideration in classic scheduling problems is that all proposed jobs are scheduled, which means that all proposed works should be done and rejection of the jobs is not allowed. Although maximum profit is not obtained when all jobs are done, and the manufacturer should decide about the works to done to obtain the maximum profit. Meanwhile, we assign a penalty cost for rejected jobs. This yields to a higher level of decision making. In this research, we focused on two series of problems: 1. Scheduling with learning effect and rejection: In this problem, various objective functions are evaluated. For each of them, NP-Hardness of them is proved and a suitable Dynamic Programming Algorithm is proposed. 2. Scheduling with rejection in fuzzy environment: A Fuzzy dynamic programming algorithm is proposed for this problem. Also, we defined a suitable criterion for comparing of fuzzy numbers and embed it in structure of algorithm. Our contribution in this research includes proof of NP-Hardness of the problems and proposing suitable dynamic programming approaches for all of them. The reason that the dynamic programming approach is preferred to classic mathematical programming is that we can apply the dominated properties of the problem in the algorithm. This would yield to a pseudo polynomial algorithm. Moreover, we had a special focus on developing a criterion for comparing fuzzy numbers and applying it in dynamic programming algorithm.
