بهینه‌سازی کلونی مورچگان برای مسأله زمان‌بندی یکپارچۀ تولید و توزیع در زنجیرۀ تأمین: کمینه‌سازی مجموع وزنی تأخیر کارها و هزینۀ ارسال

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

نویسندگان

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

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

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

چکیده

در این مقاله مسأله یکپارچۀ زمان‌بندی تولید و توزیع سفارش‌ها در حالت تک‌مشتری برای سیستم تولیدی «تولید برای سفارش» در یک زنجیرۀ تأمین بررسی شده است. یک تولیدکننده n سفارش از یک مشتری دریافت می‌کند. سفارشات لازم است توسط یک ماشین پردازش و در قالب دسته‌هایی به مشتری ارسال شود. ارسال دسته‌ایِ سفارش‌ها منجر به کاهش هزینه‌های ارسال می‌شود؛ اما ممکن است موجب افزایش تأخیر بعضی از سفارش‌ها شود. هدف تعیین توالی پردازش کارها و تعیین دسته‌بندی آنها برای ارسال است؛ به‌طوری که مجموع وزنی تأخیر کارها و هزینه‌های ارسال کمینه شود. مسئله به‌طور قوی NP-hard است. در این مقاله، مدل خطی مختلط به‌همراه روش‌های بهینه سازی کلونی مورچگان و سیستم مورچه نخبه‌گرا برای حل مسأله گفته‌شده ارائه شده است. به‌منظور بررسی کارایی این دو روش، تست‌های محاسباتی با رویکرد طراحی آزمایش‌ها به‌صورت کامل انجام شده است و تحلیل نتایج با به‌کارگیری تکنیک آنالیز واریانس صورت گرفته است. نتایج تست محاسباتی، کارایی روش ACS را نشان می‌دهد. همچنین وضعیت عملکرد روش ACS برای گروه‌های مختلف و پارامترهای مسئله، تجزیه و تحلیل شده است.

کلیدواژه‌ها

موضوعات


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

An ant colony optimization for an Integrated Production and Distribution Scheduling Model in Supply Chains: Minimizing Total Weighted Tardiness and Delivery Cost

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

  • Seyed Reza Rezaei 1
  • Seyed Reza Hejazi 2
  • Morteza Rasti Barzoki 3
1 M.Sc. student, Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
2 Associate professor, Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
3 Assistant professor, Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
چکیده [English]

In this paper, integrated production and batch delivery scheduling problem for make to order production system and one customer in supply chain has been addressed. One manufacture received n orders from one customer. Orders must be processed by single machine and sent in batches to customer. Sending several jobs as a batch leads to less transportation cost but may increase the cost of tardiness jobs. The objective is determining the production and delivery scheduling so that the related costs is minimized. The problem is strongly NP-hard. In this paper, one new math programming model including Mixed Integer Programming (MIP) model, Ant Colony System (ACS) and Elastic Ant System (EAS) are presented for solving it. In order to evaluate the efficiency of these two methods computational tests based on full factorial experimental design has been conducted. Computational test is performed for evaluation of these methods. The obtained results show that the heuristic algorithm is efficient which has been verified by using. Analysis of variance (ANOVA) technique. The results showed that the ACS is the most efficient method.

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

  • Ant colony system
  • Supply chain scheduling
  • Integer Programming
  • Batch Delivery and Total Weighted Tardiness

1- مقدمه

مدیریت زنجیرۀ تأمین[1](SCM) یکی از موضوعات بسیار مهمی است که  از نظر تئوری و از جنبۀ کاربردی سال‌ها مورد توجه پژوهشگران قرار گرفته است (مظاهری و همکاران، 1393). اما موضوع زمان‌بندی زنجیرۀ تأمین از موضوعات نسبتاً جدیدی است که اهم پژوهش‌ها آن مربوط به سال‌های بعد از 2000 میلادی است (راستی برزکی و همکاران، 1392). در سه دهۀ گذشته، پژوهش  زیادی بر مدل‌های یکپارچۀ تولید و توزیع صورت گرفته است و مقالات مروری زیادی نظیر سارمینتو و نقی[2] (1999)، ارنگوس و همکاران[3] (1999)، گوتسچالک و همکاران[4] (2002)، بیلگن و اوخاهان[5] (2004)، چن (2004) درخصوص چنین مدل‌هایی وجود دارد. به‌طور خاص موضوع زمان‌بندی یکپارچۀ تولید و توزیع نیز یکی از موضوعات مهمی است که پس از ارائۀ مقالۀ هال و پاتس[6] (2003) در سال 2003 پژوهش­های زیادی را به خود اختصاص داده است. چن[7] (2010) مطالعۀ مروری مناسبی را در این زمینه ارائه کرده است که بررسی آن  پژوهش، این موضوع را به‌خوبی نشان می‌دهد. تولید و توزیع دو جزء مهم یک زنجیرۀ تأمین را شامل می‌شوند؛ بنابراین هماهنگی برنامه‌ریزی تولید و ارسال، یکی از مسائل مهم زمان‌بندی زنجیرۀ تأمین است. در مسائل کلاسیک زمان‌بندی به هماهنگی با واحد حمل‌ونقل و درنظرگرفتن شرایط ارسال توجهی نشده است و تصمیمات مربوط به زمان‌بندی تولید و برنامه‌ریزی ارسال به‌طور جداگانه انجام می‌شود (راستی برزکی[8] و همکاران، 2013)؛ در حالی که، گرفتن تصمیمات یکپارچۀ تولید و توزیع که نگرش جامع‌تر این موضوع است، کاهش هزینه‌ها و افزایش سودآوری مرتبط با سیستم تولیدی و بهبود سطح سرویس و سطح رضایتمندی مشتری را به‌همراه دارد. یکی از مهم‌ترین شاخص‌ها جهت رضایت مشتری، عملکرد تحویل کالا یا خدمات ارائه‌داده شده است (محمد باقر فخرزاد و همکاران، 1391).

پژوهش و یافته‌های جدید نیز نشان می‌دهد که عملکرد تحویل یکی از مهم‌ترین دغدغه‌های مدیران در زنجیرۀ تأمین است (لاکامی و همکاران[9]، 2004). برآورده‌نشدن تحویل به‌موقع به‌عنوان تأخیر شناخته می شود؛ این مسئله زمانی مطرح می‌شود که تولیدکننده نتواند خدمت یا کالایی را در زمان (یا بازۀ زمانی) توافق‌شده با مشتری ارائه کند (لاکامی و همکاران، 2004). مدل‌های یکپارچۀ زمان‌بندی تولید و توزیع با توجه به هزینه‌های تأخیر و هزینه‌های زیاد لجستیک بسیار مهم هستند. چن و واراکتاراکیس (2005) و پاندور و چن (2005) نشان داده‌اند که در مدل‌هایی که آنها بررسی کرده‌اند، سود هنگفتی در گرفتن تصمیمات یکپارچه می‌تواند وجود داشته باشد. یکپارچگی تولید و توزیع، می‌تواند هزینه‌های کلی سیستم را بسته به هدف زمان‌بندی، 20درصد، 25درصد و حتی بیشتر کاهش دهد (هال و پاتس، 2005). اسلوتنیک و سوبل (2005) اشاره کرده‌اند که هزینه‌های مرتبط با تأخیر در صنعت هوا فضا می‌تواند تا نزدیک یک میلیون دلار در روز برای تأمین‌کنندگان قطعات هواپیماسازی باشد. همچنین بررسی توماس و گریفین (1996) نشان داده است که بیش از 11درصد تولید خالص ملی آمریکا صرف هزینه‌های حمل‌ونقل می‌شود و هزینه‌های لجستیک بیش از 30درصد هزینۀ کالاهای فروخته‌شده را تشکیل می‌دهد. به‌دلیل اهمیت تحویل سفارشات بدون تأخیر برای تولیدکننده، مسأله کمینه‌کردن مجموع وزنی تأخیر کارها یکی از مسائل مهم تئوری و کاربردی است که سال‌ها مورد توجه محققان قرار گرفته و تاکنون پژوهش بسیار زیادی در این زمینه انجام شده است (پاتس و همکاران، 2013). ایمون (1969) برای اولین بار با بررسی مسأله مجموع تأخیر سفارشات، اصول غلبه‌ای را ارائه داد که یکی از شاخص‌ترین توسعه‌ای است که تاکنون ارائه شده است. لاور (1977) و لنسترا و همکارانش (1977) در دو پژوهش مجزا NP-Hard بودن مسئله مجموع تأخیر کارها را از جنبۀ پیچیدگی زمانی نشان دادند. چارژه و بیکر (1978) یک الگوریتم برنامه‌ریزی پویای و پاتس و واسنهوز (1991)  با ارائۀ یک الگوریتم شاخه و کران توانستند اولین الگوریتم‌های دقیق را برای مسئله مجموع تأخیر کارها را ارائه دهند. فرنچ (1990) مسأله کمینه‌کردن مجموع وزنی تأخیر کارها (تعمیم‌یافتۀ مسأله ) را یکی از مشهورترین مسأله بهینه‌سازی ترکیبی در تئوری زمان‌بندی معرفی کرد و از عبارت اختصاری SMTWTP[10] برای بیان مسئله استفاده کرد؛‌ همچنین نمایش اختصاری مسأله گفته‌شده براساس علامت‌گذاری فرنچ به‌صورت  است.

