عنوان پایان‌نامه
به کارگیری داده کاوه برای حل مساله زمانبندی کار کارگاهی کلاسیک با تابع هدف فاصله زمانی ساخت
- رشته تحصیلی
- MBA- مدیریت عملیات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: 2889;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 67198
- تاریخ دفاع
- ۰۱ بهمن ۱۳۹۳
- دانشجو
- صادق ثالثی موسی آبادی
- استاد راهنما
- محمد مهدی نصیری خونساری
- چکیده
- مساله زمانبندی کار کارگاهی کلاسیک در زمره سخت‌ترین مسائل بهینه‌سازی طبقه‌بندی می‌شود و به همین خاطر حل این‌گونه مسائل علاقه بسیاری از محققان را به خود جلب کرده است. امروزه روش‌ها و الگوریتم‌های متنوعی برای حل مسائل کار کارگاهی ایجادشده‌اند که از آن جمله می‌توان به قوانین سرانگشتی و الگوریتم‌های فرا ابتکاری اشاره کرد؛ اما موضوعی که در حل مساله زمانبندی کار کارگاهی کمتر بدان پرداخته‌شده، استفاده از داده‌کاوی برای حل این‌گونه مسائل است. داده‌کاوی تکنیکی است که با استخراج الگوها و روابط موجود در یک پایگاه داده، آن‌ها را برای استفاده در آینده آماده می‌کند. اگر زمانبندی کار کارگاهی را، فرایند ترتیب دهی عملیاتی که باید بر روی یک ماشین پردازش شوند در نظر گرفت، این ترتیب دهی عملیات، به‌طور چشمگیری بر روی فرآیند زمانبندی تأثیر می‌گذارند و منجر به تولید برنامه زمانی خوب یا بد می‌شوند. ازاین‌رو باید رابطه‌ای بین ویژگی‌های یک عمل با موقعیتش در این ترتبی دهی عملیات وجود داشته باشد. الگوریتم‌های فرا ابتکاری، اطلاعاتی از اینکه یک ترتیب دهی عملیات چگونه منجر به تولید برنامه زمانی خوب شده است را ارائه نمی‌کنند؛ اما یک مطالعه دقیق بر روی روابط موجود در برنامه‌های زمانی خوب، می‌تواند درک بهتری از ترتیب دهی عملیات و کل فرایند زمانبندی را فراهم آورد. تحقیق حاضر قصد دارد با استفاده از داده‌کاوی روابط موجود در راه‌حل‌های خوب مسائل زمانبندی کار کارگاهی را کشف کرده و از این روابط برای حل مسائل دیگر بهره جوید. بدین منظور لازم است ابتدا مسائل کار کارگاهی به مسائلی قابل کاوش توسط داده‌کاوی تبدیل شوند. سپس یک مساله الگو انتخاب‌شده و به تعداد کافی جواب‌های بهینه یا نزدیک به بهینه آن استخراج می‌شوند. در مرحله بعد این جواب‌ها به قالب صفت‌ها و طبقه‌بندی‌های مناسب نگاشت شده و پایگاه داده تشکیل داده می‌شود. سپس، با استفاده تکنیک داده‌کاوی قوانین انجمنی و الگوریتم اپریوری، روابط و قوانین نهفته در این جواب‌ها استخراج می‌شوند. در پایان یک مدل استنتاج قوانین برای استفاده از این روابط و قوانین در حل مسائل دیگر پیشنهاد می‌گردد. واژه‌های کلیدی: زمانبندی، کار کارگاهی، داده‌کاوی، قوانین انجمنی
- Abstract
- Job-shop scheduling problems are categorized among the hardest optimization problems and therefore, solving these problems has attracted the attention of many scholars. These days, various methods and algorithms, such as dispatching rules and Meta heuristic algorithms, have been developed to solve these problems. But the topic which has been less considered in job-shop scheduling problems is to use data-mining for solving these problems. Data-mining is a technique which extracts existing patterns, relationships and rules in the large databases and makes them ready for future uses. If job-shop scheduling is considered as the sequencing of operations which should be process on the same machine, this sequencing dramatically affects the whole scheduling process and results in bad or good schedules. Hence, there should be a relationship between the position of the operation in the sequence and its specifications. Meta heuristic algorithms do not provide any information of how a sequence of operations has resulted in a good schedule but an accurate study on these relationships can provide a better understanding of the whole scheduling process. This study aims to apply data-mining to discover existing relationships and patterns in the good solutions of the job-shop scheduling problems and then benefits them for solving other job-shop scheduling problems. For this purpose, at first, job-shop scheduling problems should be converted into a format which is discoverable by data-mining technique. Then, a sample problem should be selected and plenty of its optimum or very close to optimum solutions should be obtained. Next, hidden patterns and rules in these solutions should be discovered by association rules technique of data-mining. Finally, an induction model should be suggested to use this rules and patterns for solving other problems. Keywords: scheduling, job-shop, data-mining, association rules.
