الگوریتم انجماد تدریجی چندهدفه جهت مسئلۀ هم‌زمان بالانس خطوط مونتاژ دوطرفه و تخصیص نیروی انسانی

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

نویسندگان

1 دانشیار، گروه مهندسی صنایع- دانشکده مهندسی- دانشگاه بوعلی سینا- همدان- ایران.

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

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

چکیده

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

کلیدواژه‌ها


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

A Multi-objective Simulated Annealing for Simultaneous Two-Sided Assembly Line Balancing and Operators Assignment

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

  • Parviz Fattahi 1
  • Parvaneh Samouei 2
  • Mostafa Zandiyeh 3
1 Associate Professor, Dept. of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran
2 Assistant Professor, Dept. of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran
3 Associate Professor, Faculty of Management and Accounting, Shahid Beheshti University, Tehran, Iran
چکیده [English]

This paper presents a multi-objective simulated annealing algorithm for mixed-model two-sided assembly line balancing with multi skilled operators. The objectives of the proposed model are minimizing the number of mated-stations, the number of total stations and total human cost for a given cycle time. Also, maximizing the weighted line efficiency and minimizing the weighted smoothness index are considered for the problem. An example is solved with the proposed approach in detail and the performance of this algorithm is tested on a set of test problems and changing neighborhood solution rules. The results show the proposed algorithm can be used as a good algorithm to solve the problem.

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

  • Two-sided assembly line balancing
  • Multi-Objective Optimization
  • Multi skilled operators
  • Simulated Annealing (SA)؛ Mixed-model

1- مقدمه

 

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

اولین مقالۀ علمی در مسئلۀ بالانس خطوط مونتاژ در دهۀ 1950 میلادی منتشر شد؛ ولی پس از آن به‌دلیل رشد صنایع و همچنین اهمیت موضوع بالانس خطوط مونتاژ، مقالات و کتب مختلفی در این حوزه به چاپ رسید که هریک اهداف، شرایط و محدودیت‌های متفاوتی را مد نظر قرار داده بودند. بایبارس[1] (1984، 1986)، قوش و گانون[2] (1989)، بویسِن و همکاران[3](2007، 2008)، بِکِر و اِسکول[4](2006) و باتایا و دولگوی[5](2013) مقالات مروری بسیار خوب و مفیدی در این حوزه منتشر کرده‌اند.

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

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

 

شکل 1. یک خط مونتاژ دوطرفه

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

در خطوط مونتاژ دو‌طرفه، دو ایستگاه که روبه‌روی هم قرار گرفته‌اند و ایستگاه‌های زوجی نامیده می‌شوند (لی و همکاران[6](2001)) و دو اپراتور که هریک در سمتی از این ایستگاه قرار گرفته‌اند، تجهیز شده‌اند. آنها به‌طور موازی عملیات متفاوتی را بر یک محصول انجام می‌دهند، بدون آنکه عملیات یکی تداخلی در عملیات فرد دیگر داشته باشد (چوتیما و چیمکلای[7](2012)).

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

اولین مقاله‌ای که به بالانس خطوط مونتاژ دوطرفه پرداخت، متعلق به بارسولدی[8] است که در سال 1993 منتشر شد.

براساس تعداد اهدافی که در مسئلۀ بالانس خطوط مونتاژ دوطرفه مشاهده می‌شود، این مسائل می‌توانند در دو شاخۀ تک‌هدفه و چندهدفه تقسیم شوند. به‌طور مثال زیائوفِنگ و همکاران[9] (2010) و اُزبَکِر و تاپکان[10] (2011) از یک هدف و سیماریا و ویلارینهو[11] (2009) و اُزکان و توکلو[12] (2009) از بیش از یک هدف در پژوهش‌های خود استفاده کرده‌اند.

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

به‌طور مثال سیماریا و ویلارینهو[14] (2009) به ارائۀ یک مدل ریاضی برای مسئلۀ بالانس خطوط مونتاژ دوطرفه پرداختند و یک الگوریتم کلونی مورچگان نیز برای حل آن ارائه کردند. در سال 2011 نیز اُزبَکِر و تاپکان[15] نیز به حل مسئلۀ بالانس خطوط مونتاژ دوطرفه با محدودیت‌های منطقه‌ای[16] توسط الگوریتم کلونی زنبور عسل اقدام کردند.

جدول (1): برخی روش‌های حل مسائل بالانس خطوط مونتاژ دوطرفه

مقاله

روش

رویکرد

Wu et al. (2008); Xiaofeng et al. (2010)

شاخه و کران

قطعی

Hu et al. (2008); Xiaofeng et al. (2008)

شمارش

Bartholdi (1993)

 

ابتکاری

Özcan & Toklu(2009); Özcan(2010)

انجماد تدریجی(SA)

فرا ابتکاری

Kim et al. (2000); Kim et al. (2009); Taha et al. (2011); Purnomo et al. (2013)

الگوریتم ژنتیک (GA)

Simaria & Vilarinho (2009); Baykasoglu& Dereli (2008)

کلونی مورچگان (ACO)

Özcan et al. (2010)

جستجوی ممنوعه (TS)

Chutima & Chimklai (2012)

بهینه‌سازی توده ذرات (PSO)

Özbakir & Tapkan (2011);Tapkan et al. (2012)

کلونی زنبور عسل

 

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

علاوه بر این، با توجه به طیف گسترده‌ای از صنایع خودرو و موارد مشابه که به تولید مدل‌های مختلفی از یک نوع محصول می‌پردازند، لزوم بررسی بالانس خطوط مونتاژ دوطرفه مدل‌های ترکیبی از اهمیت ویژه‌ای برخوردار است؛ اما با این حال مقالات کمی نظیر اُزکان و توکلو (2009) و چوتیما و چیمکلای[17] (2012) هستند که به این موضوع پرداخته باشند. مقالات انگشت‌شماری نظیر ناکِد و نیشیواکی[18] (2008) و کرومیناس و همکاران[19] (2008) هستند که به بررسی اثر مهارت کارگران در بالانس خطوط مونتاژ پرداخته‌اند. ناکِد و نیشیواکی (2008) به توسعۀ الگوریتمی جهت حل خطوط تولید Uشکل با مهارت‌های مختلف کارگران پرداخته‌اند. آنها فرض کردند که زمان عملیات و زمان حرکت اپراتورها قطعی است؛ اما برای اپراتورهای مختلف متفاوت است.

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

باقیماندۀ بخش‌های این مقاله به شرح زیر است:

بخش 2 به ارائۀ مفروضات و الگوریتم پیشنهادی اشاره دارد. یک مثال با جزئیات حل کامل در بخش 3 آورده شده است و در بخش 4 مثال‌های متفاوتی جهت بررسی کارایی الگوریتم ذکر شده است. درنهایت در بخش 5 نیز به بیان نتایج و همچنین پژوهش‌های آتی اشاره دارد.

2- بیان مسئله

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

1-2- مفروضات مسئله

1- عملیات روی یک خط مونتاژ دوطرفه انجام می‌پذیرند.

2- مدل‌های مختلفی از یک نوع محصول مونتاژ می‌شوند.

3- برخی از عملیات نیازمند یک سمت مشخصی از خط مونتاژ هستند؛ در حالی که برخی دیگر می‌توانند در هریک از طرفین انجام شوند.

4- نمودار روابط پیش‌نیازی فعالیت‌ها مشخص هستند.

5- کارگرانی با سطوح مهارتی متفاوت وجود دارند و زمان انجام عملیات نیز وابسته به سطح مهارت هر کارگر است.

6- عملیات باید تنها یک بار انجام شوند.

7- زمان تکمیل عملیات در مدل‌های مختلف می‌تواند متفاوت باشد.

8- موجودی در جریان ساخت مجاز نیست.

 

2-2- مدل ریاضی مسئله

در این بخش، با توجه به مفروضات فوق، مدل ریاضی چندهدفه برای مسئلۀ هم‌زمان بالانس خطوط مونتاژ دوطرفه مدل‌های ترکیبی و تخصیص نیروی انسانی با استفاده از پارامترها، اندیس‌ها و متغیرهای زیر ارائه می‌شود (شایان ذکر است که در الگوریتم پیشنهادی نیز برخی از آنها استفاده شده‌اند):

اندیس‌ها:

فعالیت

i, h

p, r

ایستگاه زوجی

J,g

مدل‌های محصول

m

مهارت

l,q

ایستگاه زوجی j و سمت  k(اگر k=1 باشد، سمت چپ و اگر k=2 باشد، سمت راست را نشان می‌دهد)

(j, k)

پارامترها و متغیرها:

مجموعۀ ایستگاه‌های زوجی

J

مجموعۀ سطح مهارت‌ها (پایین، متوسط، بالا و...)

L

مجموعۀ فعالیت‌ها در دیاگرام روابط پیش‌نیازی ترکیبی

I

مجموعۀ مدل‌های محصول

M

مجموعۀ فعالیت‌هایی که باید در سمت چپ انجام گیرند.

AL

مجموعۀ فعالیت‌هایی که باید در سمت راست انجام گیرند.

AR

مجموعۀ فعالیت‌هایی که می‌توانند در سمت چپ و یا راست انجام گیرند.

AE

زمان عملیات فعالیت i برای مدل m توسط کارگری با مهارت l

timl

هزینۀ نیروی انسانی با سطح مهارتl

HCl

زمان سیکل

C

زمان تکمیل فعالیت i برای مدل m توسط کارگری با مهارت l

tfiml

اگر فعالیت i به ایستگاه (j, k) با مهارت l تخصیص یابد، 1 و در غیر این صورت 0

xijkl

تعداد کارگر با مهارت l

Sl

تعداد ایستگاه‌های زوجی

NM

تعداد ایستگاه سمت چپ

NL

تعداد ایستگاه سمت راست

NR

تعداد کل ایستگاه‌ها

NS

مجموعۀ فعالیت‌های قابل‌تخصیص

SAT

میزان بار ایستگاه‌ها شامل بیکاری‌های غیرقابل‌اجتناب در سمت چپ ایستگاه زوجی جاری برای تمام mM

mWLNM1

میزان بار ایستگاه‌ها شامل بیکاری‌های غیرقابل‌اجتناب در سمت راست ایستگاه زوجی جاری برای تمام mM

mWLNM2

مجموعۀ فعالیت‌هایی که به سمت چپ ایستگاه زوجی حاضر تخصیص یافته است.

TLNM1

مجموعۀ فعالیت‌هایی که به سمت راست ایستگاه زوجی حاضر تخصیص یافته است.

TLNM2

مجموعۀ پیش‌نیازهای بلافاصله فعالیت i

P(i)

مجموعۀ تمام پیش‌نیازهای بلافاصله فعالیت i

Pa(i)

مجموعۀ پس‌نیازهای بلافاصله فعالیت i

Sa(i)

مجموعۀ فعالیت‌هایی که پیش‌نیاز ندارند.

P0

یک عدد مثبت خیلی بزرگ

ψ

مجموعۀ فعالیت‌هایی که جهت انجام عملیاتشان مخالف فعالیت i است.

 

C(i)

مجموعۀ جهت‌های لازم برای انجام فعالیت i

 

K(i)

متغیرها

اگر ایستگاه زوجی j استفاد شود 1 و در غیر این صورت 0

Fj

اگر ایستگاه (j,k) با اپراتوری با سطح مهارت l به بهره‌برداری برسد 1 و در غیر این صورت 0

Gjkl

اگر فعالیت i قبل از فعالیت p و در همان ایستگاه انجام گیرد 1 و اگر فعالیت p قبل از فعالیت i و در همان ایستگاه انجام گیرد 0

zip

       

 

                                                        (1)

                            (2)

     (3)

 

S.to:

(4)

 

 

(5)

 

                            (6)

 

                 (7)

            (8)

 


(9)

 

 

(10)

 

 

(11)                                                                    

                                (12)                                                       

                  (13)                                                       (14)

 

(15)

                               (16)

                      (17)

توابع هدف (1) تا (3) به ترتیب تعداد ایستگاه‌های زوجی، تعداد کل ایستگاه‌ها و هزینه‌های نیروی انسانی را حداقل می‌سازد. محدودیت (4) نشان می‌دهد هر کار دقیقاً باید به یک ایستگاه تخصیص یابد. عبارت (5) روابط پیش‌نیازی میان فعالیت‌ها را نشان می‌دهد. محدودیت (6) و (7) نیز بیان می‌کند که زمان تکمیل کارها بین زمان سیکل و مدت زمان هر عملیات می‌باشد. محدودیت‌های (8) تا (10) نیز توالی وابسته به زمان تکمیل کارها را نشان می‌دهد. محدودیت (11) نیز تضمین می‌کند برای انجام یک کار حتماً باید اپراتوری در آن مشغول باشد. محدودیت (12) نیز رابطه میان تعداد ایستگاه‌های زوجی و کل ایستگاه‌ها را نشان می‌دهد. محدودیت (13) نیز بیان می‌کند به یک ایستگاه نهایتاً می تواند 1 نفر تخصیص یابد. درنهایت نیز محدودیت‌های (14) تا (17) نیز صفر و یک بودن متغیرها را بیان می‌کند.

3- الگوریتم پیشنهادی

قبل از آنکه به بیان الگوریتم پیشنهادی پرداخته شود، لازم است توضیح مختصری دربارۀ الگوریتم انجماد تدریجی ارائه شود:

1-3- الگوریتم انجماد تدریجی استاندارد

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

2-3- الگوریتم انجماد تدریجی پیشنهادی

از آنجا که در منبع کارپ[20] (1972) ثابت شده است که مسئله بالانس خطوط مونتاژ در کلاس NP-Hard قرار می‌گیرند، می‌توان از الگوریتم‌های فرا ابتکاری نظیر SA برای حل آن کمک گرفت.

در الگوریتم پیشنهادی سعی شده است که دمای ابتدایی بالاتری جهت جستجوی بیشتر فضا استفاده شود؛ علاوه بر این، طول زنجیرۀ مارکوف برابر با تعداد عملیات لحاظ شده است؛ همچنین روند کاهش دما به‌شکل هندسی است که به‌صورت زیر معرفی می‌شود:

TC+1= r. TC

که در آن TC دمای جاری، TC+1 دما در تکرار بعد و r نرخ سردسازی است.

3-3- ایجاد راه حل ابتدایی

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

PL= {2, 1, 4, 5, 3, 6}

این مجموعه نشان می‌دهد که بالاترین اولویت به کار 2 و کمترین اولویت به کار 6 تعلق دارد.

برای ایجاد یک جواب شدنی، فعالیت‌های قابل‌تخصیص که محدودیت‌های پیش‌نیازی را تأمین می‌کنند با توجه به اولویتی که در لیست PL دارند به سمتی از ایستگاه زوجی که لازم است تخصیص می‌یابند. پس از آن فعالیت‌های قابل‌تخصیص به‌روز می‌شوند و این فرایند آنقدر ادامه می‌یابد تا تمام فعالیت‌ها تخصیص یابند.

شایان ذکر است برای بار اول که باید به یک ایستگاه فعالیتی تخصیص یابد، ابتدا باید کارگری با سطح مهارت تصادفی به آن ایستگاه تخصیص یافته باشد تا بتوان عملیات را در آن ایستگاه به انجام رساند.

4-3- ایجاد همسایگی

در الگوریتم پیشنهادی، همسایۀ جدید به‌کمک تغییرات تصادفی 2 و یا 3 عنصر تصادفی با احتمال 5/0 در لیست اولویت ایجاد می‌شود. اگر عدد تصادفی ایجادشده کوچک‌تر و یا مساوی 5/0 باشد جابه‌جایی تصادفی دو عنصر و در غیر این صورت جابه‌جایی تصادفی 3 عنصر انجام می‌گیرد.

 

شکل 2. ایجاد همسایگی

5-3- ایجاد یک راه حل شدنی

برای ایجاد یک راه حل شدنی از عبارات اختصاری زیر استفاده می‌شود:

 

رویکرد ایجاد یک جواب مطابق زیر است:

1. مقادیر زیر را برای تمام mM قرار دهید:

NM = 1, NL = 0, NR = 0, mWL11=0 and mWL12= 0 for all mM , Sl=0 for all lL

2. مجموعۀ SAT را تعیین کنید. این مجموعه شامل تمام فعالیت‌هایی است که یا پیش‌نیازشان رعایت شده و یا پیش‌نیازی ندارند. اگر SAT= Ø باشد، به مرحلۀ 6 بروید.

3. فعالیت‌های موجود در SAT را با توجه به ترتیب صعودی لیست اولویت(PL) مرتب کنید.

4. اولین فعالیت h در SAT را به شکل زیر تخصیص دهید:

1.4. اگر فعالیت h AL است، آنگاه:

1.1.4. اگر mWLNM1= 0 است، یک کارگر با مهارت تصادفی به سمت چپ ایستگاه زوجی کنونی اختصاص دهید و به تعداد کارگران دارای این مهارت در خط مونتاژ، یک واحد اضافه کنید.

2.1.4. اگر thml+mWLNM1≤C و  thml+tfrml≤C(tfrml برابر با حداکثر tfpml هایی است که تا کنون برای تمام مدل‌های محصول به سمت راست ایستگاه زوجی حاضر اختصاص یافته است)، آنگاه فعالیت h را به سمت چپ ایستگاه تخصیص دهید وTLNM1=TLNM1+{h}. همچنین برای تمام مدل‌هاtfhml=max{(thml+mWLNM1), (thml+tfrml)} و mWLNM1=tfhml را مشخص کنید و به مرحلۀ 2 بروید. در غیر این صورت به مرحلۀ 5 بروید.

2.4. اگر فعالیت hAR است، آنگاه:

1.2.4. اگر mWLNM2= 0 است، آنگاه یک کارگر با مهارت تصادفی به سمت راست ایستگاه زوجی کنونی اختصاص دهید و به تعداد کارگران دارای این مهارت در خط مونتاژ، یک واحد اضافه کنید.

2.2.4. اگر thml+mWLNM2≤C و  thml+tfrml≤C(tfrml برابر با حداکثر tfpml هایی است که تاکنون برای تمام مدل‌های محصول به سمت چپ ایستگاه زوجی حاضر اختصاص یافته است)، آنگاه فعالیت h را به سمت راست ایستگاه تخصیص دهید و TLNM2=TLNM2+{h}. همچنین برای تمام مدل‌هاtfhml=max{(thml+mWLNM2), (thml+tfrml)} و mWLNM2=tfhml را مشخص کنید و به مرحلۀ 2 بروید. در غیر این صورت به مرحلۀ 5 بروید.

3.4.اگر فعالیت hAE است، آنگاه:

1.3.4. عدد تصادفی p2 را در بازه [0, 1]انتخاب کنید. اگر p2≤0.5 آنگاه به مرحلۀ 4.1.1 بروید. در غیر این صورت به مرحلۀ 4.2.1 بروید.

5. اگر هیچ‌یک از فعالیت‌های موجود در SAT نتوانند به سمت چپ یا راست ایستگاه زوجی حاضر اختصاص یابند، ایستگاه زوجی جدیدی باز کنید. اگر TLNM1≠Ø، آنگاه NL=NL+1. اگر TLNM2≠Ø آنگاه NR=NR+1. علاوه بر این NM=NM+1. همچنین برای تمام مدل‌ها مقادیرmWLNM1 وmWLNM2 را برابر صفر قرار دهید و به مرحلۀ 2 بروید.

6. توقف کنید و مقادیر تابع هدف را محاسبه نمایید.

تعداد ایستگاه‌های زوجی برابر NM و تعداد ایستگاه‌ها نیز برابر NS است که با مجموع مقادیر NL و NS برابر است.

فلوچارت این الگوریتم در شکل 3 آمده است:

6-3- شاخص‌های به‌کارگرفته‌شده

توابع هدف و شاخص‌هایی که برای حل مسئلۀ بالانس خطوط مونتاژ دوطرفه و همچنین تخصیص نیروی انسانی با مهارت‌های مختلف به‌ازای یک زمان سیکل مشخص، در نظر گرفته شده است به شرح زیر است:

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

WLE=().100                (17)

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

                                      (18)

 

 

 

 

شکل 3. فلوچارت الگوریتم پیشنهادی


2. حداقل‌سازی شاخص هموارسازی موزون[21]. با استفاده از این شاخص سعی بر آن است که میزان تفاوت در بارگذاری‌های میان ایستگاه‌ها به حداقل ممکن برسد. این شاخص می‌تواند به‌شکل زیر تعریف شود:

(19)

که در آن WLmax حداکثر زمان ایستگاه‌ها است.

3. حداقل‌سازی هزینه‌های نیروی انسانی کل سیستم که می‌توان به‌صورت زیر تعریف کرد:

(20)

با توجه به روش مجموع موزون برای حل مسائل برنامه‌ریزی چندهدفه دِب[22] (2001) تابع هدف زیر می‌تواند به دست آید:

Minimize                                         (21)

در این رابطه WLE0، WSI0 و HC0 مقادیر به‌دست‌آمده از هر هدف در اولین تکرار است و W1، W2 و W3وزن‌هایی هستند که در این روش نشان‌دهندۀ اولویت هر هدف است. اگر W1=W2=W3= فرض شود، حداکثرسازی اثربخشی موزون خط، حداقل‌سازی شاخص هموارسازی و حداقل‌کردن هزینه‌های نیروی انسانی با درجه اولویت یکسان حاصل می‌شود.

 

7-3- کران پایین

اُزکان و توکلو[23] (2009) یک کران پایین برای تعداد ایستگاه‌ها در بالانس خطوط مونتاژ دوطرفۀ مدل‌های ترکیبی ارائه کردند؛ اما کران پایین آن مقاله برای شرایطی که زمان‌های انجام عملیات وابسته به فرد انجام‌دهنده است، تغییر کرد. در این کران از tim1استفاده شد که زمان پردازش را توسط فردی که دارای بالاترین مهارت است نشان می‌دهد. درواقع با استفاده از این پارامتر، این موضوع مد نظر قرار می‌گیرد که اگر تمام ایستگاه‌ها هم کارگرانی با مهارت بالا داشته باشند، حداقل چه تعداد ایستگاه می‌تواند در نظر گرفته شود. این کران به‌شکل زیر قابل‌محاسبه است:

(22)

 

 

 

 

 

(23)

 

عبارت (22) نشان می‌دهد حداقل تعداد ایستگاه‌های زوجی برابر با تعداد ایستگاه‌هایی است که باید به فعالیت‌های سمت راست و یا چپ تخصیص یابند. این مقدار از آنجا حداقل مقدار است که فعالیت‌های نوع E که درواقع می‌توانند به هریک از این دو سمت تخصیص یابند در نظر گرفته نشده‌اند؛ علاوه بر این روابط پیش‌نیازی میان فعالیت‌ها نیز نادیده لحاظ شده است. رابطۀ (23) که درواقع کران پایینی برای تعداد ایستگاه‌ها است، بیان می‌کند که تعداد کل ایستگاه‌ها، حداقل دو برابر کران پایین تعداد ایستگاه‌های زوجی است، از سویی این مقدار با درنظرگرفتن تعداد ایستگاه‌هایی که فعالیت‌های نوع Eمی‌توانند به آنها اختصاص یابند، به مقدار بهتر و بالاتری ارتقا یافته است.

4- مثال عددی

در این بخش، الگوریتم پیشنهادی به‌کمک یک مسئله با 9 فعالیت تشریح شده است. زمان انجام فعالیت‌ها توسط افراد مختلف و همچنین سایر داده‌های مسئله در جدول 2 آورده شده است. زمان سیکل در این مسئله 6 در نظر گرفته شده است. علاوه بر این هزینه‌های استخدام کارگران با مهارت‌های 1، 2 و 3 به ترتیب 90، 60 و40 دلار در افق برنامه‌ریزی منظور شده است.

یک راه حل تصادفی اولیه (لیست اولویت) می‌تواند به شکل PL = {1, 2, 3, 4, 5, 6, 7, 8, 9} باشد. روش ایجاد یک بالانس خط ابتدایی در جدول 3 آورده شده است.همان‌طور که جدول 3  نشان می‌دهد که در ابتدا لیست فعالیت‌های قابل‌تخصیص فعالیت‌های 1، 2 و 3 هستند و با توجه به ترتیب فعالیت‌ها در لیستPL مشخص می‌شود که ابتدا باید فعالیت 1 تخصیصیابد.

 

 

 

 

 

 

جدول (2): داده‌های مثال عدد

فعالیت

پیش‌نیاز بلافاصله

سمت

مدلA(qA=0/5)

مدل(qB=0/5)B

مهارت 1

مهارت 2

مهارت 3

مهارت 1

مهارت 2

مهارت 3

1

__

L

1/5

2

3

0

0

0

2

__

R

2

3

4

0/5

1/5

2/5

3

__

E

0

0

0

1

2/5

3/5

4

1

L

2

