ارائه مدل زمان‌بندی چندعاملی در محیط جریان کارگاهی با فرض زوال‌پذیری کارها، زمان‌های آماده‌سازی وابسته به توالی و زمان آزادسازی کارها با استفاده از الگوریتم ازدحام ذرات چندهدفه

نوع مقاله : مقاله پژوهشی

نویسندگان

1 استادیار گروه مهندسی صنایع، دانشکدۀ مهندسی، دانشگاه کاشان، کاشان، ایران

2 دانشجوی کارشناسی‌ارشد، دانشکدۀ مهندسی صنایع، دانشگاه علم و صنعت، تهران، ایران

چکیده

زمان‌بندی چندعاملی در شرایط زوال‌پذیری کارها در سال‌های اخیر مورد توجه روزافزون جوامع دانشگاهی و صنعتی قرار گرفته‌است. مسأله زمان‌بندی چندعاملی، زیرمجموعه‌ای از مسائل زمان‌بندی چندهدفه است که در آن هر عامل، دارای مجموعه‌ای از کارها است و هدف آن، بهینه کردن تابع هدف مربوط به خود است. در این پژوهش یک مسأله زمان‌بندی ‌سه‌عاملی در محیط جریان کارگاهی در شرایط زوال‌پذیری کارها مورد بررسی قرار گرفته ‌است. در مسأله درنظرگرفته شده زمان پردازش واقعی کارها تابع خطی از زمان پردازش نرمال و زمان شروع پردازش کار مربوطه می‌باشد. جهت واقعی‌تر کردن مسأله، دو فرض کاربردی» زمان‌های آماده‌سازی وابسته به توالی «و» زمان آزادسازی کاره «نیز درنظر گرفته شده‌اند. هم‌چنین یک مدل برنامه‌ریزی عدد صحیح مختلط برای مسأله توسعه داده شده که برای حل آن از روش حل دقیق محدودیت جزئی تعمیم‌یافته استفاده شده‌است. با توجه به پیچیدگی مدل و عدم توانایی روش محدودیت جزئی تعمیم‌یافته در حل مسائل با ابعاد بزرگ، الگوریتم فراابتکاری ازدحام ذرات چندهدفه پیشنهاد شده‌است. به‌منظور ارزیابی عملکرد الگوریتم پیشنهادی، به حل مسائل نمونه عددی در اندازه‌های مختلف با استفاده از این الگوریتم و الگوریتم ژنتیک مبتنی بر مرتب‌سازی نامغلوب و روش حل دقیق محدودیت اپسیلون تعمیم‌یافته پرداخته شده‌ است. سپس جهت انتخاب الگوریتم برتر از روش تصمیم‌گیری چندمعیاره ویکور استفاده شد. نتایج محاسباتی، مؤید همگرایی قابل قبول و پراکندگی خیلی خوب راه‌حل‌های الگوریتم MOPSO و هم‌چنین عملکرد بهتر این الگوریتم نسبت به روش محدودیت اپسیلون تقویت‌شده و الگوریتم NSGA-II می‌باشد.

کلیدواژه‌ها


عنوان مقاله [English]

Multi Agent Flow Shop Scheduling Model with Deteriorating Jobs and Sequence-Dependent Setup Times Using Multi Objective Particle Swarm Optimization (MOPSO) Algorithm

نویسندگان [English]

  • Somayeh Ghandi Bidgoli 1
  • Marzie Amini 2
1 Assistant Professor Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran
2 M.A Student Department of Industrial Engineering, Iran University of Science & Technology, Tehran, Iran
چکیده [English]

Multi-agent and deteriorating scheduling has gained an increasing concern from academic and industrial communities in recent years. Multi-agent scheduling problem is a subset of multi-objective scheduling problems in which each agent has a set of jobs and its aim is to optimize its own objective function. This study addresses a three-agent flow shop deteriorating scheduling problem. In the investigated problem, the actual processing time of jobs is a linear function of their normal processing time and starting time. To make the proposed problem more realistic, two practical assumptions such as sequence-dependent setup times and release date of jobs are considered. A mixed integer programming model has also been developed for the problem, which is solved using the Augmented ε-constraint exact method. Also due to the complexity of the model and its inability to solve large-scale problems, Multi Objective Particle Swarm Optimization (MOPSO) algorithm is developed. Since the parameters of meta-heuristic algorithms affect their overall performance and output, the Taguchi method has been used to adjust the parameters of the MOPSO algorithm. Finally, in order to evaluate the performance of the proposed algorithm, numerical sample problems of different structures are solved using this algorithm as well as the Non-dominated Sorting Genetic Algorithm (NSGA-II) and the exact augmented ε-constraint method. The computational results confirm the acceptable convergence and very good dispersion of the solutions of the MOPSO algorithm as well as the better performance of this algorithm compared to the augmented ε-constraint method and the NSGA-II algorithm.

کلیدواژه‌ها [English]

  • Flow shop scheduling
  • Deteriorating jobs
  • Multi agent scheduling
  • Many Objective Particle Swarm Optimization (MOPSO) algorithm
  • Sequence-Dependent Setup Time
  • Release date