در سال‌های اخیر، به‌روش‌هایی که با الهام از طبیعت به‌عنوان یک ابزار کارا برای بهینه‌سازی مسائل پیچیده بهینه‌سازی ترکیبی استفاده می‌شود توجه زیادی شده است. بعد از سال 1990 به‌دلیل پیچیدگی حل SMTWTP حجم گسترده‌ای از پژوهش  بر الگوریتم‌های فرااِبتکاری فراوانی نظیر الگوریتم تبرید[11] ((ماتسو، 1989)، (پاتس و واسنهوز،1991)، (کراول، 1998))، الگوریتم ژنتیک[12] ((کراول، 1998)، (کلوگوز، 1998))، الگوریتم جستجوی ممنوعه[13] ((کراول، 1998)، (بیلژ، 2007))، الگوریتم بهینه‌سازی مورچگان[14] (باور، 1999)، الگوریتم بهینه‌سازی انبوه ذرات[15] (تاسگترین، 2006)، الگوریتم جستجوی متغیر همسایگی[16] (ونگ و تانگ،  2009) و الگوریتم ترکیبی ابتکاری و فرااِبتکاری (آندراس نراچو، 2013) تمرکز یافته است. الگوریتم بهینه‌سازی کلونی مورچگان یکی از روش‌های فرااِبتکاری است که با الهام از رفتار مورچه‌های طبیعی، به‌عنوان یکی از الگوریتم‌های فرااِبتکاری مبتنی بر هوش جمعی و جمعیت است که تاکنون بر مسائل گوناگون پژوهش عملیاتی از جمله استفاده شده است.

مرکل و میدندورف (2005) با استفاده از الگوریتم مورچگان توانستند یک جایگشت مناسبی را برای مسأله SMTWTP ارائه کنند. لیائو و جوان (2007) یک الگوریتم مورچگان را برای SMTWTP با درنظرگرفتن زمان‌های آماده‌سازی ارائه کردند. یاگماهان و ینیسی (2008) یک مسأله زمان‌بندی چندهدفه برپایۀ الگوریتم مورچگان را برای کاهش هزینه‌های زمان‌بندی ارائه دادند. آنگینولفی و پائولوسی یک رویکرد جدید  برای توالی وابسته به زمان‌های آماده‌سازی مسأله  ارائه کرد. مادور و همکاران (2012) یک الگوریتم  برای مسئله  برای مقیاس بزرگ ارائه کردند و نتایج الگوریتم را با داده‌های الگو OR-Library مقایسه کردند. با توجه به اهمیت موضوع، در مقالۀ حاضر تابع هدف SMTWTP به‌عنوان هدف زمان‌بندی تولید برای گرفتن تصمیم یکپارچۀ تولید و توزیع انتخاب شده است.

دسته‌بندی به‌منظور کاهش هزینه‌های ارسال به مشتری صورت می‌گیرد؛ بدین ترتیب که یک دسته شامل کارهایی است که یک‌دفعه و با یکدیگر توسط یک وسیله ارسال می‌شوند. گسترش این نوع از مسائل موضوع مهمی است که اخیراً مورد توجه محققان زنجیرۀ تأمین واقع شده است. این دسته از مسائل در ادبیات موضوع به ارسال دسته‌ای[17]معروف شده است. اولین مقاله با درنظرگرفتن هزینۀ حمل‌ونقل برای ارسال دسته‌ها توسط چنگ و کالباچر (2008) ارائه شد؛ آنها مسأله  را بررسی کردند؛ در این مورد نیز اغلب مقالات مرتبط با روش ارسال مستقیم ارجاعی به این مقاله دارند. از سال 1993 تا سال 2012 بیش از 45 مقاله در این زمینه منتشر شده است که بیانگر گسترش و اهمیت این دسته از مسائل است که اخیراً مورد توجه محققان در بحث زنجیرۀ تأمین واقع شده است (راستی، 1391). در این مطالعه ارسال مستقیم سفارشات به هر مشتری بررسی می‌شود. تابع هزینۀ ارسال به‌صورت یک رابطۀ خطی بین تعداد دفعات ارسال و هزینۀ هر بار ارسال تعریف می‌شود. به نظر می‌رسد اولین مقاله در زمینۀ مسائل تولید و توزیع یکپارچۀ مسأله  باشد که در سال 1980 ارائه شد (پاتس، 1980). این پژوهش  با درنظرگرفتن زمان حمل‌ونقل اما بدون ظرفیت یا هزینۀ ارسال است. اغلب مقالات IPODS با روش ارسال تکی و فوری به مقالۀ پاتس اشاره دارند. در سال 1993 اولین مقاله با درنظرگرفتن هزینۀ حمل‌ونقل برای ارسال دسته‌ها توسط چنگ و کالباچر (2008) ارائه شد؛ آنها مسأله  را بررسی کردند. تنها مطالعۀ موجود در زمینۀ یکپارچگی تولید و توزیع با محوریت تأخیر مربوط به پاتس (2005) است که برای اولین بار در زمینۀ مسائل IPODS تابع هدف مجموع تأخیر کارها را محور بخش زمان‌بندی تولید قرار داد و آن را با مفهوم زمان‌بندی ارسال دسته‌ای ترکیب کرد و برای مسأله  یک الگوریتم برنامه‌ریزی پویا ([18]DP) شبه‌چندجمله‌ای ارائه داد. حالت تعمیم‌یافتۀ مسأله پاتس یعنی  است که ترکیب مسأله SMTWTP و ارسال دسته‌ای است در مقالۀ حاضر بررسی می‌شود (جمع‌بندی ادبیات موضوع را در جدول 1 ببینید).

 

 

جدول 1- بررسی ادبیات موضوع برحسب سال انتشار

نویسنده

سال

نویسنده

سال

نویسنده

سال

راستی

1391

کراول

1998

تاسگترین

2006

فخرزاد و همکاران

1391

سارمینتو و نقی

1999

هال و پاتس

2007

راستی برزکی و همکاران

1392

ارنگوس و همکارانش

1999

بیلژ

2007

مظاهری و همکاران

1393

باور

1999

لیائو و جوان

2007

ایمون

1969

گوتسچالک و همکارانش

2002

یاگماهان و ینیسی

2008

لاور

1977

بیلگن و اوخاهان

2004

چنگ و کالباچر

2008

لنسترا و همکارانش

1977

چن

2004

چنگ و کالباچر

2008

چارژه و بیکر

1978

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

2004

ونگ و تانگ

2009

پاتس

1980

چن و واراکتاراکیس

2005

چن

2010

ماتسو

1989

پاندور و چن

2005

مادور و همکاران

2012

فرنچ

1990

هال و پاتس

2005

راستی برزکی و همکاران

2013

پاتس و واسنهوز

1991

اسلوتنیک و سوبل

2005

پاتس و همکاران

2013

توماس و گریفین

1996

مرکل و میدندورف

2005

آندراس نراچو

2013

 

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

 

2- تعریف مسئله

یک مسأله زمان‌بندی تک‌ماشینه زنجیرۀ تأمین را در نظر بگیرید که در آن  کار توسط یک مشتری سفارش داده می‌شود. زمان پردازش کار ام  و موعد تحویل آن  است. به‌منظور کاهش هزینه‌های ارسال می‌توان کارهای پردازش‌شده را دسته‌بندی کرد و تمام کارهای یک دسته را با یک وسیله و با هزینۀ  (مستقل از حجم و تعداد کارها) ارسال کرد. فرض می‌شود به تعداد کافی وسیله وجود دارد و تحویل دسته به مشتری در زمان ارسال صورت می‌گیرد.‌ به عبارت دیگر زمان تحویل هر سفارش به مشتری، برابر زمان تکمیل دسته‌ای است که آن سفارش با آن دسته فرستاده می‌شود. هدف کمینه‌سازی مجموع وزنی تأخیر کارها و هزینه‌های ارسال است. به‌منظور تطابق بیشتر با دنیای واقعی، برای هر دسته یک زمان آماده‌سازی در نظر گرفته می‌شود. استینر و ژانگ در پژوهش­های خود اشاره کرده‌اند که استفاده از این نوع زمان آماده‌سازی بسیار واقعی‌تر و عملی‌تر است و پژوهش­ها کاربردی‌تر می‌شوند (استینر و ژانگ، 2009). نمونه‌هایی از کاربرد زمان آماده‌سازی برای هر دسته که موضوع ارسال هم در آن وجود دارد در مطالعات هاچمن و لاندی (1991) و نیز لینگ و چنگ (2005) ارائه شده است. به‌عنوان مثال می‌توان به زمان‌های موردنیاز جهت بسته‌بندی سفارشات اشاره کرد که در آن به جز زمان پردازش سفارشات زمانی هم برای آماده‌سازی پالت یا انتقال بسته باید منظور کرد. همچنین نمونه‌های دیگری از کاربرد آن در سیستم‌های بارگیری است که زمانی صرف انتقال بسته‌ها می‌شود. گفتنی است جهت محاسبۀ زمان تکمیل هر دسته باید زمان تکمیل پردازش کارهای موجود در آن دسته را با یک زمان آماده‌سازی جمع کرد (تفاوتی در اینکه زمان آماده‌سازی در کجای دسته در نظر گرفته شود وجود ندارد؛ زیرا زمان تکمیل دسته برابر مجموع زمان‌های گفته‌شده است و زمان تکمیل هر کار برابر زمان تکمیل دسته مربوطه است) (راستی برزکی و همکاران، 1391). براساس نمایش اختصاری پیشنهادشده توسط چن (2010) نمایش اختصاری این مسئله به‌صورت  است که در آن  مجموع وزنی تأخیر کارها و  کل هزینۀ ارسال است.

 

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

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

 