3

4

0

0

0

5

2

R

1

3

4

1/5

3

4

6

2/3

E

1

2

3

1

2

3

7

4/5

E

1/5

3

4

2

3

4

8

5

L

0

0

0

3

3/5

4

9

6

E

1

3

4

0/5

1

1/5

 

 

 

 

جدول(3): ایجاد بالانس خط ابتدایی

مرحله 1

مرحله2

SAT

مرحله 3

PL

مرحله 4

مرحله 5

مرحله6

NM=1; NL=0, NR=0,AWL11=0, BWL11=0, AWL12=0,BWL12=0

{1,2,3}

{1,2,3}

فعالیت 1 را انتخاب کنید.P(1) ={Ø} فعالیت 1AL.

AWL11=0, BWL11=0

مهارت تصادفی، مهارت 1 است.

1.5+0≤6; 0+0≤6; TL11= TL11+{1}; tf1A=1.5, tf1B=0, AWL11=1.5, BWL11=0.

 

 

 

{2,3,4}

{2,3,4}

فعالیت 2 را انتخاب کنید.P(2) =Ø. فعالیت 2AR.

AWL12=0, BWL12=0.

مهارت تصادفی، مهارت 3 است.

4+0≤6,2.5+0≤6,TL12= TL12+{2}; tf2A=4, tf2B=2.5, AWL12=4, BWL12=2.5.

 

 

 

{3,4,5}

{3,4,5}

فعالیت 3 را انتخاب کنید. P(3) =Øفعالیت 3AE و P2>0.5.

0+4≤6,3.5+2.5≤6,TL12= TL12+{3},tf3A=4, tf3B=6, AWL12=4, BWL12=6.

 

 

 

{4,5,6}

{4,5,6}

فعالیت 4 را انتخاب کنید.P(4) ={1}. فعالیت 4AL.

2+1.5≤6; 0+0≤6; TL11= TL11+{4}; tf4A=3.5, tf4B=0, AWL11=3.5, BWL11=0.

 

 

 

{5,6}

{5,6}

فعالیت 5 را انتخاب کنید.P(5) ={2}. فعالیت 5AR.

4+4>6; 4+6>6.

به مرحلۀ 5 بروید.

فعالیت 5 انتخاب نمی‌شود.

 

NM=2, AWL11=0, BWL11=0, AWL12=0, BWL12=0

{5,6}

{5,6}

فعالیت 5 را انتخاب کنید. P(5) ={2}فعالیت .5AR

AWL22=0, BWL22=0.

مهارت تصادفی، مهارت 2 است.

3+0≤6, 3+0≤6, TL22= TL22+{5},tf5A=3, tf5B=3, AWL22=3, BWL22=3.

 

 

 

{6,7,8}

{6,7,8}

فعالیت 6 را انتخاب کنید.P(6) ={2,3}. فعالیت 6AEو P2≤0.5.

AWL21=0, BWL21=0

مهارت تصادفی، مهارت 1 است

1+0≤6; 1+0≤6; TL21= TL21+{6}, tf6A=1, tf6B=1, AWL21=1, BWL21=1.

 

 

 

{7,8,9}

{7,8,9}

فعالیت 7 را انتخاب کنید.P(7) ={4,5}. فعالیت 7AE و P2≤0.5.

1.5+1≤6; 2+1≤6; TL21= TL21+{7}; tf7A=2.5, tf7B=3, AWL21=2.5, BWL21=3

 

 

 

{8,9}

{8,9}

فعالیت 8 را انتخاب کنید.P(8) ={5}. فعالیت.8AL

0+2.5≤6; 3+3≤6; TL21= TL21+{8}; tf8A=2.5, tf8B=6, AWL21=2.5, BWL21=6.

 

 

 

{9}

{9}

فعالیت 9 را انتخاب کنید.P(9) ={6} فعالیت 9AE است و P2>0.5.

3+3≤6; 1+3≤6 TL22= TL22+{9},tf9A=6, tf9B=4, AWL22=6, BWL22=4.

 

 

 

Ø

 

 

 

توقف

 

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

تخصیص اولیۀ فعالیت‌ها و مهارت‌های مختلف به ایستگاه‌ها برای این مسئله در جدول 4 نشان داده شده است. این جدول مشخص می‌کند که دو ایستگاه زوجی و 4 ایستگاه در مجموع وجود دارد. علاوه بر این مقادیر توابع هدف WLE، WSI ،HC و همچنینE برای این نوع تخصیص‌ها به‌ترتیب67/66%، 795/2، 280 و 1 می‌شود. همچنین در سمت چپ هر دو ایستگاه زوجی مهارت 1 و در سمت‌های راست از مهارت‌های 2 و 3 استفاده شده است.

جدول(4): تخصیص فعالیت‌ها و مهارت‌ها به ایستگاه‌های زوجی

 

ایستگاهزوجی 1

ایستگاهزوجی 2

سمتچپ

سمتراست

سمتچپ

سمتراست

فعالیت

1, 4

2, 3

6, 7, 8

5, 9

مهارت

1

3

1

2

بهترین مقدار تابع هدف  Eبا استفاده از الگوریتم پیشنهادی در 5 تکرار برابر4/0شدهاست. تعداد ایستگاه‌های زوجی برابر 1 و تعداد ایستگاه‌ها نیز برابر 2 شده است. علاوه بر اینمقادیرWLE،WSI و HC نیز به‌ترتیب2/81%،7/0 و 180 شده است. در این ایستگاه‌ها نیز دو کارگر با مهارت 1 به کار گرفته شده‌اند.

این مسئله با زمان‌های سیکل مختلف و هریک 5 بار روی کامپیوتر شخصی2/2  GHz CPU و 1GB of RAM اجرا شد. بهترین، بدترینو میانگین پاسخ‌های به‌دست‌آمدهدرایناجراهاوهمچنینبهترینوبدترینتعدادکارگرانمورداستفاده با هر مهارتی در جدول 5آوردهشدهاست.

 

جدول(5):بهترین،بدترینومتوسطنتایجبه‌دست‌آمده طی 5 اجرا برای زمان‌های سیکل متفاوت

 

C

LB

E

WSI

HC ((دلار

WLE%

NM[NS]

(S1, S2, S3)

ET#

W*

M**

B***

W

M

B

W

M

B

W

M

B

W

B

W

B

M

 

P9

4

2

0/71

0/64

0/54

1/7

1/5

1/3

370

354

330

65/6

71/3

77/1

3[6]

2[4]

(1,4,1)

(3,1,0)

0/4

 

5

1

0/69

0/45

0/32

2/2

1/2

0/2

280

250

180

65/0

73/5

97/5

2[4]

1[2]

(2,1,1)

(2,0,0)

0/4

 

6

1

0/49

0/46

0/40

1/4

0/9

0/7

180

180

180

81/2

81/2

81/2

1[2]

1[2]

(2,0,0)

(2,0,0)

0/5

 

7

1

0/61

0/46

0/39

0/9

0/7

0/6

180

156

150

69/6

84/6

94/6

1[2]

1[2]

(2,0,0)

(1,1,0)

0/5

 

8

1

0/55

0/46

0/43

0/9

0/9

0/6

150

134

130

82/8

89/1

90/6

1[2]

1[2]

(1,1,0)

(1,0,1)

0/5

 

9

1

0/66

0/47

0/38

2/2

1/1

0/6

150

138

130

73/6

79/2

80/6

1[2]

1[2]

(1,1,0)

(1,0,1)

0/5

 

                                             

W*: بدتریننتایج،:M**متوسط نتایج،B***: بهترین نتایج،ET#: زماناجرا(ثانیه)،S1: تعداد کارگر با مهارت 1 ، S2: تعداد کارگر با مهارت 2،S3: تعداد کارگر با مهارت 3

 

در جدول 5واضحاستکهبرایاینمسئلهتغییراتدرزمانسیکلتأثیر چندانی در زمان حلایجادنکردهاست. علاوه بر این نتیجه‌گیریدیگریکهمی‌توانازجدول4و5کردبهشرحزیراست:

جدول4 نشان می‌دهد که در حالت ابتدایی اگر زمان سیکل برابر با 6 در نظر گرفته شود، نیاز به 4 اپراتور(2 ماهر، 1 نیمه‌ماهرویکمبتدی) وجودداردتا 9 فعالیتاینمسئلهانجامگیرند؛ اما جدول 5 نشان می‌دهد با جستجوی همسایگی فعالیت‌ها،تغییردراولویتانجامکارهاوبه‌کاربردن الگوریتم برای همین مسئله و با زمان سیکل 6 تنها به 2 اپراتور ماهر برای انجام کارها نیاز خواهد شد. تحلیلدیگریکهبرایاینمسئلهصورتپذیرفتاستآناستکهبهترینپاسخ‌هایبه‌دست‌آمدهبرایتعدادایستگاه‌های زوجی، تعداد کل ایستگاه‌ها، هزینه‌های نیروی انسانی و همچنین زمان حل با مقادیر بهینه‌ای که به‌ازای زمان‌های سیکل مختلف به‌کمکنرم‌افزارGAMS به دستآمده، قیاس شده است. نتایج این ارزیابی‌ها در جدول 6 آمده است.

همان‌طور که از جدول 6 واضح است، الگوریتم پیشنهادیبه‌ازای زمان‌های سیکل 5، 6، 7، 8 و 9 توانسته است به مقدار بهینه‌ای که نرم‌افزار GAMS برای مقادیر تعداد ایستگاه‌های زوجی، کل ایستگاه‌ها و هزینه‌های نیروی انسانی گزارش داده است،دست یابد.

 

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

C

HC (دلار)

NM[NS]

(S1, S2, S3)

ET#

SA

OP

SA

OP

SA

OP

SA

OP

5

180

180

1[2]

1[2]

(2,0,0)

(2,0,0)

0/4

1/7

6

180

180

1[2]

1[2]

(2,0,0)

(2,0,0)

0/5

7/5

7

150

150

1[2]

1[2]

(1,1,0)

(1,1,0)

0/5

2/7

8

130

130

1[2]

1[2]

(1,0,1)

(1,0,1)

0/5

6/6

9

130

130

1[2]

1[2]

(1,0,1)

(1,0,1)

0/5

2/3

ET#: زماناجرا (ثانیه)، S1: تعداد کارگر با مهارت 1 ، S2: تعداد کارگر با مهارت 2،S3: تعداد کارگر با مهارت 3،OP: نتایج حاصل از GAMS

 

 

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

5- آزمایشاتعددی

برای بررسی اثربخشی الگوریتم پیشنهادی جهت حل مسئله، سه شیوۀ جستجوی همسایگی مختلف ارزیابیشد. این روش‌ها به جابه‌جایی دو عنصر(2-OPT)، جابه‌جایی سه عنصر (3-OPT) و جابه‌جایی تصادفی دو و یا سه عنصر تمرکز داشت. جزئیات پاسخ‌های به‌دست‌آمده برای مسئلۀP9 در جدول 7 آورده شده است.

 

جدول(7):بررسیقوانینمختلفهمسایگیبرایمسئلۀP9 به ازای زمان‌های سیکل مختلف

 

C

E

WSI

HC(دلار)

WLE%

2-OPT

3-OPT

2&3 OPT

2-OPT

3-OPT

2&3 OPT

2-OPT

3-OPT

2&3 OPT

2-OPT

3-OPT

2&3 OPT

p9

4

0/58

0/52

0/64

1/03

1/17

1/47

308

314

354

77/81

76/04

71/35

5

0/59

0/60

0/45

1/20

1/45

1/25

262

252

250

74/08

78/90

73/50

6

0/59

0/50

0/46

0/79

0/71

0/95

180

188

180

81/25

80/63

81/25

7

0/45

0/60

0/46

0/71

0/94

0/75

150

152

156

92/50

85/71

84/64

8

0/58

0/47

0/46

0/83

0/91

0/86

142

138

134

82/19

82/81

89/06

9

0/60

0/53

0/47

0/61

0/96

1/11

158

138

138

67/22

78/06

79/17

 

برای تنظیم پارامتر از روش براساس تاگوچی استفاده شد. هریکاز 4 پارامترTf،r،T0 و ) Lطولزنجیرهمارکوف) در 3 سطحزیربررسیشدند:

Tf=(0.5, 1, 2)

T0=(100, 500, 1000)

L=(3, 5, تعداد فعالیت‌ها)

r=(0.8, 0.9, 0.95)

با استفاده از نرم‌افزار Minitab خروجی زیر برای شاخص S/N به دست آمد:

 

شکل 4. تنظیمپارامتربهروشتاگوچی

بهکمکاینروشواضحاستکهبهترینمقادیراینپارامترهابرابرندبا:

Tf=2, L=5, T0=100, r=0.9

. مسائلP12 ،P14،P20،P25،P30،P39، P47وP65 هریک با جواب‌های ابتدایی تصادفی پنج بار اجرا شدند و بهترین و بدترین پاسخ‌های به‌دست‌آمدهبرای تعداد ایستگاه‌های زوجی، تعداد ایستگاه‌ها و کارگران با هر مهارت گزارش شده‌اند. علاوه بر این میانگین و همچنین بهترین مقادیرهرتابع هدف و کران پایین تعداد ایستگاه‌ها برای زمان‌های سیکل مختلف ارائه شده‌اند. جدول 8 این نتایج را نشان می‌دهد. واضح است که در مرحلۀ نخست، مقدارE برابر 1 است و در طی فرایند اجرای الگوریتم این مقدار کاهش می‌یابد و به بهترین مقدار به‌دست‌آمده با شرایط الگوریتم دست می‌یابد.

همچنین این جدول نشان می‌دهد براییک مسئله با تعداد فعالیت‌هاییکسان، زمان اجرا به‌ازای زمان‌های سیکل متفاوت تغییر چندانی نمی‌کند. علاوهبراینباافزایشزمانسیکلبراییکمسئله هزینه‌های نیروی انسانی کاهش می‌یابد؛ اما چنین چیزی برای شاخص‌هایWSI و WLE%صحتندارد. به‌گونه‌ایکه نمی‌توان نظم مشخصی را برای این شاخص‌ها تعیینکرد. علاوه بر این تعداد ایستگاه‌های زوجی و فردینیزباافزایشزمانسیکلکاهشیافتهاست.
6- نتیجه‌گیری

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

 

 

 

جدول(8):جزئیاتبه‌دست‌آمده از الگوریتم برای مسائل و زمان‌های سیکل مختلف

 

C

LB

E

WSI

HC

WLE%

NM[NS]

(S1,S2,S3)

ET#

M**

B***

M

B

M

B

M

B

W*

B

W

B

M

p

12

5

1

0/65

0/54

1/4

1/3

306

270

76/6

79/5

3[6]

2[4]

(0,5,1)

(0,3,1)

0/9

6

1

0/52

0/34

1/0

0/1

226

180

84/7

95/4

2[4]

1[2]

(1,3,0)

(2,0,0)

0/8

7

1

0/43

0/39

1/1

0/8

180

180

81/8

81/8

1[2]

1[2]

(2,0,0)

(2,0,0)

0/8

8

1

0/46

0/37

0/6

0/6

156

150

90/1

94/7

1[2]

1[2]

(2,0,0)

(1,1,0)

0/8

p

14

10

2

0/71

0/55

3/5

3/2

448

430

71/4

76/6

4[8]

3[6]

(0,7,1)

(3,2,1)

1/2

11

2

0/74

0/64

4/0

3/4

390

350

72/7

76/5

4[8]

3[6]

(0,5,3)

(1,3,2)

1/2

12

1

0/64

0/64

3/7

3/2

350

320

74/3

79/8

3[6]

3[6]

(1,4,1)

(0,4,2)

1/1

13

1

0/70

0/64

3/5

2/9

346

300

71/9

83/0

3[6]

2[4]

(1,4,1)

(2,2,0)

1/1

P

20

20

1

0/67

0/59

7/9

6/6

420

380

66/5

61/2

4[8]

3[6]

(1,4,3)

(2,2,2)

2/5

22

0

0/70

0/50

7/8

5/2

398

370

68/0

59/7

4[8]

3[6]

(0,5,3)

(1,4,1)

2/6

24

0

0/70

0/55

8/3

5/7

346

330

66/8

58/9

4[8]

2[4]

(2,2,2)

(3,1,0)

2/6

26

0

0/69

0/58

7/7

6/2

308

280

70/7

66/2

3[6]

2[4]

(3,1,0)

(0,2,4)

2/6

P

25

35

1

0/75

0/63

13/0

9/8

488

470

72/6

68/0

5[9]

4[8]

(0,7,2)

(1,5,2)

3/6

38

1

0/75

0/65

12/36

10/8

460

420

70/5

68/9

4[8]

4[8]

(0,5,3)

(1,6,1)

4/3

41

1

0/73

0/58

13/92

13/2

412

360

67/5

65/8

4[8]

4[8]

(2,2,4)

(0,2,6)

4/4

44

1

0/75

0/69

11/4

9/83

374

330

76/4

61/4

4[8]

3[6]

(1,4,3)

(1,2,3)

4/9

P

30

25

1

0/74

0/67

5/2

3/8

458

420

77/0

69/9

4[8]

3[6]

(2,4,2)

(0,5,3)

5/6

27

1

0/74

0/65

6/0

4/4

406

380

80/2

69/3

4[8]

3[6]

(3,3,0)

(2,2,2)

6/3

29

1

0/58

0/50

5/2

4/0

336

310

84/2

81/9

3[6]

3[6]

(1,3,2)

(1,1,4)

6/0

31

1

0/62

0/51

6/0

5/0

284

260

83/8

81/3

3[6]

3[6]

(0,1,5)

(0,3,3)

5/3

P

39

24

1

0/72

0/61

8/5

7/7

564

540

73/0

70/2

5[10]

4[8]

(1,7,2)

(0,7,3)

13/1

26

1

0/74

0/58

8/2

6/6

490

470

76/2

72/4

4[8]

5[9]

(2,4,2)

(1,3,5)

14/5

28

1

0/80

0/67

8/2

7/4

460

450

73/8

71/1

4[8]

4[8]

(1,4,3)

(1,6,1)

12/9

30

0

0/73

0/62

8/5

6/9

426

380

76/3

71/8

3[6]

4[8]

(0,3,5)

(3,3,0)

14/8

P

47

45

1

0/82

0/75

19/8

17/8

790

670

67/0

61/7

7[13]

8[15]

(3,9,2)

(1,5,7)

15/2

50

1

0/91

0/72

23/0

17/7

686

610

70/9

65/5

7[12]

6[11]

(3,8,1)

(1,4,7)

16/6

55

1

0/85

0/74

20/1

16/8

654

640

70/0

67/3

5[10]

6[12]

(4,2,4)

(5,2,3)

15/9

60

1

0/82

0/70

21/6

20/4

544

530

71/1

69/0

5[10]

5[10]

(1,6,3)

(1,4,5)

13/7

P

65

300

0

0/70

0/62

108/7

100/7

694

640

69/2

67/7

6[12]

6[12]

(4,4,4)

(0,8,4)

37/5

320

0

0/68

0/56

87/8

70/6

620

590

76/3

75/0

5[10]

5[10]

(4,3,3)

(1,7,2)

43/7

340

0

0/75

0/55

101/1

66/0

556

500

76/2

72/6

5[10]

4[8]

(6,1,1)

(0,5,5)

34/2

360

0

0/73

0/57

104/2

59/4

532

460

72/7

69/6

5[10]

4[8]

(4,4,0)

(0,3,7)

39/9

W*: بدترین نتایج،M**: متوسطنتایج ، B***: بهتریننتایجET#: زماناجرا (ثانیه) ،S1: تعداد کارگر با مهارت 1 ، S2: تعداد کارگر با مهارت2،S3: تعداد کارگر با مهارت3

 



1Baybars

2 Ghosh and Gagnon

3 Boysen et al.

4 Becker and Scholl

5 Battaïa and Dolgui

6 Lee et al.

7 Chutima& Chimklai

8 Bartholdi

9 Xiaofeng et al.

10 Özbakir & Tapkan

11 Simaria &Vilarinho

12 Özcan & Toklu

13 Tapkan et al.

14 Simaria & Vilarinho

15 Özbakir & Tapkan

16 zoning constraints

17 Chutima & Chimklai

18 Naked and Nishiwaki

19 Corominas et al.

20 Karp

21 The weighted smoothness index

22 Deb

23 Özcan & Toklu

Bartholdi J.J.)1993.("Balancing two-sided assembly lines: a case study".International Journal of Production Researc,31 (10): 2447–2461.

Battaïa O., Dolgui A.) 2013(."A taxonomy of line balancing problems and their solution approaches". Int. J. Production Economics,142 (2): 259–277.

Baybars I. (1984). "A Survey of Inexact Algorithms for the Simple Assembly Line Balancing Problem". Tech. Report GSIA WP-86-82-83, Carnegie-Mellon University.

Baybars I. ( 1986). "A survey of exact algorithms for the simple assembly line balancing problem". Management Science, 32: 909-932.

Baykasoglu A., Dereli T. ( 2008). "Two-sided assembly line balancing using an ant colony-based heuristic". International Journal of Advanced Manufacturing Technology, 36(5-6): 582–588.

Becker C., Scholl A. (2006). "A survey on problems and methods in generalized assembly line balancing". European Journal of Operational Research ,168(3): 694–715.

Boysen N., Fliedner M. (2007). "Scholl A. A classification of assembly line balancing problems". European Journal of Operational Research , 183: 674–693.

Boysen N., Fliedner M., Scholl A. (2008). "Assembly line balancing: Which model to use when?". International Journal of Production Economics, 111: 509–528.

Chutima P., Chimklai P.(2012). "Multi-objective two-sided mixed-model assembly line balancing using particle swarm optimisation with negative knowledge". Computers & Industrial Engineering,  62: 39–55.

Corominas A., Pastor R., Plans J. (2008). "Balancing assembly line with skilled and unskilled workers". OMEGA,36(6):1126-1132.

Deb K. (2001). "Multi-Objective Optimization Using Evolutionary Algorithms". John Wiley & Sons, New York, NY, USA, Inc.; 2001.

Ghosh S., Gagnon R.J.(1989). "A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems".International Journal of Production Research,  27(4): 637–670.

Hu X., Wu E., Jin Y.(2008)."A station-oriented enumerative algorithm for two-sided assembly line balancing".European Journal of Operational Research ,186: 435–40.

Karp, R.M.( 1972), "Reducibility among combinatorial problems". Proc. of a Symp. on the Complexity of Computer Computations, New York, 85-103

Kim Y.K., Kim Y., Kim Y.J. (2000). "Two-sided assembly line balancing: a genetic algorithmapproach".Production Planning and Control,  11(1): 44–53.

Nakade K., Nishiwaki R. (2008). "optimal allocation for heterogeneous workers in a U-shaped production." Computers and Industrial engineering, 54(3): 432-440.

Özbakir L., Tapkan P.(2011). "Bee colony intelligence in zone constrained two-sided assembly line balancing problem".Expert Syst Appl,  38: 11947–11957.

Özcan U. (2010). "Balancing stochastic two-sided assembly lines: a chance constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm".European Journal of Operational Research,  205: 81–97.

Özcan U., Gokcen H., Toklu B.(2010). "Balancing parallel two-sided assembly lines". International Journal of Production Research , 48(16): 4767–4784.

Özcan U., Toklu B.(2009)."Balancing of mixed-model two-sided assembly lines". Computers & Industrial Engineering, 57: 217–227.

Purnomo H.D., Wee H.M., Rau H. Two-sided assembly lines balancing with assignment restriction. Mathematical and Computer Modeling , 57: 189–199.

Simaria A.S., Vilarinho P.M. (2009). "2-ANTBAL: An ant colony optimization algorithm for balancing two-sided assembly lines". Computers & Industrial Engineering, 56: 489–506.

Taha R.B., El-Kharbotly A.K., Sadek Y.M., Afia N.H.( 2011)."A Genetic Algorithm for solving two-sided assembly line balancing problems."Ain Shams Engineering Journal, 2: 227–240.

Tapkan P., Özbakir L., Baykasoglu A. (2012). "Modeling and solving constrained two-sided assembly line balancing problem via bee algorithms". Applied Soft Computing , 12: 3343–3355.

Wu E.F., Jin Y., Bao J.S., Hu X.F.(2008)." A branch-and-bound algorithm for two-sided assembly line balancing". International Journal of Advanced Manufacturing Technology , 39: 1009–1015.

Xiaofeng H., Erfei W., Jinsong B., Ye J.(2010)."A branch-and-bound algorithm to minimize the line length of a two-sided assembly line". European Journal of Operational Research, 206 :703–707.

Xiaofeng H., Erfei W., Ye J.)2008)."A station-oriented enumerative algorithm for two-sided assembly line balancing". European Journal of Operational Research,186: 435–440.

 

 

 

 

 

 

 

 

پی نوشت: