رویکرد شبیه‌سازی- بهینه‌سازی برای یافتن توالی بهینه در مسئلۀ پویای تولید کارگاهی دارای خرابی و دوباره‌کاری

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

نویسندگان

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

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

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

چکیده

در این مقاله سعی شده است با ادغام شبیه‌سازی و الگوریتم ژنتیک رویکردی پیشنهاد شود که بتوان از آن در هر مسئلۀ تولید کارگاهی که قابلیت مدل‌شدن با شبیه‌سازی را داشته باشد استفاده کرد. در رویکرد پیشنهادی برای درنظرگیری محدودیت‌هایمسئله از مدل شبیه‌سازی و برای بهینه‌سازی از الگوریتم ژنتیک استفاده می‌شود. بدین منظور ماتریسی به‌عنوان رابط تعریف می‌شود که هم‌زمان نقش بردار کنترلی برای مدل شبیه‌سازی و نمایش ماتریسی جواب برای الگوریتم ژنتیک را ایفا می‌کند. در این روش با استفاده از الگوریتم ژنتیک تغییراتی درماتریس اعمال می‌شود و سپس ماتریس وارد مدل شبیه‌سازی‌شده و تابع هدف تعریف‌شده در مسئله به‌عنوان تابع برازش برای الگوریتم ژنتیک گزارش می‌شود و این روند تا رسیدن به شرایط اتمام الگوریتم ادامه پیدا می‌کند.
روش پیشنهادی بر مسائل معیار تولید کارگاهی سنتی و با تابع هدف زمان اتمام آخرین کار آزمایش می‌شود و نتایج حاصل با نتایج روش برنامه‌ریزی عدد صحیح مختلط مقایسه می‌شود. سپس اولویت‌دهی مناسب برای مینیمم‌کردن تابع هدف چندگانه، در یک سیستم تولید کارگاهی پویای دارای خرابی و دوباره‌کاری به دست می‌آید. نتایج به‌دست‌آمده نشان می‌دهد روش بهینه‌سازی براساس شبیه‌سازی از توانایی بالایی برای مدل‌سازی و یافتن جواب مناسب در اکثر مسائل تولید کارگاهی برخوردار است.

کلیدواژه‌ها

موضوعات


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

A New Method Based on Simulation-Optimization Approach to Find Optimal Solution in Dynamic Job-shop Scheduling Problem with Breakdown and Rework

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

  • Farzad Amirkhani 1
  • Amirhossein Amiri 2
  • Rashed sahraeian 3
1 M.Sc. degree, Dept. of Industrial Engineering, Shaded University, Tehran, Iran
2 Associate Professor, Dept. of Industrial Engineering, Shaded University, Tehran, Iran
3 Assistant Professor, Dept. of Industrial Engineering, Shaded University, Tehran, Iran
چکیده [English]

In this paper we propose an integrated algorithm based on combination of a discrete- event simulation and genetic algorithm. The simulation model is considered as a constraint-satisfaction procedure and if the streaming operations are initiated, then the meta-heuristic takes predefined steps to improve the solution. The latter is constructed through an interface, namely control matrix, implemented as interaction between the simulation model and refined solution of meta-heuristic. In run-time, the control matrix is accessed via simulation model for further modifications.
The proposed method is implemented on classical job-shop problems with objective of makespan and results are compared with mixed integer programming model. Moreover, the appropriate dispatching priorities are achieved for dynamic job-shop problem minimizing a multi-objective criteria. The results show that simulation-based optimization are highly capable to capture the main characteristics of the shop and produce optimal/near-optimal solutions with highly credibility degree.

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

  • Genetic Algorithm
  • Simulation based optimization
  • Dynamic job-shop scheduling

 


1- مقدمه

 

زمان‌بندییکی از اثرگذارترین عوامل تصمیم‌گیری در مسائل برنامه‌ریزی تولید است که هدف آن تخصیص منابع موجود به یک سری از فعالیت‌هاست؛ به‌طوری که یک یا چند تابع هدف تعریف‌شده برای مسئله به بهینگی برسد.

در سیستم‌های تولیدی برای کاهش هزینۀ موجودی در حال پردازش(WIP[1]) و نیز کاهش تأخیرها،محصولات بایدبراساس اولویت‌های خاصی پردازش شوند. تعیین اولویت پردازش اساس مسائل زمان‌بندی است و عواملی مانند سطوح موجودی، پیش‌بینی تقاضا، احتیاجات منابع و شرایط سیستم تولیدی بر آن اثر می‌گذارند(بیکر و همکاران[2]، 2007).

مسئلۀزمان‌بندیِسیستمِ تولیدِکارگاهینوع خاصی از مسائل زمان‌بندی است که در آن هر محصول فرایندهای از پیش تعیین‌شده و متوالی را روی ماشین‌ها طی می‌کندکه این فرایندها از محصولی به محصول دیگر متفاوت است (پیندو[3]، 2012). پژوهش‌های انجام‌شده نشان می‌دهد این مسئله حتی با بسیاری از فرض‌های محدودکننده دارای پیچیدگی زیادی است و درصورت وجود سه ماشین یا بیشتر جزء مسائل NP-hard به حساب می‌آید (گری و همکاران[4]، 1976).

پیچیدگی تنها مشکل موجود در حل مسئلۀ تولید کارگاهی نیست و ماهیت این سیستم موجب می‌شود پویایی و عدم‌قطعیت  از اجزای جدایی‌ناپذیر آن باشد (نور[5]، 2007). در این مسئله اگرحداقل یکی از پارامترهای اثرگذار دارای حالت قطعی نباشد،مسئله دارای حالت احتمالی یا فازی است. از طرفی اگر در ابتدای زمان‌بندی تمامی کارها و پارامترهای مرتبط با آنها مشخص باشد،مسئله ایستا و در غیر این صورت پویا خواهد بود (بیکر و همکاران، 2007).حالت پویا خود به دو زیر شاخۀ آنلاین و آفلاین تقسیم می‌شود که در حالت آفلاین در ابتدای زمان‌بندی اطلاعاتی دربارۀ کارهایی که در آینده باید زمان‌بندی شوند وجود دارد؛ ولی در حالت آنلاین این اطلاعات هم در دسترس نیستند (جی و همکاران[6]، 2006).

پس از تعریف‌های ارائه‌شده باید مشخص شود عوامل عدم‌قطعیت و پویایی در سیستم تولید کارگاهی چیست؟ این عوامل را می‌توان در سه دسته به‌صورت زیر طبقه‌بندی کرد:

الف) تقاضا: اصولاً در سیستم تولید کارگاهی محصول زمانی تولید می‌شود که سفارشی برای آن وجود داشته باشد (حالت تولید برای سفارش[7]MTO)، زمان سفارش یک محصول جدید و فواصل زمانی سفارشات برای تولیدمحصولات جزء متغیرهای تصادفی این مسئله خواهد بود.

ب) ماهیت محصول تولیدی: به‌دلیل منحصربه‌فرد‌ بودن فرایند تولید هر محصول و ماهیت شبه‌پروژه‌ای، اظهارِنظر قطعی دربارۀ فرایندهای موردنیاز و زمان‌های فرایند محصولات در سیستم تولید کارگاهی امکان‌پذیر نیست؛ به‌علاوه جهت رعایت الزامات کیفی ممکن است درصدی ازمحصولات نیاز به دوباره‌کاری داشته باشند.

ج) محیط کارگاه: خرابی و دردَسترس‌نبودن دستگاه‌ها از واقعیت‌هایی است که در اکثر مسائل تولیدی و به‌ویژه تولید کارگاهی جهت ساده‌ترشدن مسئلهاز آن چشم‌پوشی می‌شود. برای نزدیک‌شدن جواب بهینۀ مدل و سیستم واقعی باید پارامترهای زمان بین دو خرابی([8]MTBF) و نیز زمان لازم برای تعمیر خرابی(MTTR[9]) در مدل وارد شوند.

پس از بیان کلیاتی دربارۀمسئله و عوامل ایجاد عدم‌قطعیت در آن، در ادامه به بررسی روش‌هایمدل‌سازی و حل مسئله پرداخته می‌شود؛این روش‌هابه دو دستۀمدل‌های تحلیلی و شبیه‌سازی تقسیم می‌شوند(ژانگ و همکاران[10]، 2012). مدل‌های تحلیلی در قالب روابط ریاضی مدل‌سازیمی‌شوند و براساس توابع هدف، میزان سختی و خطی و غیرخطی‌بودن روش‌های مشخصی برای بهینه‌سازی آنها وجود دارد.

یکی از مهم‌ترینمدل‌های تحلیلی در مسئلۀ تولید کارگاهی توسط مان[11] (1966) ارائه شده استکه در آن با استفاده از برنامه‌ریزی اعداد صحیح مختلط[12] اقدام به مدل‌سازیمسئلۀ تولید کارگاهی شده است. به‌علاوه در سال‌های اخیر، روش‌های شاخه و کران توسط لائو[13] و همکاران (2004)و بالاسوبرامانیان[14] و همکاران (2002)، ابتکاری(پیندو، 2005) و فرااِبتکاری (تانگ [15]و همکاران، 2011؛ گوا[16]، 2008؛ چن[17] و همکاران،2012؛ پزلا [18]و همکاران، 2008)برای حل مسئلۀ تولید کارگاهی براساس روش تحلیلی پیشنهاد شده است.

از سوی دیگر مدل‌هایشبیه‌سازی رفتار مدل را توصیف می‌کنند و برای آزمون‌های تحلیل حساسیت و ارزیابی سیستم به کار گرفته می‌شوند. این مدل‌ها قرابت زیادی به سیستم‌های واقعی تولید دارند و برای ساختن آنها نیازی به روابط ریاضی و درنظرگیری فرض‌های محدودکننده نیست. به‌عنوان مثال روش‌هایاولویت‌دهی رایج در سیستم‌های تولید(FIFO[19]، SPT[20]،LPT[21]،[22]EDDو...) یا تعداد ماشین‌های مناسب برای ایستگاه‌های کاری با استفاده از مدل‌هایشبیه‌سازی بررسی و ارزیابی شده‌اند (وینود[23]و همکاران، 2011؛ چن[24] و همکاران، 2003؛ دومینیک[25] و همکاران، 2004؛ ایکاسوقلی[26] و همکاران، 2010).

هر دو روش ذکرشده دارای مزایا و معایبی هستند که نولان[27] و همکاران (1972) آن ها را بررسی و مورد مقایسه قرار داده است.بیشتر مدل‌های تحلیلی به‌دلیل خلاصه‌سازی بیش از حد، باعث ازبین‌رفتن جزئیات سیستم می‌شوند؛ به‌علاوه در صورتی که پیچیدگی سیستم واقعی زیاد باشد این مدل‌ها توانایی خود را از دست می‌دهند؛از طرفی نمی‌توان از مدل‌هایشبیه‌سازیبرای یافتن جواب مناسب برای سیستم استفاده کرد.

با ادغام روششبیه‌سازی و تحلیلی می‌توان مدلی ساخت که مزایای هر دو روش را داشته باشد؛ این مدل‌ها،مدل‌های ترکیبی شبیه‌سازی-تحلیلی نامیده می‌شوند (سارگنت[28]، 1994).