2-2- پیچیدگی مسئله

واضح است مسائلی که علاوه بر اهداف معمول زمان‌بندی و توالی، هزینه‌های ارسال را نیز در نظر می‌گیرند پیچیده‌تر از مسائل کلاسیک هستند. مسئلة ، به‌طور قوی[21]NP-hard است (چنگ، 2004). بنابراین، مسئلة  نیز به‌طور قوی NP-hard است.

 

2-3- علائم اصلی

علائم مورداستفاده در برنامه‌ریزی عدد صحیح مسئله موردبررسی در جدول 2 آمده است.

 


جدول 2- تعریف علائم مورداستفاده در مدل

علائم

تعریف

 

اندیس سفارشات (کارها)

 

تعداد کل سفارشات

 

زمان آماده‌سازی هر دسته

 

هزینة ارسال هر دسته

 

تعداد دسته‌ها (متغیر تصمیم)

 

زمان پردازش کار jام

 

یک اگر کار  متعلق به دستة bام باشد؛ صفر در غیر این صورت (متغیر تصمیم)

 

وزن (جریمه) دیرکرد کار ام

 

تأخیر کار ام (متغیر تصمیم)

 

یک اگر دستة bام خالی نباشد؛ صفر در غیر این صورت (متغیر تصمیم)

 

زمان تکمیل دستة bام (متغیر تصمیم)

 

موعد تحویل کار jام

 

یک عدد بزرگ

 

زمان ارسال کار jام

 

 

3- برنامه‌ریزی عدد صحیح مختلط

در این بخش، برنامه‌ریزی عدد صحیح مختلط برای مسئلة گفته‌شده ارائه می‌شود (رضایی و همکاران، 1392)..

تابع هدف شامل کمینه‌کردن مجموع هزینه‌های تأخیر و ارسال است که در رابطۀ (1) نشان داده شده است. رابطۀ (2) مقدار تأخیر هر کار را محاسبه می‌کند. رابطۀ (3) نشان می‌دهد که هر کار باید فقط به یک دسته اختصاص یابد. رابطۀ (4)، زمان تکمیل پردازش یک دسته را با درنظرگرفتن زمان آماده‌سازی محاسبه می‌کند. مقدار اولیه متغیر زمان تکمیل دسته ( ) در رابطۀ (5) آورده شده است. رابطۀ (6) زمان ارسال هر کار را با استفاده از زمان تکمیل دسته‌ای که آن کار متعلق به آن دسته است، محاسبه می‌کند. رابطۀ (8) و (9) تعداد دسته‌های بهینۀ مسئله را با استفاده از متغیر  مشخص می‌کند. روابط (10) تا (13) نیز وضعیت متغیرهای مدل را نشان می‌دهند.

 

4- معرفی الگوریتم مورچگان.

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

 

4-1- الگوریتم جمعیت مورچگان[22] (ACS).

.تاکنون نسخه‌های مختلفی برای الگوریتم ACO ارائه شده است. از جملۀ این الگوریتم‌ها می‌توان به الگوریتم سیستم مورچگان[23] (AS)، سیستم مورچگان ماکس مین[24] (MMAS) و سیستم اجتماع مورچگان(ACS) اشاره کرد (لیائو و جوان، 2007). البته عمده تفاوت نسخه‌های مختلف الگوریتم ACO در نحوۀ به‌روزرسانی فرومون‌های آنها است. الگوریتم ACS، یکی از موفق‌ترین نسخه‌های الگوریتم ACO است که آن را دوریگو و گامباردلا (2005) ارائه کرده‌اند.

شکل 1 شبه‌کدهای این الگوریتم را نشان می‌دهد.

 

مقداردهی اولیه را انجام بده

تا هنگامی که شرایط خاتمه برقرار نشده

جواب‌های مورچه‌ها را بساز و به‌روزرسانی محلی فرومون‌ها را انجام بده

جستجوی محلی را انجام بده /اختیاری/

به‌روزرسانی سراسری فرومون‌ها را انجام بده

پایان

شکل 1- شبه‌کدهای الگوریتم ACS

 

4-2- معرفی پارامترهای روش ACS

: مقدار فرومون روی یالی است که گره‌های  و  را به هم متصل می‌کند.

: احتمال حرکت از گره  به گره ملاقات‌نشدۀ  و به‌وسیلۀ مورچۀ k است.

: اطلاعات ابتکاری برای اندازه‌گیری میدان دید مورچه است.

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

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

: یک پارامتر آستانه‌ثابت در  است که نسبت اهمیت استخراج به اکتشاف را تعیین می‌کند. توجه کنید که انتخاب  روش ACS را به‌روش AS تبدیل می‌کند. بنابراین موقعی که q کمتر یا مساوی  باشد مورچه‌ها اکتشاف را به کار می‌گیرند تا کار j را به‌عنوان کار بعدی در زمان‌بندی انتخاب کنند؛ در حالی که اگر q بزرگ‌تر از  باشد مورچه‌ها از استخراج برپایۀ احتمال، برای انتخاب کار بعدی استفاده می‌کند.

4-3- مقداردهی اولیه[25]

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

 

4-4- ساخت جواب[26]

در مرحلۀ ساخت جواب، هر مورچه یک توالی شدنی را در  گام می‌سازد. در هر گام، مورچۀ   که در کار ام قرار دارد، با احتمال  کار بعدی‌اش، j را طبق رابطۀ (14) حساب می‌کند:

 

همچنین با احتمال  کار بعدی‌اش را به‌صورت احتمالی طبق رابطۀ (15) حساب می‌کند:

 

که در این روابط  طول کمان ،  یک مقدار ابتکاری و  میزان تأثیر این مقدار ابتکاری را نشان می‌دهد. همچنین  مجموعۀ کارهای کاندید مورچۀ  برای حرکت بعدی‌اش است.

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

4-5- به‌روزرسانی محلی فرومون‌ها

در طول فرایند ساخت جواب، به محض اینکه یک مورچه یک کمان  را طی کند، میزان فرومون روی آن کمان نیز طبق رابطۀ (16)  به‌روز می‌شود.

 

که در این رابطه  ،  یک پارامتر است. به این فرایند، به‌روزرسانی محلی فرومون‌ها می‌گویند.

 

4-6- به‌روزرسانی سراسری فرومون‌ها

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

 

که ، نرخ تبخیر،  و  نیز مقدار  است. البته همین عمل سبب تشویق مورچه‌های دیگر به تکرار این تور می‌شود (الابیب و همکاران، 2007).

 

4-7- شرط خاتمه

الگوریتم ACS در صورتی خاتمه می‌یابد که تعداد تکرارهای الگوریتم به بیشترین مقدار خود برسد (این مقدار در تنظیم پارامترها تعیین می‌شود).

 

5- الگوریتم سیستم مورچۀ نخبه‌گرا[27] (EAS)

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

فرض کنید  بهترین جوابی است که تاکنون در اجرای کامل الگوریتم به دست آمده است؛ بنابراین در هنگام به‌روزرسانی فرومون، مسیر طی‌شده به‌وسیلۀ مورچه‌ای که مسیر  را تولید کرده است یک مقدار اضافی از فرومون با مقدار  را جذب می‌کند. بنابراین معادلۀ به‌روزرسانی فرومون به‌صورت رابطۀ (19) اصلاح می‌شود.

 

که در آن:

e: وزن تور  است و دارای یک مقدار ثابت است که توسط کاربر تعیین می­شود.

: هزینۀ توری است که مورچۀ kام پیموده است.

: نرخ تبخیر ثابت در دامنه  است که کاربر بدین وسیله کاهش فرومون روی یال‌ها را تنظیم می‌کند.

: مجموعه یال‌هایی که توسط مورچۀ kام مورد ملاقات قرار گرفته است.

: مقدار فرومون‌ریزی محلی است که در آن مورچه‌ها در حین حرکت ما بین هر گره i و j ، مقداری فرومون، به‌اندازۀ عکس اندازه‌ای که هر کدام تاکنون پیموده‌اند، روی یال مربوطه می‌ریزند (رابطۀ (20)) .

 

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

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

 

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

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

6- تنظیم پارامترها

قبل از اجرای ACS و EAS برای حل مسائل، ابتدا باید پارامترهای الگوریتم تنظیم شوند بدین منظور مهم‌ترین پارامترهای الگوریتم پیشنهادی که تأثیر بسزایی در همگرایی الگوریتم دارند، تجزیه و تحلیل می‌شوند. برای این منظور برای هر پارامتر موردنظر مقادیر مختلفی آزمایش می‌شود تا بهترین مقادیر برای پارامترهای موردبررسی در بازۀ انتخاب‌شده یافت شود. برای انتخاب این مقادیری، آزمایشی مطابق جدول طراحی شد و برای هر تعداد کار در هر گروه، 3 مسئله به‌صورت تصادفی تولید شدند؛ بنابراین، تعداد کل مسائل تولیدشده برای 27 گروه و 108 (27 4) تیمار، 324 (3 108) مسئله است. هر مسأله تولیدشده توسط روش ACS  به‌ازای تمام پارامترهای موجود در جدول یعنی 486 (3 3 3 2 3 3) مرتبه حل شد از طرف دیگر در هنگامی که یک پارامتر بررسی می‌شود، بقیۀ پارامترها ثابت در نظر گرفته می‌شوند تا به این ترتیب بتوان با دقت بیشتری پارامتر موردآزمایش را بررسی کرد. نتایجی که در جدول نشان داده شده است، بهترین مقادیری است که الگوریتم توانسته است در حل 157464 (324 486) مسئله به دست آورد.

 

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

