نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 استادیار گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه اراک، اراک، ایران
2 دانشیار مجتمع دانشگاهی مدیریت و مهندسی صنایع، دانشگاه صنعتی مالک اشتر، تهران، ایران
چکیده
کلیدواژه‌ها
موضوعات
عنوان مقاله [English]
نویسندگان [English]
Purpose: The fundamental function of a cellular manufacturing system (CMS) is based on the definition and recognition of the type of similarity among the parts that should be produced in a planning period. Cell formation (CF) and cell/machine layouts are two major steps in implementing the CMS design. This paper aims to propose a new mathematical nonlinear programming model for cell formation that employs the rectilinear distance concept to determine layout in a continuous space. In the proposed model, the benefits of cellular layout consideration are used, and the objective function computes the cost of cell reconfiguration and the costs of intra-cell and inter-cell material handling movements. Due to its problem complexity, a genetic algorithm (GA) and a particle swarm optimization (PSO) algorithm are proposed to solve the problem. To address the efficiency of the linearized model and solution methods, the production information of a real case study is used and 30 test problems in different dimensions are presented.
Design/methodology/approach: In this paper, a mathematical programming model of cell formation and cell layout has been proposed in a continuous space, using the concept of rectilinear distance. In the proposed model, production information similar to the production flow between machines, alternative process routing, cells capacity, and the inter-cell and intra-cell transportation costs has been considered. Due to the nature and complexity of the proposed model, two metaheuristic algorithms, i.e., GA and PSO have been also developed for larger problems.
Findings: In this paper a real case study in the BATA company was studied and the result of configuration was illustrated. By computing the efficiency of the linearized model and solution methods, the production information of a real case study was used and 30 test problems in different dimensions were presented. Findings highlighted the high efficiency of the genetic algorithm in solving large-scale problems.
Research limitations/implications: Issues such as assuming similar dimensions for machines or their constant availability are considered as the limitations of this study. For future research, the following subjects can be attractive and the present study can provide the necessary background for researchers who seek to work on such subjects:
Considering unequal dimensions for machines; in the proposed model, machines were considered as squares of equal area with unit dimension. To obtain a more appropriate schema from the space of a job shop, machines’ dimensions can be assumed as the input parameters.
Developing probabilistic models and fuzzy model factors (e.g., available machines, operation time, costs, transportation time, and demand for each part) can be considered fuzzy or probabilistic.
To make the model more realistic, production data such as setup times and holding inventory between periods can be incorporated. Also, the proposed model can be integrated with the scheduling problem.
Practical implications: CMS, which is the most important application of GT, overcomes the inefficiency of traditional approaches by reducing transportation time and distance. A flow shop layout has high efficiency in a mass production system, while a job shop is a very flexible system for producing various parts. Each of these systems does not have any other benefits. The CMS is an approach between the two manufacturing systems and aims to improve flexibility and efficiency to produce manufacturing groups in different sizes. In a CMS, machines and parts assignment to cells must impose a minimum cost on the system. Due to the practical nature of the proposed mathematical model, a real case was studied in which, the production information of the BATA company was used.
Originality/value: In this study, a new non-linear mixed-integer programming model was proposed which considered the simultaneous cell formation and intra-cell and inter-cell layouts in a continuous space. The model aimed to determine the cell formation and the intra and inter-cell layout concurrently in a way that the total transportation cost of parts and the reconfiguration cost of cells were minimized. The proposed model attempted at calculating the material handling costs realistically. The material handling cost was computed based on the actual location of machines and cells on the shop floor regarding the dimensions of equal-sized machines. Handling both intra/intercellular materials using batch sizes for transferring parts was taken into account in calculating the transportation cost. The transportation cost was calculated based on the rectilinear travel distance, according to the center-to-center interval among machines.
کلیدواژه‌ها [English]
در دنیای کنونی به‌دلیل افزایش قدرت انتخاب مشتری و گسترش بازارهای رقابتی، سازمانها مجبور به اصلاحاتی در ساختار خودند. شرکتها به‌دلیل فشار بازار و رقابت تنگاتنگ، بایستی کارآیی و بهرهوری بالایی داشته باشند و از تمام منابع خود مانند مواد اولیه، سرمایه و نیروی انسانی بهطور مؤثر استفاده کنند و هزینه‌های خود را کاهش دهند. در این بین بازنگری و بهینه‌سازی نوع سیستم تولیدی در بنگاههای تولیدی بهمنظور کمینه‌کردن هزینه‌ها، برای ماندن در شرایط رقابتی از ملزومات به شمار میرود. تکنولوژی گروهی[i] یکی از فلسفههای تولید است که هدف آن تعیین، طبقه‌بندی و تخصیص قطعات به گروهها و خانوادههای قطعات[ii] و نیز تخصیص ماشین‌ها به سلولهایی برای تولید این خانواده از قطعات است. این فرآیند براساس خصوصیات قطعات و شباهتشان (ضریب تشابه[iii]) در تولید و طراحی انجام میگیرد.
سیستم تولید سلولی[iv] (CMS) که مهم‌ترین کاربرد تکنولوژی گروهی محسوب می‌شود، ابزاری کارا برای بهبود بهرهوری و انعطافپذیری تولید دستههای کوچک تا متوسط گونههای مختلف قطعات به شمار میرود. تولید سلولی بر ناکارآمدی روشهای سنتی، ازطریق کاهش در مسافت و زمان حمل‌ونقل غلبه می‌کند. طراحی چیدمان به‌صورت خط تولید[v]، کارآیی بالایی در سیستم تولید انبوه دارد؛ در حالی که تولید کارگاهی[vi]، سیستم بسیار منعطفی برای تولید قطعات متنوع است. بهعبارتی میتوان گفت در هریک از این دو سیتم قوت و ضعفی وجود دارد؛ انعطافپذیری بالا در سیستم تولید کارگاهی و حجم تولید مناسب در سیستم خط تولید، قوت محسوب می‌شوند. CMS روشی مابین این دو نوع سیستم تولید است که انعطاف و کارآیی لازم برای ساخت دستههای تولیدی با اندازههای مختلف را داراست. تخصیص ماشین‌ها و قطعات به سلول‌ها باید بهگونهای صورت گیرد که کمترین هزینه را به سیستم تحمیل کند. پس از مشخص‌شدن تخصیص ماشین‌ها و قطعات باید مکان قرارگیری ماشین‌ها را مشخص کرد. این موضوع با عنوان جانمایی سلولی[vii] مطرح می‌شود. در ادامه مطالعات اخیر در این حوزه بررسی می‌شود.
تحقیقات صورت‌گرفته در مسئلۀ تشکیل سلول به دو دستۀ زیر طبقه‌بندی می‌شود:
ازجمله اساسیترین تحقیقاتی که در طراحی CMSs انجام شده است، به موارد ذیل اشاره می‌شود:
کارتیکیان و همکاران[viii] (2016) یک سیستم تولید سلولی را با تغییر مقدار تقاضا در دوره‌های مختلف زمانی با الگوریتم‌های فراابتکاری طراحی کردند. تابع هدف این تحقیق شامل، به کمینه‌کردن هزینۀ نگهداری، هزینۀ سفارش بازگشت، هزینۀ ماشین و هزینۀ حقوق و دستمزد بود. نتایج محاسباتی حاصل از این تحقیق نشان داد الگوریتم ازدحام ذرات[ix] (PSO)، کارآیی بالاتری نسبت‌به الگوریتم ژنتیک[x](GA) دارد. گل‌محمدی و همکاران[xi] (2016) یک مسئلۀ تولید سلولی را در یک محیط پویا با رویکرد چیدمان تسهیلات طراحی کردند. آنها برای ساده‌ترشدن مدل فرض کردند که هزینه‌های حمل‌ونقل درون و برون سلولی ثابت است. آنها برای حل مدل از یک GA سلسله‌مراتبی استفاده کردند. ایمران و همکاران[xii] (2017) در مقاله‌ای به کمینه‌سازی هزینه‌ها در یک مسئلۀ تولید سیستم سلولی با استفاده از یک الگوریتم ژنتیک ترکیبی[xiii] (HGA) پرداختند، این الگوریتم ترکیبی از الگوریتم شبیه‌سازی تبرید[xiv] (SA) و الگوریتم GA بود. نتایج حل مدل با استفاده از این الگوریتم، بهبود 55/8% خروجی مدل نسبت‌به الگوریتم‌های دیگر بود. کومار و سینگ[xv] (2017) یک مدل سیستم تولید سلولی طراحی کردند و برای حل مدل خود از یک الگوریتم دومرحلهای استفاده کردند که هدف آن کاهش هزینه‌های کل سیستم بود. سولکی و ارکات[xvi] (2018) یک مسئلۀ CMS برای انتخاب مکان مناسب برای هریک از تسهیلات و فرآیندهای تولید پیشنهاد دادند. آنها در این مقاله خود، یک مدل برنامه‌ریزی خطی عدد صحیح مختلط برای یکپارچه‌سازی بخش‌های تولید، توزیع و تأمین در زنجیرۀ تأمین سه‌سطحی ارائه دادند و از الگوریتم بهینه‌سازی جهش ژنتیکی ترکیبی استفاده کردند. نتایج حاصل از تحقیق نشان از کارآیی بالای این الگوریتم در مقایسه با الگوریتم ژنتیک بود. ایگبال و گمدی[xvii] (2018)، بهینه‌سازی انرژی مرتبط را با تخصیص فرآیندهای تولید به ماشین‌های مختلف و دستهبندی ماشین‌آلات در سلول‌های مختلف برای کمینه‌کردن فاصلۀ حمل‌ونقل قطعات ارائه کردند. گل‌محمدی و همکاران (2018) یک مدل ریاضی برای مسئلۀ چیدمان در سیستم‌های تولید سلولی با در نظر گرفتن قابلیت اطمینان ماشین‌ها ارائه کردند؛ در مدل ارائه‌شده فرض بر آن بود که فاصلۀ زمانی خرابی بین ماشین‌ها از یک توزیع نمایی پیروی می‌کند. آرگیش و همکاران[xviii] (2018) یک مدل ریاضی غیرخطی عدد صحیح مختلط برای طراحی CMS پیشنهاد دادند. مدل آنها شامل عناصری نظیر تشکیل سلول، طرح‌بندی سلولی و تخصیص اپراتور و ابزار بود. تابع هدف مسئله شامل کمینه‌سازی هزینه‌های کل سیستم تولید سلولی بود. آنها برای حل مسئله از الگوریتم شاخه و کران[xix] (B&B) در اندازۀ کوچک و الگوریتم‌های بهینه‌سازی ازدحام ذرات، تکامل دیفرانسیلی و پروانه-آتش در اندازۀ بزرگ‌تر استفاده کردند. نتایج حاصل از تحقیق نشان‌دهندۀ عملکرد بالای الگوریتم بهینه‌سازی ازدحام ذرات نسبت‌به الگوریتم‌های تکامل دیفرانسیلی و پروانه-آتش بود. گل‌محمدی و همکاران (2020) با ارائۀ یک مدل ریاضی، قطعیت‌نداشتن تقاضا را برای مسئلۀ تشکیل سلول و چیدمان ماشین‌آلات تحت شرایط فازی بررسی کردند و یک الگوریتم ژنتیک برای حل آن ارائه دادند.
ازجمله مهم‌ترین تحقیقاتی که در ارائۀ روشهای حل در طراحی سیستم‌های سلولی انجام گرفته است، به‌صورت خلاصه به تحقیقات ذیل اشاره می‌شود:
چاندرزخاران و راجاگپالان[xx] (1993) از روش مقیاسبندی چندبعدی برای حل مسئلۀ چیدمان سلول‌ها استفاده کردند. آنها حجم تولید محصولات و ابعاد سلول‌ها را ثابت در نظر گرفتند و فرض کردند که ماتریس قطعه - ماشین که یکی از ورودیهای مسئله است به روش ZODIAC به دست آمده است. توکلیمقدم و همکاران در سال (2008) مسئلۀ چیدمان سلول‌ها و چیدمان درون‌سلولی را در شرایطی که میزان تقاضا به‌صورت غیرقطعی در نظر گرفته می‌شود به‌صورت یک مدل غیرخطی تخصیص مضاعف دوهدفه[xxi] (bi-QAP) درآوردند و پس از خطیکردن آن با استفاده از Lingo، آن را برای مسائل مختلف حل کردند. در مقالۀ آنها میزان تقاضا از توزیع نرمال[xxii] پیروی می‌کند، اندازۀ ماشین‌ها یکسان در نظر گرفته می‌شود و سلول‌ها استقرار Uشکل دارد. بجستانی و همکاران[xxiii] (2009)، مدل برنامه‌ریزی چندمعیاره برای تشکیل سلول ارائه داده‌اند. مؤلفان مدل ارائه‌شده را با استفاده از الگوریتم جست‌وجوی پراکنده[xxiv] حل کردند و نشان دادند الگوریتم جست‌وجوی پراکنده برای این مسئله، بهتر از الگوریتم ژنتیک چندمعیاره عمل می‌کند. دیکزیت و میشرا[xxv] (2009) الگوریتم CLASS مهدوی و مهادوان را توسعه دادند. نوری و هانگ[xxvi] (2013) برای نخستین‌بار یک الگوریتم بهینه‌سازی مبتنی بر باکتری جست‌وجوگر را برای مسئلۀ تشکیل سلول، برای زمانی ارائه دادند که تغییرات بار برای ماشین‌ها وجود دارد و آن را با دیگر الگوریتم‌های ارائه‌شده مقایسه کردند. چاندرزکار و ونکومار[xxvii] (2013) یک HGA را برای طراحی هم‌زمان چیدمان درون‌سلولی و بین‌‌سلولی به کار بردند. دادههای ورودی مدل آنها یک ماتریس قطعه - ماشین بود که توالی عملیات قطعات نیز در آن در نظر گرفته شده بود. آنها کارآیی و اثربخشی الگوریتم ارائه‌شده را مقایسه کردند که در مقابل کارهای پیشین انجام شده است. آنها همچنین نشان دادند الگوریتم جدید ارائه‌شده نتایج بهتری را نسبت‌به رویکردهای پیشین ارائه میدهد. شوکلا و همکاران[xxviii] (2019) در مقاله‌ای از مدل شبیه‌سازی برای ارزیابی معیارهای عملکرد سیستم در یک مسئلۀ تولید سلولی استفاده کردند. آنها برای این کار از نرم‌افزار MATLAB استفاده کردند و ارزیابی خود را بر مسئله‌ای با 3 کار و 4 ماشین نشان دادند. ربانی و همکاران (2019) یک مدل ریاضی چندهدفه را برای CMS با در نظر گرفتن قابلیت اطمینان دستگاه‌ها ارائه دادند. در مدل آنها، هدف اصلی یکپارچه‌سازی خانواده (سلول/ قطعه) و نیز اختصاص‌دادن اپراتورها به سلول‌ها بود. تابع هدف اول این مقاله شامل کاهش هزینه‌های کل مربوط به سیستم تولید سلولی و تابع هدف دوم نیز بهرهوری کار و درنهایت، کمینه‌سازی مقدار واریانس بارکاری بین سلول‌های مختلف را بهینه‌سازی می‌کرد. آنها برای حل مسئله نیز در اندازۀ کوچک از نرم‌افزار GAMS و در اندازههای بزرگ‌تر از الگوریتم‌های ازدحام ذرات، تحت شرایط چندهدفه[xxix] (MOPSO) و الگوریتم ژنتیک بر پایۀ ناچیرگی[xxx] (NSGAII) استفاده کردند.
در جدول(1) تعدادی از مشخصترین مقالات بررسی‌شده در مقایسه با یکدیگر آورده شده است.
با بررسی مطالعات بارز در این حوزه، مشخص می‌شود در مطالعات گذشته برای قرارگیری ماشین‌ها در فضای سلول‌های تولیدی، تنها مکانهایی به‌صورت چیدمان خطی در نظر گرفته می‌شوند و ماشین‌ها به این موقعیتها تخصیص داده می‌شوند. بدیهی است که در صورت اختصاص تعدادی ماشین به یک سلول که نتوان صرفاً آنها را به‌صورت خطی جانمایی کرد، این چیدمان در سلول تولیدی به‌صورت Uشکل در میآید که باعث تحمیل هزینه‌های اضافی به سیستم می‌شود. با توجه به این نکته، استفاده از مفهوم فاصله برای محاسبۀ میزان جابه‌جایی قطعات میان دو و یا چند ماشین در یک سلول و یا بیش از یک سلول، بهجای در نظر گرفتن موقعیتهایی برای اختصاص ماشین‌ها به سلول‌های تولیدی، به واقعیترشدن مسئله و محاسبۀ هزینه‌های جابه‌جایی کمک بسزایی می‌کند. مدل پیشنهادی این مقاله علاوه بر مسئلۀ تشکیل سلول، چیدمان ماشین‌آلات را در یک سلول و چیدمان سلول‌ها را در سطح کارگاه تعیین می‌کند. در مدل ارائه‌شده با به‌کارگیری مفهوم فاصله سعی شده است تا مکان دقیق مختصات مرکز ماشین‌آلات در سطح کارگاه تعیین شود و با توجه به توالی ساخت قطعات و حجم تقاضای قطعات، تخمین دقیقتری از هزینه‌ها محاسبه شود.
جدول1- جمعبندی مقالات بررسی‌شده
Table 1- Summary of the literature review
|
روش حل |
معیارهای دستهبندی مقالات |
نویسندگان |
ردیف |
|||||||||
|
توالی عملیات |
حدود کارگاه |
چیدمان بر اساس فاصله |
مسیرهای عملیاتی چندگانه |
ظرفیت ماشین‌آلات |
هزینۀ تغییر مکان ماشین‌آلات |
هزینۀ عملیات ماشین‌آلات |
چیدمان ماشین‌آلات |
ظرفیت سلول |
سال انتشار |
|||
|
GA & PSO |
|
|
|
|
|
|
|
|
|
2020 |
گل‌محمدی و همکاران |
1 |
|
Simulation |
|
|
|
|
|
|
|
|
|
2019 |
شوکلا و همکاران |
2 |
|
GA & PSO |
|
|
|
|
|
|
|
|
|
2018 |
گل‌محمدی و همکاران |
3 |
|
NSGAII MOPSO |
|
|
|
|
|
|
|
|
|
2019 |
ربانی و همکاران |
4 |
|
HGA |
|
|
|
|
|
|
|
|
|
2018 |
سولکی و ارکات |
5 |
|
SA |
|
|
|
|
|
|
|
|
|
2018 |
ایگبال و گمدی |
6 |
|
PSO |
|
|
|
|
|
|
|
|
|
2018 |
ارگیش و همکاران |
7 |
|
HGA |
|
|
|
|
|
|
|
|
|
2017 |
ایمران و همکاران |
8 |
|
Cplex |
|
|
|
|
|
|
|
|
|
2017 |
کومار و سینگ |
9 |
|
GA & PSO |
|
|
|
|
|
|
|
|
|
2016 |
کارتیکیان و همکاران |
10 |
|
GA , GEM |
|
|
|
|
|
|
|
|
|
2016 |
گل‌محمدی و هنرور |
11 |
|
Metaheuristics |
|
|
|
|
|
|
|
|
|
2014 |
باقری و بشیری |
12 |
|
GA, PSO |
|
|
|
|
|
|
|
|
|
2021 |
مقالۀ حاضر |
|
در این بخش مدل مسئلۀ تشکیل سلول با بیان مفروضات، پارامترها، متغیرهای تصمیم، تابع هدف و محدودیتها معرفی می‌شود.
مفروضات مدل به شرح زیر است:
اندیسها و نمادهای به کار رفته در این مدل به شرح زیر است:
|
|
: |
اندیس مربوط به قطعات: |
|
|
|
: |
اندیس مربوط به مسیرهای ساخت قطعه: |
|
|
|
: |
اندیس مربوط به ماشین‌ها: |
|
|
|
: |
عمل ام از مسیر انتخاب‌شده برای قطعۀ : |
|
|
|
: |
اندیس مربوط به سلول‌ها: |
|
|
|
: |
میزان تقاضای قطعۀ یا حجم تولید قطعۀ ؛ |
|
|
: |
تعداد سلول‌های در نظر گرفته شده؛ |
|
|
: |
بیشینۀ تعداد ماشین‌ها در یک سلول؛ |
|
|
: |
تعداد مسیرهای تولید قطعۀ ؛ |
|
|
: |
تعداد عملیات قطعۀ در مسیر تولید ؛ |
|
|
: |
هزینۀ جابه‌جایی بین‌‌سلولی برای قطعۀ ؛ |
|
|
: |
هزینۀ جابه‌جایی درون‌سلولی برای قطعۀ ؛ |
|
|
: |
طول افقی کارگاه (طول کارگاه)؛ |
|
|
: |
طول عمودی کارگاه (عرض کارگاه)؛ |
|
|
: |
مؤلفۀ متغیرهای صفر و یک؛ |
|
|
: |
عدد بزرگ. |
|
|
||
|
|
||
|
|
: |
مؤلفۀ افقی مکان ماشین |
|
|
: |
مؤلفۀ عمودی مکان ماشین |
|
|
: |
مؤلفۀ افقی سمت چپ مکان سلول |
|
|
: |
مؤلفۀ افقی سمت راست مکان سلول |
|
|
: |
مؤلفۀ عمودی پایین مکان سلول |
|
|
: |
مؤلفۀ عمودی بالای مکان سلول |
|
(1) |
|
|
|
|
|
|
|
(2) |
|
|
|
(3) |
|
|
|
(4) |
|
|
|
(5) |
|
|
|
(6) |
|
|
|
(7) |
|
|
|
(8) |
|
|
|
(9) |
|
|
|
(10) |
|
|
|
(11) |
|
|
|
|
|
|
تابع هدف مدل بالا (رابطۀ 1)، مجموع هزینۀ جابه‌جایی قطعات را محاسبه می‌کند. این هزینه شامل دو بخش هزینۀ جابه‌جایی بین‌‌سلولی و هزینۀ جابه‌جایی درون‌سلولی است. محدودیت اول (رابطۀ 2)، هزینۀ جابه‌جایی بین‌‌سلولی را محاسبه می‌کند. این محدودیت به هر جفت ماشین متوالی که در دو سلول متفاوت قرار دارند، یک جابه‌جایی بین‌‌سلولی را تخصیص میدهد. محدودیت دوم (رابطۀ 3)، هزینۀ جابه‌جایی درون‌سلولی را محاسبه می‌کند. این محدودیت به هر جفت ماشین متوالی که در یک سلول واحد قرار دارند، یک جابه‌جایی درون‌سلولی را تخصیص میدهد. محدودیت سوم (رابطۀ 4) تضمین می‌کند که به هرکدام از قطعات تنها یک مسیر عملیاتی اختصاص یابد. محدودیت چهارم (رابطۀ 5) نشان میدهد هر ماشین فقط باید به یک سلول اختصاص یابد. محدودیت پنجم (رابطۀ 6) تضمین می‌کند که بیشینۀ تعداد ماشین‌های قرار گرفته شده در هر سلول از مقدار تجاوز نکند. محدودیت (7) سبب همپوشانی‌نداشتن ماشین‌ها می‌شود؛ به عبارت دیگر این رابطه تضمین می‌کند که ماشین‌ها بر یکدیگر قرار نگیرند. (ابعاد ماشین‌ها 1×1 فرض شده است). مجموعۀ روابط (8) باعث می‌شوند هر ماشین درون فضای سلول متناظر خود قرار گیرد. مجموعۀ روابط (9) تضمین می‌کنند که سلول‌ها درون فضای کارگاه قرار گیرند. مجموعۀ روابط (10) تضمین می‌کنند که سلول‌ها بر هم قرار نمیگیرند. بهعبارتی این مجموعه روابط، باعث همپوشانی‌نداشتن سلول‌ها می‌شوند. محدودیت آخر (رابطۀ 11) نشان میدهد متغیرهای و متغیرهای دودویی و دیگر متغیرها مثبت و صحیح‌اند. تابع هدف و برخی محدویتهای مدل شکل غیرخطی دارند. برای تبدیل تابع هدف غیرخطی ارائه‌شده به یک تابع هدف خطی از تغییر متغیر زیر استفاده می‌شود.
مدل ارائه‌شده به‌دلیل وجود تابع قدر مطلق و همچنین حاصلضرب متغیرهای صفر و یک شکل غیرخطی دارد. برای تبدیل حاصلضرب متغیرهای دودویی در تابع هدف ارائه‌شده به یک تابع هدف خطی، از تغییر متغیرهای زیر استفاده شده است:
|
(12) |
|
|
(13) |
|
زمانی برابر با یک خواهد بود که مسیر عملیاتی برای قطعۀ انتخاب شود و عمل ام در سلول و عمل ام در سلول پردازش شود. زمانی برابر با یک خواهد بود که مسیر عملیاتی برای قطعۀ انتخاب شود و عمل و ام در سلول پردازش شود. با در نظر گرفتن متغیرهای جدید در تابع هدف، محدودیتهای زیر به مدل اضافه می‌شوند که روابط (14) تا (17) به‌ترتیب محدودیتهای متناظر با متغیر جدید و اند.
|
(14) |
|
|
|
(15) |
|
|
|
(16) |
|
|
|
(17) |
|
|
همچنین برای خطی‌سازی قدر توابع مطلقی از تعاریف و روابط زیر استفاده می‌شود:
|
|
(18) |
|
|
(19) |
|
|
(20) |
|
|
(21) |
از تعاریف بالا به‌راحتی میتوان نتیجه گرفت که:
|
|
(22) |
|
|
(23) |
|
|
(24) |
|
|
(25) |
با جایگذاری مقادیر به دست آمده، مدل مسئلۀ چیدمان با در نظر گرفتن جابهجاییهای درون و بین‌‌سلولی در یک فضای پیوسته به شکل زیر مطرح می‌شود:
|
(26) |
|
||
|
|
|||
|
(27) |
|
||
|
(28) |
|
||
|
(29) |
|
|
|
|
(30) |
|
|
|
|
(31) |
|
|
|
|
(32) |
|
|
|
|
(33) |
|
|
|
|
(34) |
|
|
|
|
(35) |
|
|
|
|
(36) |
|
|
|
|
(37) |
|
|
|
|
(38) |
|
|
|
|
(39) |
|
|
|
|
(40) |
|
|
|
|
(41) |
|
|
|
|
|
|
||
بهمنظور اعتبارسنجی مدل، از اطلاعات تولیدی مربوط به ماشین‌آلات و برخی محصولات شرکت BATA استفاده شده است. BATA در سال 1935 با تولید روزانه 168000 جفت کفش و 6500 کارگر تمام‌وقت، یکی از بزرگ‌ترین شرکتهای اروپایی شناخته شد. این شرکت با تولید در 18 کشور و 5300 نمایندگی فروش در اروپا، آسیا و آمریکا، برترین شرکت بینالمللی تولید کفش شناخته می‌شود.
براساس اطلاعات مطالعۀ موردی، یک مسئله شامل 8 ماشین، 14 قطعه و 25 مسیر عملیاتی ارائه شده است. بیشینۀ تعداد ماشین‌ها در هر سلول برابر با 4 است و تعداد سلول برابر با 2 در نظر گرفته شده است. اطلاعات تولیدی موردنیاز در جدول (2) و پارامترهای مدل در جدول (3) آورده شده است. پیکربندی و ساختار سلولی به دست آمده در جدول (4) و شکلهای (1) و (2) نشان داده شده است. در جدول (2) به‌ترتیب از چپ به راست، ستون اول نشانگر شمارۀ قطعات است که در این مسئله 14 قطعه در نظر گرفته شده است. ستون دوم میزان تقاضای هریک از قطعات و ستون سوم تعداد مسیرهای عملیاتی را نشان میدهد که هر قطعه میتواند داشته باشد؛ برای مثال قطعۀ شمارۀ 10 با 75 واحد تقاضا ازطریق سه‌مسیر پردازش می‌شود. توالی ساخت هرکدام از قطعات و زمان پردازش هریک از ماشین‌آلات بر هرکدام از قطعات در ستونهای چهارم و پنجم این جدول آورده شده است. جدول (3) مقادیر تنظیم‌شده را برای هرکدام از پارامترهای مسئله مشخص می‌کند. و اندازۀ مسئلۀ تعریف‌شده را نشان میدهد که در این مسئله به‌ترتیب برابر با 8 و 14 است. و ضرایب هزینۀ جابه‌جایی درون‌سلولی و بین‌‌سلولی را تعیین می‌کنند. طبیعی است که میزان ضریب هزینۀ جابه‌جایی بین‌‌سلولی به مراتب بیشتر از ضریب هزینۀ جابه‌جایی درون‌سلولی است. به عبارت دیگر جابه‌جایی بین‌‌سلولی مربوط به قطعاتی است که مجموعۀ عملیات موردنیاز آنها در یک سلول به اتمام نمیرسد و برای تکمیل فرآیند ساخت، نیازمند حرکت در بین سلولهااند. این قطعات را در اصطلاح قطعات استثنا[xxxi] مینامند. مدل ارائه‌شده میکوشد تعداد این قطعات را کمینه کند. در مثال ارائه‌شده مقادیر این دو پارامتر هزینۀ جابه‌جایی از توزیع یکنواخت پیروی می‌کند که در جدول (2) نشان داده شده است. تعداد سلول‌ها در این مسئله برابر 2، حداکثر تعداد ماشین‌ها در هر سلول برابر 4 و ابعاد کارگاه در این مسئله یک مربع به طول 4 است.
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
1 |
2 |
1 |
1 |
2 |
1 |
B.R |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
M/P |
|
|
|
1 |
|
|
1 |
1 |
1 |
|
1 |
|
1 |
|
|
|
|
|
1 |
|
|
1 |
|
|
1 |
|
|
1 |
1 |
|
1 |
|
|
|
|
|
|
1 |
|
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
|
|
1 |
|
1 |
|
|
1 |
1 |
|
1 |
|
1 |
|
1 |
1 |
|
|
1 |
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
|
|
|
1 |
|
1 |
|
|
1 |
1 |
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
شکل 1- ماتریس قطعه ماشین بهینه برای مسئله با 14 قطعه و 8 ماشین
Fig. 1 - Optimal machine-part matrix for problem 8*14
جدول 2- اطلاعات تولیدی برای مسئله با ابعاد 14× 8
Table 2. Production information for the problem 8*14
|
تقاضا |
مسیر تولید |
توالی ساخت |
زمان پردازش (دقیقه) |
|
|
1 |
110 |
1 |
6—5—3—4 |
6—6—2—5 |
|
2 |
120 |
1 |
3—1—4—5 |
5—7—3—7 |
|
2 |
5—3—6 |
3—6—7 |
||
|
3 |
100 |
1 |
4—2—5 |
3—6—6 |
|
2 |
3—7—1—8 |
2—4—4—3 |
||
|
4 |
125 |
1 |
5—4—6 |
6—3—7 |
|
2 |
7—6 |
2—6 |
||
|
5 |
110 |
1 |
8—3—7 |
6—2—6 |
|
6 |
135 |
1 |
2—1—3 |
4—3—5 |
|
2 |
5—3—2 |
5—2—7 |
||
|
7 |
80 |
1 |
3—8—2—6 |
7—3—3—6 |
|
8 |
110 |
1 |
6—5—7 |
6—5—7 |
|
9 |
80 |
1 |
3—1—4 |
5—6—6 |
|
10 |
75 |
1 |
5—2—3—4 |
3—5—3—3 |
|
2 |
3—4—2 |
5—5—7 |
||
|
3 |
4—3—6—2 |
7—3—6—6 |
||
|
11 |
90 |
1 |
5—6—2 |
5—6—3 |
|
2 |
6—2—8 |
5—6—4 |
||
|
3 |
5—4—1—2 |
7—3—3—4 |
||
|
12 |
100 |
1 |
6—1—3 |
5—2—2 |
|
2 |
2—3—7—8 |
3—3—6—2 |
||
|
13 |
130 |
1 |
7—6—2 |
7—3—7 |
|
14 |
80 |
1 |
4—5—1 |
7—5—2 |
جدول 3- پارامترهای مدل برای مسئله با ابعاد 14× 8
Table 3. Process of generating parameters for the problem 8*14
|
|
|
|
|
|
|
|
|
|
8 |
14 |
[ 5 ، 1]U |
[40 ، 30]U |
2 |
4 |
4 |
4 |
جدول 4- پیکربندی سلولی و مسیرهای عملیاتی بهینۀ انتخاب‌شده برای پردازش قطعات برای مسئله با ابعاد 14× 8
Table 4. Cell configuration and optimally selected operational routings for processing parts for the problem 8*14
|
سلول‌ها |
1 |
2 |
|
ماشین‌ها |
2 ، 4 ، 5 و 6 |
1 ، 3 ، 7 و 8 |
|
قطعات (بهترین مسیر) |
1(1) ، 2(2) ، 3(1) ، 4(1)، 6(2) ، 8(1) ، 10(2) ، 11(1) ، 13(1) ، 14(1) |
5(1) ، 7(1) ، 9(1) ، 12(1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
#Cell_1 |
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
aisle |
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
#Cell_2 |
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
#Workshop |
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Fig.2 - Optimal configuration of cell formation and cell layout for problem 8*14
همانطور که اشاره شد، با توجه به آنکه مسئلۀ چیدمان در سیستم‌های تولید سلولی جزء مسائل NP-سخت دستهبندی می‌شود (چاندرزخاران و راجاگپالان، 1993)، برای حل مدل در اندازههای بالاتر از الگوریتم‌های فراابتکاری استفاده می‌شود. بررسی مطالعات گذشته نشان میدهد دو الگوریتم GA و PSO جزء متداولترین الگوریتمهاییاند که در زمینۀ CMS به کار گرفته می‌شوند و در مقایسه با دیگر الگوریتمها نتایج مناسبتری را ارائه می‌دهند. همچنین از آنجایی که تمرکز اصلی این مطالعه بر مدلسازی مسئله بوده است، در این مقاله نیز دو الگوریتم مذکور استفاده شده و نتایج حاصل از آنها با یکدیگر مقایسه شده است. نحوۀ استفاده از دو الگوریتم و عملکرد عملگرهای آن و همچنین نتایج عددی حاصل از آنها به شرح زیر است.
4-2-1- ارائۀ الگوریتم ژنتیک پیشنهادی
در این بخش برخی از زوایای الگوریتم ژنتیک و طریقۀ به‌کارگیری آن در طراحی CMS بررسی می‌شود. ویژگیهای خاص این الگوریتم باعث می‌شود نتوانیم آن را یک جست‌وجوگر تصادفی ساده قلمداد کنیم. برخی از تفاوتهای الگوریتم ژنتیک با دیگر روشهای بهینه‌سازی در موارد زیر بیان می‌شود، این تفاوت‌ها موجب برتری نسبی این الگوریتم می‌شود.
در به‌کارگیری الگوریتم ژنتیک، مرحلههای زیر مهم و ضروری‌اند:
کروموزموم در نظر گرفته شده برای این مسئله با در نظرگیری شرایط چیدمان، عبارت است از یک ماتریس با M ستون که این ماتریس به سه قسمت تقسیمبندی می‌شود. ماتریس به‌صورت تصادفی از اعداد بین 1 تا به دست میآید. عناصر ماتریسهای و طوری انتخاب می‌شوند که ماشین‌ها بر هم قرار نگیرند، بهصورتی که اعداد یک ستون از و با ستون دیگری از و ، به‌صورت هم‌زمان مساوی نباشند.
در الگوریتم پیشنهادی عملگر تقاطع، ژنهایی از یک والد را با همان ژنها از والد دیگر جایگزین می‌کند تا دو فرزند شبیه به دو والد متولد شوند. در این مطالعه از عملگر تقاطع یکنواخت استفاده شده است. عملکرد این عملگر به این صورت است که اولین والد از بین بهترین افراد در جامعه انتخاب می‌شود، در حالی که والد دیگر بهطور تصادفی از بین جمعیت انتخاب می‌شود؛ سپس یک ردیف عدد تصادفی به تعداد طول کروموزوم (تعداد ژنها) بهطور یکنواخت در فاصلۀ صفر تا یک تولید می‌شود. اگر مقدار تصادفی ایجادشده، بزرگ‌تر از مقدار آستانۀ از پیش تعیین شده به نام احتمال تقاطع[xli] ( ) باشد، از مقدار ژن والد اول برای تولید فرزند اول استفاده می‌شود و در غیر این صورت از ژن والد دوم برای ژن متناظر فرزند اول استفاده می‌شود.
در این مقاله ساختار کروموزومها بهگونهای طراحی شده است که با توجه به تعریف نوع متغیرها و مقادیر مجاز مقداردهی، به‌جز دستۀ محدودیت شمارۀ 8، دیگر محدودیتها را در خود دارد و هرگز نقض نمیشود. اما محدودیت نام برده شده در فوق را با استفاده از جریمۀ تابع هدف به سمت شدنی‌بودن جواب مسئله حرکت میدهیم؛ به اینصورت که مقدار تابع هدف به دست آمده را با مقدار جریمۀ به دست آمده جمع می‌کنیم و مقدار حاصل را ارزش کروموزوم در نظر میگیریم و هرچه این مقدار کمتر باشد، کروموزوم ارزش بهتری دارد. مقدار جریمه پویاست؛ یعنی در تکرارهای اولیه مقدار جریمه کم و در تکرار های پایانی جریمه سنگین است.
برای انتخاب اعضای نسل بعد از مکانیسم چرخ رولت[xlii] استفاده شده است. شرط توقف استفاده‌شده در این الگوریتم، رسیدن به تعداد تکرارهای مشخص نسلهاست.
4-2-2- الگوریتم بهینه‌سازی ازدحام ذرات
الگوریتم PSO یکی از تکنیکهای بهینه‌سازی است که برای مواجهه با مسائلی به کار میرود که در آنها بهترین جواب به‌صورت یک نقطه یا یک سطح در فضای بُعدی باشد (کندی، 1997). در ابتدا مجموعۀ اعضا[xliii] در فضای جواب قرار میگیرند و با سرعت اولیهای شروع به حرکت می‌کنند، سپس این اعضا در فضای جواب حرکت می‌کنند و بر طبق معیار خاصی در هر مرحله ارزیابی می‌شوند. با گذشت زمان، این اعضا به سمت دیگر اعضای موجود در گروه ارتباطی خود شتاب میگیرند که مقدار بالاتری برای برازندگی دارند. یکی از مزایای این روش بر دیگر روشهای موجود در رابطه با کمینه‌سازی این است که وجود تعداد زیادی از اعضا باعث می‌شود این الگوریتم نسبت‌به پدیدۀ نقطۀ بهینه محلی به مقدار درخور توجهی پایدار باشد. فلوچارت الگوریتم PSO در شکل (5) نشان داده شده است.
|
|
Fig. 5 - Flowchart of the PSO
در یک فضای جست‌وجوی بعدی، اُمین ذره در این فضا با بردار موقعیت به شکل زیر توصیف می‌شود:
|
(42) |
|
بردار سرعت اُمین ذره نیز به شکل زیر تعریف می‌شود:
|
(43) |
|
بهترین موقعیتی را که ذرۀ اُم پیدا کرده است با تعریف می‌شود:
|
(44) |
|
بهترین موقعیتی را که بهترین ذره در بین کل ذرات پیدا کرده است با به‌صورت زیر تعریف می‌شود:
|
(45) |
|
برای بهروزرسانی محل هرکدام از ذرات از رابطۀ زیر استفاده می‌شود:
|
(46) |
|
|
|
که به‌ترتیب داریم:
|
|
: |
ضریب وزنی اینرسی (حرکت در مسیر خودی) که نشان‌دهندۀ میزان تأثیر بردار سرعت تکرار قبل بر بردار سرعت در تکرار فعلی است. |
||
|
|
: |
ضریب ثابت یادگیری (حرکت در مسیر بهترین مقدار ذرۀ بررسی‌شده) |
||
|
|
: |
ضریب ثابت یادگیری (حرکت در مسیر بهترین ذرۀ یافت‌شده در بین کل جمعیت) |
||
|
|
: |
دو عدد تصادفی با توزیع یکنواخت در بازۀ 0 تا 1 |
||
|
|
: |
بردار سرعت در تکرار ام |
||
|
|
: |
بردار موقعیت در تکرار ام |
||
برای جلوگیری از افزایش بیش از حد سرعت حرکت یک ذره در حرکت از یک محل به محل دیگر (واگراشدن بردار سرعت)، تغییرات سرعت در بازۀ تا محدود می‌شود؛ یعنی:
|
(46) |
|
تولید تصادفی جمعیت اولیه بهطور ساده عبارت است از: تعیین تصادفی محل اولیۀ ذرات با توزیع یکنواخت در فضای حل (فضای جست‌وجو). مرحلۀ تولید تصادفی جمعیت اولیه تقریباً در تمامی الگوریتم‌های بهینه‌سازی احتمالاتی وجود دارد؛ اما در این الگوریتم علاوه بر محل تصادفی اولیۀ ذرات، مقداری برای سرعت اولیۀ ذرات نیز اختصاص مییابد. بازۀ پیشنهادی اولیه برای سرعت ذرات از رابطۀ زیر استخراج می‌شود:
|
(47) |
|
افزایش یا کاهش تعداد ذرات اولیه هرکدام مزایا و معایبی دارد. افزایش تعداد ذرات اولیه موجب کاهش تعداد تکرارهای لازم برای همگراشدن الگوریتم می‌شود. هرچند که افزایش تعداد ذرات اولیه کاهش تعداد تکرارها را در پیدارد، اما این امر باعث می‌شود که الگوریتم در مرحلۀ ارزیابی ذرات، زمان بیشتری را صرف کند که این افزایش در زمان ارزیابی باعث می‌شود زمان اجرای الگوریتم تا رسیدن بههمگرایی با وجود کاهش در تعداد تکرارها کاهش نیابد. همچنین اگر تعداد ذرات را کاهش دهد برای اینکه الگوریتم به جواب بهینه برسد، تعداد تکرارها افزایش مییابد و باعث می‌شود زمان اجرای برنامه کاهشی نداشته باشد. همچنین با کاهش تعداد ذرات ممکن است الگوریتم در بهینههای محلی[xliv] گیر بیفتد و از رسیدن به مینیمم اصلی باز بماند. از این رو لازم است در مورد حتماً تحلیل حساسیت صورت گیرد و در این مقاله با بهرهگیری از طراحی آزمایشها[xlv] این مهم صورت گرفت.
در این مرحله باید هریک از ذرات را ارزیابی کنیم که نشان‌دهندۀ یک حل برای مسئلۀ بررسی‌شده است. بسته به مسئلۀ بررسی‌شده، روش ارزیابی متفاوت خواهد بود. مثلاً اگر امکان تعریف یک تابع ریاضی برای هدف وجود داشته باشد، با جایگذاری پارامترهای ورودی، که از بردار موقعیت ذره استخراج شدهاند، به‌راحتی مقدار هزینۀ این ذره محاسبه خواهد شد.
در این مرحله با توجه به شمارۀ تکرار، دو حالت بررسی می‌شود:
اگر در تکرار اول باشیم ، موقعیت فعلی هر ذره را بهترین محل یافت‌شده برای آن ذره در نظر میگیریم.
|
(48) |
|
|
(49) |
|
در دیگر تکرارها، مقدار هزینۀ به دست آمده برای ذرات در مرحلۀ 2 را با مقدار بهترین هزینۀ به دست آمده برای تکتک ذرات مقایسه می‌کنیم. اگر این هزینه کمتر از بهترین هزینۀ ثبت‌شده برای این ذره باشد، آنگاه محل و هزینۀ این ذره جایگزین مقدار قبلی می‌شود، در غیر این صورت تغییری در محل و هزینۀ ثبت‌شده برای این ذره ایجاد نمیشود؛ یعنی:
|
(50) |
|
برای بهروزرسانی ذرهها داریم:
|
(51) |
|
ضرایب ، و با توجه به مسئلۀ مدنظر بهروش تجربی تعیین می‌شوند؛ امّا بهعنوان یک قانون کلی باید کمتر از یک باشد؛ زیرا اگر بزرگ‌تر از یک انتخاب شود، دائماً افزایش مییابد، تا جایی که واگرا شود. هرچند در حالت تئوری ضریب میتواند منفی نیز باشد، اما در استفادۀ عملی از این الگوریتم هیچگاه نباید این ضرایب را منفی در نظر گرفت؛ زیرا منفی‌بودن موجب ایجاد نوسان در می‌شود. و نیز نباید زیاد از حد بزرگ انتخاب شوند؛ زیرا انتخاب مقادیر بزرگ برای این دو ضریب باعث انحراف شدید ذره از مسیر خودی می‌شود. مقدار تنظیم‌شدۀ این پارامترها با روش طراحی آزمایش صورت گرفته و در جدول (6) و شکل (7) نشان داده شده است.
در این بخش مدل ارائه‌شده برای 30 مسئله در تعداد اندازههای مختف، توسط الگوریتم‌های GA و PSO حل شده و زمان حل و کیفیت نتایج حاصل از آنها با نتایج حاصل از حل مدل خطیسازیشده توسط Cplex مقایسه شده است. برای تنظیم پارامتر الگوریتم‌های GA و PSO از روش تاگوچی[xlvi] استفاده شده و سطوح مختلف آن در جداول (5) و (6) نشان داده شده است. الگوریتم‌های ارائه‌شده با استفاده از نرم‌افزار MATLAB کدنویسی شده و با یک کامپیوتر شخصی پنتیوم 4 اجرا شده است. با توجه به وجود متغیرهای دودوئی متعدد، از حلکنندۀ شاخه و کران برای Cplex استفاده شده است. حداکثر زمان اجرا 2 ساعت در نظر گرفته شده و پس از دو ساعت، برنامه قطع شده و بهترین جواب به دست آمده، ثبت و گزارش شده است. تعداد سلول‌ها برای تعداد 3 تا 7 ماشین برابر 2 و برای تعداد 8 تا 12 ماشین، برابر 3 در نظر گرفته شده است. نتایج عددی حاصل از حل مدل در ادامه آورده شده است.
|
جدول 5- سطوح در نظر گرفته شده برای پارامترهای الگوریتم ژنتیک Table 5. Considered levels of parameters of GA |
||||
|
الگوریتم ژنتیک |
پارامتر |
سطح 1 |
سطح 2 |
سطح 3 |
|
تقاطع |
6/0 |
7/0 |
8/0 |
|
|
جهش |
1/0 |
15/0 |
2/0 |
|
|
اندازۀ جمعیت |
50 |
70 |
90 |
|
|
جدول 6- سطوح در نظر گرفته شده برای پارامترهای الگوریتم ازدحام ذرات Table 6. Considered levels of parameters of PSO |
||||
|
الگوریتم ازدحام ذرات |
پارامتر |
سطح 1 |
سطح 2 |
سطح 3 |
|
|
1 |
5/1 |
2 |
|
|
|
1 |
5/1 |
2 |
|
|
ضریب وزنی اینرسی |
3/0 |
6/0 |
9/0 |
|
|
|
|
|
|
|
|
شکل 6- میانگین نسبت (S/N) برای تنظیم پارامترهای الگوریتم GA Fig. 6 - Mean (S/N) ratios for the proposed GA |
شکل 7- میانگین نسبت (S/N) برای تنظیم پارامترهای الگوریتم PSO Fig. 7 - Mean (S/N) ratios for the proposed PSO |
در ادامه 30 مسئله نمونه در اندازههای مختلف ارائه شده است تا نتایج حاصل از آنها با یکدیگر مقایسه شود. با بررسی جداول و شکلهایی که در ادامه نشان داده شده است، نحوۀ تغییر زمان حل و کیفیت جوابهای حاصل‌شده در دو الگوریتم GA و PSO، با افزایش اندازۀ مسائل بهخوبی ملاحظه می‌شود.
جدول 7- مقایسۀ نتایج به دست آمده از الگوریتم‌های GA و PSO و نرم‌افزار Cplex
Table 7. Comparison of the obtained results between GA, PSO & Cplex
|
Cplex |
|
PSO |
|
GA |
|
ابعاد مسئله |
|||||||
|
زمان B&B |
کران پایین |
جواب |
|
میانگین زمان |
بهترین جواب |
میانگین 10 جواب |
|
میانگین زمان |
بهترین جواب |
میانگین 10 جواب |
|
||
|
42 |
24283 |
24283 |
|
9 |
24283 |
24283 |
|
12 |
24283 |
24283 |
|
5×3 |
|
|
317 |
28641 |
28641 |
|
14 |
29120 |
29350 |
|
17 |
28641 |
28641 |
|
6×4 |
|
|
1853 |
1117 |
84253 |
|
19 |
84620 |
85425 |
|
22 |
84180 |
85637 |
|
8×5 |
|
|
7200 |
0 |
121203 |
|
29 |
120996 |
121102 |
|
32 |
116046 |
120903 |
|
9×6 |
|
|
7200 |
0 |
248907 |
|
38 |
228635 |
231325 |
|
42 |
215470 |
224095 |
|
11×7 |
|
|
7200 |
0 |
706036 |
|
60 |
546236 |
562362 |
|
65 |
456124 |
497882 |
|
13×8 |
|
|
7200 |
0 |
771098 |
|
65 |
715625 |
736251 |
|
79 |
664902 |
706813 |
|
12×10 |
|
|
7200 |
0 |
1325097 |
|
119 |
899622 |
936251 |
|
125 |
813358 |
872845 |
|
14×10 |
|
|
7200 |
0 |
2314656 |
|
160 |
1425638 |
1632514 |
|
195 |
1182580 |
1285357 |
|
16×11 |
|
|
7200 |
0 |
2633294 |
|
192 |
1896325 |
1936025 |
|
231 |
1558945 |
1707296 |
|
18×12 |
|
|
*زمانها برحسب ثانیه است. |
|||||||||||||
|
|
|||||||||||||
|
|||||||||||||
|
شکل 8- مقایسۀ میانگین زمان حل دو الگوریتم GA و PSO برای ابعاد 3 تا 12 ماشین Fig. 8 - Behavior of algorithms in terms of the mean computational time (3 to 12 machines)
|
|||||||||||||
|
|
|||||||||||||
شکل 9- مقایسۀ کیفیت جوابهای خروجی دو الگوریتم GA و PSO برای ابعاد 3 تا 12 ماشین
Fig. 9 - Comparison of quality of solutions between GA & PSO (3 to 12 machines)
جدول 8- مقایسۀ نتایج به دست آمده از الگوریتم‌های GA و PSO و نرم‌افزار Cplex
Table 8. Comparison of the obtained results between GA, PSO & Cplex
|
ابعاد مسئله |
|
GA |
|
PSO |
|
Cplex |
|||||||
|
|
میانگین 10 جواب |
بهترین جواب |
میانگین زمان |
|
میانگین10 جواب |
بهترین جواب |
میانگین زمان |
|
جواب |
کران پایین |
زمان B&B |
||
|
4×3 |
|
23308 |
23308 |
9 |
|
23587 |
23308 |
7 |
|
23308 |
23308 |
85 |
|
|
6×3 |
|
26908 |
26351 |
13 |
|
27059 |
26351 |
10 |
|
26351 |
26351 |
437 |
|
|
8×3 |
|
29904 |
29364 |
18 |
|
30025 |
29460 |
16 |
|
29180 |
0 |
3257 |
|
|
9×3 |
|
32504 |
32467 |
24 |
|
32908 |
32611 |
19 |
|
34624 |
0 |
7200 |
|
|
5×4 |
|
27154 |
27009 |
15 |
|
27211 |
27096 |
13 |
|
26986 |
0 |
6482 |
|
|
7×4 |
|
31587 |
31469 |
18 |
|
31658 |
31520 |
15 |
|
33625 |
0 |
7200 |
|
|
9×4 |
|
36254 |
35984 |
25 |
|
37294 |
36351 |
21 |
|
39624 |
0 |
7200 |
|
|
12×4 |
|
41598 |
40935 |
30 |
|
42517 |
41720 |
25 |
|
49635 |
0 |
7200 |
|
|
8×6 |
|
110598 |
110015 |
29 |
|
111635 |
110365 |
25 |
|
125636 |
0 |
7200 |
|
|
15×6 |
|
186325 |
185362 |
42 |
|
186954 |
186325 |
36 |
|
239571 |
0 |
7200 |
|
|
*زمانها برحسب ثانیه است. |
|||||||||||||
|
|
|
||||||||||||
شکل 10- مقایسۀ میانگین زمان حل و کیفیت جوابهای خروجی دو الگوریتم GA و PSO برای ابعاد 3 تا 6 ماشین
Fig. 10 - Comparison in terms of mean time and quality of solutions between GA & PSO (3 to 6 machines)
جدول 9- مقایسۀ نتایج به دست آمده از الگوریتم‌های GA و PSO و نرم‌افزار Cplex
Table 9. Comparison of the obtained results between GA, PSO & Cplex
|
ابعاد مسئله |
|
GA |
|
PSO |
|
Cplex |
|||||||
|
میانگین 10 جواب |
بهترین جواب |
میانگین زمان |
|
میانگین 10 جواب |
بهترین جواب |
میانگین زمان |
|
جواب |
کران پایین |
زمان B&B |
|||
|
10×8 |
|
389120 |
388625 |
98 |
|
391250 |
389003 |
83 |
|
512748 |
0 |
7200 |
|
|
12×8 |
|
451635 |
449365 |
109 |
|
451935 |
450214 |
98 |
|
635174 |
0 |
7200 |
|
|
14×8 |
|
511251 |
510302 |
137 |
|
512350 |
511250 |
119 |
|
674814 |
0 |
7200 |
|
|
16×8 |
|
610251 |
609514 |
174 |
|
611514 |
610037 |
156 |
|
691759 |
0 |
7200 |
|
|
18×8 |
|
635214 |
633514 |
237 |
|
636214 |
634215 |
278 |
|
704726 |
0 |
7200 |
|
|
11×10 |
|
685632 |
683625 |
409 |
|
686214 |
684251 |
310 |
|
713032 |
0 |
7200 |
|
|
13×10 |
|
836251 |
835624 |
549 |
|
837154 |
835954 |
488 |
|
862145 |
0 |
7200 |
|
|
15×10 |
|
886325 |
885369 |
674 |
|
887145 |
886321 |
586 |
|
911475 |
0 |
7200 |
|
|
16×10 |
|
914257 |
912547 |
916 |
|
914965 |
913157 |
813 |
|
968741 |
0 |
7200 |
|
|
20×10 |
|
1093214 |
1087568 |
1138 |
|
1095636 |
1088635 |
991 |
|
1252364 |
0 |
7200 |
|
|
|
|||||||||||||
|
|||||||||||||
شکل 11- مقایسۀ میانگین زمان حل دو الگوریتم GA و PSO (8 تا 10 ماشین)
Fig. 8 - Behavior of algorithms in terms of the mean computational time (8 to 10 machines)
با توجه به مقادیر حاصل‌شده در جداول 7 تا 9 و همچنین شکلهای 8 تا 11 مشاهده می‌شود که الگوریتم GA ازنظر کیفیت جوابها و الگوریتم PSO ازنظر سرعت و زمان حل، کارآیی بالاتری را نشان داده‌اند. در اندازههای بالاتر، هر دو الگوریتم معرفی‌شده نسبت‌به جواب Cplex عملکرد بهتری دارند. این عملکرد به اندازهای بهتر است که در اندازههای بالا، اختلاف جواب Cplex با دو الگوریتم معرفی‌شده تفاوت زیادی دارد. در این اندازهها مشاهده می‌شود که GA نسبت‌به PSO جوابهای بهتری را استخراج کرده است، اما زمان حل آن نسبت‌به الگوریتم PSO بیشتر است.
امروزه صنایع تولیدی باید از توانایی تولیدی محصولات خود با هزینه‌های پایین و کیفیتی بالا برخوردار باشند. سیستم‌های تولیدی سنتی مثل سیستم‌های کارگاهی و خط تولید، رفته‌رفته توانایی خود را برای برآوردهکردن این نیازها از دست داده‌اند و نیاز به سیستمی بیش از پیش احساس می‌شود که قابلیت برآوردهکردن این نیازهای تولیدی را داشته باشد. سیستم تولید سلولی سیستمی معرفی شده است که توانسته با تلفیق انعطافپذیری سیستم کارگاهی و کارآیی سیستم‌های خط تولید برای تیراژ بالای تولید، توانایی مناسبی را برای تولید در خود ایجاد کند. از طرفی جانمایی تسهیلات و ساختار فیزیکی سیستم تولیدی چنانچه کارآیی لازم را نداشته نباشد، بهشدت باعث افزایش جابهجاییها و تحمیل هزینه‌های حمل‌ونقل به سیستم می‌شود. در این مطالعه سعی شد تا پس از بررسی کاملی مقالات و مطالعات پیشین و بیان مفروضات مختلف، آثار مدلسازی هم‌زمان مسائل تشکیل سلول و جانمایی سلولی براساس محاسبۀ دقیق هزینه‌ها ارائه شود. در مدل ارائه‌شده، اطلاعات تولیدی مهمی نظیر میزان جریان تولیدی بین ماشین‌ها، ظرفیت سلول‌ها و هزینۀ جابه‌جایی قطعات و ماشین‌ها مدنظر قرار گرفت.
بهطور کلی مهم‌ترین مزایای مدل پیشنهادی عبارتند از:
به‌کارگیری تؤامان موارد فوق سبب آن شد تا مدلی ارائه شود که تا حد پذیرفتنی به مسائل دنیای واقعی نزدیک باشد. از این رو از اطلاعات تولیدی واقعی، یک مطالعۀ موردی در کشور هلند استفاده شد تا کارآیی مدل نشان داده شود. با توجه به پیچیدگی مدل ارائه‌شده و نیاز به حل آن در ابعاد بالای تعداد ماشین‌آلات و قطعات، ناگزیر به استفاده از الگوریتم‌های فراابتکاری شده و دو الگوریتم ژنتیک و ازدحام ذرات ارائه و نتایج آنها با نتایج حاصل از Cplex مقایسه شده است که عملکرد آنها در بخش 4 بهطور مبسوط تشریح شد. بهطور کلی میتوان نتیجه گرفت الگوریتم ژنتیک، در زمان کمتر مناسبتر از الگوریتم ازدحام ذرات است. همچنین مشاهده می‌شود که الگوریتم ژنتیک در اندازههای بزرگ عملکرد بهتری نسبت‌به الگوریتم ازدحام ذرات دارد.
سیستم تولید سلولی سیستمی معرفی شده است که توانسته با تلفیق انعطافپذیری سیستم کارگاهی و کارآیی سیستم‌های خط تولید برای تیراژ بالای تولید، توانایی مناسبی را برای تولید در خود ایجاد کند. در این مطالعه سعی شد تا پس از بیان مفروضات مختلف، آثار مدلسازی هم‌زمان مسائل تشکیل سلول و جانمایی سلولی در یک فضای پیوسته بررسی شود. در مدل ارائه‌شده، اطلاعات تولیدی مهمی نظیر میزان جریان تولیدی بین ماشین‌ها، مسیرهای عملیاتی چندگانه، ظرفیت سلول‌ها و هزینۀ جابه‌جایی قطعات مدنظر قرار گرفت. در این مقاله از دادههای شرکت BATA برای ارائۀ یک مسئلۀ واقعی استفاده شده و پیکربندی به دست آمده نشان داده شده است. با توجه به ماهیت مدل ارائه‌شده، دو الگوریتم فراابتکاری GA و PSO نیز برای مسائل در اندازههای بالاتر توسعه داده شده است. نتایج حاصل نشانگر آن است که در اندازههای بالاتر، الگوریتم GA همواره عملکرد بهتری نسبت‌به الگوریتم PSO دارد، ولی زمان حل مسئله با افزایش ابعاد آن در الگوریتم GA نسبت‌به PSO پیشی میگیرد.
در نظر گرفتن ابعاد نامساوی ماشین‌ها، دو برابر کردن ماشین‌های گلوگاه، توسعۀ مدلهای احتمالی و فازی، توسعۀ مدل ارائه‌شده برای چیدمانهای چندطبقه و به‌کارگیری دیگر الگوریتم‌های فراابتکاری و مقایسۀ نتایج حاصل از آنها با الگوریتم‌های اشاره‌شده در این تحقیق، بهعنوان موضوعات مناسبی برای مطالعات آتی پیشنهاد می‌شود.
[i] Group Technology (GT)
[ii] Parts Families
[iii] Similarity Coefficient (SC)
[iv] Cellular Manufacturing Systems (CMS)
[v] Flow Shop
[vi] Job Shop
[vii] Cellular layout
[viii] Karthikeyan, S. et al
[ix] Particle Swarm Optimization (PSO)
[x] Genetic Algorithm (GA)
[xi] Golmohammadi, A. M. et al
[xii] Imran, M. et al
[xiii] Hybrid Genetic Algorithm (HGA)
[xiv] Simiulated Anneling (SA)
[xv] Kumar, R., & Singh, S. P.
[xvi] Soolaki, M., & Arkat, J.
[xvii] Iqbal, A., & Al-Ghamdi, K. A.
[xviii] Arghish, O. et al
[xix] Branch & Bound (B&B)
[xx] Chandrasekharan, M. P., & Rajagopalan, R.
[xxi] Bi-objective Quadratic Assignment Problem (Bi-QAP)
[xxii] Normal Distribuion
[xxiii] Bajestani, M. A. et al.
[xxiv] Scatter Search (SS)
[xxv] Dixit, A. R., & Mishra, P. K
[xxvi] Nouri, H., & Hong, T. S.
[xxvii] Chandrasekar, K., & Venkumar, P.
[xxviii] Shukla, O. J. et al.
[xxix] Multiple Objective Particle Swarm Optimization (MOPSO)
[xxx] Non-dominated Sorting Genetic Algorithm-II (NSGAII)
[xxxi] Exceptional Parts
[xxxii] Initial Solution
[xxxiii] Population Size
[xxxiv] Mutation
[xxxv] Crossover
[xxxvi] Chromosome
[xxxvii] Parent
[xxxviii] Offspring
[xxxix] Fitness function
[xl] Stopping criteria
[xli] Crossover Probability
[xlii] Roulette Wheel
[xliii] Particles
[xliv] Local Optimum
[xlv] Design of Experiment
[xlvi] Taguchi
)