استفاده از رویکرد شبیه‌سازی- بهینه‌سازی در چند سال اخیر گسترش پیدا کرده است و پژوهشگران با کمک این روش سعی در کم‌کردن فاصلۀ بین مدل و سیستم واقعی تولید داشته‌اند. در این زمینه (هالثوس[29]،1999) از شبیه‌سازی برای تحلیل اثر خرابی و قوانین اولویت‌دهی بر زمان‌های اتمام و میزان تأخیرها در سیستم تولید کارگاهی پویا استفاده کرده است. کلمت[30] و همکاران (2007) با ترکیب مدل شبیه‌سازی و روش‌های جستجوی محلی سعی در کاهش زمان جریان و زمان نصب قطعه روی ماشین در یک سیستم تولید کارگاهی داشته‌اند. غلامی[31] و همکاران (2009) یک سیستم تولید کارگاهی انعطاف‌پذیر دارای خرابی را در نظر گرفته‌اند که زمان‌های ورود و فرایند در آن قطعی و زمان خرابی‌ها تصادفی است. آنها با ترکیب شبیه‌سازی و الگوریتم ژنتیک سعی کرده‌اند تابع هدف چندگانۀ متشکل از زمان‌های اتمام و میانگین زمان‌های تأخیر را مینیمم کنند. کلمت و همکاران(2009( کیفیت و زمان رسیدن به جواب را در دو روش شبیه‌سازی- بهینه‌سازی وبرنامه‌ریزی عدد صحیح مختلط با هم مقایسه کرده‌اند و پس از بررسی مزایا و معایب دو روش، یک رویکرد ترکیبی براساس شبیه‌سازی و برنامه‌ریزی عدد صحیح مختلط برای مسئله پیشنهاد کرده‌اند. مهدوی و همکاران (2010) از یک رویکرد تصمیم‌گیری براساس شبیه‌سازی در یک سیستم تولید کارگاهی انعطاف‌پذیر استفاده کرده‌اند و با ترکیب آن با روش گرادیان سعی کرده‌اند آن را به سمت جواب بهینه برای تابع هدف زمان اتمام آخرین کار هدایت کنند. شهزاد و همکاران(2012) با شبیه‌سازی، یک سیستم تولید کارگاهی را مدل کرده‌اند و از داده‌کاوی برای کشف قوانین اولویت‌دهی مناسب در مسئله استفاده کرده‌اند؛ بدین منظور آنها از روش جستجوی ممنوع برای جستجوی فضای جواب مسئله استفاده کرده‌اند. امیرخانی و همکاران (2013) با شبیه‌سازی مسئلۀ تولید کارگاهی دارای خرابی تصادفی و تغییر در قوانین اولویت‌دهی رایج در پشت صف هر ماشین با الگوریتم ژنتیک، سعی در یافتن روش اولویت‌دهی مناسب برای صف‌های مختلف در سیستم تولید داشته‌اند. کولکارنی[32] و همکاران (2014) از ترکیب مدل شبیه‌سازی و برنامه‌ریزی خطی برای رسیدن به جواب بهینه در مسائل تولید کارگاهی معیار استفاده کرده‌اند.در جدول1 مهم‌ترین پژوهش‌های انجام‌شده در زمینۀمدل‌سازی و حل مسائل تولید کارگاهی و تولید کارگاهی انعطاف‌پذیر با روش شبیه‌سازی-بهینه‌سازی،براساس شرایط مسئله و توابع هدف، طبقه‌بندی شده‌اند.

بررسی پژوهش های انجام‌شده در این حوزه نشان می‌دهد. بر‌خلاف پتانسیل بالای رویکرد شبیه‌سازی- بهینه‌سازیدر مدل‌سازی و یافتن جواب مناسب برای مسئلۀ تولید کارگاهی، مطالعات انجام‌شده در این حوزه از جامعیت لازم برخوردار نیست و روش‌های پیشنهادشده قابلیت مدل‌سازی و یافتن جواب برای حالت خاصی از مسائل را دارند؛ از طرفی در بیشتر این پژوهش‌ها از عوامل ایجاد عدم‌قطعیت مانند خرابی‌ها و دوباره‌کاری‌هاکه از ویژگی‌های ذاتی مسئلۀ کارگاهی است چشم‌پوشی شده است.

مسئلۀ درنظرگرفته‌شده در این پژوهش، یک مسئلۀ پویای آفلاین است که در آن عوامل ایجاد عدم‌قطعیت مانند زمان‌هایورود سفارش‌های جدید، زمان‌های فرایند، فرایندهای موردنیاز، زمان‌های خرابی، زمان لازم برای تعمیر و دوباره‌کاری‌ها به‌صورت تصادفی در نظر گرفته شده است و در آن اطلاعاتی از کارهایی که در آینده وارد سیستم خواهند شد در دسترس است.

در روش پیشنهادی برای این مسئله از یک ماتریس  استفاده شده است که mتعداد ماشین‌های کارگاهو nتعداد کل محصولات موردپردازش روی ماشین‌هاست. این ماتریس جهت یافتن توالی بهینه از اصلی‌ترینتصمیم‌گیری لازم در مسائل زمان‌بندی که انتخاب اولویت پردازش کارها روی ماشین‌هاست استفاده می‌کند. ماتریس پیشنهادشده به‌صورت هم‌زمان نقشِ نمایشِ ماتریسی برای الگوریتم ژنتیک و بردار کنترلی برای مدل شبیه‌سازی را ایفا می‌کند و براساس آن، جواب‌های مناسب برای مسئله ازطریق عملگرهای الگوریتم ژنتیک تولید، و مقادیرتابع هدف آنها با استفاده از مدل شبیه‌سازی حاصل می‌شوند.

در چنین حالتی شرایط واقعی سیستم تولیدی با استفاده از مدل شبیه‌سازی‌شده در مسئله اعمال می‌شود و می‌توان انواع عوامل ایجاد عدم‌قطعیت در سیستم، از جمله زمان‌های ورود و فرایند تصادفی، خرابی‌ها و دوباره‌کاری‌ها را در مدل شبیه‌سازی‌شده وارد کرد و جواب مناسب برای آن را با جستجوی هوشمند ازطریق الگوریتم ژنتیک به دست آورد.

جدول(1): مدل‌های ترکیبی به‌کارگرفته‌شده در مسائل تولید کارگاهی

تابع هدف

روش حل

شرایط مسئله

خصوصیات

 

 

مقاله

دوباره‌کاری

خرابی

زمان پردازش

ورود کارها

سیستم تولید

Flow time

Tardy jobs

 

Simulation+ dispatching rules

-

ü

قطعی

قطعی

JSP

هالثوس،1999

Set up time

Idle time

Simulation+

local search algorithms

-

-

احتمالی

احتمالی

JSP

کلمت و همکاران، 2007

 

GA+ simulation

-

ü

قطعی

قطعی

FJSP

غلامی و همکاران، 2009

 

 

MIP vs.

Simulation-based optimization

-

-

قطعی

قطعی

JSP

کلمت و همکاران، 2009

 

 

Simulation+Gradient based optimization

-

-

احتمالی

احتمالی

FJSP

مهدوی و همکاران،2010

 

Simulation based optimization+TS+data mining

-

-

احتمالی

قطعی

JSP

شهزاد و همکاران، 2012

 

 

Simulation based optimization + GA+ dispatching rules

-

ü

احتمالی

احتمالی

JSP

امیرخانی و همکاران، 2013

 

Simulation based optimization +Linear programming

-

-

قطعی

قطعی

JSP

کولکارنی و همکاران، 2014

 

Simulation based optimization + GA

ü

ü

قطعی

احتمالی

قطعی

احتمالی

JSP

روش پیشنهادی پژوهش

 

 

 

 

 

 

 

 

در این صورت درنظرگیری فرض‌های محدودکننده در مسئله که از مشکلات مدل‌های تحلیلی است از بین می‌رود و از طرف دیگر می‌توان جواب مناسب برای آن را با استفاده از روش الگوریتم ژنتیک به دست آورد.بر این اساس نوآوری‌های موجود در این مقاله به شرح زیر است:

  • استفاده از شبیه‌سازی- بهینه‌سازی برای اولویت‌دهی مناسب در مسئلۀ پویای احتمالی تولید کارگاهی به‌گونه‌ای که برای درنظرگیریمحدودیت‌هایمسئله از مدل شبیه‌سازی و برای بهینه‌سازی از الگوریتم ژنتیک استفاده شده است.
  • استفاده از منطق عمومی مسائل توالی عملیات، مبنی بر تصمیم‌گیری دربارۀ اولویت پردازش کارها در صف ماشین‌ها ودرنتیجه توانایی رویکرد پیشنهادی در یافتن جواب مناسب برای انواع مسائل قطعی/ احتمالی و ایستا/پویا
  • تعریف یک ماتریس اولویت‌دهی که در مدل شبیه‌سازی نقش بردار کنترلی و در الگوریتم ژنتیک نقش نمایش ماتریسی جواب را ایفا می‌کند و ارتباط بین الگوریتم ژنتیک و مدل شبیه‌سازی را برقرار می‌کند.
  • درنظرگرفتن عامل دوباره‌کاری در کنار سایر عوامل ایجاد عدم‌قطعیت در مسئله

ساختار مقاله به این صورت است که در بخش دوم رویکرد به‌کارگرفته برای حل مسئله تشریح می‌شود، در این قسمت ابتدا دربارۀ کلیت روش شبیه‌سازی- بهینه‌سازی توضیحاتی ارائه می‌شود و سپس چگونگی مدل‌سازی و بهینه‌سازیمسئله توصیف می‌شود.بخش سوم مقاله به بررسی انواع سیستم‌های تولید کارگاهی به‌کارگرفته‌شده در مسئله و نیز تابع هدف موردنظر مقاله می‌پردازد. در بخش چهارم نتایج به‌دست‌آمده ارائه می‌شود و نتایج حاصل، با سایر روش‌های موجود در ادبیات مسئله مقایسه می‌شود. بخش آخر مقاله نیز به نتیجه‌گیری و ارائۀ پیشنهادهای آتی اختصاص داده شده است.

2- توصیف مسئله

1-2-سیستم تولید

مدلی که مان(1966) برای مسئلۀ سنتی تولید کارگاهی ارائه کرده، از مهم‌ترینمدل‌های تحلیلی در ادبیات این مسئله است که در آن مفروضات زیر در نظر گرفته شده است:

  • تمامی کارها از زمان آغاز فرایند در دسترس هستند.
  • n کار و mماشین در سیستم وجود دارد.
  • هر کار زمان فرآیند مشخصی دارد و باید با یک ترتیب خاص از تمامیmماشین عبور کند.
  • در هر لحظه ماشینمی‌تواند فقط یک کار را انجام دهد.
  • در صورت آزادبودن ماشین و نیاز یک محصول به آن، هیچ دلیلی برایاجرانشدن فرایند مربوط به آن محصول روی ماشین وجود ندارد.
  • هیچ زمان اتمام موردانتظاری وجود ندارد.
  • تابع هدف مینیمم‌کردن زمان اتمام آخرین کار است.

براساس این مدل یک مسئلۀ تولید کارگاهی با n کار وm ماشین، شامل  متغیر باینری و  محدودیت خواهد بود. برای ارزیابی روش پیشنهادی برمسئلۀ تولید کارگاهی، در ابتدا از مسائل معیار کلاسیکموجود استفاده شده است که برای تعیین تعداد پارامترها و محدودیت‌ها در این مسائل از روابط مدل مان استفاده شده است.

پس از ارزیابی روش پیشنهادی برای مدل‌های کلاسیک سعی شده سه عامل ایجاد عدم‌قطعیت اشاره‌شده در مقدمه، به مسئله افزوده شود تا مدل از هر لحاظ به سیستم واقعی تولید نزدیک شود. برای این کار با مراجعه به ادبیات مسئله سعی شده است پارامترهای مناسب برای سیستم تولید احتمالی و پویا تعریف شود. سیستمی بین 4 تا 10 ماشین، پیچیدگی مناسبی برای مسئله ایجاد می‌کند(رانگساریتراتسامی[33] و همکاران، 2004)؛بنابراین در این مقاله از 8 ایستگاه کاری در سطح کارگاه استفاده شده است که در هر ایستگاه 2 ماشین کاملاً مشابه وجود دارد که در صورت آزادبودن هر کدام از ماشین‌های موجود در ایستگاه، باید کاری به آن تخصیص داده شود. با فرض اینکه تمامی محصولات برای اتمام فرایندهایشان باید از همۀماشین‌ها عبور کنند توالی کارها، براساس جایگشت هشت‌تایی و به‌صورت تصادفی تعیین می‌شود.

مناسب‌ترین توزیع برای زمان‌های بین دو ورود متوالی و نیز زمان پردازش کارها روی ماشین‌ها توزیع نمایی است(رانگساریتراتسامی و همکاران، 2004)؛بنابراین زمان پردازش کارها برماشین‌ها دارای توزیع نمایی با میانگین یک واحد زمانی در نظر گرفته شده است. برای تولید زمان‌های بین ورود دو کار متوالی باید عامل ضریب بهره‌مندیماشین‌ها هم لحاظ شود. از این رو برای تولید زمان بین دو ورود متوالی از رابطۀ (1) استفاده شده است (رانگساریتراتسامی و همکاران، 2004).

 

 

(1)

در این رابطه مقدار متوسط زمان فرایند (  ) برابر با یک واحد زمانی، متوسط تعداد ماشین‌های موردنیاز برای هر محصول( ) برابر با 8، ضریب بهره‌مندی از ماشین( ) 9/0 و تعداد ماشین‌های موجود در کارگاه( ) 16 در نظر گرفته شده است و بر این اساس زمان بین دو ورود متوالی 55/0 واحد زمانی خواهد بود.

برای درنظرگیری خرابی ماشین‌ها در حین فرایندباید دو مقدار زمان بین دو خرابی متوالی و زمان تعمیر تعیین شود که مقادیر موجود برای این دو عامل در مقالات براساس توضیح نمایی تولید می‌شوند (هالثوس،1999)؛ از این رو زمان بین دو خرابی توزیع نمایی با میانگین 250 واحد زمانی برای هر ایستگاه و زمان تعمیر نمایی با میانگین20 واحد زمانی در نظر گرفته شده است.

با توجه به وجود عوامل اثرگذار در سیستم تولید کارگاهی به‌دلیل غیراتوماتیک‌بودن سیستم، از جمله تفاوت در اپراتورها، ماشین‌ها و چگونگی نصب قطعه روی ماشین وجود محصولات نامنطبق با معیارهای کیفی در این سیستم امری رایج است؛ با این حال در بیشتر مقالات فرض شده هر محصول فقط یک بار روی ماشین پردازش می‌شود. در اینجا برای نزدیک‌شدن مدل با سیستم واقعی تولید فرض شده 10درصد از محصولات هر ایستگاه کاری بعد از بازرسی کیفی نیاز به دوباره‌کاری پیدا می‌کنند که دوباره به صف ایستگاه ارجاع داده می‌شوند و فرایند موردنظر دوباره بر آنها انجام می‌شود.

2-2- تابع هدف

 

توابع هدف مختلفی را می‌توان برای یک مسئلۀزمان‌بندی تعریف کرد که پرکاربردترین تابع هدف به‌کاررفته در مقالات مینیمم‌کردن زمان اتمام آخرین کار در سیستم ( )است. برای ارزیابی کارایی روش پیشنهادی با مسائل معیار تولید کارگاهی کلاسیک، از این تابع هدف استفاده شده است. با این حال کاهش تأخیرها در سیستم نیز یکی از پارامترهای مهم برای واحدهای تولیدی است. معمولاً در زمان دریافت سفارش، زمان اتمام موردانتظار[34](D) برای هر کار توسط مشتری یا سازمان تعیین می‌شودو در صورتی که کار موردنظر دیرتر از زمان موردانتظار تمام شود هزینه‌هایی به سیستم تحمیل خواهد شد؛ از این رو میزان تأخیر در سیستم برای هر کار براساس رابطۀ (2) تعیین می‌شود.

 

 

(2)

این رابطه  زمان اتمام کار  و  زمان اتمام مورد انتظار کار است.برای حالت تصادفی و پویای مسئله، از تابع چندهدفه‌ای کهادیبی و همکاران (2010) به کار گرفته‌اند، براساس  وTاستفاده شده است که مقادیر مناسبی را برای تصمیم‌گیری دربارۀ عملکرد سیستم تولید می‌کند و به‌صورت رابطۀ (3) تعریف می‌شود.

 

 

(3)

با توجه به آزمایش‌های صورت‌گرفته در این مسئله، واریانس  کمتر از T است از این رو ضریب مناسب برای زمان اتمام آخرین کار برابر با ۵ و برای میزان تأخیرها این ضریب ۲ در نظر گرفته شده است (رانگساریتراتسامی و همکاران، 2004).

برای تعیین زمان اتمام موردانتظارجهت تعیین میزان تأخیر از روش کل محتوای کار[35] استفاده شده است که براساس رابطۀ (4) به دست می‌آید.

 

(4)

3- روش حل مسئله

همان‌طور که گفته شد استفاده از روش ترکیبی شبیه‌سازی- تحلیلی برای مدل‌سازی و تلاش برای یافتن جواب بهینه برای مسئله براساس این مدل‌ها رویکرد شبیه‌سازی-بهینه‌سازی نامیده می‌شود. اگر یک مسئلۀشبیه‌سازی- بهینه‌سازی همراه با محدودیت‌هایش به فرم زیر نمایش داده شود:

 

(5)

به‌طوری که داشته باشیم:

 

(6)

در این صورت  برابر با مقدار تابع هدف برای یک نمونۀ خاص از مسئله و  مقدار آثار تصادفی در سیستم است. Xدر این رابطه، بردار کنترلی برای مسئله و مجموعۀمحدودیت‌ها برای X است.در روش پیشنهادی، مسئله با شرایط گفته‌شده در قسمت قبل و با کمک شبیه‌سازی مدل شده و سپس سعی شده با ایجاد ارتباط بین این مدل و الگوریتم ژنتیک جواب مناسب برای آن به دست آید. یکی از عوامل اصلی در پیاده‌سازی مدل ترکیبی شبیه‌سازی- بهینه‌سازی تعداد دفعاتی است که مدل‌هایشبیه‌سازی و بهینه‌سازی با هم ارتباط برقرار می‌کنند. بر این اساس مدل‌های ترکیبی را می‌توان به دو گروه بدون تکرار و با تکرار تقسیم کرد. حالت بدون تکرار معمولاً برای ارزیابی و بررسی صحت جواب بهینه به کار گرفته می‌شود و در حالت با تکرار در هر مرحله از بازخورد مرحلۀ قبلی برای بهبود جواب استفاده می‌شود. با توجه به درجۀ سختی مسائل زمان‌بندی، روش با تکرار برای این مسئلهمناسب‌تر خواهد بود. در این رویکرد بعد از انجام شبیه‌سازی، بازخورهای موردنظر از آن گرفته شده و به مسئلۀ

 

سعی می‌شود مدل به سمت جواب بهینه هدایت شود و نتایج دوباره در مدل شبیه‌سازی اعمالشود و این روند تا رسیدن به یک جواب مناسبتکرار می‌شود (شکل 1).گفتنی است در قسمت شبیه‌سازی شکل 1،پیکان‌های مشکی توپر مسیر حرکت محصولات روی ایستگاه‌های مختلف و پیکان‌هایخط‌چین دوباره‌کاری‌ها را نمایش می‌دهند؛ مثلاً محصول شماره چهار پس از انجام‌شدن فرایند

شکل1. رویکرد کلی به‌کارگرفته‌شده برای حل مسئله

 


موردنظرش روی ایستگاه کاری سه، در صف ایستگاه شماره یک قرار گرفته است و محصول سه در ایستگاه یک نیاز به دوباره‌کاری داشته و به همین دلیل به صف بازگردانده شده است.

مهم‌ترین تصمیمی که در یک مسئلۀ توالی باید گرفته شود این است که در پشت صف ماشین‌ها

اولویت به کدام کار باید تخصیص داده شود تا تابع هدف موردنظر مینیمم شود. اگر در حالت قطعی، کارگاهی با m ماشین وnکار را در نظر بگیریم در این صورت  حالت برای اولویت‌دهی به کارها وجودخواهد داشت که با وجود mصف، در کل راه حل متفاوت برای حل این مسئله وجود دارد؛بنابراین برای بهینه‌سازی باید از یک روش جستجوی هدفمند استفاده شود تا در عین سرعت در رسیدن به جواب، فضای جواب را برای متغیرهای تصمیم غیرکمّی تعریف‌شده در مسئله، به‌صورت مناسب جستجو کند؛ برای این منظور الگوریتم ژنتیک از کارایی مناسبی برخوردار است(پائول[xxxvi]، 1998)؛بنابراین رویۀ کلی در روش پیشنهادی به این صورت است که یک جمعیت اولیه به‌صورت تصادفی برای تعیین اولویت‌دهی کارهای موجود در صف ماشین‌ها تولید می‌شود. سپس این اعضای این جمعیت به‌عنوان یک بردار کنترلی وارد مدل شبیه‌سازیمی‌شوند و توابع هدف موردنظر برای مسئله از مدل شبیه‌سازی استخراج می‌شوند و به‌عنوان مقدار تابع برازندگی[xxxvii] به الگوریتم ژنتیک داده می‌شوند و الگوریتم ژنتیک تغییراتی روی این جمعیت ایجاد می‌کند و دوباره مدل براساس تغییرات حاصله شبیه‌سازیمی‌شود و این روند ادامه پیدا می‌کند.

1-3-الگوریتم ژنتیک

 

گام‌های اصلی جهت پیاده‌سازی الگوریتم ژنتیک برای یک مسئله تعیین چگونگی نمایش، تقاطع، جهش و شرایط خاتمه برای مسئله است. بدین منظور شرایط زیر برای مدل برقرار شده است:

الف) نمایش: برای تعریف کروموزوم‌ها در الگوریتم ژنتیک به جای تعریفرشته‌ای از اعداد، از یک ماتریس  استفاده شده است که هر سطر در آن اولویت کارها در صف پشت یک ماشین را مشخص می‌کند و بر این اساس به تعداد ماشین‌های موجود در کارگاه، سطر برای ماتریس وجود خواهد داشت.هر کار شمارۀ مخصوص خود را دارد و زمانی که ماشین در یکی از ایستگاه‌ها آزاد شد، کاری که در پشت صف ماشین اولویت بالاتری دارد روی آن پردازش می‌شود (شکل 2).

با این شرایط جمعیت معینیاز کروموزوم‌هاتولید می‌شود و مقادیر تابع هدف آنها از مدل شبیه‌سازی‌شده به دست می‌آید و مرتب می‌شود.

ب) تقاطع: پس از انتخاب والدین با چرخۀ رولت، برای تعداد مشخصی از افراد جامعه عمل تقاطع تکی و دوتایی با احتمال برابر انجام می‌شود.باید این را در نظر داشت که اگر از روش معمول تقاطع استفاده شود امکان تولید کروموزوم‌های نامناسب وجود دارد؛ مثلاً اگر کروموزومی با 6 ژن را در نظر بگیریم ایجاد تقاطع تکی باعث تولید دو اولویت برای کارهای 4 و 3 در یکی از فرزندان می‌شود و اولویت کار یک حذف می‌شود (شکل3).

 

 