در این بخش به‌منظور ارزیابی عملکرد روش‌های ارائه‌شده، نتایج محاسباتی ارائه می‌شود. داده‌های معیاری برای مسأله مطرح‌شده یافت نشد. در این تست عملکرد ACS در مقایسه با CPLEX ارزیابی می‌شود. روش‌ها ACS در محیط MATLAB 2011 (a) و مدل MIP در محیط GAMS23.7 کدنویسی شدند. CPLEX یکی از مشهورترین و بهترین محصولات تجاری برای حل MIP در نرم‌افزار GAMS است (براکر و همکاران، 2008). رایانۀ مورداستفاده دارای مشخصات CPU 2.30GHz, RAM 2GB, OS Windows 7 (64-bit) است. با توجه به پیچیدگی بالای مسئله (SNP) و محدودیت پردازشگرها، CPLEX و ACS جهت استفاده مسائلی با تعداد محدودی از کارها مورد توجه قرار می‌گیرند. از آنجایی که مقادیر پارامترهای مسئله بر زمان حل آن تأثیر می‌گذارند در این تست بازه‌های مختلفی برای تعدادی از پارامترهای مهم مسئله در نظر گرفته شده است. این تست نشان می‌دهد که مقادیر پارامترها چگونه بر زمان حل مسائل تأثیر می‌گذارد. پارامترهای مسائل به‌طور تصادفی از توزیع یکنواخت در بازه‌هایی به‌شرح زیر تولید شدند:

زمان‌های پردازش ( )‌ در بازۀ ،

زمان راه‌اندازی دسته برای مشتری ( ) در بازۀ ،

وزن کارها ( ) در بازه‌های ،  و ،

موعد تحویل هر کار ( ) در بازه‌های ، ، و ،

جدول 3 عوامل انتخاب‌شده و سطوح موردنظر را نشان می‌دهد.

برای هر تعداد کار در هر گروه، 10 مسئله به‌صورت تصادفی تولید و حل شدند؛ بنابراین، تعداد کل مسائل تولیدشده برای 27 گروه و 108 (27 4) تیمار، 1080 (10 108) مسئله است. همچنین، یک محدودیت زمانی 3600 ثانیه‌ای برای حل هر مسئله در نظر گرفته شد؛ به‌طوری که اگر الگوریتم در محدودیت گفته‌شده به پایان نرسد بالاجبار متوقف می‌شود. نتایج تست محاسباتی برای 27 گروه و 108 تیمار گفته‌شده در جدول 5 آورده شده است.

 

جدول 3- عوامل و سطوح انتخاب‌شده برای پارامترها

Factor

Value

Level

Code

 

 jobs

 

-

   

Low

1

 

High

2

 

Outspread

3

   

Tight

1

 

Medium

2

 

Loose

3

   

Low

1

 

High

2

 

Outspread

3

 

جدول 4- نتایج تنظیم پارامتر برای روشACS

e

max_it

       

k

روش تنظیم پارامتر

الگوریتم

-

10

20

30

0.6

0.79

0.98

1

3

5

1

2

0.1

0.5

0.9

2

5

8

Function

 

 

*

 

 

*

 

 

*

 

*

 

 

*

 

 

*

DOE

EAS

-

 

 

*

 

 

*

 

*

 

 

*

 

 

*

 

 

*

DOE

ACS

 

جدول 5- نتایج تست محاسباتی برای روش‌های ACS و MIP

 

d

W

n

Avg. of running time (s)

 

No. of optimum instances

 

MIP

ACS

Avg

Max

Min

MIP

ACS

 
 

1

1

1

4

0.90

0.89

2.04

7.67

0.00

10

4

 

1

1

1

7

4.10

1.76

1.65

6.59

0.00

10

2

 

1

1

1

10

1239.35

2.55

4.53

10.16

0.39

8

0

 

1

1

1

13

-*

-

-

-

-

-

-

 

1

1

2

4

1.01

0.88

0.56

5.06

0.00

10

8

 

1

1

2

7

9.14

1.70

2.50

10.53

0.00

10

2

 

1

1

2

10

1566.47

2.51

5.43

7.63

0.00

8

1

 

1

1

2

13

-

-

-

-

-

-

-

 

1

1

3

4

0.25

0.91

0.00

0.00

0.00

10

10

 

1

1

3

7

2.83

1.72

0.84

4.80

0.00

10

5

 

1

1

3

10

472.16

2.48

5.88

11.54

0.92

10

0

 

1

1

3

13

963.55

3.30

33.59

33.59

33.59

1

0

 

1

2

1

4

0.20

0.87

0.00

0.00

0.00

10

10

 

1

2

1

7

0.95

1.64

1.96

10.04

0.00

10

7

 

1

2

1

10

21.14

2.39

5.94

29.19

0.00

10

6

 

1

2

1

13

1052.68

3.18

11.02

34.52

0.00

7

3

 

1

2

2

4

0.20

0.86

0.10

0.98

0.00

10

9

 

1

2

2

7

0.84

1.65

10.62

45.24

0.00

10

5

 

1

2

2

10

66.98

2.39

17.22

80.00

0.00

10

4

 

1

2

2

13

759.34

3.17

18.18

53.24

0.00

10

4

 

1

2

3

4

0.20

0.88

0.00

0.00

0.00

10

10

 

1

2

3

7

0.85

1.66

5.97

30.48

0.00

10

8

 

1

2

3

10

31.74

2.43

4.96

16.77

0.00

10

6

 

1

2

3

13

751.13

3.19

6.41

32.07

0.00

9

6

 

1

3

1

4

0.18

0.84

1.10

10.96

0.00

10

9

 

1

3

1

7

0.25

1.62

0.00

0.00

0.00

10

10

 

1

3

1

10

2.80

2.36

6.82

34.83

0.00

10

8

 

1

3

1

13

0.64

3.14

3.33

33.33

0.00

10

9

 

1

3

2

4

0.20

0.84

0.00

0.00

0.00

10

10

 

1

3

2

7

0.26

1.61

0.00

0.00

0.00

10

10

 

 

ادامه جدول 5- نتایج تست محاسباتی برای روش‌های ACS و MIP

 

d

W

n

Avg. of running time (s)

 

No. of optimum instances

 

MIP

ACS

Avg

Max

Min

MIP

ACS

 
 

1

3

2

10

0.74

2.35

8.33

50.00

0.00

10

8

 

1

3

2

13

1.29

3.13

3.33

33.33

0.00

10

9

 

1

3

3

4

0.19

0.84

0.00

0.00

0.00

10

10

 

1

3

3

7

0.27

1.62

5.38

33.44

0.00

10

8

 

1

3

3

10

0.51

2.35

0.00

0.00

0.00

10

10

 

1

3

3

13

2.14

3.15

3.33

33.33

0.00

10

9

 

2

1

1

4

0.22

0.88

0.72

3.94

0.00

10

8

 

2

1

1

7

2.86

1.71

1.59

4.54

0.00

10

3

 

2

1

1

10

998.48

2.50

5.39

11.51

1.09

10

0

 

2

1

1

13

-

-

-

-

-

-

-

 

2

1

2

4

0.20

0.90

0.50

4.98

0.00

10

9

 

2

1

2

7

5.64

1.64

1.34

5.51

0.00

10

2

 

2

1

2

10

1914.29

2.38

2.94

9.01

0.91

6

0

 

2

1

2

13

-

-

-

-

-

-

-

 

2

1

3

4

0.22

0.89

2.25

14.36

0.00

10

7

 

2

1

3

7

1.89

1.67

0.82

2.62

0.00

10

5

 

2

1

3

10

344.85

2.42

6.10

11.72

1.16

8

0

 

2

1

3

13

-

-

-

-

-

-

-

 

2

2

1

4

0.27

0.89

0.29

2.88

0.00

10

9

 

2

2

1

7

1.05

1.62

5.06

39.46

0.00

10

6

 

2

2

1

10

52.38

2.32

5.59

19.48

0.00

10

3

 

2

2

1

13

607.05

3.06

24.94

65.97

0.00

7

2

 

2

2

2

4

0.22

0.86

0.30

2.25

0.00

10

8

 

2

2

2

7

1.00

1.61

0.05

0.45

0.00

10

9

 

2

2

2

10

57.02

2.35

18.60

39.60

0.00

10

2

 

2

2

2

13

1316.76

3.09

24.65

76.76

0.00

5

3

 

2

2

3

4

0.21

0.86

1.01

5.99

0.00

10

8

 

2

2

3

7

0.76

1.60

3.73

35.30

0.00

10

8

 

2

2

3

10

14.52

2.32

8.34

74.42

0.00

10

8

 

2

2

3

13

909.12

3.07

22.54

64.67

0.00

10

4

 

2

3

1

4

0.20

0.85

0.00

0.00

0.00

10

10

 

2

3

1

7

0.31

1.58

1.20

12.03

0.00

10

9

 

2

3

1

10

1.45

2.31

3.59

30.26

0.00

10

8

 

2

3

1

13

5.93

3.03

5.00

50.00

0.00

10

9

 

2

3

2

4

0.20

0.86

2.59

15.48

0.00

10

8

 

2

3

2

7

0.29

1.60

0.00

0.00

0.00

10

10

 

2

3

2

10

0.83

2.28

0.00

0.00

0.00

10

10

 

2

3

2

13

0.66

3.03

15.00

50.00

0.00

10

7

 

2

3

3

4

0.19

0.84

0.00

0.00

0.00

10

10

 

2

3

3

7

0.29

1.58

0.00

0.00

0.00

10

10

 

2

3

3

10

1.37

2.29

1.31

13.10

0.00

10

9

 

2

3

3

13

1.78

3.02

3.33

33.33

0.00

10

9

 

3

1

1

4

0.21

0.88

0.31

2.49

0.00

10

8

 

3

1

1

7

3.44

1.66

1.96

5.51

0.00

10

4

 

3

1

1

10

910.81

2.42

2.99

8.69

0.27

9

0

 

3

1

1

13

-

-

-

-

-

-

-

 

3

1

2

4

0.23

0.88

0.89

3.44

0.00

10

7

 

3

1

2

7

10.50

1.69

2.61

8.60

0.00

10

3

 

3

1

2

10

1283.52

2.41

7.08

14.04

1.65

9

0

 

3

1

2

13

-

-

-

-

-

-

-

 

3

1

3

4

0.22

0.91

0.00

0.00

0.00

10

10

 

3

1

3

7

2.77

1.67

2.19

6.03

0.00

10

3

 

3

1

3

10

296.95

2.42

9.16

25.39

0.21

9

0

 

ادامه جدول 5- نتایج تست محاسباتی برای روش‌های ACS و MIP

 

d

W

n

Avg. of running time (s)

 

No. of optimum instances

 

MIP

ACS

Avg

Max

Min

MIP

ACS

 
 

3

1

3

13

1601.80

3.21

5.83

5.83

5.83

1

0

 

3

2

1

4

0.20

0.85

0.04

0.41

0.00

10

9

 

3

2

1

7

0.79

1.59

1.27

12.73

0.00

10

9

 

3

2

1

10

32.36

2.31

12.94

41.53

0.00

10

4

 

3

2

1

13

568.03

3.07

19.75

86.61

0.00

9

3

 

3

2

2

4

0.22

0.85

0.35

3.47

0.00

10

9

 

3

2

2

7

0.97

1.59

3.38

18.96

0.00

10

6

 

3

2

2

10

66.93

2.32

11.61

38.28

0.00

10

2

 

3

2

2

13

1214.25

3.07

26.45

47.52

0.00

8

1

 

3

2

3

4

0.22

0.85

0.00

0.03

0.00

10

9

 

3

2

3

7

0.74

1.60

2.16

9.25

0.00

10

7

 

3

2

3

10

22.40

2.31

10.39

45.53

0.00

10

5

 

3

2

3

13

649.94

3.05

16.07

64.24

0.00

10

3

 

3

3

1

4

0.19

0.83

0.00

0.00

0.00

10

10

 

3

3

1

7

0.27

1.57

2.06

20.57

0.00

10

9

 

3

3

1

10

1.09

2.27

10.35

52.13

0.00

10

6

 

3

3

1

13

0.67

3.01

7.20

35.57

0.00

10

7

 

3

3

2

4

0.19

0.84

0.00

0.00

0.00

10

10

 

3

3

2

7

0.30

1.59

0.00

0.00

0.00

10

10

 

3

3

2

10

0.77

2.30

0.00

0.00

0.00

10

10

 

3

3

2

13

25.98

3.03

5.00

50.00

0.00

10

9

 

3

3

3

4

0.19

0.83

0.00

0.00

0.00

10

10

 

3

3

3

7

0.37

1.58

0.00

0.00

0.00

10

10

 

3

3

3

10

0.48

2.31

0.00

0.00

0.00

10

10

 

3

3

3

13

1.23

3.01

14.72

50.00

0.00

10

7

 

* علامت "-"  نشان‌دهندۀ این است که الگوریتم نتواسته است مسائل تولیدشده را در محدودیت زمانی 3600 ثانیه حل کند.

 

 

 

برخلاف الگوریتم‌های دقیق که زمان معیار اصلی موفقیت آنها محسوب می‌شود، دو موضوع مهم در ارزیابی الگوریتم‌های فرااِبتکاری مورد توجه است: اول سرعت الگوریتم و دوم دقت جواب. براساس مشاهدات تست‌های انجام‌شده، کمترین، متوسط و بیشترین متوسط انحراف ACS از جواب بهینه برای همۀ تیمارها به‌ترتیب 00/0درصد، 11/5درصد و 59/33درصد است. ACS ، 28/62درصد از مسائل تولیدشده را صورت بهینه حل کرده است؛ این در حالی است که روشMIP با توجه به ساختار مسئله 89درصد مسائل تولیدشده را حل کرده است؛ همچنین کمترین، متوسط و بیشترین زمان اجرای ACS برای همۀ تیمارها به‌ترتیب 3/3، 83/. و 92/1 ثانیه است البته همان‌طور که از شکل 2 مشهود است با افزایش تعداد کارها، زمان حل مسائل روش MIP به‌صورت کاملاً نمایی افزایش یافته است؛ این در حالی است که روش ACS توانسته است مسائل را در زمان بسیار اندکی حل کند. این موضوع نشان می‌دهد که الگوریتم فرااِبتکاری طراحی‌شده در معیار زمان بسیار بهتر از روش دقیق است و می‌تواند عدم‌کارایی روش MIP را برای اندازه‌های بزرگ جبران کند. بنابراین می‌توان نتیجه گرفت با درنظرگرفتن هم‌زمان دو معیار سرعت و دقت الگوریتم و توجه به پیچیدگی بالای مسأله  ، این نتایج برای روش فرااِبتکاری بسیار مناسب هستند. نتایج حاصل از آنالیز واریانس برای تست گفته‌شده در

 آورده شده است. براساس p-value مدل، مدل برای همۀ روش‌ها معنادار است؛ بنابراین، حداقل یکی از عوامل انتخاب‌شده دارای اثر اصلی یا حداقل دو مورد از عوامل انتخاب‌شده دارای آثار متقابل بر روش مورداستفاده هستند. گفتنی است آثار از درجۀ دو به بالا به‌عنوان باقیمانده در مدل در نظر گرفته شده است. مطابق جدول 6، علاوه بر وجود آثار اصلی معنادار یکی از آثار متقابل عوامل نیز معنادار هستند؛ بنابراین، در تحلیل نتایج لازم است به آثار متقابل عوامل دقت شود. همچنین در سطح معناداری 5درصد، سختی مسئله برای هر سه رویکرد متأثر از عوامل تعداد کارها، وزن کارها و موعد تحویل است. بنابراین، عملکرد ACS و CPLEX نه تنها به اندازۀ مسئله بلکه به مقادیر پارامترها نیز بستگی دارد.

برای ارزیابی کارایی ACS و EAS برای ابعاد متوسط و بزرگ (30،15، 45، ...، 105) شاخص‌های متعدد و متنوعی وجود دارد که پس از انجام مطالعات مرتبط، سه شاخص زمان حل، کیفیت و پراکندگی جواب‌های به‌دست‌آمده انتخاب شده است که در ادامه بحث خواهد شد.

شکل 2- زمان اجرای روش‌های ACS و MIP برحسب n به‌صورت تجمعی

شکل 3- نمودار آثار اصلی، متغیر پاسخ: درصد جواب‌های بهینة به‌دست‌آمده توسط ACS

 

 

جدول 6- تحلیل ANOVA برای CPLEXو ACS

Method

 

ACS

 

CPLEX

Source

 

s.s.*

d.f.**

F

p

 

s.s.

d.f.

F

P

Corrected

Model

 

1057.333

39

17.954

0.000

 

197.607

39

13.184

0.000

 

 

2490.323

1

1649.183

0.577

 

5671.474

1

14757.768

0.119

 

 

1.677

2

.555

0.000

 

1.695

2

2.205

0.000

 

 

459.641

2

152.195

0.006

 

88.795

2

115.527

0.046

 

 

17.003

2

5.630

0.000

 

2.499

2

3.251

0.000

 

 

336.107

3

74.194

0.671

 

118.103

3

102.438

0.667

 

 

3.562

4

.590

0.430

 

.917

4

.596

0.499

 

 

9.117

6

1.006

0.907

 

2.080

6

.902

0.267

 

 

1.522

4

.252

0.000

 

2.052

4

1.335

0.000

 

 

141.622

6

15.631

0.194

 

103.905

6

45.062

0.335

 

 

9.485

4

1.570

0.963

 

1.790

4

1.165

0.151

Error

 

92.112

61

 

 

 

23.443

61

 

 

Total

 

5243.000

101

 

 

 

9422.000

101

 

 

Corrected

Total

 

1149.446

100

 

 

 

221.050

100

 

 

* مجموع مربعات           ** درجه آزادی

 

جدول 7- نتایج تست‌های محاسباتی برای روش‌های ACS و EAS

Index

Avg. of CPU time (s)

EAS/ACS

RPD

Index

Avg. of CPU time (s)

EAS/ACS

RPD

ACS

EAS

Avg.

Max

ACS

EAS

Avg.

Max

1_1_1_15

20.40

20.68

1.11

1.32

0.44

2_2_1_15

18.67

19.89

1.64

3.97

0.23

1_1_1_30

45.17

45.71

1.08

1.18

0.58

2_2_1_30

41.72

44.22

1.24

2.02

0.46

1_1_1_45

75.20

75.06

1.04

1.15

0.49

2_2_1_45

69.00

73.72

1.08

1.72

0.45

1_1_1_60

111.14

110.95

1.02

1.14

0.41

2_2_1_60

103.61

109.32

0.96

1.32

0.57

1_1_1_75

152.91

152.41

1.04

1.16

0.43

2_2_1_75

142.55

149.76

1.05

1.33

0.65

1_1_1_90

199.97

199.00

1.01

1.09

0.43

2_2_1_90

186.64

195.45

0.98

1.47

0.36

1_1_1_105

252.94

251.31

1.01

1.09

0.55

2_2_1_105

236.06

248.78

1.01

1.54

0.28

1_1_2_15

20.36

20.60

1.09

1.21

0.60

2_2_2_15

18.62

19.85

1.64

3.32

0.28

1_1_2_30

45.41

45.75

1.06

1.10

0.45

2_2_2_30

41.55

44.37

1.31

1.88

0.44

1_1_2_45

75.23

75.16

1.02

1.06

0.74

2_2_2_45

69.02

73.67

1.13

1.78

0.39

1_1_2_60

111.70

111.79

1.02

1.08

0.56

2_2_2_60

103.57

109.89

1.05

1.56

0.40

1_1_2_75

152.99

153.03

1.03

1.14

0.36

2_2_2_75

142.67

150.46

1.10

1.45

0.57

1_1_2_90

199.64

199.58

1.01

1.10

0.56

2_2_2_90

186.92

195.62

0.97

1.17

0.49

1_1_2_105

253.31

251.34

1.02

1.07

0.55

2_2_2_105

237.09

248.45

1.03

1.47

0.39

1_1_3_15

20.35

20.65

1.12

1.32

0.44

2_2_3_15

18.68

19.93

1.56

2.46

0.45

1_1_3_30

45.35

45.69

1.09

1.20

0.55

2_2_3_30

41.57

44.13

1.63

3.78

0.31

1_1_3_45

75.06

75.00

1.03

1.16

0.55

2_2_3_45

68.93

73.70

0.94

1.78

0.48

1_1_3_60

110.86

111.31

1.05

1.14

0.45

2_2_3_60

103.58

109.24

1.10

1.60

0.53

1_1_3_75

152.97

153.37

1.06

1.11

0.70

2_2_3_75

142.30

150.22

1.17

1.81

0.30

1_1_3_90

199.96

199.82

1.04

1.10

0.63

2_2_3_90

186.36

195.30

1.13

2.37

0.34

1_1_3_105

253.38

251.80

1.01

1.09

0.50

2_2_3_105

237.65

249.73

1.04

1.66

0.30

1_2_1_15

19.67

19.84

1.37

2.47

0.38

2_3_1_15

19.19

20.39

1.25

1.86

0.32

1_2_1_30

43.92

43.90

0.93

1.36

0.54

2_3_1_30

42.75

45.22

1.02

1.28

0.51

1_2_1_45

72.71

72.38

1.10

1.57

0.59

2_3_1_45

70.75

75.30

1.07

1.35

0.46

1_2_1_60

108.07

107.59

1.11

1.94

0.29

2_3_1_60

106.10

111.81

1.01

1.11

0.53

1_2_1_75

150.19

148.94

0.89

1.48

0.37

2_3_1_75

145.39

153.00

1.02

1.10

0.49

1_2_1_90

198.88

197.93

0.81

1.33

0.32

2_3_1_90

189.97

200.04

1.07

1.22

0.61

1_2_1_105

251.73

248.11

0.84

1.06

0.47

2_3_1_105

242.01

254.80

1.10

1.22

0.62

1_2_2_15

20.31

20.40

1.37

2.95

0.38

2_3_2_15

19.21

20.43

1.15

1.48

0.35

1_2_2_30

44.97

44.80

1.27

2.49

0.34

2_3_2_30

42.82

45.46

1.04

1.29

0.50

1_2_2_45

74.14

73.85

1.13

1.51

0.60

2_3_2_45

70.94

75.83

1.10

1.20

0.53

1_2_2_60

109.87

109.08

0.99

1.46

0.47

2_3_2_60

105.93

111.89

1.00

1.09

0.56

1_2_2_75

150.82

150.36

0.95

1.17

0.41

2_3_2_75

145.93

153.44

1.05

1.16

0.61

1_2_2_90

197.53

194.93

0.86

1.07

0.43

2_3_2_90

190.15

199.42

1.03

1.20

0.52

1_2_2_105

250.72

247.56

0.88

1.08

0.60

2_3_2_105

242.86

254.57

1.02

1.10

0.68

1_2_3_15

20.31

20.39

1.97

3.04

0.48

2_3_3_15

19.31

20.41

1.34

2.10

0.36

1_2_3_30

44.96

44.62

1.20

1.90

0.52

2_3_3_30

42.79

45.46

1.05

1.32

0.56

1_2_3_45

74.30

73.43

0.87

1.47

0.35

2_3_3_45

71.08

75.29

1.11

1.38

0.56

1_2_3_60

109.46

108.96

0.85

1.22

0.57

2_3_3_60

107.07

111.98

1.05

1.32

0.41

1_2_3_75

150.90

150.03

0.90

1.24

0.53

2_3_3_75

146.40

153.12

1.09

1.20

0.55

1_2_3_90

197.43

194.81

0.87

1.28

0.42

2_3_3_90

191.39

199.48

0.97

1.11

0.60

1_2_3_105

249.95

246.95

0.86

1.25

0.47

2_3_3_105

243.83

255.39

1.04

1.10

0.55

1_3_1_15

20.67

20.84

1.36

2.04

0.47

3_1_1_15

20.79

21.19

1.16

1.30

0.60

1_3_1_30

45.83

46.08

1.13

1.50

0.35

3_1_1_30

45.22

45.63

1.07

1.15

0.59

1_3_1_45

75.90

75.40

1.11

1.34

0.52

3_1_1_45

74.91

75.07

1.05

1.31

0.35

1_3_1_60

111.96

111.98

0.99

1.20

0.39

3_1_1_60

112.66

112.81

1.08

1.21

0.48

1_3_1_75

154.15

153.85

1.02

1.22

0.47

3_1_1_75

153.67

154.16

1.04

1.14

0.55

1_3_1_90

201.75

200.65

1.05

1.14

0.56

3_1_1_90

200.84

200.94

1.03

1.08

0.62

1_3_1_105

258.80

259.46

1.05

1.18

0.52

3_1_1_105

254.86

253.66

1.02

1.11

0.57

1_3_2_15

20.85

21.08

1.17

1.28

0.36

3_1_2_15

20.48

20.79

1.07

1.14

0.49

1_3_2_30

45.96

46.00

1.09

1.63

0.31

3_1_2_30

45.34

45.73

1.05

1.12

0.50

1_3_2_45

76.18

75.60

1.05

1.18

0.49

3_1_2_45

75.11

75.36

1.04

1.12

0.49

1_3_2_60

112.51

112.27

1.05

1.20

0.41

3_1_2_60

111.86

111.97

1.04

1.10

0.48

1_3_2_75

155.22

154.97

1.02

1.15

0.34

3_1_2_75

153.25

152.72

1.02

1.09

0.47

 

ادامه جدول 7- نتایج تست‌های محاسباتی برای روش‌های ACS و EAS

Index

Avg. of CPU time (s)

EAS/ACS

RPD

Index

Avg. of CPU time (s)

EAS/ACS

RPD

ACS

EAS

Avg.

Max

ACS

EAS

Avg.

Max

1_3_2_90

199.88

200.01

1.10

1.24

0.38

3_1_2_90

201.61

200.37

1.02

1.09

0.55

1_3_2_105

253.73

253.50

1.02

1.13

0.53

3_1_2_105

255.40

254.99

1.03

1.09

0.54

1_3_3_15

20.72

20.92

1.36

1.99

0.38

3_1_3_15

20.51

20.78

1.10

1.37

0.43

1_3_3_30

45.78

46.04

1.14

1.37

0.46

3_1_3_30

45.44

45.76

1.05

1.28

0.45

1_3_3_45

75.80

75.41

1.13

1.49

0.34

3_1_3_45

75.18

75.28

1.03

1.13

0.46

1_3_3_60

112.58

112.41

1.05

1.22

0.47

3_1_3_60

112.12

111.77

1.03

1.14

0.47

1_3_3_75

154.72

154.68

1.04

1.22

0.51

3_1_3_75

153.96

152.62

1.03

1.10

0.51

1_3_3_90

203.43

203.09

1.03

1.20

0.46

3_1_3_90

201.90

201.58

1.03

1.13

0.49

1_3_3_105

257.82

256.39

1.02

1.10

0.55

3_1_3_105

256.47

256.47

1.04

1.16

0.43

2_1_1_15

19.66

21.30

1.11

1.30

0.43

3_2_1_15

19.82

19.95

1.14

1.37

0.57

2_1_1_30

43.70

46.18

1.07

1.24

0.36

3_2_1_30

44.19

44.10

1.18

2.27

0.31

2_1_1_45

71.77

76.59

1.03

1.19

0.51

3_2_1_45

73.00

72.73

1.24

1.87

0.39

2_1_1_60

107.21

113.78

1.02

1.12

0.40

3_2_1_60

109.17

108.04

0.93

1.46

0.43

2_1_1_75

147.26

155.38

1.04

1.15

0.46

3_2_1_75

150.13

148.21

0.96

1.61

0.31

2_1_1_90

191.95

201.90

1.03

1.10

0.58

3_2_1_90

197.32

196.21

0.89

1.15

0.48

2_1_1_105

243.16

258.89

1.03

1.08

0.53

3_2_1_105

250.50

249.13

0.94

1.19

0.39

2_1_2_15

19.56

20.75

1.10

1.19

0.59

3_2_2_15

19.84

19.95

1.94

4.23

0.34

2_1_2_30

43.45

45.87

1.04

1.09

0.45

3_2_2_30

44.06

43.98

1.01

2.37

0.38

2_1_2_45

71.87

76.56

1.04

1.10

0.49

3_2_2_45

72.87

72.54

0.86

1.16

0.41

2_1_2_60

107.44

113.95

1.04

1.09

0.51

3_2_2_60

109.55

108.77

0.99

1.26

0.48

2_1_2_75

146.67

155.21

1.02

1.06

0.65

3_2_2_75

150.13

149.22

0.83

1.02

0.51

2_1_2_90

190.58

202.62

1.02

1.08

0.48

3_2_2_90

196.99

195.99

0.93

1.25

0.44

2_1_2_105

241.25

256.65

1.02

1.06

0.52

3_2_2_105

249.28

247.90

0.94

1.09

0.57

2_1_3_15

19.55

20.76

1.10

1.40

0.40

3_2_3_15

19.80

19.96

1.46

2.18

0.47

2_1_3_30

43.59

45.94

1.10

1.24

0.43

3_2_3_30

44.07

44.04

1.37

3.30

0.33

2_1_3_45

71.77

76.78

1.06

1.15

0.61

3_2_3_45

72.85

72.63

1.16

2.32

0.39

2_1_3_60

107.33

116.39

1.04

1.14

0.39

3_2_3_60

109.35

108.45

0.89

1.32

0.44

2_1_3_75

147.02

156.93

0.99

1.07

0.58

3_2_3_75

149.93

149.02

0.81

1.23

0.43

2_1_3_90

191.76

202.09

1.05

1.11

0.57

3_2_3_90

197.20

196.03

0.97

1.14

0.51

2_1_3_105

242.88

256.19

0.97

1.04

0.66

3_2_3_105

249.69

248.18

0.88

1.12

0.54

 

 

در این بخش، از نسبت  برای مقایسة کیفیت جواب‌های به‌دست‌آمده توسط هر روش استفاده می‌شود. برای درک بهتری از عملکرد روش‌های ACS و EAS برای ابعاد متوسط و بزرگ شکل 4 که نسبت  را برای اندازه‌های مختلف  را نشان می‌دهد ترسیم شده است. همان‌طور که مشاهده می‌شود با افزایش ، نسبت  کاهش می‌یابد که بیانگر عملکرد بسیار خوب ACS در ابعاد متوسط نسبت به EAS و عملکرد مشابه هر دو الگوریتم در ابعاد بزرگ است.

 

شکل 4- نمایش نسبت  برای اندازه‌های مختلف

 

 

 

7-1- شاخص پراکندگی

در این مقاله، برای ارزیابی پراکندگی جواب‌های تولیدشده الگوریتم‌های فرااِبتکاری از معیار درصد انحراف نسبی[xxviii] ( ) استفاده شده است. این شاخص را زندیه و همکاران معرفی کرده‌اند؛ نحوة محاسبة شاخص در رابطة (17) مشاهده می‌شود.

(17)

 

در این رابطه،  نشان‌دهندة نسبت جواب به‌دست‌آمده توسط الگوریتم‌های توسعه داده شده است و  و  به‌ترتیب، کوچک‌ترین و بزرگ‌ترین مقدار نسبت  از اجرای الگوریتم‌ها در هر 10 مسئلة تولیدی در هر گروه، در نظر گرفته شده است. مقدار نشان می‌دهد که جواب‌ها در هر الگوریتم تا چه اندازه از حداقل نسبت به‌دست‌آمده (حداقل نسبت بیانگر حداقل برتری الگوریتم تحت مطالعه نسبت به الگوریتم معیار است) در 10 مسئلة تولیدشده فاصله دارند. هر چه این فاصله بیشتر باشد به این معنی است که الگوریتم‌ها جواب‌های پرت‌تری تولید می‌کنند و متقابلاً هر چه این فاصله کمتر باشد، نشان می‌دهد که الگوریتم‌ها جواب‌های بهتری تولید می‌کنند و درنتیجه الگوریتم‌های مناسب‌تری هستند. شکل 5 تغییرات متوسط RDP را برای اندازه‌های مختلف مسائل تولیدشده نمایش می‌دهد. همان‌طور که مشاهده می‌شود میانگین کل این معیار برای همة مسائل کمتر از 5/0 است و تغییرات مقدار RDP برای nهای مختلف نشان‌دهندة یک ثبات و پایداری مناسب در میانگین نسبت به‌دست‌آمده متناظر هر  در شکل 5 است.

 

شکل 5- متوسط  برای اندازه‌های مختلف

 

7-2- مقایسة زمان اجرای ACS وEAS  

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

شکل 6- متوسط زمان حل روش‌های ACS و EAS

 

8- نتیجه‌گیری

در این مقاله، مسئله تصمیم‌گیری هم‌زمان (یکپارچه) زمان‌بندی تولید و ارسال دسته‌ای با هدف کمینه‌سازی مجموع وزنی تأخیر کارها و هزینة ارسال مورد بررسی قرار گرفت و پس از معرفی ، برای ابعاد کوچک مدل ریاضی مسئله (MIP) و یک روش ACS برای مسئلة گفته‌شده ارائه شد. به‌منظور بررسی کارایی این دو روش، تست‌های محاسباتی با رویکرد طراحی آزمایش‌ها به‌صورت کامل انجام شده و تحلیل نتایج با به‌کارگیری تکنیک آنالیز واریانس صورت گرفته است. همچنین وضعیت عملکرد روش ACS برای گروه‌های مختلف و پارامترهای مسئله تجزیه و تحلیل شده است. نتایج تست محاسباتی براساس تعداد جواب‌های بهینه،‌ درصد خطای روش ابتکاری و متوسط زمان حل، کارایی روش ACS را نشان می‌دهد. اما به‌منظور بررسی عملکرد روش ACS در ابعاد متوسط و بزرگ، یک EAS ارائه شد و عملکرد روش ACS برای شاخص‌های کیفیت، پراکندگی و زمان مطالعه شد که نتایج تست‌های محاسباتی، کارایی روش ACS را نشان می‌دهد. همچنین می‌توان به‌منظور انجام پژوهش­های آتی به تغییر تابع هدف زمان‌بندی همچون ترکیب آن با مجموع وزنی زودکردها اشاره کرد. ارسال به‌صورت مسیریابی[xxix] به جای ارسال مستقیم (که در آن می‌توان سفارشات چند مشتری را با یکدیگر و به‌طور هم‌زمان به‌وسیلة یک وسیله ارسال کرد) نیز از جمله فعالیت‌های آتی گسترش این پژوهش است.

 

9- تشکر و قدردانی

در پایان وظیفة خود می‌دانم که از آقای علی بهشتی برای هم‌فکری‌ها و راهنمایی‌هایی که در تدوین این مقاله داشته‌اند، صمیمانه تشکر و قدردانی کنم.



[1]- Supply Chain Management

[2]- Sarmiento and Nagi

[3]- Erenguc et al.

[4]- Goetschalckx et al.

[5]- Bilgen and Ozkarahan

[6]- Hall and Potts

[7]- Chen

[8]- Rasti Barzoki et al.

[9]- Lockamy et al.

[10] Single Machine Total Weighted Tardiness Problem

[11]- Simulated Annealing

[12]- Genetic Algorithm

[13]- Tabu Search

[14]- Ant Colony Optimization

[15]- Particle Swarm Optimization

[16]- Variable Neighborhood Search

[17]- Batch Delivery

[18]- Dynamic Programming

[19]- MIP

[20]- ACS

[21]- Strongly

[22]- ACS

[23]- Ant Colony System

[24]- Max-Min Ant System

[25]- Initialization

[26]- Tour Construction

[27]- Elitist Ant System

[xxviii]- Relative Deviation Percentage

[xxix]- Routing

مظاهری، علی؛ کرباسیان، مهدی؛ سجادی، سید مجتبی؛ شیرویه زاد، هادی و همکاران (1393). «ارائة مدلی جهت بهینه‌سازی زنجیرة تأمین یکپارچه با استفاده از روش برنامه‌ریزی تصادفی چندهدفه»، نشریة بین‌المللی مهندسی صنایع و مدیریت تولید، ۲(25). 186- 204.

راستی برزکی، مرتضی؛ حجازی، سیدرضا و مهدوی مزده، محمد. (1392). «یک FPTAS برای کمینه‌کردن مجموع وزنی تعداد کارهای تأخیری با درنظرگرفتن مجموع هزینه‌های تخصیص موعد تحویل گروهی، تخصیص منابع و برنامه‌ریزی توزیع در زنجیرة تأمین»، نشریة بین‌المللی مهندسی صنایع و مدیریت تولید، در دست چاپ.

راستی برزکی، مرتضی. (1391). «مدل یکپارچه تخصیص موعد تحویل، تخصیص منابع و زمان‌بندی تولید و توزیع در زنجیرة تأمین»،‌ رسالة دکتری، دانشگاه صنعتی اصفهان.

رضایی، سید رضا؛ حجازی، سیدرضا و راستی برزکی، مرتضی. (1392). «کمینه‌کردن مجموع وزنی تأخیر کارها و هزینة ارسال برای مدل زمان‌بندی یکپارچة تولید و توزیع در زنجیره تأمین»، نشریة بین‌المللی مهندسی صنایع و مدیریت تولید، در دست بررسی.

راستی برزکی، مرتضی و حجازی، سیدرضا. (1392). «کمینه‌کردن مجموع وزنی تعداد کارهای تأخیری با درنظرگرفتن مجموع هزینه‌های تخصیص موعد تحویل گروهی و هزینه‌های ارسال»، نشریة بین‌المللی مهندسی صنایع و مدیریت تولید، در دست چاپ.

فخرزاد، محمدباقر و عظیم‌زاده، مهدی. (1391). «الگوریتم ژنتیک برای مسئلة زمان‌بندی تک‌ماشین با جرایم زودکرد خطی، دیرکرد توان دوم و با درنظرگرفتن زمان بیکاری و شکست کار»، مدیریت تولید و عملیات، 3(1)، 69-92.

قجاوند، حمزه؛ زندیه، مصطفی؛ دری، بهروز (1390) به‌کارگیری الگوریتم‌های فرااِبتکاری در مدل یکپارچه‌سازی شبکة لجستیک توزیع کالا، چشم‌انداز مدیریت صنعتی، 3، 99-119.

 

Andreas C. Nearchou. (2012). "A Hybrid Metaheuritic For The Single-Machine Total Weighted Tardiness Problem". Cybernetics and Systems, 43)8(, 651-668.

Bauer, A., Bullnheimer, B., Hartl, R. F., and Strauss, C. (1999). "An Ant Colony Optimization Approach for the Single Machine Total Tardiness Problem". In Proceedings of CEC’99, P. J. Angeline, Z. Michalewicz, M.Schoenauer, X. Yao, and A. Zalzalan (eds.), 1445–1450.

Bilge, U., Kurtulan, M., and Kırac, F. (2007). "A Tabu Search Algorithm for the Single Machine Total Weighted Tardiness Problem". European Journal of Operational Research, 176, 1423–35.

Bilgen, B., I. Ozkarahan. (2004). "Strategic tactical and operational production-distribution models: A review",  Internat. J. Tech. Management, 28, 151–171.

Brucker P., Kampmeyer T. (2008). "A general model for cyclic machine scheduling problems". Discrete Applied Mathematics, 156, 2561-2572.

C. Liao, and H. Juan. (2007). "An ant colony optimization for single machine tardiness scheduling with sequence-dependent setups". Computers & Operations Research, 34, 1899-1909.

Chen Z-L. (2010). "Integrated Production And Outbound Distribution Scheduling: Review and Extensions". Operations Research, 58, 130-148.

Chen Z-L., Vairaktarakis L.G. (2005). "Integrated Scheduling of Production and Distribution Operations". Management Science, 51, 614-628.

Chen, Z.-L. (2004). " Integrated production and distribution operations: Taxonomy, models, and review". D. Simchi-Levi, S. D. Wu, Z.-J. Shen, eds. Handbook of Quantitative Supply Chain Analysis: Modeling in the E-Business Era. Kluwer Academic Publishers, Norwell, MA.

Cheng, T. C. E., H. G. Kahlbacher. (1993). "Scheduling with delivery and earliness penalties". Asia-Pacific Jpurnal of Operation Research, 10, 145–152.

Cheng, T.C.E., (2004). "Single machine scheduling to minimize total weighted tardiness".  European Journal of Operational Research, 165, 423–443.

Crauwels, H. A. J., Potts, C. N. and Van Wassenhove, L. N. (1998). "Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem". INFORMS Journal on Computing, 10, 341–350.

Dorigo M, Stützle T. (2002). " The ant colony optimization metaheuristics: algorithms, applications, and advances". In: Glover F, Kochenberger G, editors. Handbook of metaheuristics, vol. 57. International Series in Operations Research & Management Science. Dordrecht: Kluwer;  251–85.

Ellabib, I., Calamai, P. and Basir, O. (2007): "Exchange strategies for multiple ant colony system". Information Sciences. an International Journal, 177, 1248-1264.

Emmons, H. (1969). "One-machine sequencing to minimize certain functions of job tardiness". Operations Research, 17, 701–715.

Erenguc, S.S., N.C. Simpson, A. J. Vakharia. (1999).  "Integrated production/distribution planning in supply chains: An invited review". European Journal of Operational Research, 115, 219–236.

French, S. (1990). "Sequencing and Scheduling, an Introduction to the Mathematics of the Job-Shop". NewYork: EllisHorwood, John-Wiley&Sons.

Goetschalckx, M., C. J. Vidal, K. Dogan. (2002). "Modeling and design of global logistics systems: A review of integrated strategic and tactical models and design algorithms". European Journal of Operational Research, 143, 1–18.

Hall N.G., Potts C.N. (2003). "Supply Chain Scheduling: Batching And Delivery". Operations Research, 51 4, 566-584.

Hall, N. G., C. N. Potts. (2005). "The coordination of scheduling and batch deliveries". Annual Operations of Research, 135, 41–64.

Hochbaum, D.S., Landy, D. (1994). "Scheduling with batching: minimizing the weighted number of tardy jobs". Operations Research Letters, 16, 79-86.

Kellegoz, T., Toklu, B., and Wilson, J. (2008). "Comparing Efficiencies of Genetic Crossover Operators for One Machine Total Weighted Tardiness Problem". Applied Mathematics and Computation, 199, 590–598.

Lawer, E. L. (1977). "A ‘Pseudopolynomial" Algorithm for Sequencing Jobs to Minimize Total Tardiness". Annuals of Discrete Mathematics, 1, 331–342.

Lenstra, J. K., Rinnoy Kan, A. H. G., and Brucker, P. (1977). "Complexity of Machine Scheduling Problems". Annuals of Discrete Mathematics, 1, 343–362.

Lin, B.M.T., Cheng, T.C.E. (2005). "Two-machine flowshop batching and scheduling". Annals of Operations Research, 133, 149-161.

Lockamy, A., McCormack, K. (2004). "Linking SCOR planning practices to supply chain performance". International Journal of Operations and Production Management, 24, 1192-1218.

M. Dorigo, and L. M. Gambardella. (1997). "Ant Colony System: A cooperative learning approach to the traveling salesman problem".  IEEE Transactions on Evolutionary Computation, 1, 53-66.

Matsuo, H., Suh, C. J., and Sullivan, R. S. (1989). "A Controlled Search Simulated Annealing Method for the Single Machine Weighted Tardiness Problem". Annals of Operations Research, 21, 85–108.

Potts, C. N. and Van Wassenhove, L. N. (1991). "Single Machine Tardiness Sequencing Heuristics". IEE Transactions, 23, 346–354.

Potts, C. N. (1980). "Analysis of a heuristic for one machine sequencing with release dates and delivery times". Operations Research, 28, 1436–1441.

Potts, C. N., Kanet, J. J., Birkemeier, C. (2013).  "Weighted tardiness for the single machine scheduling problem:An examination of precedence theorem productivity". Computers & Operations Research, 40, 91-97.

Pundoor, G., Z.-L. Chen. (2005). "Scheduling a production-distribution system to optimize the trade off between delivery tardiness and total distribution cost". Naval Research Logistics, 52, 571-589.

Rasti-Barzoki, M., Hejazi, S.R., Mazdeh, M.M. (2013). "Minimizing the weighted number of tardy jobs with due date assignment and capacity constrained deliveries for multiple customers in supply chains". European Journal of Operational Research, 228, 345-357.

Sarmiento, A. M., R. Nagi. (1991). "A review of integrated analysis of production-distribution systems". IIE Trans, 31, 1061–1074.

Scharge, L., and K. R. Baker. (1978). "Dynamic Programming Solution of Sequencing Problems With Precedence Constraints". Operationals Research, 26, 444-449.

Slotnick, S. A., & Sobel, M. J. (2005). "Manufacturing lead-time rules: Customer retention versus tardiness costs". European Journal of Operational Research, 169, 825–856.

Steiner G, Zhang R. (2009). "Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains". Journal of Scheduling,12,. 565-574.

Tasgetiren, M. F., Liang, Y.-C., Sevkli, M., and Gencyilmaz, G. (2006). "Particle Swarm Optimization and Differential Evolution for the Single Machine Total Weighted Tardiness Problem". International Journal of Production Research, 22, 4737–4754.

Thomas, D. J., & Griffin, P. M. (1996).  "Coordinated supply chain management". European Journal of Operational Research, 94, 1–15.

Wang, X. and Tang, L. (2009). "A Population-Based Variable Neighborhood Search for the Single Machine Total Weighted Tardiness Problem". Computers & Operations Research, 36, 2105–2110.