توسعه و حل یک مدل دو هدفه جهت تکمیل توأم موجودی چند کالا با محدودیت فضای انبار

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

نویسندگان

1 دانشجوی دکتری مهندسی صنایع، دانشگاه علم و صنعت ایران و عضو هیأت علمی دانشگاه صنعتی مالک اشتر

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

چکیده

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

کلیدواژه‌ها


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

Developing and Solving a Bi-Objective Joint Replenishment Problem under Storing Space Constraint

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

  • Ommolbanin Yousefi 1
  • Mirbahadorgholi Aryanezhad 2
  • Seyed-Jafar Sadjadi 2
1 Ph.D. Student, Faculty of Industrial Engineering, Iran University of Science and Technology
2 Professor, Faculty of Industrial Engineering, Iran University of Science and Technology
چکیده [English]

In this research, a bi-objective joint replenishment problem has been developed and solved with the assumption of one restricted resource. The proposed model has a storing space constraint and tries to optimize two objective functions simultaneously. They include minimizing annual holding and setup costs and minimizing annual inventory investment. Then, for solving this problem, a multi-objective genetic algorithm (MOGA) has been developed. In order to analyze the algorithm efficiency, its performance has been examined in solving 1600 randomly produced problems using parameters extracted from literature. The findings imply that the proposed algorithm is capable of producing a good set of Pareto optimal solutions. Finally, the application of the problem solving approach and the findings of the proposed algorithm have been illustrated for a special problem, which has been randomly produced.

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

  • Joint replenishment problem
  • Multi-Objective Optimization
  • Storing space constraint
  • Genetic Algorithm

مقدمه

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

ü     تأثیرات متقابل به علت محدودیتها

ü     تأثیرات متقابل در هزینه های سفارش دهی

ü     تأثیرات متقابل در قیمتهای خرید

ü     تأثیرات متقابل در محدودیتهای تولید

در عمل مدلهای موجودی مختلفی وجود دارد که با چندین محصول در ارتباطند، هدف این مدلها، اغلب مینیمم کردن هزینه کل بوده در حالیکه تقاضا نیز برآورده شود. هزینه کل، معمولاً از دو جزء تشکیل می شود:

الف ) هزینه راه اندازی یا سفارش دهی[1]

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

ب ) هزینه نگهداری[2]

این هزینه، همان هزینه نگهداری موجودی است که شامل هزینه درگیر در موجودی، مالیات، بیمه و نظایر آن می باشد.

مهمترین مسأله در مسائل چند محصولی عبارت است از تصمیم گیری روی مقادیر بهینه محصولات مختلف در یکی از حالات زیر: (گویال [3]، 1974)

1- هنگامی که چندین کالا به یک تأمین کننده سفارش داده می شوند.

2- هنگامی که چندین محصول از تجهیزات حمل و نقل مشترک استفاده می کنند.

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

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

الف ) یک هزینه کلی سفارش دهی [4]که از تعداد محصولات مختلف در یک سفارش مستقل است.

ب ) یک هزینه جزئی سفارش دهی[5] که به تعداد محصولات مختلف در یک سفارش بستگی دارد.

مسأله فوق به «مسأله تکمیل همزمان موجودی[6] »یا JRP معروف است. به علت وجود هزینه کلی سفارش دهی، بکارگیری سفارش دهی گروهی ممکن است منجر به صرفه جویی معنی داری در هزینه ها شود. این صرفه جویی بطور قابل توجهی وقتی تقاضای بین اقلام بطور نزدیکی به‌هم مرتبط هستند، افزایش می یابد (تسا و هوانگ [7]، 2009). بعلاوه صرفه جویی حاصل از محل سفارش دهی گروهی هر چه هزینه کلی سفارش دهی بزرگتر باشد، معنی دارتر است.

استراتژیهای حل JRP می تواند به دو نوع تقسیم شود:

1- استراتژی گروهبندی مستقیم[8] (DGS)

2-استراتژی گروهبندی غیرمستقیم [9] (IGS)

در استراتژی DGS، محصولات به تعدادی گروه از قبل مشخص شده، تقسیم می شوند و محصولات داخل هر گروه، با یک زمان سیکل مشترک سفارش داده می شوند. در استراتژی IGS، سفارش دهی در فواصل زمانی منظم انجام می شود که معمولاً به آن زمان سیکل پایه گفته می شود. هر محصول، ضریب عدد صحیحی از زمان سیکل پایه را داراست و در سیکلهای سفارشی که مضرب صحیح از این ضریب است سفارش داده می شود. گروهها در استراتژی IGS، بصورت غیر مستقیم، با محصولاتی که دارای یک ضریب صحیح یکسان هستند، تشکیل می شود. آرکین[10] و همکاران(1989)، ثابت کردند که مسأله JRP، یک مسأله با پیچیدگی سخت [11] است، بنابراین الگوریتمی که در یک زمان چند جمله ای بتواند مسأله JRP مخصوصاً با ابعاد بزرگ را حل کند وجود ندارد و لذا در مقالات بسیاری، با استفاده از الگوریتم­های فراابتکاری، روش­های حل تقریبی برای مسأله توسعه داده شده است. برای اولین بارگویال(1974) با محاسبه یک حد بالا و پایین روی زمان سیکل پایه یک الگوریتم محاسباتی، برای مشخص کردن کلیه می نیمم های محلی و در نتیجه می نیمم کل ارائه داد. بنابراین رویکرد گویال منجر به یافتن جواب بهینه برای مسأله JRP می شد ولی ممکن بود از لحاظ محاسباتی برای مسائل بزرگ به جواب نرسد. سیلور[12] (1976) یک الگوریتم کارا برای حل JRP، ارائه داد که در سال 1979 توسط گویال بهبود داده شده، سپس توسط کسپی و روزنبلات[13] (1983) توسعه بیشتری یافت. این الگوریتم شاید معروفترین روش هیوریستیک در حل JRP بوده و به نام الگوریتم RAND معروف است . این الگوریتم بر اساس محاسبه m مقدار مساوی برای زمان سیکل پایه از طریق حد پائین و بالای آن یعنی روی فاصله، Tmax] [Tmin و سپس بکارگیری الگوریتم سیلور جهت بهبود الگوریتم برای هر مقدار از زمان سیکل پایه می باشد.

 

بررسی تحقیقات انجام شده

تحقیقاتی که تا کنون روی مسأله JRP انجام شده است را می توان به دو دسته کلی زیر تقسیم کرد:

ü       ارائه روشهای مختلف جهت حل مدل JRP کلاسیک

ü    توسعه مدلهای جدید از روی مسأله JRP کلاسیک و ارائه روشهای مختلف جهت حل آنها که در این مورد عمدتاً موارد زیر در تحقیقات گذشته به چشم می خورد:

الف- توسعه « مدل تکمیل موجودی توأم چند کالا در حالت احتمالی[14] » یا SJRP که در آن تقاضای محصولات به صورت احتمالی در نظر گرفته می شودو هدف مینیمم کردن هزینه مورد انتظار در هر واحد زمان می باشد.

ب- توسعه« مدل تکمیل موجودی توأم چند کالا در حالت پویا[15] » یا DJRP که در آن تقاضای قطعی است ولی نسبت به زمان یکنواخت نیست و هدف عبارتست از مینیمم کردن هزینه کل در افق برنامه ریزی که شامل چند پریود می باشد.

ج- توسعه یکی از مدلهای JRP یا SJRPیاDJRP با در نظر گرفتن شرایط خاص بعنوان مثال:

ü       در نظر گرفتن زیر مجموعه ای از پریودهای زمانی گسسته جهت تکمیل موجودی

ü       در نظر گرفتن تخفیف های مقداری کلی

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

ü       بکارگیری JRP بعنوان یک زیر مسأله در سایر مسائل

ü       در نظر گرفتن وابستگی هزینه های سفارش دهی به ترکیب موجود در کالاهایی که سفارش داده می شوند.

ü       در نظر گرفتن محدودیتهایی در مدل نظیر ظرفیتهای انبار و حمل و نقل و بودجه

ü       در نظر گرفتن تقاضای نا معین مشتری و همچنین تخمین های نا دقیق واحد هزینه نگهداری

در زمینه توسعه مدل JRP کلاسیک در شرایط خاص که تحقیق حاضر نیز به آن متعلق است، موارد زیر از ادبیات موضوع قابل استخراج می باشد، کلین و ونچورا[16] (1995) ، جهت ایجاد یک سیاست سفارش دهی ساده تر برای پیاده سازی در صنعت مدلی را ارائه دادند که در آن زمانهای تکمیل موجودی تنها به ابتدای پریودهای زمانی گسسته محدود شد. مون و چا[17](2005)، دو الگوریتم برای حل JRP، وقتی تأمین کننده تخفیف های مقداری کلی پیشنهاد می کند، توسعه دادند. نویسندگان دو قضیه اثبات کردند که سپس در توسعه دو الگوریتم برای پیدا کردن جواب بکار بردند. خوجا و همکاران[18] (2005) فرض کردند که هزینه هر واحد محصولات در یک افق زمانی محدود و متناسب با یک آهنگ پیوسته نسبت به زمان کاهشی یا افزایشی است و یک الگوریتم برای حل JRP، ارائه دادند. سیاجادی[19] و همکاران (2005)، مدلی را فرموله کرد که در آنها JRP بعنوان یک زیر مسأله بکار رفت، آنها مدل بهینه سازی تصمیمات موجودی یک فروشنده که بطور همزمان چندین قطعه را برای تولید محصول نهایی بکار می برد، را توسعه دادند. چان[20] و همکاران(2006)، یک رویکرد حل برای برنامه ریزی تحویل از یک تأمین کننده به چندین خریدار توسعه دادند که خریداران JRP را برای تکمیل موجودی خود از تأمین کننده بکار می برندو در ادامه مسأله برنامه ریزی تحویل تحت 4 هدف مختلف فرموله شد. هوک[21] (2006)، یک مدل توسعه یافته از JRP برای در برگرفتن موارد عملی با در نظر گرفتن ظرفیتهای انبار و حمل ونقل و محدودیت بودجه ارائه داده است و یک رویکرد ساده برای محاسبه حد پایین مناسب برای سیکل مشترک پایه ارائه داد. السن[22] (2008)، حالتی از مسأله JRP را در نظر گرفت که در آن هزینه های جزئی سفارش دهی به یکدیگر وابسته اند. وابستگی خطی هزینه های جزیی سفارش دهی در JRP، هنگامی رخ می دهد که هزینه وارد کردن یک آیتم در یک سفارش به اینکه کدامیک از کارهای دیگر در سفارش هستند، بستگی دارد وی در ادامه، یک الگوریتم تکاملی [23] (EA) برای حل چنین مسأله ای ارائه داد. در مقاله ای که وانگ[24] و همکاران (2008) ارائه دادند به مطالعه ای از مسأله JRP، تحت تقاضاهای نا معین مشتری و تخمین نا دقیق واحد هزینه نگهداری پرداختند. سو[25] (2009)، مسأله JRP را برای مدلسازی تصمیمات موجودی برای یک کارخانه مرکزی و شعبه های آن در یک سیستم تولید بهنگام بکار گرفت. لی[26] (2004) یک مدل JRP وقتی چندین خریدار وجود دارند مدلسازی کرده و با توسعه ای از الگوریتم RAND آنرا حل نمود. اکثر مدلهای موجودی چندین مفهوم هزینه ای و نیز احتیاجات سطح سرویس دهی به مشتری را در داخل یک تابع هدف تکی جایگزین می کنند، سپس تصمیمات بهینه در مورد اینکه چقدر سفارش داده شود و کی سفارش داده شود، توسط روشهای سنتی بهینه سازی آغاز می شود، در حالیکه موارد زیادی در مسائل مربوط به سیستم های واقعی کنترل موجودی وجود دارد که تصمیم گیرندگان مایل به بهینه سازی بیش از یک هدف که بعضاً ممکن است با یکدیگر در تضاد نیز باشند هستند. در مورد مسأله JRP، تا کنون به حالتی که بیش از یک هدف در مدل در نظر گرفته شده و در نتیحه بر کارایی کاربردی و عملی آن بیفزاید، پرداخته نشده است. در مقاله حاضر به مدلسازی مسأله JRP با در نظر گرفتن دو هدف پرداخته شده است و از طرفی جهت کاربردی تر شدن مدل، محدودیت فضای انبار نیز که در عمل اکثر سیستمهای کنترل موجودی با آن مواجه هستند نیز به مدل اضافه شده است. هدف دیگر مقاله حاضر، ارائه یک رویکردی کارا برای حل مسأله پیشنهادی است که به این منظور به توسعه الگوریتم ژنتیک چند هدفه که کارایی خوبی برای بهینه سازی مسائل چند هدفه از خود نشان داده است پرداخته و نتایج حاصل نشان داده شده است. روش انجام تحقیق حاضر، روش اسنادی و مطالعات کتابخانه ای یا مراجعه به منابع در دسترس در خصوص موضوعات مرتبط با موضوع تحقیق می باشد. همچنین استفاده از نرم افزارهای محاسباتی و برنامه نویسی پیچیده و بهره گیری از امکانات کامپیوترمنا سب در اجرای مدل توسعه داده شده ضروری خواهد بود. در ادامه مطالب ارائه شده در مقاله حاضر در 5 بخش ارائه می شود. در قسمت سوم به معرفی مدل پیشنهادی می پردازیم. به معرفی الگوریتم ژنتیک چند هدفه در بخش چهارم پرداخته می شود. توسعه الگوریتم ژنتیک چند هدفه برای حل مدل پیشنهادی در قسمت پنجم انجام می شود. در قسمت ششم نتایج حاصل از حل مسأله با روش پیشنهادی ارائه می شود و در قسمت هفتم نیز به جمع بندی، نتیجه گیری و ارائه پیشنهاد برای ادامه تحقیق در مورد این موضوع می پردازیم.

 

معرفی مدل دو هدفه تکمیل توأم موجودی چند کالا با وجود محدودیت فضا

در این قسمت به معرفی فرضیات، پارامترها و متغیرهای تصمیم در مدل پیشنهادی پرداخته و سپس مدل نهایی ارائه می شود.

 

فرضیات

فرضیات مدل، شبیه فرضیات در مدل JRP کلاسیک می باشد که آن هم شبیه فرضیات مدل «مقدار سفارش اقتصادی[27]» یا همان EOQاست که این فرضیات عبارتند از:

1-      وجود تقاضای قطعی و یکنواخت

2-      عدم وجود تخفیف

3-      خطی بودن هزینه نگهداری

4-      عدم مجاز بودن کمبود

علاوه بر آن فرضیات زیر نیز اضافه می شوند:

5-      استفاده از استراتژی IGS

6-      محدودیت فضای انبار

 

پارامترهای مدل

n: تعداد محصولات

i: اندیس محصولات n , ... , i = 1

Di: تقاضای سالیانه محصول i ام

hi: هزینه نگهداری سالیانه برای محصول i ام

S: هزینه کلی سفارش دهی در هر بار سفارش

si: هزینه جزئی سفارش دهی که در صورت سفارش محصول iام سفارش داده شود پرداخت می شود

ci: هزینه خرید یک واحد محصول i ام

V: ماکزیمم فضای انبار

vi: فضای لازم برای انبار کردن یک واحد کالای i‌ام

 

متغیرهای تصمیم

Qi: میزان سفارش محصول i ام (واحد کالا)

T: زمان بین دو سفارش متوالی یا زمان سیکل پایه

Ti: فاصله زمانی بین دو سفارش متوالی محصول i ام

ki: ضریب عدد صحیح سفارش دهی محصول i ام

متغیرهای تصمیم ا صلی عبارتند از Tو ki، بطوریکه مطابق روابط 1و2 متغیرهای Qiو Ti از روی آنها قابل بدست آوردن هستند.

(1)

 

 (2)

 

 

توابع هدف

الف) هزینه کل سفارش دهی [28] (TCS) و نگهداری موجودی[29] (TCH) در واحد زمان (f1 )

ب ) هزینه کل سرمایه درگیر در موجودی (f2 )

 

 مدل پیشنهادی

(3)

 

 (4)

 

 (5)

 

 

 

 

توسعه الگوریتم ژنتیک چند هدفه برای حل مدل پیشنهادی

بهینه سازی مسائل چند هدفه

یک دسته از سخت ترین و در عین حال پرکاربردترین مدلها در مسائل بهینه سازی، مسائل چند هدفه هستند. در یک مسأله بهینه سازی چند هدفه، معمولاً یک جواب بهینه منحصر به فرد وجود دارد ولی در مسائل بهینه سازی چند هدفه، توابع هدف ممکن است با یکدیگر در تعارض باشند، بنابراین پیدا کردن یک جواب بهینه بطوریکه بصورت همزمان کلیه اهداف را بهینه کند معمولاًامکان پذیر نیست. یکی از روشهای حل اینگونه مسائل ادغام کردن اهداف مختلف در یک تابع هدف است. در چنین مواردی جواب بهینه با استفاده از متدهایی نظیر تابع مطلوبیت و یا مجموع وزین توابع هدف بدست می آید، و لیکن در این روشها نیز انتخاب اوزان مناسب برای توابع هدف و یا انتخاب یک تابع مطلوبیت مناسب یک چالش محسوب می شود. از جمله روشهای دیگر حل مسائل چند هدفه، روشهایی هستند که هدفشان بدست آوردن جوابهای بهینه پارتویی و یا زیر مجموعه ای کارا ازآن می باشد. مجموعه جوابهای پارتویی[30] شامل جوابهایی می شود که توسط هیچ جواب دیگری ازمجموعه جوابهای امکان پذیر مسأله چیره[31] نمی شوند. یک جواب چیره ناپذیر جوابی است که بهبود در یک تابع هدف آن منجر به بدتر شدن حداقل یک تابع هدف دیگر می شود. با استفاده از چنین روشهایی وارائه مجموعه جوابهای چیره ناپذیر، این فرد تصمیم گیرنده است که با توجه به تبادل[32] بین اهداف به انتخاب جواب مطلوب خود می پردازد. (کناک[33] و همکاران، 2006)

 

الگوریتمهای تکاملی چند هدفه[34]

در طی دهه گذشته الگوریتمهای مبتنی بر جمعیت مانند الگوریتمهای ژنتیک در بهینه سازی مسائل چند هدفه کاربرد زیادی پیدا کرده اند، چرا که این الگوریتمها می توانند مجموعه جوابهای پارتویی را با یک بار اجرای الگوریتم بدست آورند، در حالیکه سایر روشهای بهینه سازی سنتی با چند بار اجرای متوالی و جدا گانه به این مجموعه دست پیدا می کنند. (کناک و همکاران، 2006)

در یک الگوریتم تکاملی چند هدفه که یک توسعه از الگوریتم تکاملی است به دو سؤال اساسی بایستی پاسخ داده شود:

1- مکانیزم انتخاب کروموزومها به نحوی که جوابهای چیره ناپذیر شانس بیشتری برای انتخاب و ایجاد نسل بعد را داشته باشند.

2- مکانیزم ایجاد تنوع در جوابهای تولید شده به نحوی که حتی المقدور کل فضای جواب جستجو شده و تا حد امکان کل مجموعه جوابهای پارتویی ارزیابی شود.

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

1- توابع ادغامی[35] که مجموع وزین توابع هدف را بعنوان یک تابع هدف کلی در نظر می گیرند.

2- روشهای مبتنی بر جمعیت [36]، به عنوان یک مثال کلاسیک از این دسته VEGA[37] را می توان نام برد.

3- روشهای مبتنی بر جوابهای پارتویی[38]، یک مثال کلاسیک از این دسته MOGA[39] است.

 

 الگوریتم ژنتیک چند هدفه (MOGA)

در مکانیسم انتخاب در MOGA رتبه هر کروموزوم در جمعیت برابر است با تعداد جوابهایی که آنرا چیره می کنند. کل جوابهایی که چیره ناپذیرند دارای رتبه برابر هستند و در نتیجه شانس برابری برای انتخاب در تکرار بعد و تولید جمعیت جدید را دارند. MOGA به منظور ایجاد پراکندگی لازم در فضای جواب از رویکرد اشتراک برازندگی[40] برای بدست آوردن جوابهایی که بطور یکنواخت در مجموعه جوابهای پارتو توزیع شده اند، استفاده می کند. در این تکنیک جوابهایی که در مناطقی قرار دارند که چگالی جوابهای یکسان در آنها زیاد است، برازندگیشان کاهش می یابد.

برای توسعه هر الگوریتم ژنتیک اجزاء اصلی و مهم الگوریتم بایستی به دقت تعریف شوند که در ادامه به معرفی آنها می پردازیم:

 

 

حدود متغیرهای تصمیم

همانطور که قبلاً نیز اشاره شد در استراتژی IGS که ما نیز از آن استفاده می کنیم متغیرهای تصمیم عبارتند از، زمان سیکل پایه(T) و ضرایب عدد صحیح مربوط به هر کالا(ki,s). حد بالا و پایین مقادیر T را بصورت زیر در نظر می گیریم (خوجا و همکاران، 2000):

(6)

 

(7)

 

حد پایین برای مقادیر(ki,s) که مسلماً عبارتست از ki(min) =1 برای بدست آوردن حد بالا هم ابتدا مقادیر Ti(in) از فرمول EOQ بصورت مستقل برای هر کالا بدست می آید و سپس Tmin به صورت زیر بدست می آید (خوجا و همکاران، 2000).

(8)

 

(9)

 

بطوریکه در رابطه فوق منظور ازنماد [a] اولین عدد صحیح بزرگتر از a است.

تابع هدف دوم ما بر روی روابط فوق بی تأثیر است ولی محدودیت مدل، Tmax را بصورت زیر تغییر می کند:

(10)

 

 

نمایش[41]

یکی از مهمترین مسائل در الگوریتم ژنتیک، نحوه باز نمایی یا کد کردن جوابها می باشد. در مدل پیشنهادی ما، یک کروموزوم یا یک جواب حاوی (n+1) ژن می باشد، بطوریکه n ژن اول که مقادیر عدد صحیح بوده حاوی مقادیر (ki,s) می باشند و یک ژن آخر حاوی مقدار مربوط به زمان سیکل پایه بوده و متغیری پیوسته می باشد.

 

جمعیت اولیه[42]

جمعیت اولیه بصورت تصادفی ایجاد می شود. برای ایجاد هر عضو جمعیت، ابتدا n عدد تصادفی عدد صحیح بین ki(min) و ki(max) تولید می شود و سپس یک عدد تصادفی پیوسته بین Tmin و Tmax ایجاد می شود. قاعدتاً از بین جوابهای تولید شده جوابهایی قابل قبول هستند که در محدودیت مدل صدق کنند.

 

استراتژی انتخاب[43]

برای انتخاب والدین[44] از میان جمعیت برای ایجاد نسل بعدفرزندان[45] از مکانیسم چرخ رولت[46] استفاده می شود. در این مکانیزم انتخاب کروموزومها احتمالی است، به طوریکه کروموزومهای با تابع برازندگی بیشتر شانس بیشتری برای انتخاب شدن دارند و در واقع احتمال انتخاب i امین کروموزوم با تابع برازندگی fi، عبارتست از  .

 

تابع برازندگی[47]

میزان برازندگی هر کروموزوم مطابق مراحل زیر ارزیابی می شود:

1- برای هر کروموزوم در هر تکرار، رتبه آن یعنیr(x,t) مطابق رابطه زیر محاسبه می شود:

 

nq(x,t) عبارتست از تعداد جوابهایی که در تکرار t، جواب x را چیره می کنند. و منظور از pt، تکرار t ام جمعیت می باشد.

2- برای هر جواب بر اساس رتبه بدست آمده یک مقدار برازندگی مطابق رابطه زیر محاسبه می شود:

(12)

 

nk عبارتست از تعداد جوابهای با رتبه k و لذا  عبارتست از تعداد جوابهای با رتبه r(x,t)

1- برای هر جواب یک شمارنده تشابه یعنی nc(x,t) مطابق رابطه زیر محاسبه می کنیم:

 

(13)

 

shareσ آستانه تشابه نام دارد و می تواند بین 0 تا 1 تغییر کند.

dz(x,y) فاصله اقلیدسی بین دو جواب x,y در فضای نرمال سازی شده توابع هدف بوده و بین صفر و یک می باشد و مطابق رابطه زیر بدست می آید:

(14)

 

 

1- برای هر جواب  مقداربرازندگی اشتراکی یعنی  مطابق رابطه زیر بدست می آید:

(15)

 

2- مقادیربرازندگی با بکارگیری مقادیر برازندگی اشتراکی به صورت زیر نرمالسازی می شود:

(16)

 

 

 تقاطع[48] و جهش[49]

بعد از انتخاب والدین با مکانیزم چرخ رولت و بر اساس  که در رابطه 16 ارائه شد، فرزندان با دو مکانیزم تقاطع و جهش تولید می شوند. متدهای مختلفی برای انجام این دو عملگر وجود دارند. در اینجا از متد نقطه تصادفی جهت عملگر تقاطع استفاده می شود، بطوریکه این عملگر با احتمال pc عمل می کندو تعدادی کروموزوم تصادفی از دو والد با مکان مشترک را نتخاب می کند و جای آنها را تعویض می کند. بعد از تولید فرزندان با این مکانیزم، عملگر جهش به کار گرفته می شود که در این عملگر هر کروموزوم با احتمال ضعیف برابر pmتغییر می کند. در هر یک از دو عملگر فوق مقدار هر کروموزوم بین حدود پایین و بالایی که در قسمتهای قبل ارائه شد تغییر می کند و همچنین تنها جوابهایی که در محدودیت مسأله صدق کنند قابل قبول خواهند بود.

 

جایگزینی[50]

بعد از تولید قرزندان، مجدداً از مکانیزم چرخ رولت استفاده می شود وبه تعداد اندازه جمعیت که از قبل تعریف شده است، از فرزندان جدید و نسل قبل به نسل بعد منتقل می شوند.

 

شرط توقف[51]

هر گاه تعداد جوابهای بهینه پارتویی در طی 50 تکرار متوالی تغییر نکند، الگوریتم متوقف خواهد شد.

 

مراحل کلی الگوریتم ژنتیک چند هدفه

قدم 1: با یک جمعیت اولیه تصادفی(p0) شروع کنید(t=0)

قدم 2: اگر شرط توقف برقرار است متوقف شوید، جواب نهایی عبارت است از pt

قدم 3: برای هر عضو جمعیت مقدار تابع برازندگی f (2) (x,t) را با استفاده از رابطه 16 محاسبه کنید.

قدم 4: با استفاده از متد چرخ رولت و بر اساس مقادیر f (2) (x,t) والدها را جهت تولید نسل بعد انتخاب کنید.

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

قدم 6: با استفاده از مکانیزم چرخ رولت از مجموع والدین و فرزندان تولید شده به تعداد اندازه جمعیت کروموزوم انتخاب کنید.

قدم 7: قرار دهید t = t + 1 و به قدم 2 بروید.

 

نتایج حاصل از اجرای مدل

برای بررسی عملکرد الگوریتم پیشنهادی جهت حل مدل، الگوریتم پیشنهادی روی 1600 مسأله که هر یک بصورت تصادفی ایجاد شده اند، تست شده است . هر مسأله دارای 6 پارامتر اصلی است که از مقاله خوجا و همکاران(2000) استخراج شده و در جدول 1 خلاصه شده است، همچنین پارامترهای مورد نیاز الگوریتم نیز در جدول 2 خلاصه شده است. این پارامترها با تکرار الگوریتم به تعداد دفعات زیاد و مطابق با بهترین نتایج حاصل انتخاب شده است.

 

 

 

 

 

 

 

 

 

جدول1. مقادیر پارامترهای هر مسأله

حدود مقادیر پارامتر

پارامتر

[100,100000]

تقاضا(Di)

5,10,15,20

هزینه کلی سفارش دهی(S)

[0. 5,5]

هزینه سفارش دهی جزیی (si)

10,20,30,50

تعداد محصولات (n)

[0. 2,3]

هزینه نگهداری

1

قیمت خرید هر قلم کالا

1

فضای مورد نیاز جهت انبار هر قلم کالا

 

جدول 2. مقادیر پارامترهای الگوریتم

مقدار

پارامتر

100

سایز جمعیت

6/0

احتمال انجام عملگر تقاطع

2/0

احتمال انجام عملگر جهش

1

 

 

 

برای هر مقدار n و S که با توجه به جدول 1 شامل 16 مقدار می شود، 100 مسأله تصادفی تولید شده که تفاوت آنها در مقادیر Di و siوHi می باشد، این مسائل با الگوریتم پیشنهادی که توسط نرم افزار ویژوال بیسیک 2007 کد شده، حل گردیده و نتایج حاصل در جدول 3 خلاصه شده است. ستون پنجم این جدول نشان دهنده متوسط تعداد جوابهای بهینه پارتویی است که برای هر ردیف در 100 مسأله تصادفی ایجاد شده، بدست می آید. روند تغییرات این مقادیر در نمودار 1 نشان داده شده است، همانگونه که این نمودار نشان می دهد با افزایش ابعاد مسأله تعداد جوابهای پارتویی نیز افزایش یافته است . در ادامه در هر ردیف این جدول برای هر مسأله تولید شده از بین جوابهای بهینه پارتویی مقدار مینیمم f1 را انتخاب کرده و میانگین آن را روی هر 100 مسأله محاسبه کرده واز مقادیر متناظر f2 آنها نیز میانگین گرفته و این مقادیر را در ستون ششم و هفتم جدول ارائه شده است. همین کار برعکس برای مقادیر می نیمم f2 و مقادیر متناظر f1 نیز انجام شده و نتایج درستون هشتم و نهم جدول ارائه شده است. ستون دهم جدول تفاضل ستونهای 8 و6 و ستون یازدهم تفاضل ستونهای 9و 7 جدول می باشد هر چه مقادیر دو ستون آخر جدول بزرگتر باشد نشان دهنده این است که جوابهای پارتویی دارای پراکندگی بیشتری هستند. این مقادیر در قالب نمودار 2 نمایش داده شده است، همانگونه که ملاحظه می کنید؛ اولاً با افزایش ابعاد مسأله این مقادیر زیادتر شده و در واقع جوابهای پارتویی دارای تنوع بیشتری می شوند و ثانیاً در کل مقادیر مربوط به f1 نسبت به مقادیر f2 از پراکندگی بیشتری برخوردارند.

 

 

جدول 3. نتایج حاصل اجرای 1600 مسأله تصادفی

ردیف

حداکثر فضای در دسترس(میلیون)

تعداد کل کالاها(N)

هزینه کلی سفارش دهی(S)

متوسط تعداد جوابهای بهینه پارتویی

مقایسه مینیمم f1 و مقادیر متناظر f2

مقایسه مینیمم f2 و مقادیر متناظر f1

متوسط f1- متوسط مینیمم f1

متوسط f2- متوسط مینیمم f2

متوسط مینیمم f1

متوسط f2

متوسط f1

متوسط مینیمم f2

1

3

10

5

2. 93

7,395

5,180

7,937

4,781

542

399

2

6

10

10

2. 15

7,833

5,109

8,133

4,953

300

157

3

9

10

15

2. 19

8,678

5,731

8,967

5,527

290

204

4

12

10

20

1. 8

9,240

5,843

9,572

5,758

332

85

5

10

20

5

3. 19

19,049

12,971

19,755

11,910

706

1,061

6

20

20

10

2. 64

19,257

12,561

19,968

11,846

711

715

7

30

20

15

3. 01

20,717

13,022

21,572

12,590

855

432

8

40

20

20

2. 22

21,932

13,662

22,310

13,175

378

487

9

30

30

5

3. 19

32,589

20,925

33,810

20,063

1,221

862

10

45

30

10

3. 14

37,269

23,218

38,265

22,597

996

621

11

68

30

15

3. 02

39,027

25,429

40,436

24,644

1,410

786

12

90

30

20

3. 2

43,017

27,890

44,708

26,898

1,691

993

13

50

50

5

3. 59

46,146

29,710

47,052

28,826

906

884

14

100

50

10

3. 33

52,881

34,764

54,323

33,657

1,442

1,107

15

150

50

15

3. 83

56,024

36,799

57,799

35,743

1,775

1,056

16

200

50

20

4. 2

56,150

40,342

57,976

39,424

1,826

918

متوسط

3

29,825

19,572

30,787

18,899

961

673

 

 

نمودار1. متوسط تعداد جوابهای بهینه پارتویی برای مقادیر مختلف n وS

 

نمودار 2 . میزان پراکندگی جوابهای پارتویی

 

 

در ادامه نتایج حاصل از اجرای یک مسأله تصادفی ارائه می شود. در این مسأله پارامترها عبارتند از: N=30,S=15, . الگوریتم پیشنهادی طی 457 تکرار این مسأله را حل کرده است . روند تغییرات تعداد جوابهای پارتویی که مسأله طی تکرارهای متوالی الگوریتم به آن دست پیدا کرده در نمودار 3 ارائه شده است . همانگونه که ملاحظه می شود و در شرط توقف الگوریتم نیز ذکر شد در طی 50 تکرارآخر الگوریتم این تعداد بدون تغیر مانده است.

 

 

 

نمودار 3. روند تغییر تعداد جوابهای بهینه پارتویی در طی تکرارهای الگوریتم

 

 

جوابهای نهایی این مسأله که شامل 7 جواب بهینه پارتویی می شود در نمودار 4 ارائه شده است. همانگونه که ملاحظه می‌کنید هیچ یک از این جوابها دیگری را مغلوب نمی کند، یا به عبارت ساده تر جوابی که هر دو تابع هدفش از دو تابع هدف سایر جوابها بهتر باشد وجود ندارد و نهایتاً این تصمیم گیرنده است که با توجه به تبادلات بین اهداف یکی از این جوابهای پارتویی را به عنوان جواب رضایت بخش خود انتخاب می کند. لازم به ذکر است که در هر تکرار الگوریتم تعدادی جواب پارتویی بدست می آید که ممکن است لیست جوابهای پارتویی که تا آن تکرار بدست آمده را تغییر دهد. بعنوان نمونه در نمودار 5 جوابهای پارتویی تکرار آخر که شامل 5 جواب می باشد ارائه شده است. روند بهبود f1 و f2 طی تکرارهای متوالی الگوریتم نیزبه ترتیب در نمودارهای 6و7 آمده است، همانگونه که ملاحظه می کنید شیب بهبود در مورد هر دو نمودار در ابتدای الگوریتم تندتر از تکرارهای پایانی است که نشان دهنده عملکرد منطقی الگوریتم پیشنهادی است. لازم به ذکر است که برای حل این مسأله از پارامترهای جدول 2 استفاده شده است، ولی برای حل این مسأله یا هر مسأله دلخواه دیگری میتوان با ترکیبات مختلف پارامترها مسأله را حل کرد تا بهترین ترکیب پارامترها برای هر مسأله بدست آید.

 

 

 

نمودار 4. جوابهای بهینه پارتویی نهایی

 

 

نمودار 5. جوابهای بهینه پارتویی تکرار آخر الگوریتم

 

 

نمودار 6. روند بهبود f1 در طی تکرارهای الگوریتم

 

نمودار 7. روند بهبود f2 در طی تکرارهای الگوریتم

 


7- نتیجه گیری و پیشنهادات

معمولاًدر بسیاری از مدلهای کنترل موجودی، به علت ارتباطات بین کالاها بعنوان مثال استفاده از فضای انبار مشترک یا بودجه مشترک و یا مشترک بودن قسمتی از هزینه های سفارش دهی، سیستم های کنترل موجودی به صورت مستقل برای کالاهای مختلف عمل نمی کنند و اصطلاحاً بایستی از سیستم هایی که سفارشات کالاها را بصورت توأم در نظر می گیرد، استفاده نمود. یکی از این نوع سیستم ها مدل تکمیل موجودی توأم کالاها(JRP) است. در تحقیق حاضر حالت خاصی از این مدل که در عمل می تواند مفید باشد ولی تا بحال بدان پرداخته نشده توسعه داده شده و حل گردیده است. در مدل پیشنهادی برای مسأله JRP کلاسیک دو تابع هدف در نظر گرفته شده و همچنین محدودیت فضای انبار که معمولاً در عمل با آن مواجهیم نیز به مدل اضافه شده است. بعنوان تحقیقات آتی می توان به این مدل توابع هدف یا محدودیت های دیگری را نیز اضافه کرده و یا جایگزین توابع هدف و محدودیت موجود نمود . از آنجاییکه مدل پیشنهادی با الگوریتمهای ریاضی دقیق قابل حل نیست، جهت حل به توسعه یکی از الگوریتمهای متاهیوریستیک که کارایی خوبی در حل مسائل چند هدفه از خود نشان داده است یعنی الگوریتم ژنتیک چند هدفه، پرداخته ایم. برای یک مسأله نمونه تعداد جوابهای بهینه پارتویی نمایش داده شده، همچنین روند کاهش دو تابع هدف درطی تکرارهای متوالی الگوریتم را نمایش داده و نشان داده ایم که میزان کاهش در تکرارهای ابتدایی الگوریتم بیشتر است. به منظور بررسی عملکرد کلی الگوریتم، 1600 مسأله به صورت تصادفی تولید کرده و حل شده است . روند تغییر تعداد جوابهای بهینه پارتویی با افزایش ابعاد مسأله نمایش داده و نشان داده شده است که این تعداد با افزایش ابعاد مسأله افزایش می یابد. همچنین نشان داده ایم که پراکندگی جوابهای بهینه پارتویی نیز با افزایش ابعاد مسأله افزاش می یابد. در زمینه توسعه الگوریتم کاراتر جهت حل مدل برای تحقیقات آتی می توان به توسعه الگوریتمهای هیوریستیک موجود در حل JRP کلاسیک مانند الگوریتم RAND پرداخت. به نظر می رسد ترکیب الگوریتم RAND و ژنتیک چند معیاره می تواند هم کیفیت جوابها را بهبود می دهد و هم زمان رسیدن به جواب نهایی را کاهش دهد و لذا توسعه چنین الگوریتمی هم می تواند زمینه ای برای تحقیقات آتی باشد.



[1] Set up or ordering cost

[2] Holding cost

[3] Goyal

[4] Major ordering cost

[5] Minor ordering cost

[6] Joint Replenishment Problem (JRP)

[7] Tsai and Huang

[8] Direct Grouping Strategy (DGS)

[9] Indirect Grouping Strategy (IGS)

[10] Arkin

[11] NP-hard

[12] Silver

[13] Kaspi and Rossenbllat

[14] Stochastic demand joint replenishment problem(SJRP)

[15] Dynamic demand joint replenishment problem (DJRP)

[16] Klein and Ventura

[17] Moon and Cha

[18] Koudja et al

[19] Siadjadi et al

[20] Chan et al

[21] Hoque

[22] Olsen

[23] Evolutionary Algorithms

[24] Wang et al

[25] Hsu

[26] Li

[27] Economic Order Quantity

[28] Total cost of set up

[29] Total cost of holding

[30] Pare to solution

[31] Dominate

[32] Trade off

[33] Konack et al

[34] Multi-Objective Evolutionary Algorithms

[35] Aggregate functions

[36] Population-based approaches

[37] Vector Evaluated Genetic Algorithm

[38] Pareto-based approaches

[39] Multi-Objective Genetic Algorithms (MOGAs)

[40] Fitness sharing

[41] Representation

[42] Initial population

[43] Selection strategy

[44] Parents

[45] Offsprings

[46] Roulette-wheel selection mechanism

[47] Fitness function

[48] Crossover

[49] Mutation

[50] Survive selection

[51] Stopping criteria

Arkin, E. , Joneja, D. , & Roundy,. R (1989). Computational com­plexity of uncapacitated multi echelon production planning problems. Operations Research Letters , 8, 61-66.

Chan, C. K. , Yuk-on Li, L. , To Ng, C. , Kin-sion Cheung, B. , & Langevin, A. (2006). Scheduling of multi-buyer joint replenishments. International Journal of Production Economics, 102,132-142.

Goyal, S. K. , & Belton, A. S. (1979) . A simple method of determining order quantities in joint replenishments under deterministic demand. Management Science , 25, 604- 614.

Goyal, S. K . (1974). Determination of optimum packaging fre­quency of items jointly replenished. Management Science, 21,436-443.

Hoque, M. A. (2006). An optimal solution technique for the joint replenishment problem with storage and transport capacities and budget constraints. European Journal of Operational Research, 175, 1033-1042.

Hsu, S. L. (2009). 0ptimal joint replenishment decisions for a central factory with multiple satellite factories. Expert Systems With Applications, 36,2494-2502.

Kaspi, M. , & Rosenblatt, M. J. (1983). An improvement of silver's algorithm for the joint replenishment problem. IIE Transac­tions, 15,264-269.

Khouja, M. , Goyal, S . (2008). A review of the joint replenishment problem literature:1989-2005. European Journal of Operational Research ,186 ,1–16.

Khouja, M. , Park, S. , & Saydam, C. ( 2005). Joint replenishment problem under continuous unit cost change . International Journal of Production Research, 43,311-326.

Khouja, M. , Michalewicz, M. , & Satoskar ,S. (2000). A comparison between genetic algorithms and the RAND method for solving the joint replenishment problem. Production Planning and Control, 11,556-564.

Klein, C. M. ,& Ventura, J. A. (1995). An optimal method for a deterministic joint replenishment inventory policy in discrete time. The Journal of the Operational Research Society, 46,643-657.

Konak ,A. ,Coit, D. W. ,& Smith, A. E. (2006). Multi-objective optimization using genetic algorithms: a atutorial. Reliability Engineering & System Safety,91,992-1007.

Li,Q. (2004). Solving the multi-buyer joint replenishment problem with the RAND method. Computer and Industrial Engineering ,466,755-762.

Moon, I. K. , & Cha, B. C. (2oo6). The joint replenishment problem with resource restriction. European Journal of Operational Research , 173, 190-198.

Olsen, A. (2008). Inventory replenishment with interdependent ordering: An evolutionary algorithm solution. International Journal of Production Economics ,113,359-369.

Siajadi, H. , Ibrahim, R. N. ,Lochert, P. B. , & Chan, W. M. ( 2005). Joint replenishment policy in inventory production systems. Production Planning and Control, 16 ,255-262.

Silver, E. (1976). A simple method of determining order quantities in joint replenishments under deterministic demand. Man­agement Science, 22, 1351-1361.

Tsai, C. Yu. , Tsai, C. Ya. ,& Huang, P. W. ( 2009 ). An association clustering algorithm for can order policies in the joint replenishment problem. International Journal of Production Economics, 117 ,30-41.