کاربرد مساله اندازه انباشته چند سطحی با در نظر گرفتن موجودی تخریب شدنی و هزینه‏ های دفع

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

نویسندگان

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

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

چکیده

در این پژوهش، مدل مسأله اندازه انباشته چند سطحی[i] مورد استفاده برایتعیین اندازه انباشته تولید در محیط­های صنعتی، توسعه داده شده و مسأله جدیدی با عنوان مسأله اندازه انباشته چند سطحی با موجودی تخریب شدنی و هزینه­های دفع[ii] ارائه می گردد. در مسأله ارائه شده، فرض موجودی تخریب شدنی[iii] به منظور با پوشش قرار دادن محصولاتی از قبیل الکل، گازوئیل، مواد رادیو­ اکتیو، مواد غذایی و سایر کالاهای تخریب شدنی به مدل مسأله اندازه انباشته چند سطحی افزوده شده است. علاوه­بر این، میزانی هزینه با عنوان هزینه­های دفع که بیانگر هزینه دور کردن موجودی­های فاسد شده از محیط انبار با مدل تعمیم یافته ترکیب شده و این مدل را کامل‌تر و به واقعیت نزدیکتر می‌نماید. این هزینه دفع، شامل هزینه هر واحد دفع و هزینه ثابت دفع (مستقل از میزان موجودی فاسدشده) است. در مسأله جدید علاوه­بر تعیین میزان تولید و زمان تولید هر یک از محصولات در هر یک از سطوح تولید، دوره­های زمانی که در آن موجودی­های فاسد شده دفع می‏شوند نیز تعیین می‏شوند و در تابع هدف مسأله نیز مجموع هزینه­های دفع اضافه می­گردد. از آنجایی که مسأله اندازه انباشته چند سطحی یک مسأله NP-hard است، برای حل مسأله از دو الگوریتم­ فراابتکاری شامل الگوریتم ژنتیک[iv] و شبیه سازی تبرید[v] استفاده می­شود. به منظور مقایسه کارایی الگوریتم­های پیشنهادی با یکدیگر و همچنین، با روش­های موجود در ادبیات موضوع، مسائل نمونه مطابق با پژوهش­های پیشین ایجاد شده و به بررسی و تحلیل روش­های حل پرداخته شده است.



[i]- Multi-Level Lot Sizing Problem (MLLSP


[ii]- Disposal costs


[iii] -Deterioration Inventory


[iv] -Genetic Algorithm(GA)


[v] -Simulated Annealing (SA) Algorithm

کلیدواژه‌ها


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

Multi-Level Lot Sizing Problem with Deterioration Inventory and Disposal Costs

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

  • Mahmood Vahdani 1
  • Ardeshir Dolati 2
1 M.Sc of Industrial Engineering, University of Shahed, Tehran, Iran
2 Associate Professor, Department of science, University of Shahed, Tehran, Iran
چکیده [English]

In this paper, a multi-level lot sizing problem has been developed which is used to determine the production lot sizes in industrial environments, and the new problem is introduced as “multi-level lot sizing problem with deteriorating inventory and disposal costs”. The aim of multi-level lot sizing problem is to determine the production quantity in production periods for each product in each level, so that the total cost production costs, holding costs and setup costs minimized.
In the proposed model, the deteriorating property of inventory is considered.Also, deteriorating property of inventory is added to the lot sizing model in order to cover the products such as alcohol, gasoline, radio-active materials, foods and other deteriorating goods. Furthermore, disposal costs that represent the costs for removing the perishable inventories from the storage environments, is combined with the generalized model in order to make the model closer to reality. Disposal cost consists of per unit disposal cost and fixed disposal cost. In the new problem, the production quantity for each product in each level, the periods in which the perishable inventory to be disposed will be determined. Also, the disposal costs are considered in the objective function of the problem. As multilevel lot sizing problem is NP-hard, meta-heuristic algorithms consist of genetic algorithm and simulated annealing algorithm are used to solve the proposed problem. In order to compare the performance of the proposed algorithms with existing methods in the literature, instance problems are created and the results are analyzed.

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

  • Multi-level lot sizing problem
  • Deteriorating inventory
  • Disposal costs
  • Genetic Algorithm
  • Simulated Annealing Algorithm

مقدمه

در قرن گذشته مباحث تخصیص و تسطیح منابع محدود در برنامه­ریزی تولید، تکامل قابل توجهی داشته است. برنامه­ریزی تأمین مواد (MRP)[1] یک روش مورد استفاده در تخصیص منابع محدود برنامه‏ریزی تولید برای تأمین قطعات و مواد اولیه محصولات نهایی است. به دنبال آن برنامه­ریزی منابع ساخت(MRPⅡ)[2] و برنامه­ریزی منابع سازمان (ERP)[3] برمبنای ساختار برنامه تولید سلسله مراتبی ایجاد شده است (خادمی زارع و همکاران 1389). با وجود این با جهانی شدن اقتصاد، رشد و پویایی بازارهای جهانی و نیازمندی‌های مشتریان، مقوله صرفه جویی هزینه­های‌ مربوطه در سیستم­های تولیدی به عنوان یکی از مسائل مهم اقتصادی مطرح است. به همین علت MRP دیگر در سیستم­های تولیدی کارا نیست زیرا فلسفه اصلی MRP، تضمین این است که تعداد درستی از اجزاء و در زمان درستی برای تأمین تقاضای کالاها برنامه­ریزی شوند. در نتیجه MRP تنها یک جواب شدنی برای مسأله برنامه­ریزی تولید- موجودی فراهم می­کند، در حالی که شرکت­ها به دنبال برنامه­ریزی هستند که علاوه بر برآورده کردن تقاضا برای محصولات پایانی مجموع هزینه­های مرتبط را نیز حداقل کند. در نتیجه، تعیین یک سیاست اندازه انباشته مناسب قطعا یک معیار کلیدی در کنترل موجودی است تا با قرار دادن اندازه­ تولیدهای مناسب کاهش قابل توجهی در هزینه­های مرتبط با موجودی ایجاد کند. در سال 1958 میلادی وگنر و ویتین مسأله اندازه انباشته تک محصولی (SILSP)[4] را معرفی کردند. این مدل نخستین فرمول‏بندی از مسأله­ی اندازه ­انباشته با تقاضا پویا است و با فرض اینکه فرایند تولیدی تنها شامل یک مرحله و یک محصول پایانی است و تقاضا در هر دوره مشخص و متغیر بر روی افق زمانی است، به مدل سازی این مسأله پرداختند. پس از وگنر و ویتین توسعه­های زیادی بر روی مسأله اندازه انباشته انجام شد تا هر چه بیشتر این مسأله را به مسائل موجود در دنیای واقعی نزدیک­تر کند.

یکی از توسعه­های مسأله اندازه انباشته، مسأله اندازه انباشته چند سطحی است. سطوح تولید در واقع تعداد ایستگاه­های کاری و یا تعداد عملیاتی است که محصول در طول فرایند تولید باید از آنها عبور کند. مسأله اندازه انباشته با سیستم تولید چند‏سطحی، یک فرایند تولیدی است که در آن اجزاء قطعات به وسیله­ی تولید یا خرید به دست می­آید. سپس زیرمونتاژهای تولید به هم مونتاژ شده و در نهایت به محصول پایانی تبدیل می‏شوند. همه­ محصولات پایانی در سطح صفر ساختار تولید قرار می­گیرند. محصولاتی که به طور مستقیم بر محصولات پایانی تاثیر می­گذارند، در سطح یک قرار می­گیرند و به همین ترتیب ادامه می­یابد. در این سیستم، برای هر محصول علاوه­ بر تقاضای خارجی، تقاضای داخلی نیز از طریق محصولات سطوح بالاتر وجود دارد (براهیمی و همکاران 2006).

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

در این پژوهش، دو مدل مسأله اندازه انباشته با موجودی تخریب شدنی و مسأله اندازه انباشته چند سطحی را ترکیب کرده و علاوه­ بر این میزانی هزینه با عنوان هزینه­های دفع برای موجودی فاسد شده در نظر می گیریم. به مدل­سازی و حل این مسأله جدید با عنوان" مسأله اندازه انباشته چند سطحی با موجودی تخریب شدنی و هزینه­های دفع"، که به طور اختصار با  [5]MLLSP-DIDCنشان می­دهیم، خواهیم پرداخت. در مسأله ارائه شده هزینه­های دفع بیانگر هزینه دور کردن موجودی­های فاسد شده از محیط انبار و یا هزینه­ی ضایعات است. این هزینه دفع، شامل هزینه هر واحد دفع و هزینه ثابت دفع (مستقل از میزان موجودی فاسدشده) است. در مسأله جدید علاوه ­بر تعیین میزان تولید و زمان تولید هر یک از محصولات در هر یک از سطوح تولید، دوره‏های زمانی که در آن موجودی­های فاسد شده دفع می‏شوند نیز تعیین می‏شوند و در تابع هدف مسأله نیز حداقل کردن مجموع هزینه­های دفع اضافه می­گردد.

در ادامه ابتدا به مرور ادبیات مسأله اندازه انباشته با موجودی تخریب شدنی پرداخته و سپس به مدل‏سازی مسأله MLLSP-DIDC می­پردازیم، سپس به بیان روش حل ابداعی برای حل این مسأله و آزمایش‏های عددی خواهیم پرداخت و در نهایت نتیجه­گیری و پیشنهادات آتی را خواهیم داشت.

 

1- مرور ادبیات

تحقیق­های زیادی روی موجودی­های تخریب شدنی و فاسد شدنی انجام شده است. وینات[6] (1960)، ون زیل[7] (1964)، ناهمیاس و پی­یرسکالا[8] (1973)، روی تعیین مقدار سفارش اقتصادی محصولات فاسد شدنی با عمر ثابت کار کردند. گاره و اسچاردر[9] (1963) مسأله اندازه انباشته با موجودی تخریب شدنی را که در آن نرخ تخریب (کاهش ارزش موجودی) از توزیع وایبول پیروی می­کرد را مدل‏سازی کردند. شاه[10] (1977) مدلی را به منظور تعیین سیاست سفارش­دهی بهین برای موجودی­های تخریب شدنی در سیستمی که در آن تقاضا به شکل نمایی افزایش می­یافت و همچنین، دو انبار برای نگهداری کالا­ها استفاده می­شد، توسعه دادند. کاچن[11] (1977)، موجودی­های تخریب شدنی را که در آن نرخ تخریب از توزیع نمایی پیروی می­کرد را در نظر گرفته و به تعیین نرخ قیمت و سطوح تولید پرداختند. تادیکامالا[12] (1978) تعیین مقدار سفارش اقتصادی کالاهایی که نرخ تخریب در آنها از توزیع گاما پیروی می­کرد را بررسی کردند. ناهمیاس و ونگ[13] (1979) مسأله اندازه انباشته با موجودی­های تخریب شدنی که در آن تخریب موجودی به شکل پیوسته تخریب می‏شوند را در نظر گرفتند و از روشی ابتکاری برای حل آن استفاده کردند. کارونا و ادوارد[14] (1994) یک مدل برنامه ریزی پویای تصادفی برای تعیین مقدار سفارش اقتصادی بهین برای محصولات تخریب شدنی ارائه دادند. آنها عمر محصولات را تصادفی در نظر گرفتند به طوری که در پایان هر دوره، کل موجودی باقی مانده یا بی ارزش می­شود و یا برای حداقل یک دوره ی بعد قابل استفاده می­ماند. خدهایری و تاج[15] (2007) موجودی را تخریب شدنی در نظر گرفتند و فرض کردند که نرخ تخریب از توزیع وایبول پیروی می­کند که به طور تجربی مشاهده شده برای محصولاتی مانند مواد غذایی منجمد، بستنی، شیر پاستوریزه و . . . صحیح است. کینگو و همکاران[16] (2008) مسأله اندازه انباشته­ی اقتصادی با موجودی فاسد شدنی را بررسی کردند که در آن سفارش عقب افتاده مجاز بود و شخص می‏توانست تقاضای یک دوره را (در شکل لزوم) در دوره های بعد با میزانی جریمه برآورده کند. اچسو و همکاران[17] (2010) سیستم کنترل موجودی با کالاهای از نوع تخریب شدنی در نظر گرفتند و به تعیین سیاستی بهینه برای سفارش­دهی از طریق کاهش نرخ تخریب موجودی­ها با استفاده از تکنولوژی­های محافظتی پرداختند. وحدانی وهمکاران (۲۰۱۳) روی مساله اندازه انباشته با موجودی تخریب شدنی که در آن چند انبار با نرخ تخریب متفاوت در دسترس است کار کردند. اخیرا باکر و همکاران[18] (2012) بررسی جامعی از تلاش­های انجام شده در زمینه کنترل موجودی کالاهای فاسد شدنی و تخریب شدنی ارائه داده­اند. آنها به جستجوی مقالات منتشر شده در زمینه کنترل موجودی کالاهای فاسد شدنی و تخریب شدنی از ابتدای سال 2001 تا پایان سال 2011 برمبنای کلمات کلیدی انتخاب شده از چند ژورنال معتبر پرداختند. آنها موفق به یافتن 227 پژوهش مرتبط شدند و آنها را بر اساس نوع تخریب شدن (چرخه عمر) موجودی و تقاضا طبقه­بندی کردند.

مقالات زیادی مرتبط با موجودی تخریب شدنی وجود دارد. با وجود این تقریبا تمام مدل­های موجود در ارتباط با مسائلی هستند که در آنها تقاضا مستقل هستند یا به عبارت دیگر تمامی مدل­ها مربوط به مسائل با افق زمانی پیوسته است. تمامی ادبیات ذکر شده در بالا متعلق به این دسته از مسائل اندازه انباشته است. وی و شام[19] (1999) ادعا کردند که در نظر گرفتن موجودی تخریب شدنی در سیستم­های MRP (تقاضای وابسته یا افق زمانی گسسته) تقریبا وجود ندارد و یک روش برای وارد کردن تاثیر موجودی تخریب شدنی در سیستم­های MRP تک سطحی معرفی کردند. بر طبق تحلیل آنها، در نظر گرفتن موجودی تخریب شدنی به طور معناداری بر کل هزینه­های مرتبط و سیاست­های تصمیم­گیری تاثیر می­گذارد (در پژوهش آنها با در نظر گرفتن نرخ تخریب 4%، کل هزینه­های مرتبط تقریبا 35% افزایش می­یافت) و در نتیجه حتما بایستی تاثیر آنها را در سیستم­های MRP در نظر گرفت. آنها سپس دو الگوریتم ابتکاری حداقل هزینه دوره (LPC)[20] و حداقل هزینه واحد (LUC)[21] را برای حل این مسأله اصلاح کردتد. در ادامه هوو و همکاران[22] (2007) سه الگوریتم ابتکاری حداقل هزینه دوره­ای خالص (nLPC)[23] ، حداقل هزینه کل (LTC)[24] و الگوریتم سهم دوره (PPA)[25] را برای مسأله اندازه انباشته با موجودی تخریب شدنی، اصلاح کردند. آنها با انجام آزمایش‏های عددی این سه الگوریتم را با الگوریتم­ها ارائه شده توسط وی و شام (1999) مقایسه کردند و مشاهده کردند که الگوریتم nLPC بهترین عملکرد را دارد. چوو وهمکاران[26] (2005) یک مسأله اندازه انباشته اقتصادی را در نظر گرفتند که در آن هزینه­ی نگهداری موجودی و همچنین، نرخ تخریب موجودی در پایان هر دوره وابسته به عمر (تعداد دوره هایی که از سفارش آن گذشته یا نعداد دوره هایی که در انبار نگهداری شده)آن بود. کارهای انجام شده توسط اچسو[27] (2000) و اچسو (2003) نیز مربوط به این دسته از مسائل (افق زمانی گسسته) هستند.

پاهل و همکاران[28] (2010) مسأله­ی اندازه انباشته گسسته چند محصولی و تک سطحی که شامل محدودیت­های تخریب شدن و از بین رفتن محصول بود، را مدل­سازی کردند. همچنین، پاهل و همکاران (2011) مسأله­ی اندازه انباشته با موجودی تخریب شدنی را با در نظر گرفتن هزینه­ی راه­اندازی وابسته به توالی مدلسازی کردند. آنها چگونگی تغییر ارزش کالا روی افق زمانی برای محصولات فاسد شدنی و تخریب شدنی را به شکل شکل (1) نشان دادند. که در آن شکل (الف) چگونگی فاسد شدن را نشان می‏دهد که ارزش موجودی به یکباره به صفر می‏رسد. شکل (ب) نحوه ی کاهش ارزش برای موجودی تخریب شدنی گسسته را نشان می­دهد و شکل (ج) چگونگی کاهش ارزش برای موجودی تخریب شدنی پیوسته را نشان می­دهد که شامل سه منحنی a و b و c است که تغییر ارزش محصول نسبت به زمان در آن ها به ترتیب به شکل محدب، خطی و مقعر تغییر می‏کند.

 

 

 

 شکل 1- روند فاسد شدن و تخریب شدن موجودی (پاهل و همکاران 2011)

 

بر اساس مرور شکل در گرفته در ادبیات موضوع مشخص گردید که علی رغم اهمیت برنامه­ریزی برای دفع موجودی­های فاسد شده، تا کنون هیچ پژوهشی این موضوع را در مدل­سازی مسأله اندازه انباشته وارد نکرده است. بنابراین، ما در این پژوهش به معرفی توسعه جدیدی از مسأله اندازه انباشته که در آن به شکل توأم موجودی تخریب شدنی و هزینه­های دفع موجودی­های فاسد شده در نظر گرفته شده خواهیم پرداخت. بدین منظور، ما در ادامه کار انجام شده توسط پاهل و همکاران (2011)، ارزش موجودی فاسد شده را منفی و میزانی هزینه برای آن در نظر می‏گیریم. توجیه این امر را نیز می­توان هزینه­های دفع موجودی فاسد شده بیان کرد. به عبارت دیگر وقتی ارزش موجودی به صفر می­رسد و تبدیل به محصولی غیر مفید و یا زباله می­شود، نه­تنها دیگر ارزشی ندارد بلکه هزینه­هایی را برای دفع آن از محیط تولید باید بپردازیم. بنابراین، می­توان شکل (1) را به صورت شکل (2) تغییر داد.

 

 

بپردازیم. بنابراین، می­توان شکل (1) را به شکل شکل (2) تغییر داد.

 

 

شکل2- روند فاسد شدن و تخریب شدن موجودی با در نظر گرفتن هزینه دفع

 

2- تعریف مسأله و مدلسازی

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

بنابراین، در این مسأله علاوه بر تعیین اندازه انباشته تولید در هر سطح و در هر دوره زمانی، به دنبال تعیین سیاست بهین برای زمان دفع موجودی فاسد شده می­باشیم به طوریکه مجموع هزینه­های تولیدی (شامل هزینه­های متغیر تولید و هزینه­های راه اندازی)، هزینه­های نگهداری موجودی و هزینه­های دفع موجودی (شامل هزینه­ دفع هر واحد موجودی فاسد شده و هزینه ثابت دفع) حداقل شود.

علاوه بر این، مسأله مورد مطالعه مفروضاتی دارد که عبارتند از:

  • افق زمانی مسأله محدود و گسسته است.
  • تقاضا در هر دوره زمانی مشخص، قطعی و پویا است.
  • ظرفیت تولید در دسترس در هر دوره زمانی نامحدود است.
  • ظرفیت انبار در هر دوره زمانی نامحدود است.
  •  سفارش عقب افتاده مجاز نیست
  • جدول 1- تعریف پارامترها و متغیرهای تصمیم

 

 


پارامترها

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

m : تعداد محصولات.

T : تعداد دوره­های زمانی.

di,t : میزان تقاضا محصول i در دوره زمانی t ام.

ri,j : میزانی از محصول i که برای تولید یک واحد از محصول j مورد نیاز است.

Sci,t : هزینه راه اندازی محصول i ام در دوره زمانی t ام.

Vci,t : هزینه تولید هر واحد محصول i در دوره زمانی t ام.

hci,t : هزینه نگهداری هر واحد محصول i در دوره زمانی  tام.

Fdci,t : هزینه ثابت هر بار دفع برای محصول i در دوره زمانی t ام.

Dci,t : هزینه هر واحد دفع محصول i در دوره زمانی t ام.

a : نرخ تخریب موجودی در شکل عدم وجود موجودی فاسد.

λ  : میزان افزایش نرخ تخریب به ازای وجود هر واحد موجودی فاسد.

مجموعه D(i)، مجموعه محصولات پس نیاز برای محصول i ام را نشان می­دهد.

xi,t: میزان تولید محصول i ام در دوره زمانی t.

Ii,t: میزان موجودی ناخالص انتقال داده شده از محصول i ام در دوره زمانی t.

Idi,t: میزان موجودی فاسد از محصول i ام در دوره زمانی t.

Βi,t : نرخ تخریب موجودی برای محصول i ام در دوره زمانی t.

yi,t : متغیر دوتایی راه اندازی برای محصول i ام در دوره زمانی t (اگر در دوره t ام محصول i ام تولید شود برابر است با 1 و در غیر این شکل برابر است با صفر)

Si,t : متغر دوتایی دفع موجودی فاسد (اگر در انتهای دوره زمانی t ام، موجودی فاسد شده از محصول نوع i ام دفع شود برابر است با 1 و در غیر این شکل برابر است با صفر)

 

 

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

  • سفارش عقب افتاده مجاز نیست.
  • تأخیرهای زمانی راه اندازی و تولید صفر در نظر گرفته شده است.

در جدول (1) پارامترها و متغیرهای تصمیم به کار گرفته شده در مدل تعریف شده­اند. بر این اساس مدل برنامه­ریزی غیرخطی عدد صحیح مختلط برای MLLSP-DIDC به شکل مجموعه معادلات (1) تا (9) فرموله می‌شود.

 

تشریح مدل:

تابع هدف (1) مسأله به دنبال حداقل کردن مجموع هزینه­های راه اندازی، تولید محصول، نگهداری موجودی و هزینه­های دفع شامل هزینه ثابت و متغیر دفع بر روی تمام محصولات در کل افق زمانی است. محدودیت (2) و (3)، محدودیت­های بالانس موجودی است و بیان می­کند که در هر دوره زمانی و برای هر محصول، از موجودی خالص انتقال داده شده از دوره قبل به علاوه­ی تولید در آن دوره برای برآورده کردن مجموع تقاضاهای داخلی (تقاضای وابسته) و تقاضای خارجی استفاده می­شود و باقی به شکل موجودی به دوره زمانی بعد انتقال می­یابد. محدودیت (4) نرخ تخریب موجودی برای محصولi  ام در دوره زمانی t ام را نشان می­دهد. این نرخ در شکل عدم وجود موجودی فاسد از محصولi  در دوره زمانی t یعنی  Si,t-1=1 یا       Idi,t-1=0 ، برابر نرخ ثابت a است و در غیر این شکل به ازای وجود هر واحد محصول  فاسد به میزان λ به این نرخ اضافه می­شود.محدودیت (5) نیز میزان موجودی فاسد موجود از محصولi  در دوره زمانی t را نشان می­دهدکه این میزان برابر موجودی فاسد شده در همان دوره به علاوه موجودی فاسد انتقال داده شده از دوره زمانی قبل در شکل عدم دفع موجودی است. محدودیت (6)، که در آن M یک عدد بزرگ است، بیان می­کند که در شکل وجود موجودی فاسد شده از هر محصول در یک دوره زمانی، این موجودی باید در آن دوره و یا یکی از دوره­های زمانی باقی مانده تا پایان افق زمانی دفع گردد.

 

 


محدودیت (7)، که مجددا در آن M عددی بزرگ است، تضمین می­کند که در هر بار تولید باید راه‏اندازی دستگاه انجام گردد. در نهایت محدودیت (8) باینری بودن متغیرهای راه اندازی و دفع موجودی و محدودیت (9) نیز پیوسته و غیر منفی بودن متغیرهای موجودی ناخالص، نرخ تخریب، مقدار تولید و موجودی فاسد را نشان می­دهد.

3- روش حل پیشنهادی

از آنجایی که مسائل اندازه انباشته چند سطحی NP-hardهستند (استینبرگ و ناپیر[29]1980)، تنها نمونه­های کوچک این مسأله می­توانند در مدت زمان منطقی حل شوند. به همین علت ابزار اصلی مورد استفاده ما برای حل این مسأله استفاده از روش­های فراابتکاری خواهد بود. در این پزوهش، از دو الگوریتم فراابتکاری SA و GA برای حل مسأله استفاده شده است. ابتدا به تشریح نمایش جواب پیشنهادی خواهیم پرداخت و سپس با اصل بهینگی که در ادامه گفته خواهد شد به چگونگی محدود کردن فضای جواب و جستجوی الگوریتم­های SA و GA در این فضا خواهیم پرداخت.

3-1-  نمایش جواب پیشنهادی

به منظور ارائه نمایش جواب پیشنهادی برای مسأله MLLSP_DIDC  ابتدا اصل بهینه­سازی زیر تعریف می­شود (پاچت و والسی[30] 2006).

اصل بهینگی: برای هر مسأله اندازه انباشته بدون ظرفیت چند سطحی، یک جواب بهینه وجود دارد به طوری که داریم:

 

 

که در آن di,t,β به شکل زیر تعریف می­شود:

 

به عبارت دیگر در هر دوره زمانی برای هر محصول، یا از موجودی دوره­های قبل برای برآورده کردن تقاضا (داخلی یا خارجی) استفاده می­کنیم و یا از تولید در همان دوره و هیچ گاه همزمان انتقال موجودی از دوره قبل و تولید را نخواهیم داشت.

با توجه به اصل بهینگی ذکر شده، در مسأله اندازه انباشته کلاسیک تنها با تعیین دوره­های زمانی تولید در افق زمانی می­توان میزان تولید در هر مرحله و در نتیجه میزان موجودی انتقال یافته در هر دوره زمانی را تعیین کرد. اما در مسأله MLLSP-DIDC به منظور حصول متغیرهای تصمیم، باید علاوه بر تعیین دوره‏های زمانی تولید، دوره­های زمانی که در آن تصمیم به دفع موجودی داریم نیز مشخص شوند. در نتیجه نمایش جواب پیشنهادی برای مسأله MLLSP-DIDC به شکل دو ماتریس مجزای m´T بُعدی Y و S با درایه­های باینری صفر و یک است، به طوریکه بردار Y نشان دهنده­ی دوره­های زمانی تولید و بردارS  نشان دهنده دوره­های زمانی دفع موجودی برای تمام محصولات است. به عبارت دیگر:

به طوری که yi,t (1≤i≤m ,1≤t≤T )  با یک برابر است، اگر در دوره زمانی t برای محصول i راه‏اندازی انجام شود و در غیر این شکل با صفر برابر است. همچنین، si,t (1≤i≤m ,1≤t≤T ) با یک برابر است اگر در دوره زمانی t تصمیم به دفع موجودی فاسد از محصول i شود و در غیر این صورت با صفر برابر است.

با استفاده از دو ماتریس S و Y می­توان مقدار تولید از هر محصول در هر دوره زمانی را تعیین کرد. البته به شرط آن ­که ابتدا میزان تولید تمام محصولات پس نیاز آن محصول تعیین شده و در نتیجه میزان تقاضای داخلی برای آن محصول در هر دوره زمانی مشخص شده باشد. میزان تقاضای کل (تقاضای داخلی به علاوه تقاضای خارجی) برای هر محصول به شکل زیر به دست می­آید:

 

(5)     

 

 

 

 

که در آن  Tdi,tتقاضای کل از محصول iام در دوره زمانی t ام است و مقدار آن با میزان تقاضای خارجی از محصول  iام در دوره زمانی  tام (di,t) به علاوه مجموع تقاضای داخلی از محصول iام در دوره زمانی t ام برابر است. تقاضای داخلی توسط هر محصول پس­نیاز برابر با میزان تولید از آن محصول ضربدر نسبت ri,j که برابر تعداد محصول مورد نیاز از محصول i برای تولید هر واحد محصول j ام است. همچنین، توجه شود برای محصول پایانی (محصول شماره 1)، محصول پس­نیاز و در نتیجه تقاضای داخلی وجود ندارد. در نتیجه محاسبات مربوط به تقاضای کل و سایر محاسبات باید از محصول شماره 1 که اولا خود تقاضای داخلی ندارد و ثانیا تقاضای داخلی برای سایر محصولات را مشخص می­کند، آغاز شود.

­با مشخص بودن ماتریس­های Y و S و محاسبه­ی تقاضای کل برای محصول i  در دوره­های زمانی t  (1≤t≤T) میزان تولید و سایر متغیرهای تصمیم به شرح ذیل قابل محاسبه خواهد بود:

 اگر yi,t=1 باشد، میزان تولید از محصول i در دوره زمانی t برابر است با مجموع تقاضاهای متورم شده از محصول i از دوره زمانی t تا دوره زمانی t¢-1 به طوریکه yi,t¢=1 و yi,j=0(t<j<t¢).

اگر yi,t=0 باشد، میزان تولید از محصول i در دوره زمانی t با صفر برابر است.

توجه شود، در بالا از اصطلاح "تقاضای متورم شده" استفاده شد زیرا موجودی در نظر گرفته شده از نوع تخریب شدنی است و به عنوان مثال برای برآورده کردن تقاضای دوره­های t تا e به وسیله­ی تولید در دوره t، اندازه انباشته برابر است با:

 

در این رابطه، اندیس i نشان دهنده محصول i ام و اندیس­های j و τ نشان دهنده دوره زمانی هستند. این رابطه را می­توان به شکل زیر نیز نشان داد:

 

اما همان طور که در مدل­سازی مسأله مشاهده شد، βi,t­ (نرخ تخریب محصول i در دوره t ) در این رابطه خود متغیر تصمیم است. با این حال می­توان آن را به شکل زیر به دست آورد:

 

در این رابطه مقدار si,t-1 مشخص است (با استفاده از ماتریس S)، ولی Idi,t-1 (میزان موجودی فاسد از محصول i در دوره زمانی t-1)متغیر تصمیم است و مقدار آن برابر است با :

 

در این رابطه نیز Ii,t-1(میزان موجودی ناخالص از محصول i در دوره زمانی t-1) به شکل زیر محاسبه می­شود:

 

 همان طور که مشاهده می­شود روابط (9)، (10) و (11) کاملا برگشتی هستند یعنی در نهایت هر یک از متغیرهای Ii,t، βi,t و IDi,t تابعی از مقادیر Ii,1، Bi,1 و IDi,1 یعنی موجودی محصول i در دوره زمانی اول، نرخ تخریب محصول i در دوره زمانی اول و موجودی فاسد از محصول i در دوره زمانی اول خواهند شد. اما همانطور که می­دانیم در دوره زمانی اول Ii,1 برابر است با:

 

همچنین، βi,1 مقداری ثابت و برابر با a (نرخ تخریب ثابت در هر دوره زمانی) است. در نتیجه مقدار Idi,1 نیز به راحتی برحسب I­i,1­ به دست می­آید (Idi,1=a . Ii,1) و در ادامه در دوره زمانی دوم به ترتیب می­توان مقادیر Ii,2 ، سپس βi,2 و سپس IDi,2 را برحسب Ii,1 نوشت.

همچنین، رابطه (8) را می­توان به شکل زیر نوشت:

 

یا

 

حال در این رابطه می­توان تمام متغیرهای βi,t  و همچنین، Ii,t را برحسب Ii,1 نوشت و در نتیجه معادله به دست آمده را برحسب Ii,1 حل کرده و به طور بازگشتی سایر متغیرهای Ii,t، βi,t و Idi,t را به دست آورد.

به منظور درک بیشتر به مثال زیر توجه کنید:

 

مثال

مسأله­ اندازه انباشته تک سطحی شامل 5 دوره زمانی و 1 محصول را درنظر بگیرید. نرخ تخریب ثابت برابر 0.1 (a=0.1) و میزان افزایش نرخ تخریب به ازای وجود هر واحد محصول فاسد 0.01 (λ=0.01) است. میزان تقاضای کل برای این محصول در جدول (2) آورده شده است. همچنین، ماتریس­های S و Y مشخص و به شکل ذیل است. می­خواهیم جواب متناظر با این ماتریس­ها را به دست آوردیم.

Y=[1 0 0 1 0]

S=[0 1 0 0 1]

 

جدول 2-میزان تقاضای کل در هر دوره زمانی

 

حل:

میزان تولید در دوره 1 برابر است با:

(توجه: چون تنها یک محصول داریم متغیرها شامل یک اندیس اند که نشان دهنده دوره زمانی است)

 

 

در این رابطه داریم:

β1=a=0.1

Id11.I1=0.1 I1

β2=a+λ.Id1.(1-s1)=0.1+0.01´0.1×I1´

(1-0)=0.1+0.001 I1

در نتیجه داریم:

 

با ساده کردن این معادله داریم:

 

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

 

در دوره­های زمانی 2 و 3 و 5 چون yt برابر صفر است، میزان تولید برابر صفر است. اما در دوره زمانی 4 داریم:

 

خلاصه جواب­ نهایی در جدول (3) آورده شده است.( لازم به ذکر است که در محاسبات اعداد تا دو رقم اعشار گرد شده اند.)

جدول 3- خلاصه جواب­های مثال

5

4

3

2

1

دوره زمانی

0

33/11

0

0

13/46

xt

1003/.

1/.

1/.

1003/.

1/.

βt

0

33/3

0

11/1

46/3.

It

33/.

33/.

0

45/.

34/.

Idt

3-2- رویکرد حل ابداعی

با استفاده از اصل بهینگی بیان شده در بخش قبل و توضیحات مفصل داده شده می­توان فضای جواب مسأله MLLSP-DIDC را محدود کرد با این اطمینان که جواب بهین حتما در این فضا وجود دارد. به این شکل که برای هر ماتریس مشخص S برای هر محصول i(1≤i≤m) ماتریس Mi را به شکل زیر تشکیل می­دهیم:

 

 

که در آن Mi,t,k(1≤i≤m , 1≤t≤T, t≤k≤T) میزان تولید از محصول i در دوره t برای برآورده کردن تقاضای دوره­های t، t+1، . . . و k   را نشان می­دهد و برابر است با :

 

بنابراین، برای هر ماتریس مشخص S و Y می توانیم میزان تولید از هر محصول در هر دوره زمانی را مطابق رابطه زیر تعیین کرد:

 

که در آن yt¢=1 و yj=0(t<j<t¢) .

از این روش ابداعی در دو الگوریتم فراابتکاری GA و SA به طور مشابه استفاده می­کنیم. روال کار به این ترتیب است که در هر تکرار الگوریتم­های فراابتکاری ابتدا برای محصولات پایانی که محصول پس نیاز ندارند و تقاضای کل آنها مشخص است، با استفاده از ماتریس مشخص S (که تصادفی تولید شده­ یا از همسایگی جواب به دست آمده­) ماتریس M را تشکیل داده و سپس با استفاده از ماتریس Y  (که تصادفی تولید شده­ یا از همسایگی جواب به دست آمده­) میزان تولید و سایر متغیرهای تصمیم برای هر دوره زمانی را محاسبه کرده و سپس به سراغ محصولات پیش­نیاز مستقیم آنها رفته (یکی یکی) و تقاضای کل (TD) آن­ را محاسبه کرده و مشابه محصول اول، میزان متغیرهای تصمیم در هر دوره را محاسبه می­کنیم. این روال را تا شامل شدن تمامی محصولات ادامه می­دهیم.

 

3-3- طراحی پارامترهای الگوریتم GA

  • هر کروموزوم متشکل از دو ماتریس S و Y است، که چگونگی نمایش آنها در بخش "نمایش جواب پیشنهادی" به تفصیل شرح داده شد.
  • ایجاد جمعیت اولیه: جمعیت اولیه در این پژوهش به شکل تصادفی ایجاد شده و متشکل از ماتریس­های S و Y است.
  • اندازه جمعیت: اندازه جمعیت در این پژوهش برابر 50 در نظر گرفته شد.
  • رویه انتخاب: روش انتخاب کرورموزوم­ها برای تولید نسل جدید بر اساس  روش چرخ رولت است، به طوری که کروموزوم­های جدید بر اساس تابع برآزندگی آنها (افراد با برازندگی بیشتر، شانس بیشتری برای انتخاب دارند) انتخاب می‏دهد.
  • عملگر تقاطع: در این پژوهش از عملگر تقاطعی تک نقطه­ای برای تولید فرزندان از والدین بهره گرفته می­شود. احتمال اجرای عملگر تقاطع نیز 0.9 در نظر گرفته شده است.
  • عملگر جهش: با توجه به باینری بودن درایه­های دو ماتریس S و Y،  برای ایجاد جهش در کروموزوم های حاصل از عملگر تقاطع، از جهش معکوس استفاده شده است. بدین ترتیب که مقدار هر ژن در شکل جهش، معکوس می شود. به عبارت دیگر اگر 0 باشد تبدیل به 1 و اگر 1 باشد تبدیل به 0 می شود.  احتمال جهش نیز برابر 1/T (T طول رشته کروموزوم است) در نظر گرفته شده است.
  • قاعده توقف: قاعده توقف برای پایان دهی به الگوریتم، تعداد نسل های تولید شده است که در این پژوهش معادل 10 نسل در نظر گرفته شده است.

3-4- طراحی پارامترهای الگوریتم SA

به علت فقدان نتایج نظری در زمینه طراحی پارامترهای الگوریتم SA، این پارامترهای بایستی با توجه به مسأله مورد بررسی، تنظیم گردد. در این تنظیم، کیفیت نتایج و زمان محاسباتی الگوریتم مد نظر قرار می گیرد. بنابراین، پارامترهای SA در این پژوهش از طریق سعی و خطا و با مقایسه با نتایج حاصل از نرم افزار LINGO تعیین شد. نتایج این سعی و خطا در جدول (4) آمده است.

جدول 4-پارامترهای الگوریتم SA

پارامتر

مقدار

دمای اولیه

100 T0 =

دمای انجماد

0.01Tf =

نرخ کاهش دما

0.95a =

طول زنجیره مارکوف

5Nlimit_max = ، 10Nover_max=

 

 

= Nover_max ماکزیمم تعداد جواب‏های پذیرفته شده در هر دما

 = Nlimit_maxماکزیمم تعداد جواب‏های بد پذیرفته شده در هر دما

3-5- نحوه برخورد با جواب ناموجه

جواب­های ناموجه در مسأله MLLSP-DIDC ،جواب­هایی هستند که در آنها دو شرط زیر رعایت نشود.

1)           در دوره زمانی اول حتما برای تمامی محصولات باید راه اندازی انجام شود زیرا هیچ موجودی از هیچ کدام از محصولات در دوره صفر وجود ندارد. به عبارت دیگر:

 

2)    هیچ موجودی فاسدی در انتهای افق زمانی نباید وجود داشته باشد. به بیان دیگر شرط زیر باید صادق باشد:

 

( M  یک عدد بزرگ است)

چنانچه پس از عملیات تقاطع و یا جهش جواب ناموجهی تولید گردد از استراتژی اصلاحی زیر در برخورد با جواب ناموجه استفاده می­شود.

جواب­های ناموجه­ای که شرط 1 را برآورده نمی‏کنند را می­توان به راحتی با تبدیل کردن 0 به 1 در تمامی متغیرهای yi,1 روی تمامی محصولات در ماتریس Y، به جواب موجه تبدیل کرد. همچنین، جواب­های ناموجه­ای که شرط دوم را برآورده نمی‏کنند را می­توان به این شکل موجه کرد که، برای هر محصول (i) در دوره زمانی (k) که در آن موجودی فاسد تولید می­شود، دفع موجودی انجام شود. دوره زمانی k دوره­ای است که در تمام دوره‏های زمانی بعد آن راه­اندازی ماشین برای آن محصول انجام می­شود. به عبارت دیگر:

 

 

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

4- ارزیابی روش حل

به منظور ارزیابی دقت روش حل ارائه شده ، در این بخش به مقایسه الگوریتم­های SA و GA پیشنهادی با روش­های ابتکاری ارائه شده توسط هوو و همکاران (2007) خواهیم پرداخت. اما همان­طور که می­دانیم این روش حل برای مسأله ارائه شده در این پژوهش تعریف شده و مقایسه آن با روش­های ارائه شده قبلی مقایسه مع­الفارق است. به­ همین علت، ابتدا روش حل پیشنهادی خود را برای مسأله ارائه شده توسط هوو و همکاران (2007) اصلاح می­کنیم. آنها یک مسأله اندازه انباشته تک سطحی گسسته با نرخ تخریب ثابت a را در نظر گرفتند و سه روش ابتکاری nLPC، PPA(-) و   LTC(-)را برای این مسأله اصلاح کردند.

به منظور مقایسه روش حل پیشنهادی در این پژوهش با این روش­ها،  فرضیات ذیل را بر روی مدل و روش حل خود اعمال می­کنیم:

  • تعداد سطوح تولید رابرابر یک فرض می‏کنیم.
  • تعداد محصولات تولیدی را برابر یک فرض می­کنیم.
  • با در نظر گرفتن میزان افزایش نرخ تخریب به ازای وجود هر واحد محصول فاسد برابر با صفر (λ=0)، نرخ تخریب در هر دوره زمانی را ثابت و برابر با a  قرار می­دهیم.
  • هزینه­های ثابت دفع (Fdc) و هزینه­های دفع هر واحد محصول فاسد (Dc) در تمام دوره‏های زمانی را برابر صفر قرار می­دهیم.

با اعمال این فرضیات بر روی مدل پیشنهادی در این پژوهش، مدل تبدیل به یک مدل مسأله اندازه انباشته با موجودی تخریب شدنی با نرخ تخریب ثابت، تبدیل می­شود. همچنین، با اعمال این فرضیات بر روی روش حل، ماتریس­های نمایش جواب S و Y به بردارهای S و Y تبدیل می‏دهد. لازم به ذکر است که الگوریتم­های SA و GA در نرم افزار برنامه نویسی MATLAB کد نویسی و اجرا شده است.

حال می­توان مقایسه بهتری بین روش حل پیشنهادی خود و روش­های ابتکاری ارائه شده توسط هوو و همکاران (2007) انجام داد. آزمایش‏های عددی آنها بر روی 6 نمونه مسأله انجام شد. تعداد دوره­های زمانی در تمام آزمایش‏های برابر 12 و تقاضا در هر دوره زمانی به ترتیب برابر با 10، 10، 15، 20، 70، 180، 250، 270، 230، 40، 0 و 10 در نظر گرفته شده و همچنین، هزینه نگهداری موجودی(hc)، هزینه تولید هر واحد محصول (Vc) و هزینه راه­اندازی (Sc)، در


 

جدول5- مقدار تابع هدف برای ارزیابی روش های nLPC، PPA(-) و LTC(-) با روش های SA و GA

 

مسأله

a

روش دقیق

 

روش­های هوو و همکاران (2007)

 

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

جواب بهین

 

nLPC

PPA(-)

LTC(-)

 

SA

GA

1

0

836

 

844

896

944

 

836

836

2

0.005

861.75

 

861.75

861.75

1021.08

 

861.75

861.75

3

0.01

887.82

 

887.82

887.82

1069.79

 

887.82

887.82

4

0.015

914.21

 

914.21

914.21

934.60

 

914.21

914.21

5

0.02

940.91

 

940.91

940.91

950.45

 

940.91

940.91

6

0.025

966.15

 

966.15

966.15

966.46

 

966.15

966.15

متوسط

-

901.14

 

902.47

911.14

981.65

 

901.14

901.14

 

عدد پررنگ نشان می­دهد که روش مربوطه بهترین جواب شناخته شده را یافته است

 

 

تمام دوره­های زمانی ثابت و به ترتیب برابر با 2، 100 و 92 در نظر گرفته شده است. نرخ تخریب موجودی (a) در مسائل به ترتیب برابر 0، 0.005، 0.01، 0.015، 0.02 و 0.025 در نظر گرفته شده است. جدول (5) نتایج ارزیابی را نشان می­دهد.

همان طور که در جدول (5) مشاهده می­شود، در بین روش­های پیشنهادی هوو و همکاران (2007)، روش  nLPC عملکرد بهتری نسبت به سایر روش­ها دارد، به طوری که در 5 مسأله از 6 مسأله حل شده، جواب بهین را به دست می­آورد و در مسأله­ای که جواب بهین را به دست نمی­آورد (مسأله 1) مقدار آن بهتر از روش PPA(-) است. اما با مقایسه روش­های پیشنهادی ما با روش nLPC مشاهده می­شود که روش پیشنهادی ما، هم برای SA و هم برای GA در هر 6 مسأله جواب بهین را به دست می­آورد و عملکرد بهتری نسبت به روش nLPC دارد.

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

5- تولید آزمایش‏های تصادفی

دو دسته از آزمایش‏ها در این قسمت تولید می‏شوند. دسته اول شامل مسائل با ابعاد کوچک (6 محصول روی افق زمانی شامل 5 دوره زمانی) است، که برای این دسته از آزمایش‏های، عملکرد الگوریتم­های SA و GA پیشنهادی را با جواب دقیق به دست آمده از نرم افزار LINGO مقایسه می­کنیم. دسته دوم شامل مسائل با ابعاد بزرگ است (15 محصول روی افق زمانی شامل 15 و 20 دوره زمانی) و برای این دسته از آزمایش‏های از آنجایی که روش دقیق قابل حل آنها در زمان منطقی نیستند، به مقایسه دو الگوریتم SA و GA ( کد شده در نرم افزار MATLAB) و تحلیل نتایج می­پردازیم. در هر دو دسته مسأله، ساختار محصولی برحسب پیچیدگی مشخصی تعریف می­شود. به طوریکه ما از شاخص پیچیدگی پیشنهاد شده توسط کیمز[31] (1997) که به  روش زیر تعریف می­شود استفاده می­کنیم.

 

در این رابطه A تعداد کمان‏های موجود در ساختار محصول است، که مقدار آن برابر است با:

 

همچنین، Amin، حداقل تعداد کمآنهای ممکن است که به ازای آن ساختار محصول متصل بماند و مقدار آن برابر است با:

 

برعکس، Amax حداکثر تعداد کمان‏هایی است که ساختار محصول می­تواند شامل شود.

 

ساختاری که در آن تعداد کمان‏ها برابر حداقل تعداد کمان‏های ممکن باشد (A=Amin)، یک ساختار مونتاژ بوده و مقدار شاخص C برای آن برابر صفر است. همچنین، ساختاری که در آن A=Amax باشد، شاخص C به ازای آن برابر یک است. بنابراین، مقدار شاخص بین صفر و یک متغیر است.

 

5-1- فاز نخست: تست در مقابل جواب­ دقیق (مسائل با اندازه نمونه کوچک)

حل مسأله با استفاده از روش دقیق تنها برای نمونه مسائل کوچک امکان پذیر است. به همین علت ما در فاز نخست به بررسی عملکرد هزینه­ای دو الگوریتم پیشنهادی SA و GA در اندازه نمونه­های کوچک می­پردازیم. بدین منظور، ما ساختاری شامل 6 محصول با 3 سطح تولید روی افق زمانی شامل 5 دوره زمانی را در نظر می‏گیریم. همچنین، ما شاخص پیچیدگی (C) را برای هر یک از مقادیر موجود در مجموعه­ی {0.00, 0.25, 0.5, 0.75} مورد آزمایش قرار می­دهیم. به منظور ساده­سازی بدون از دست دادن کلیات مسأله، ما فرض می­کنیم که تعداد محصولات پایانی برابر با یک (P(0)=1) بوده و همچنین، فرض می­کنیم که در هر مورد نسبت­های تولید یک رابطه یک به یک بین محصولات است(ri,j=1). تقاضا در هر دوره زمانی برای هر محصول به شکل تصادفی و از طریق یک توزیع یکنواخت بین 0 تا 20 تولید می­شود. هزینه­های راه‏اندازی، نگهداری موجودی و هزینه­های متغیر تولید را برای تمام محصولات و در تمام دوره­های زمانی ثابت و به ترتیب برابر 100، 1 و 10 در نظر می‏گیریم، همچنین، هزینه دفع هر واحد را برابر 1 و هزینه ثابت هر بار دفع را برابر 3 واحد در نظر می‏گیریم. علاوه­ بر این نرخ ثابت تخریب موجودی (a) برابر 0.1 و میزان افزایش نرخ تخریب به ازای وجود هر واحد محصول فاسد (λ) برابر 0.01 در نظر گرفته شده است. به منظور ایجاد آزمایش‏هایی با ترکیب این پارامترها، برای هر یک از شاخص­های پیچیدگی، 3 مرتبه تقاضای تصادفی تولید می­شود و بنابراین، 4´3=12 آزمایش تولید می­شود.

5-2- فاز دوم: مسائل با اندازه نمونه بزرگ

فاز دوم آزمایش‏های شامل ساختار محصولی با 15 محصول در 6 سطح تولید و افق زمانی برابر با 15 و 20 دوره زمانی است. مجددا ما شاخص پیچیدگی را از مجموعه­ی C={0.00, 0.25, 0.5, 0.75} انتخاب می­کنیم و همچنین، ساختار تولید را شامل یک محصول پایانی و نسبت تولید یک به یک بین محصولات در نظر می‏گیریم. مجددا تقاضا در هر دوره زمانی برای هر محصول به شکل تصادفی و از طریق یک توزیع یکنواخت بین 0 تا 20 تولید می­شود و هزینه­های راه­اندازی، نگهداری موجودی، هزینه­های متغیر تولید، هزینه هر واحد دفع و هزینه ثابت هر بار دفع را به ترتیب برابر 1000، 100، 10، 1 و 3 در نظر می‏گیریم. علاوه­ بر این، نرخ ثابت تخریب موجودی (a) برابر 0.1 و میزان افزایش نرخ تخریب به ازای وجود هر واحد محصول فاسد (λ) برابر 0.01 در نظر گرفته شده است. به منظور تولید آزمایش‏های تصادفی، برای هر یک از شاخص­های پیچیدگی و افق زمانی یک مرتبه تقاضا به شکل تصادفی تولید شده و در نتیجه 4´2=8 نمونه مسأله در این فاز طراحی می‏شود.

5-3- نتایج

در این بخش به بیان و تحلیل نتایج حاصل از اجرای الگوریتم­های پیشنهادی بر روی مسائل طراحی شده برای هر یک از دو فاز خواهیم پرداخت.

5-3-1- نتایج فاز اول

جدول (6) خلاصه نتایج به دست آمده از مسأله­ها را نشان می­دهد. بهترین، میانگین و بدترین جواب حاصل از 5 بار تکرار هر یک از الگوریتم­های SA و GA پیشنهادی کد نویسی شده در نرم افزار MATLAB و همچنین، میانگین زمان حل در این جدول گزارش شده است.

برای حل دقیق مسأله از کدنویسی در نرم افزار LINGO و حل آن با استفاده از روش شاخه و کران استفاده شده است. محدودیت زمان حل برای هر مسئله 5 ساعت یا 18000 ثانیه در نظر گرفته شده است. جواب و زمان حل به دست آمده از این روش نیز برای هر مسئله در جدول (6) آمده است.

همان طور که مشاهده می­شود روش دقیق به جز در مسائل 2، 3، 6 و 11 بهترین جواب را یافته است. همچنین، در مسأله 2 و 3 بهترین جواب متعلق به روش GA بوده و در مسائل 6 و 11 روش SA بهترین جواب را یافته است. بنابراین، نمی­توان بطور قطعی اظهار کرد که کدام روش عملکرد بهتری دارد. در نمونه مسائل ایجاد شده به علت تفاوت در ابعاد مسأله و در نتیجه تفاوت در مقادیر توابع هدف، به منظور مقایسه روش­های حل از معیار درصد انحراف نسبی[32] (RPD)، که طبق رابطه­ی زیر به دست می­آید، برای مقایسه­ی الگوریتم­ها استفاده شده است.

 

(25)

 

که در آن، ALGsolجواب حاصل از الگوریتم وMinsolکمینه مقدار جواب­ها­ست. در این نسبت، هرچه RPD کمتر باشد، کیفیت جواب و عملکرد الگوریتم بهتر است. در واقع با استفاده از معیار RPD مقادیر جدول (6) نرمال­سازی می‏دهد. نتایج RPD حاصل از روش­های حل در جدول (7) آورده شده است.

 

جدول 6- نتایج محاسباتی فاز اول


مساله

مقدار

C

الگوریتم SA

الگوریتم GA

روش دقیق

مجموع هزینه­ها

میانگین

 زمان حل

مجموع هزینه

میانگین زمان حل

مجموع هزینه­ها

زمان حل

بهترین

میانگین

بدترین

بهترین

میانگین

بدترین

1

.

9435.3

9518.1

9571.5

473

9547.5

9613.36

9669.3

859.43

9408.1

18000

2

0

11398

11487

11536

799.15

11288

11380.2

11536

835.10

11312.9

18000

3

0

10899

10992.6

11126

662.66

10862

10982

11084

859.10

10943.7

18000

4

0.25

9169.9

9248.78

9327.9

888.62

9250.9

9325.84

9404.3

952.38

9118.46

18000

5

0.25

11038

11154.2

11293

815.95

11208

11250.4

11302

1022.2

10936.9

18000

6

0.25

7776.2

7926.72

8066.5

1238

7788.3

9776.2

8140

977.08

7971.45

18000

7

0.5

14925

15089.6

15182

790.27

15045

15087.6

15129

1158

14798.4

180000

8

0.5

13695

13811.6

14021

822.47

13720

13798

13960

1197.8

13662.6

18000

9

0.5

11963

12019.4

12081

973.22

11968

12001.2

12060

1100.4

11805.5

18000

10

0.75

10878

11003.8

11124

719.98

11061

11113.2

11190

955.6

10781.7

18000

11

0.75

13865

13901.6

13963

934.52

13934

13977

14026

1071.1

13872.1

18000

12

0.75

17533

17601.6

17661

699.61

17566

17682.4

17720

976.96

17430.7

18000

 

عدد پررنگ نشان می­دهد که روش مربوطه بهترین جواب شناخته شده را یافته است

 

جدول 7- درصد انحراف نسبی (RPD) الگوریتم‌ها برای مسائل نمونه فاز اول


مسئله

الگوریتم شبیه­سازی تبرید

الگوریتم ژنتیک

روش دقیق

بهترین

میانگین

بدترین

بهترین

میانگین

بدترین

1

0.28

1.16

1.73

1.48

2.05

2.4

0

2

0.97

1.54

1.97

0

0.59

1.97

0.22

3

0.34

0.44

1.66

0

0.35

1.28

0.75

4

0.56

1.42

2.29

1.45

2.27

3.13

0

5

0.92

1.98

3.25

2.47

2.86

3.33

0

6

0

0

1.19

0.15

0.62

2.11

2.51

7

0.85

1.96

2.59

1.66

2.23

1.95

0

8

0.23

1.09

2.62

0.42

0.99

2.17

0

9

1.33

1.81

2.33

1.37

1.65

2.15

0

10

0.89

2.05

3.17

2.59

3.07

3.78

0

11

0

0.21

0.65

0.49

0.75

1.10

0.05

12

0.58

0.98

1.32

0.77

1.44

1.65

0

میانگین

0.58

1.22

2.11

1.07

1.57

2.25

0.29

 

 

 

RPD مقادیر جدول (6) نرمال­سازی می‏دهد. نتایج RPD حاصل از روش­های حل در جدول (7) آورده شده است.

نتایج جدول (7) نشان می­دهد که در بین روش‏های حل، در مجموع روش دقیق بهترین عملکرد را دارد و پس از آن روش SA دارای عملکرد بهتری از روش GA دارد. همچنین، بدترین و میانگین جواب حاصل از روش SA به ترتیب بهتر از بدترین و میانگین جواب حاصل از GA است.

همان‏طور که بیان شد، روش دقیق بهترین جواب را به دست می­آورد اما این روش دو عیب اساسی دارد: اول اینکه تنها برای مسائل نمونه­ای کوچک قابل استفاده است و دوم اینکه حتی برای مسائل نمونه­ای کوچک هم مدت زمان جواب آن بسیار طولانی­تر از روش­ها فرا ابتکاری است.

5-3-2- نتایج فاز دوم

جدول (8) خلاصه نتایج به دست آمده از آزمایش‏های طراحی شده در فاز دوم بر روی 8 مسأله نمونه را نشان می­دهد.

بهترین، میانگین و بدترین جواب حاصل از 5 بار تکرار هر یک از الگوریتم­های SA و GA پیشنهادی و همچنین، میانگین زمان حل در این جدول گزارش شده است. همچنین، شایان ذکر است که نرم افزار LINGO روی پردازشگر 2/2 گیگاهرتز و سه هسته‏ایی با 2 گیگابایت رَم و با سیستم عامل ویندوز 7 به علت ابعاد بزرگ مسأله توانایی حل مسائل این دسته را ندارد.

همان‏طور که در این جدول مشاهده می­شود در تمام مسائل نمونه­ای این بخش، الگوریتم SA جواب بهتری از الگوریتم GA یافته است و در نتیجه بدون نیاز به معیار RPD می­توان گفت در نمونه مسائل با ابعاد بزرگ فاز دوم، SA عملکرد بهتری از GA داشته است.

 

جدول8- نتایج محاسباتی فاز دوم


مساله

مقدار

C

 

الگوریتم SA

الگوریتم GA

تعداد دوره زمانی

مجموع هزینه­ها

میانگین

 زمان حل

مجموع هزینه

میانگین زمان حل

 

بهترین

میانگین

بدترین

بهترین

میانگین

بدترین

1

0

15

71436

71582

71739

3991.46

71690

71732

71750

4513.48

2

0

20

85784

85908

85978

4538.42

85795

85884

85990

4566

3

0.25

15

88125

88454

88757

5030.8

88250

88494.7

88790

5124.4

4

0.25

20

90150

90249

90387

5334

90280

90354

90456

5508

5

0.5

15

91145

91206

91297

5443.4

91378

91490

91647

5490

6

0.5

20

93711

93760

93804

5650.2

93798

93828

93847

5740

7

0.75

15

96009

96043

96074

5796

96037

96092

96180

5813

8

0.75

20

98165

98237

98300

5932

98209

98305

98400

6122.8

 

عدد پررنگ نشان می­دهد که روش مربوطه جواب بهتری را یافته است


تحلیل تأثیر شاخص پیچیدگی (C) روی زمان حل

در این بخش قصد داریم به تحلیل تأثیر مقدار شاخص C بر روی زمان حل بپردازیم. بدین منظور به مقایسه زمان حل در مسائل فاز دوم وبه طور مجزا بین مسائل با افق زمانی شامل 15 و 20 دوره زمانی که دارای مقادیر مختلفی از C هستند، می­پردازیم. در این قسمت نیز از ابزارهای گرافیکی برای تحلیل نتایج به کار می‏گیریم. شکل­های (3) و (4) تأثیر اندازه C بر روی میانگین زمان حل به ترتیب برای مسائل با افق زمانی شامل 15 و 20 دوره زمانی را نشان می­دهند.

شکل­های (3) و (4) تأثیر محسوس مقدار C بر میانگین زمان حل هر یک از دو الگوریتم SA و GA در هر دو افق زمانی را نشان می­دهد به طوری‏که با افزایش مقدار شاخص پیچیدگی، میانگین زمان حل افزایش می­یابد.

نکته­ی دیگری که در این دو شکل می­توان مشاهده کرد این است که در هر دو شکل (هر دو افق زمانی) میانگین زمان حل الگوریتم SA کمتر از میانگین زمان حل الگوریتم GA است. از طرف دیگر همان‏طور که در بخش قبل مشاهده شد، الگوریتم SA جواب بهتری نیز نسبت به الگوریتم GA می­یابد. بنابراین، می­توان نتیجه گرفت که در مسائل نمونه­ای بزرگ، الگوریتم SA کارایی و عملکرد بهتری نسبت به الگوریتم GA دارد.

6- نتیجه گیری

در این پزوهش، مسأله اندازه انباشته چند سطحی توسعه داده شده و مسأله جدیدی با مسأله اندازه انباشته با موجودی تخریب شدنی و هزینه­های دفع ارائه گردید. مسأله جدید علاوه بر برنامه ریزی دوره‏های زمانی تولید، برنامه ریزی دوره­های زمانی دفع موجودی فاسد شده را نیز شامل می­شود. سپس به مدل سازی و حل این مسأله پرداخته شد و به منظور ارزیابی روش­های حل با یکدیگر و نسبت به ادبیات موضوعی انجام شده، مسائل نمونه­ای طراحی و مورد آزمایش قرار گرفت. در مسأله مورد مطالعه موجودی از نوع تخریب شدنی در نظر گرفته شد، مدل­سازی و حل مسأله در حالت موجودی فاسد شدنی (دارای ماکزیمم عمر مفید)، موضوع بسیار مناسبی برای تحقیقات آتی خواهد بود. همچنین، در نظر گرفتن فرضیات متداول در حوزه مسائل اندازه انباشته مانند هزینه راه­اندازی وابسته به توالی، در نظر گرفتن چند ماشین، محدودیت انبار و محدودیت منابع در دسترس در مسأله MLLSP-DIDC هر یک می­توانند پژوهش­های خوبی را برای تحقیقات آتی رقم بزنند.

 

 

 


[1] -Material Resource Planning (MRP)

[2] -Material Resource PlanningⅡ(MRPⅡ)

[3] -Enterprise Resource Planning (ERP)

[4] -Single Item Lot-Sizing and Scheduling Problem (SILSP)

[5] -Multi-Level Lot Sizing Problem with Deterioration Inventory and Disposal Costs (MLLSP-DIDC)

[6] -Veinott

[7] -Van Zyl

[8] -Nahmias & Pierskalla

[9] -Ghare& scharder

[10]- Shah

[11] -Cochen

[12] -Tadikamalla

[13] -Nahmias & Wang

[14] -Karuna & Edvard

[15] -Khedhairi & Taj

[16] -Qinguo

[17] -Hsu

[18] -Baker

[19] -Wee &  Shum

[20] -Least Period Cost

[21] -Least Unit Cost

[22] -Ho

[23] -net Least Period Cost

[24] -Least Total Cost

[25]- Part Period Algorithm

[26] -Chu

[27] -Hsu

[28] -Pahl

[29] -Steinberg & Napier

[30] -Pochet & Wolsey

[31] -Kimms

[32] -Rational Percentage deviation (RPD)

 

 

 

خادمی زارع، حسن؛ فاطمی‏قمی، سیدمحمدتقی؛ کریمی، بهروز؛ جنابی ، مسعود؛ راد، عباس. (فروردین ماه ۱۳۸۹)، "توسعه یک رویکرد حل بر مبنای آزادسازی لاگرانژ و الگوریتم ژنتیک برای مسئله تعیین اندازه انباشته چندمحصولی، چندمرحله ای و چندپریودی با در نظرگیری محدودیت منابع تولیدی". نشریه تخصصی مهندسی صنایع، (1)44، 37-25.

Baker, K.R. (1989). “Lot-sizing procedures and a standard data set: a reconciliation of the literature”, Journal of Manufacturing and Operations Management, 2, 199-221

Bakker M, Riezebos J, Teunter R.H. .(2012). “Review of inventory systems with deterioration since 2001”, European Journal of Operational Research, 221(2), 275-284

Brahimi, N., Dauzere-Peres, S., Najid, M. and Nordli, A. (2006). “Single Item lot Sizing problems (Invited Review)”, European Journal of Operational Research, 168, 1-16.

Chu, L.Y., Hsu, Z. and Shen, M. (2005). “An Economic Lot-sizing Problem with Perishable Inventory and Economices of scale costs: Approximation Solutions and worst case analysis”. Naval Research Logistics, 52, 536-548.

Cochen, M.A. (1977). “Joint pricing and ordering policies for expomentially decaying inventory with known demand”. Naval Research Logistics Quarterly, 24, 257-268.

Ghare, P., and scharder, G. (1963). “A model for exponentially decaying inventories”. Journal of Industrail Engineering, 14, 238-243.

Ho J.C, Solis A.O, Chang Y.L. (2007). “An evaluation of lot-sizing heuristics for deteriorating inventory in material requirements planning systems”. Computers & operation researrch, 34(9), 2562-2575 .

Hsu VN, (2000). “Dynamic Economic Lot Size Model with perishable Inventory”. Management Science, 46 (8), 1159-1169

Hsu VN, (2003). “An economic lot size model for perishable products with age-dependent inventory and backorder costs”, IIE Transactions, 35(8), 775-780

Hsu P.H, Wee H.M, Teng H.M. (2010). “preservation technology investment for deteriorating inventory”, International Journal of Production Economics, 124 (2), 338-394.

Karuna, J. and Edvard, A. (1994).“ Lot sizing for a product subject to obsolescence or perishability”. European Journal of Operation Research, 75, 287-295.

Khedhairi, A. and Taj, L. (2007). “Optimal control of a production inventory system with Weibull distributed deterioration”. Applied Mathmatical Science, 1(35), 1703-1714.

Kimms A, (1997). “Multi-Level Lot-Sizing and Scheduling Methods for Capacitated, Dynamic, and Deterministic Models”. Physica Verlag Series on Production and Logistics, Springer, Berlin.

Nahmias, S. and Pierskalla, W.P. (1973). “Optimal ordering policies for product that perishes in two periods subject to stochastic demand”. Naval Research Logistics Quarterly, 20, 207-229.

Nahmias, S. and Wang, S. (1979). “A heuristic lot size reorder point model for decaying inventories”. Management Science, 25, 90-97

Pahl. j. and Voß.S. (2010). “Discrete lot-sizing and scheduling including deterioration and perishability constraints”. In Advanced Manufacturing and Sustainable Logistics, Lecture Notes in Business Information Processing. Springer Berlin Heidelberg, 46, 345–357.

Pahl J., VoßS., Woodruff. (2011). “Discrete lot-sizing and scheduling with sequence dependent setup times and costs including deterioration and perishability constraints”. Proceedings of the 44th Hawaii. International Conference on System Sciences.

Pochet Y, Wolsey L.A. (2006). “production planning by mixed integer programing”. Belgium, Springer Science+Business Media, Inc., 233 Spring Street.

 

Qinguo, B., Qinguo, X. and Zhang,Y. (2008). “An Approximation Solution to the ELS Model for Perishable Inventory with Backlogging”. the 7th International Symposium on Operation Research and Its Applications(ISORA'08), 66-73.

Shah, Y. (1977). “An order level lot size inventory model for deteriorating itams”, IIE Transactions, 9, 190-197.

Steinberg, E., Napier, H.A. (1980). “Optimal multilevel lot sizing for requirements planning systems”. Management Science, 26 (12), 1258–1271.

Tadikamalla, P.R. (1978). “An EOQ model for items with Gamma distributed deterioration”. AIIE Transaction, 10, 100-103.

Vahdani, M., Dolati, A., Bashiri, M. (2013). “Single-Item Lot-Sizing and Scheduling Problem with Deteriorating Inventory and Multiple Warehouses”. Scientia Iranica E, 20(6), 2177-2187.

Wagner, H.M. and Whithin, T.M. (1958). “Dynamic Version of the Economic Lot Size Model”. Management Science, 5(1), 89-96.

Wee H-M, Shum Y-S. (1999).“Model development for deteriorating inventory in material requirement planning systems”. Computer and Industrial Engineering, 36(1), 219-225.