شکل 2. چگونگی تعریف کروموزوم‌ها

 

شکل 3. ایجاد کروموزوم نامناسب در حالت تقاطع معمولی

بنابراین برای تولید کروموزوم‌های مناسب بعد از تعیین محل تقاطع، قسمت اول والد اول نگه داشته می‌شود، سپس اعداد مربوط به ژن‌های بخش اول والد اول از والد دوم حذف می‌شود و قسمت دوم کروموزوم اول براساس ژن‌های باقیمانده از والد دوم و به همان ترتیب در قسمت دوم کروموزوم اول وارد می‌شود(شکل4). این کار برای والد دوم تکرار می‌شود و به این ترتیب از تکرار و حذف اولویت‌ها در کروموزوم‌ها جلوگیری می‌شود.

 

شکل 4.نحوۀ انجام تقاطع تکی

ج) جهش: بدین منظور به‌صورت تصادفی تعدادی از اعضای جامعه انتخاب می‌شوند و برای هر سطر والد، دو نقطه به‌صورت تصادفی انتخاب می‌شود و اعداد مربوط به آن نقاط تصادفی با یکدیگر عوض می‌شوند.

د) شرایط اتمام: شرایط خاتمۀ الگوریتم برای حالت قطعی و احتمالی با هم فرق می‌کند که در هر بخش به آن اشاره خواهد شد.

 

2-3- مدل شبیه‌سازی‌شدۀمسئله

برای استفاده از روش حل ترکیبی، باید مدل شبیه‌سازی و روش بهینه‌سازی به‌صورت مناسب و سریعی با یکدیگر ارتباط برقرار کنند تا با اعمال شرایط بردار کنترلی در مدل و حصول تابع هدف موردنظر، روش حل به سمت جواب بهینه حرکت کند.

 در این شرایط، استفاده از دو نرم‌افزار متفاوت برای شبیه‌سازی و بهینه‌سازیمی‌تواند سرعت رسیدن به جواب را تحت‌تأثیر قرار دهد. با بررسی‌های انجام‌شده در این حوزه برای شبیه‌سازی سیستم تولید، از جعبه‌ابزار[xxxviii]سیم‌ایونتز[xxxix] از مجموعۀ سیمولینک[xl] متلب استفاده شده است. این جعبه‌ابزار برای شبیه‌سازیسیستم‌های گسسته پیشامد طراحی شده و اجزای مختلف سیستم در آن، به‌صورت بلاک‌هایی قابل تعریف است. در این جعبه‌ابزارمی‌توانکدنویسی‌های مورد نیاز برای مدیریت خصیصه‌ها را انجام داد. ترکیب این امکانات با سیستم کدنویسی متلب، قابلیت انعطاف‌پذیری فراوانی ایجاد می‌کند.شبیه‌سازی برای روش حل ارائه شده در سیم‌ایونتز از بخش‌های زیر تشکیل شده است:

  • بخش اول: تولید نهادها

در مدل پیشنهادی محصولاتی که برای تکمیل فرایندهایشان نیازمند ماشین‌های کارگاه هستند به عنوان نهاد در نظر گرفته شده‌اند. ماتریس arrivalبا ابعاد  بر اساس تابعِ توزیعِ فواصلِ زمانیِ بینِ ورودِ دو محصول متفاوت ایجاد شده و با اتصال آن به بلاک «تولید نهاد بر اساس زمان[xli]» اقدام به تولید نهاد برای مدل می‌کند. در مسائلی که سیستم تولیدی حالت ایستا دارد و در دسترس بودن تمامی کارها از ابتدای فرایند از مفروضات مسئله است این بردار مقدار صفر به خود می‌گیرند.

  • بخش دوم: تخصیص خصیصه‌های لازم به هر نهاد

با اختصاص یک سری از داده‌ها به هر نهاد می‌توان در مواقع نیاز در قسمت‌های مختلف مدل از آنها استفاده نمود. در بخش دوم مدل سعی می‌شود اطلاعات زیر در قالب خصیصه ضمیمه‌ی نهادها شود:

-      شمارۀ هر محصول برای پیگیری‌های بعدی در قالب ماتریس J_Numberو در ابعاد  ایجاد و به هر کار تخصیص دادهمی‌شود.

-      زمان‌های پردازش کارها روی ماشین‌ها در قالب ماتریس P_timeو در ابعاد  در نظر گرفته می‌شود(شکل 5).

 

شکل 5. ماتریس زمان پردازش

با توجه به اینکه با ورود کارها به سیستم تولیدی باید زمان‌های فرایند اول هر کار مشخص شود، ستون اول این ماتریس در نظر گرفته می‌شود و به‌عنوان خصیصۀ زمان فرایند به کارها تخصیص داده می‌شود.

-         مسیر کارها روی ماشین‌ها، در ماتریسی مشابه ماتریس زمان‌های پردازش تعریف می‌شود و با نام Routeدر نظر گرفته می‌شود.

-      ماتریس نشانگر برای نمایش وضعیت کار در سطح کارگاه و با نام amalgدر نظر گرفته شده است. در این ماتریس اعداد 1 تا  در قالب یک ماتریس  مرتب شده‌اند. با مشخص‌کردن این خصیصه برای هر کار می‌توان تعیین کرد هر محصول در سیستم تولید در حال تکمیل فرایند چندم است.

برای مثال در صورتی که مقدار این خصیصه برای محصول دوم برابر با  باشد با توجه به قرارگیری این آرایه در سطر دوم که نشان‌دهندۀشمارۀ محصول و ستون دوم که نشان‌دهندۀشمارۀ فرایند انجام‌شده بر محصول است می‌توان نتیجه گرفت محصول دوم فرایند دوم موردنیازش را طی می‌کند که با مراجعه به ماتریس‌های مسیر و زمان پردازش می‌توان اطلاعات مربوط به فرایندهای هر کار را در هر مرحله از این سه ماتریس استخراج کرد و به آنها تخصیص داد (شکل 6).

 

شکل 6. ماتریس نشانگر

-      موعد تحویل برای هر کار به‌منظور تعیین میزان تأخیرها به‌صورت ماتریس  و با نام DDتعیین و به نهادها تخصیص داده می‌شود. برای مشخص‌کردن موعد تحویل محصولات از روش TWkاستفاده شده است.

-     اولویت کارها در صف ماشین‌ها: چون اولویت هر کار روی هر ماشین ویژگی منحصربه‌فرد آن است mخصیصه برای هر کار تعریف می‌شود و اعداد مربوط به اولویت‌دهی از بردار کنترلی دریافت و در آن ذخیره می‌شود.

  • بخش سوم: ارسال نهادها به صف ماشین‌ها

محصولاتی که وارد کارگاه شده‌اند با یکی از فرایندهایشان به پایان رسیده و به فرایند(های) دیگری نیاز دارند باید به صف ماشین بعدی موردنیازشان هدایت شوند. در این بخش براساس خصیصۀRouteهر محصول در صف ماشین موردنیاز قرار می‌گیرد.

  • · بخش چهارم: سیستم صف و ماشین‌ها

اولویت‌دهی به کارها در صف ماشین‌ها براساس خصیصۀ هر کار اعمال می‌شود.

  • · بخش پنجم: تعیین فرایند بعدی برای کارها

بعد از اتمام هر کدام از فرایندهای محصولات، باید تغییراتی در خصیصه‌ها ایجاد شود. در این راستا شمارۀ فرایند، زمان فرایند و ماشین بعدی موردنیاز برای هر محصول باید مشخص شود. بدین منظور از کدنویسی در داخل مدل شبیه‌سازی استفاده شده است. بر این اساس خصیصۀ مربوط به شمارۀ فرایند برای هر محصول بررسی می‌شود و با توجه به اتمام فرایند موردنظر بر محصول یک واحد به خصیصۀ مرتبط با شمارۀ فرایند افزوده می‌شود. به تبع این افزایش، تغییرات درویژگی مربوط به ماشین بعدی و زمان فرایند موردنیاز برای فرایند بعدی به محصول تخصیص داده می‌شود. در قسمت پایانی این کد، در صورتی که یک محصول تمامی فرایندهای موردنیاز را طی کرده باشد از سیستم خارج می‌شود و در غیر این صورت به بخش سوم تحویل داده می‌شود تا وارد صف ماشین موردنیاز بعدی شود.

  • · بخش ششم: مرحلۀ ثبت اطلاعات زمان اتمام و تأخیرها

در این مرحله زمان اتمام تولید محصول و میزان تأخیر هر پاسخ تولیدشده براساس خصیصۀاولویت‌دهی ثبت می‌شود و مقدار تابع هدف براساس رابطۀ (3)به دست می‌آیدو در اختیار بخش بهینه‌سازی قرار می‌گیرد.

4- نتایج محاسبات

رویکرد پیشنهادی در سه مرحله ارزیابی شده است. در مرحلۀ اول روش پیشنهادی با قسمتی از روش‌های فرااِبتکاری جدید موجود مقایسه شده است. در مرحلۀ دومکیفیت و زمان حل نتایج حاصل از روش پیشنهادیبا روش‌های دقیق حل مسئله بررسی شده و در مرحلۀ بعدی رویکرد پیشنهادی روی یک سیستم پویای غیرقطعی اجرا شده است.

1-4-مقایسۀ نتایج حاصل برای مسائل معیار با سایر روش‌های فرااِبتکاری موجود

در این بخش سعی می‌شودعملکرد روش پیشنهادی در همگرایی به مقادیر بهینه با قسمتی از الگوریتم‌های متاهیورستیک جدید پیشنهادشده مقایسه شود.

 برای این کار از روش‌هایی که اسدزاده و همکاران (2010)، کیساری و همکاران (2013) و بانهارنساکون و همکاران (2010) پیشنهاد کرده‌اند، استفاده شده است. آنها به‌ترتیب از تکنیک‌های الگوریتم ژنتیک، کولونی مورچه([xlii]ABC) و بهینه‌سازی براساس تدریس- آموزش([xliii]TLBO) برای حل مسئله استفاده کرده‌اند.

برای تعیین سه عامل تعداد جمعیت اولیه، درصد تقاطع و درصد جهشِ الگوریتم ژنتیک در این قسمت از روش تاگوچی استفاده شده است؛بدین صورت که برای هر کدام از عوامل ذکرشده 4 سطح و برای هر سطح 3 تکرار در نظر گرفته شد و با درنظرگرفتن مقادیر کوچک‌تر- بهتر[xliv]مناسب‌ترین مقدار برای این سه عامل با 100 مرتبه اجرای الگوریتم ژنتیک و استفاده از روش تاگوچی به‌صورت جدول 2 حاصل شد.

جدول(2): پارامترهای الگوریتم ژنتیک

مقدار

پارامتر

100

تعداد تکرارها

30

جمعیت اولیه

70/0

درصد تقاطع

15/0

درصد جهش

نتایج محاسبات بر مسائل Orb01-Orb10کتابخانۀ تحقیق در عملیات[xlv]نشان می‌دهد که روش پیشنهادی مبتنی بر ژنتیک نتایج بهتری نسبت به روش مشابه PaGAتولید می‌کند؛ لیکن نسبت به روش‌های کلونی مورچه و تدریس- آموزش بدتر عمل می‌کند.

2-4- مقایسۀ نتایج حاصل برای مسائل معیار با سایر روش‌های حل دقیق مسئله

            جدول (3): مقایسۀ نتایج حاصل از روش پیشنهادی با تعدادی از الگوریتم‌های متاهیورستیک

مسئله

ابعاد

BKS*

PaGA[31]

ABC[32]

TLBO[33]

روش پیشنهادی

orb01

10 10

1059

1149

1059

1059

1112

orb02

10 10

888

929

888

888

911

orb03

10 10

1005

1129

1005

1005

1054

orb04

10 10

1005

1062

1005

1005

1047

orb05

10 10

887

936

886

886

909

orb06

10 10

1010

1060

1010

1010

1060

orb07

10 10

397

416

397

397

416

orb08

10 10

899

1010

899

899

956

orb09

10 10

934

994

934

934

942

orb10

10 10

944

-

944

944

961

*Best known solution

در بخش اول سعی شده است رویکرد پیشنهادی روی مسائل معیار تولید کارگاهی سنتی در ابعاد مختلف اجرا شود و با نتایج حاصل از روش‌های دقیق حل مقایسه شود. در این زمینه کلمت و همکارانقسمتی از این مسائل را با دو روش برنامه‌ریزی عدد صحیح مختلط و شبیه‌سازی- بهینه‌سازی حل کرده‌اند و با هم مقایسه کرده‌اند. آنها برای پایان الگوریتم حداکثر زمان اجرا 300 ثانیه را در نظر گرفته‌اند و در صورتی که جواب دقیق بهینه در زمان تعیین‌شده به دست آید، الگوریتم متوقف می‌شود و زمان رسیدن به جواب در داخل پارانتز گزارش می‌شود و در غیر این صورت مقدار تابع هدف حاصل‌شده در 300 ثانیه بدون زمان گزارش می‌شود. به‌دلیل اینکه زمان رسیدن به جواب دارای حالت تصادفی است آنها الگوریتم ژنتیک را 20 مرتبهاجرا کرده‌اند و از زمان رسیدن به جواب میانگین گرفته‌اند. همین رویه دوباره با روش پیشنهادی اجرا شد و نتایج حاصل برای مقایسه به جدولی که آنها ارائه کرده‌اند، اضافه شد(جدول (4)).

بر اساس نتایج به‌دست‌آمده در واحد زمان، مشخص است که در مسائل با مقیاس کوچک،رویکرد برنامه‌ریزی عدد صحیح مختلط در کوتاه‌ترین زمان ممکن به جواب بهینه مسئلهمی‌رسد؛ ولی الگوریتم شبیه‌سازی-بهینه‌سازی تقریبی از جواب بهینه را ارائه می‌کند. با افزایش ابعاد مسئله به‌تدریج برنامه‌ریزی عدد صحیح مختلط از رسیدن به جواب بهینۀ دقیق باز می‌ماند و روش شبیه‌سازی- بهینه‌سازیجواب‌های بهتری را حاصل می‌کند.

به‌طوری که در مسئلۀ معیاریبا 20ماشین و 100 کار رویکرد برنامه‌ریزی عدد صحیح مختلط قادر به یافتن جواب مناسب برای مسئلهنیست؛ بنابراین با افزایش ابعاد مسئله، رویکرد پیشنهادی حتی بر مسئلۀ سنتی تولید کارگاهی با زمان‌های ورود و فرایند قطعی و بدون درنظرگرفتن عوامل ایجاد عدم‌قطعیت، جواب‌های بهتری نسبت به روشمدل‌سازی تحلیلی ارائه می‌کند. در صورت نزدیک‌ترکردن مسئله به سیستم واقعی تولید، یعنی واردکردن عوامل عدم‌قطعیت و افزایش ابعاد مسئله که بر پیچیدگی مسئله می‌افزاید، روش تحلیلی توانایی خود را از دست خواهد داد.

جدول (4):مقایسه نتایج رویکرد پیشنهادی با روشMIP و روش کلمت و همکاران برای مسائل معیار

جواب مسئله

جواب MIP

(زمان)

نتایج به دست آمده توسط کلمت و همکاران (زمان)

جواب حاصله

(زمان)

تعداد

محدودیت‌ها

تعداد متغیرهای باینری

کار

 

ماشین

مسئله

555

55 (0/2s)

58

58

216

90

6 6

FT06

666

666 (5/5s)

666 (5/5s)

666 (12/7s)

500

225

10 5

LA01

593

593 (6/1s)

-

593 (8/28s)

500

225

10 5

LA05

943

943 (15s)

973

977

1000

450

10 10

ABZ6

951

951 (50/6s)

951

951 (50/39s)

1125

525

15 5

LA09

1046

1102

1113

1126

2250

1050

15 10

LA21

927

942

986

992

2250

1050

  15 10

LA22

1218

1334

1296

1298

4000

1900

20 10

LA26

1235

1439

1351

1346

4000

1900

20 10

LA27

1787

1912

1809

1824

9000

43500

30 10

LA31

-

-

6144

6163

200000

99000

100 20

TA71

3-4- نتایج حاصل برای مسئلۀ پویا

در ادامۀ روند ارزیابی متد پیشنهادی بر مسائل تولید کارگاهی یک سیستم تولیدی با شرایط ذکرشده در قسمت 3-1 با استفاده از شبیه‌سازی مدل شده است و سعی شده با الگوریتم ژنتیک اولویت‌دهی به کارها به‌گونه‌ای انجام شود که تابع هدف تعریف‌شدهدر رابطۀ 3 مینیمم شود. شرایط خاتمه برای الگوریتم ژنتیک در این مسئله 100 مرتبه تکرار الگوریتم در نظر گرفته شده است و بعد از 100 مرتبه تکرار بهترین جواب به‌دست‌آمده برای مسئله گزارش می‌شود.

مهم‌ترین مزیت مقایسۀ نتایج با مسائل معیار، امکان مقایسۀ نتایج به‌دست‌آمده با جواب‌های موجود برای مسائل معیار است. در صورتی که داده‌های تصادفی در مسئله اثرگذار باشد تولید نتایج قبلی تقریباً غیرممکن خواهد بود. از طرفی برای سنجش میزان بهبود حاصل‌شده توسط رویکرد پیشنهادی نیاز است نتایج حاصل با سایر نتایج به‌دست‌آمده مقایسه شود. بر این اساس برای مقایسۀ نتایج به‌دست‌آمده با ثابت درنظرگرفتن سایر عوامل، مدل شبیه‌سازیمسئله با پنج روش اولویت‌دهی رایج در ادبیات مسئله(FIFO، LIFO،SPT ،LPT، CR)مقایسه شده است. نتایج به‌دست‌آمده نشان می‌دهد روش کوتاه‌ترین زمان فرایند (SPT) بین روش‌های سنتی اولویت‌دهی به کارها،جواب‌های مناسب‌تری را برای مسئله حاصل می‌کند.مقایسۀروش‌های سنتی اولویت‌دهی به کارها با رویکرد پیشنهادی نشان می‌دهد استفاده از رویکرد پیشنهادشده در سیستم موجب کاهش مقدار تابع هدف مسئلهمی‌شود.

5- نتیجه‌گیری و پیشنهادها برای مطالعات آتی

 

در این مقاله روش‌های مختلف مدل‌سازی و حل مسائل تولید کارگاهی در دو دستۀ کلی روش‌هایشبیه‌سازی و روش‌های تحلیلی طبقه‌بندیشد و به تشریح روشبهینه‌سازی براساس شبیه‌سازی برای حل

 

مسئلۀ تولید کارگاهی پرداخته شد. در ادامه روشی برای اولویت‌دهی به کارها در سیستم تولید کارگاهی پیشنهاد شد که با استفاده از آن می‌توان انواع مسائل قطعی و احتمالی تولید کارگاهی با شرایط مختلف را مدل‌سازیکرد و توالی مناسب را برای آن به دست آورد.

جدول (5):نتایج به‌دست‌آمده برای مسئلۀ پویا با پارامترهای تصادفی

CR

LPT

SPT

LIFO

FIFO

روش پیشنهادی

شماره مسئله

 کار

36/790

7/1369

24/482

71/783

57/585

30/415

1

8 50

3/827

1/1408

54/546

21/847

88/634

01/503

2

9/810

1426

46/553

12/924

2/689

2/492

3

8/3218

6318

3/2183

1/4343

3/3747

8/1986

1

8 100

4/3408

1/6485

2/2367

6/4486

7/3886

2061

2

3/3411

9/6545

2/2304

4/4490

11/3911

7/2100

3

16005

28599

15728

23689

18049

15534

1

8 200

17261

30973

16555

25116

19206

16367

2

16683

29447

2/14163

23981

18515

15827

3

در مرحلۀ اول رویکرد پیشنهادی جهت بررسی میزان همگرایی با قسمتی از روش‌های فرااِبتکاری موجود مقایسه شد. در مرحلۀ بعدی این روش بر مسائل معیار موجود در سیستم تولید کارگاهی سنتی اجرا شد و نتایج حاصل از آن با نتایج حاصل از روش برنامه‌ریزی عدد صحیح مختلط مقایسه شد.در مرحلۀ بعد یک سیستم کارگاهی انعطاف‌پذیر با ماشین‌های یکسان در هر ایستگاه که دارای خرابی و دوباره‌کاری نیز هست، در نظر گرفته شد و تابع هدف به‌دست‌آمدۀ ناشی از توالی پیشنهادی، با مقدار تابع هدف ناشی از روش‌های رایج اولویت‌دهی مقایسه شد. این روش محدودیتی در تعیین توالی مناسب برای انواع مسائل تولید کارگاهی ندارد و هر نوع سیستم تولیدی که بتوان آن را با شبیه‌سازی مدل کرد می‌توان با این رویکرد توالی مناسب را برای آن به دست آورد.

در روش پیشنهادی فقط بر تعیین اولویت در صف پشت ماشین‌ها تمرکز شده است؛ در حالی که اگر نوع ماشین‌های موجود در سیستم تولید کارگاهی انعطاف‌پذیر متفاوت باشد باید تعیین شود کدام کار روی کدام ماشین پردازش می‌شود. برای انجام مطالعات آتی در این زمینه می‌توان این امر را نیز وارد مسئلهکرد و دربارۀ اولویت و تخصیص بهینۀ کارها به ماشین‌هاتصمیم‌گیریکرد؛ همچنین برای افزایش کارایی الگوریتم ژنتیک می‌توان قسمتی از جواب‌هایمسئله که به‌دلیل رعایت پیش‌نیاز‌ها نشدنی می‌شوند با درنظرگیری گراف انفصال[xlvi] از فضای جواب مسئله حذف کرد تا سرعت و کارایی اجرای الگوریتم افزایش پیدا کند.

 

 



1Work In Process

2 Bakeret al.

3 Pinedo

4 Garey et al.

5Noor

6 Ji et al.

7 Make To Order

8Mean Time Between Failure

9 Mean Time To Repair

10 Zhang et al.

11 Manne

12 Mixed Integer Programming

13 Liao

14 Balasubramanian

15Tang

16Gao

17 Chen

18Pezzella

19First In First Out

20Shortest Processing

21 Longest Processing Time

22Earliest Due Date

23 Vinod

24 Chan

25Dominic

26Baykasoğlu

27Nolan

28 Sargent

29Holthaus

[30]Klemmt

31 Gholami

32 Kulkarni

33 Rangsaritratsamee

34 Due Date

35 Total Work Continent

36 Paul

37 Fitness Function

38 Toolbox

39 Simevents

40 Simulink

41 Time based entity Generator

42 Artificial Bee Colony

43 Teaching- Learning Optimization

44 Smaller the better

45 OR Library

46 Disjunctive graph

 

Adibi, M. A., Zandieh, M., & Amiri, M. (2010). "Multi-objective scheduling of dynamic job shop using variable neighborhood search". Expert Systems with Applications, 37(1), 282-287.

Amirkhani,F., R. Sahraeian, (2103). "Integrating Simulation and Optimization to Schedule a DynamicJob shop problem", Proceedings of 9th International Conference on Industrial Engineering, Tehran, Iran

Asadzadeh, L., & Zamanifar, K. (2010). "An agent-based parallel approach for the job shop scheduling problem with genetic algorithms". Mathematical and Computer Modelling, 52(11), 1957-1965.

Baker, K. R., & Trietsch, D. (2013). Principles of sequencing and scheduling. John Wiley & Sons.

Balasubramanian, J., & Grossmann, I. E. (2002). "A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times". Computers & Chemical Engineering, 26(1), 41-57.

Banharnsakun, A., Sirinaovakul, B., & Achalakul, T. (2012). "Job Shop Scheduling with the Best-so-far ABC". Engineering Applications of Artificial Intelligence, 25(3), 583-593.

 Baykasoğlu, A., & Özbakır, L. (2010). "Analyzing the effect of dispatching rules on the scheduling performance through grammar based flexible scheduling system". International Journal of Production Economics, 124(2), 369-381.

Chan, F. T. S., Chan, H. K., Lau, H. C. W., & Ip, R. W. L. (2003). "Analysis of dynamic dispatching rules for a flexible manufacturing system". Journal of Materials Processing Technology, 138(1), 325-331.

Chen, J. C., Wu, C. C., Chen, C. W., & Chen, K. H. (2012). "Flexible job shop scheduling with parallel machines using Genetic Algorithm and Grouping Genetic Algorithm". Expert Systems with Applications, 39(11), 10016-10021.

Dominic, P. D., Kaliyamoorthy, S., & Kumar, M. S. (2004). "Efficient dispatching rules for dynamic job shop scheduling". The International Journal of Advanced Manufacturing Technology, 24(1-2), 70-75.

Gao, J., Sun, L., & Gen, M. (2008). "A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems". Computers & Operations Research, 35(9), 2892-2907.

 Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117-129.

Gholami, M., & Zandieh, M. (2009). "Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop". Journal of Intelligent Manufacturing, 20(4), 481-498.

Holthaus, O. (1999). "Scheduling in job shops with machine breakdowns: an experimental study". Computers & Industrial Engineering, 36(1), 137-162.

Ji, M., He, Y., & Cheng, T. E. (2006). "Scheduling linear deteriorating jobs with an availability constraint on a single machine". Theoretical Computer Science, 362(1), 115-126.

Keesari, H. S., & Rao, R. V. (2014). "Optimization of job shop scheduling problems using teaching-learning-based optimization algorithm". OPSEARCH, 51(4), 545-561.

 Klemmt, A., Horn, S., Beier, E., & Weigert, G. (2007, May). "Investigation of modified heuristic algorithms for simulation-based optimization". Proceedings of 30th International Spring Seminar onElectronics Technology, (pp. 24-29). IEEE.

 Klemmt, A., Horn, S., Weigert, G., & Wolter, K. J. (2009). "Simulation-based optimization vs. mathematical programming: A hybrid approach for optimizing scheduling problems". Robotics and Computer-Integrated Manufacturing, 25(6), 917-925.

Kulkarni, K., & Venkateswaran, J. (2014, December). Iterative simulation and optimization approach for job shop scheduling. Proceedings of the 2014 Winter Simulation Conference (pp. 1620-1631). IEEE Press.

Liao, C. J., & Chen, W. J. (2004). "Scheduling under machine breakdown in a continuous process industry". Computers & Operations Research, 31(3), 415-428.

Mahdavi, I., Shirazi, B., & Solimanpur, M. (2010). "Development of a simulation-based decision support system for controlling stochastic flexible job shop manufacturing systems". Simulation Modelling Practice and Theory, 18(6), 768-786.

Manne, A. S. (1960). "On the job-shop scheduling problem". Operations Research, 8(2), 219-223.

Nolan, R. L., & Sovereign, M. G. (1972). "A recursive optimization and simulation approach to analysis with an application to transportation systems". Management Science, 18(12), 676-690.

Noor, S. (2007). Operational scheduling of traditional and flexible manufacturing systems using genetic algorithms, artificial neural networks and simulation, Ph.D Thesis, University of Bradford

Paul, R. J., & Chanev, T. S. (1998). "Simulation optimisation using a genetic algorithm". Simulation Practice and Theory, 6(6), 601-611.

Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). "A genetic algorithm for the flexible job-shop scheduling problem". Computers & Operations Research, 35(10), 3202-3212.

 Pinedo, M. (2005). Planning and scheduling in manufacturing and services (Vol. 24). New York: Springer.

Pinedo, M. L. (2012). Scheduling: theory, algorithms, and systems. Springer Science & Business Media.

Rangsaritratsamee, R., Ferrell, W. G., & Kurz, M. B. (2004). "Dynamic rescheduling that simultaneously considers efficiency and stability". Computers & Industrial Engineering, 46(1), 1-15.

Sargent, R. G. (1994, December). "A historical view of hybrid simulation /analytic models". Proceedings of the 26th conference on Winter simulation (pp. 383-386). Society for Computer Simulation International.

 Shahzad, A., & Mebarki, N. (2012). "Data mining based job dispatching using hybrid simulation-optimization approach for shop scheduling problem". Engineering Applications of Artificial Intelligence, 25(6), 1173-1181.

Tang, J., Zhang, G., Lin, B., & Zhang, B. (2011). "A hybrid algorithm for flexible job-shop scheduling problem". Procedia Engineering, 15, 3678-3683.

Vinod, V., & Sridharan, R. (2011). "Simulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system". International Journal of Production Economics, 129(1), 127-146.

Zhang, R., & Wu, C. (2012). "Bottleneck machine identification method based on constraint transformation for job shop scheduling with genetic algorithm". Information Sciences, 188, 236-252.

 

 

 

پی نوشت: