نشریه تخصصی مهندسی صنایع، دوره 50، شماره 2، پاییز و زمستان 1395، از صفحه 191 تا 203

زمان بندی تولید و حمل ونقل و تخصیص سفارش ها در زنجیرة تأمین

محمدعلی بهشتی نیا1*، امیر قاسمی2، معین فرخ نیا3 ‌
استادیار دانشکدة فنی و مهندسی، دانشگاه سمنان
دانشجوی کارشناسی ارشد مهندسی صنایع دانشکدة فنی و مهندسی، دانشگاه سمنان
دانشجوی کارشناسی ارشد مهندسی صنایع دانشکدة فنی و مهندسی، دانشگاه سمنان

)تاریخ دریافت 16/12/93 ـ تاریخ دریافت روایت اصلاحشده 24/10/94 ـ تاریخ تصویب 28/1/95( چکیده
این پژوهش مسئلة زمان بندی در زنجیرة تأمین دو مرحله ای را بررسی می کند. مرحلة اول شامش تـأم ین کننـدگان ، مرحلـ ة دوم شـامش ناوگـانحمش ونلش کااها به یک شرکت تولیدکنندة محصوات نهایی است. هدک تخصـیص سـفارش هـا بـه تـأمین کننـدگان ، تعیـین تـوالی تولیـد درتأمین کنندگان، تخصیص سفارش ها به وسایش نللیه و تعیین اولویت حمش سفارش ها از طریق وسـایش نللیـه بـه منظـور کمینـه کـر دن مجمـوعزمان های پردازش و حمش است. این مسئله تاکنون در ادبیات موضوع بررسی نشده است. ابتدا مدل ریاضی به صورت برنامه ریـزی عـدد صـحیحمختل ارائه می شود. به منظور حش مسئله، یک الگوریتم فرا ابتکاری ترکیبـی ارائـه مـ ی شـود کـه تلفیـق جدیـدی از الگـور یتم هـای ژنتیـک وشبیه سازی تبرید را درنظر می گیرد. الگوریتم به منظور ارزیابی کیفیت با یکی از الگوریتم های مطرح شده در ادبیات موضوع ،الگـور یتم ژنتیـک و الگوریتم شبیه سازی تبرید به صورت مجزا ملایسه می شود. ملایسة نتایج نهایی محاسبات الگوریتم ها بیانگر برتری الگوریتم تلفیلی در ملایسه با الگوریتم های مورد ملایسه است.

واژه‌های‌کلیدی: الگوریتم ژنتیک، الگوریتم شبیه سازی تبرید، برنامه ریزی حمش ونلش، زمان بندی، زنجیرة تأمین.

مقدمه
زنجیرة تأمین از جمله مهم ترین موضوعات مورد پژوهش در حوزة تولید و توزیع در بیست سال اخیـر بـوده اسـت. یـکزنجیرة تأمین شامش تمام مراحلی است که در یک محصول ارزش اف زوده ایج اد م ی کن د. اهمی ت یکسارچ ه س ازی و همگام سازی جریان مواد و اطلاعات در یک سیستم زنجیرة تأمین سبب ایجاد تمایش بسـیار بـاای صـاحبان صـنعت وپژوهشگران آکادمیک شده اسـت. درکـش ، مباحـث زنجیـرة تـ أمین شـ امش تمـ ام روابـ بـ ین تـ أمین کننـ دگان، تولیدکنندگان، توزیع کنندگان و مصرک کنندگان مـ ی شـود .
زمان بندی جریان مـواد در بـین بخـش هـا ی مختلـف یـکزنجیرة تأمین از جمله مهم ترین مباحث کنترل موجـودی ومدیریت زنجیره تأمین است که تا به حال توجه چندانی بـهآن نشده است و پژوهش های کمـی در ایـن زمینـه صـورتگرفته است 1[.
در این پژوهش، مسئلة زمان بندی در زنجیرة تـأمین بـا
دو مرحلـــه بررســـی مـــی شـــود. مرحلـــة اول شـــامش
548658965

* نویسندة مسئول: دورنگار: 02333654275

تأمین کنندگانی اسـت کـه در نـواحی مختلـف جغرافیـاییپراکنده اند، مرحلة دوم شامش ناوگان حمش ونلـش کااهـا بـه یـک ش رکت تول یدکنن دة محصـوات نه ایی اس ت. ه دکتخصیص سفارش ها به تأمین کنندگان، تعیین تـوالی تولیـددر تأمین کنندگان، تخصیص سفارش ها بـه وسـایش نللیـه وتعیین اولویـت حمـش سـفارش هـا از طریـق وسـایش نللیـهبه منظور کمینه کردن مجموع زمان تکمیش سـفارش هاسـت.فرض می شود تأمین کننـدگان از یـک ناوگـان حمـش ونلـشمشتر که مشابه مسئلة مسیریابی وسایش نللیـه )VRP(1 است برای انتلال سفارش ها به شرکت تولیدکننده اسـتفادهمی کنند. مسئلة VRP نسـخه هـا ی متعـددی دارد. در ایـنتحلیق، حالتی از مسئلة VRP درنظر گرفته می شود کـه درآن تعدادی از تأمین کنندگان قرارگرفته در نلاط جغرافیایی متفاوت، متلاضی انتلال ملدارهای مشخصـی از کااهـا بـهیک کارخانه )انبار مرکزی( هستند. سـرو ی دهـی بـه ایـنتأمین کنندگان از طریق چند وسیلة نللیه بـا هرف یـت هـای
Email: [email protected]
حمش متفاوت صورت می پذیرد. هر وسیلة نللیه در یـک بـار حمش به چند تأمین کننده سروی مـی دهـد کـه ایـن امـرموجب کاهش هزینـه هـای حمـش ونلـش در زنجیـرة تـأمینمی شود.
با توجه بـه جدیـدبودن مسـئله و بررسـی نشـدن آن در ادبیات موضوع، یک مدل ریاضی عدد صحیح مختل بـرایمسئله توسعه داده شده است و یک الگـوریتم فـرا ابتکـاری به نام GA-SA که تلفیق جدیدی از الگـور یتم هـای ژنتیـک )GA(2 و ش بیه س ازی تبری د) SA(3 را درنظ ر م ی گی رد ،به منظور حش مسـئله ارائـه شـده اسـت. نـوآور ی هـای ایـنتحلیق به شرح زیر است:
ترکیب مسئلة زمان بندی تولید و حمـش ونلـش درحــالتی کــه تــأمین کننــدگان از یــک ناوگــانحمش ونلش مشتر مانند مسـئل ة VRP اسـتفادهمی کنند؛
توسعة مدل ریاضی برای مسئلة مذکور؛
ارائة یک الگوریتم فرا ابتکاری با تلفیق جدیدی از الگوریتم های ژنتیک و شبیه سازی تبرید.
درادامه، مرور ادبیات زمان بندی در زنجیرة تـأمین ارائـهمی شود. سس مسئله تشریح می شود و مدل ریاضـی عـددصحیح مخـتل مسـئله ارائـه مـی شـود . بعـد از آن ، چهـار الگوریتم فرا ابتکاری برای حش مسئله ارائه می شود و نتـا یج محاســباتی حاصــش از حــش مســائش مختلــف از طریــق الگوریتم های فرا ابتکـار ی بررسـی مـی شـود . درنهایـت نیـزنتیجه گیری و زمینه های تحلیلات آتی بیان می شود.
ادبیات موضوع
تاکنون تحلیلات مختلفی درمورد مسئلة زمان بنـ دی تولیـددر زنجیرة تأمین صورت گرفته است. در ایـن بخـش، مـرورادبیات زمان بندی تولید در زنجیرة تأمین ارائه می شود. لـیو ومــر 2[ مســئلة ترکیــب بنــدی زنجیــرة تــأمین را بــا درنظرگرفتن محدودیت منابع بررسی کرده اند. سـاویک 3[ یک مدل برنامه ریزی عدد صحیح مختل برای یک مسـئل ة زمان بندی مونتاژ در یک زنجیرة تأمین با افق برنامـه ریـزی بلندمــدت ارائــه داده اســت. ذگــردی و بهشــتی نیــا 4[ یکسارچگی زمان بندی تولید و حمـش ونلـش در یـک زنجیـرة دومرحله ای را بررسی کرده اند که تأمین کنندگان در نـواحیجغرافیایی از پیش تعیین شده ای قـرار دارنـد و فاصـلة بـینتأمین کنندگانی که در یک ناحیـ ة جغرافیـایی قـرار دارنـد،قابش چشم پوشی است. همچنین، وسایش نللیه ای که به یـکناحیة جغرافیایی تعلق دارند ،فل می تواننـد سـفارش هـا ی تخصیص یافته به تأمین کنندگان همان ناحیه را حمش کنند .
آورباخ 5[ زمان بندی بر خ در زنجیرة تـأمین متشـکش ازیک کارخانه و چند مشتری با هدک کمینـه سـازی مجمـوعوزنی جریان کاری سفارش ها را بررسی کرده است. اسـکولزریتر و همکاران 6[ یکسارچگی تولید و حمش ونلـش در یـکزنجیرة تأمین عمومی را بررسی کرده اند و یک مدل ریاضی به منظور حش مسئله ارائه داده اند. باتنگر و همکاران 7[ بـهبررسی برنامه ریزی حمش ونلش و زمان بندی در حالت وجـوددو نوع حمش ونلش هـوایی و دریـایی پرداختـه انـد. یونـگ وهمکاران 8[ زمان بندی در یک زنجیرة تأمین دومرحلـه ای را با درنظرگرفتن چندین پنجرة زمانی تحویـش مشـتر بـاهدک کمینه کردن هزینه های حمش ونلش و موجودی بررسی کرده اند. مهرآوران و لجنـدران 9[ زمـان بنـد ی در محـی جریان کاری را با زمان های آماده سازی وابسته به تـوالی بـادو تابع هدک کمینـه کـرد ن سـفارش هـا ی نیمـه سـاخته 4 و بیشینه کردن سطح سروی بررسی کرده اند. آن ها یک مدل ریاضی خطی و یک الگوریتم جست وجوی ممنوع برای حش مسئله ارائـه داده انـد. عثمـان و دمیرلـی 10[ زمـان بنـد ی تحویش و اندازة انباشتة اقتصادی در یک زنجیرة تأمین سـهمرحله ای و چندمحصولی را بررسی کرده اند. آن ها یک مدل جدید بر پایة مسئلة تخصیص مضـاعف بـرای مسـئله ارائـهداده اند که یک سیکش مشتر هماهنگی پر و تخلیـه شـدنانبارها را تعیـین مـی کنـد . آوربـاخ و بایسـان 11[ مسـئل ة زمان بندی بر خ 5 در یک زنجیرة تأمین دوسطحی با چنـدمشتری را بررسی کرده اند و یک الگوریتم تخمینی برای آن ارائه داده اند. در مسئلة آن ها، قطـع عملیـات مجـاز اسـت و تحویش سفارش ها به صـورت دسـته ای درنظـر گرفتـه شـدهاست. کابرا و همکاران 12[ زمان بنـد ی در زنجیـر ة تـأمینداروسازی را برای یک محی چندمرحله ای، چندمحصولی و چنددوره ای بررسی کرده اند. آن ها زمان بنـد ی را بـه صـورتپیوسته درنظر گرفته اند و یک مدل برنامه ریزی عدد صحیح مختل 6 برای آن ارائه داده اند .پژوهش آن ها توسعة تحلیـقشیا و فلویدز 13[ است که محدودیت های اضافی نظیـرتغییرات وابسـته بـه تـوالی7، زمـان هـا ی تحویـش چندگانـهمیانی8، تاریخ انلضا9 و محصوات معیوب، وجود هزینه هـای مربوط به دیرکرد در تحویش سـفارش هـا را بـه مـدل آن هـااضــافه کــرده انــد. آلــریچ 14[ یکســارچگی زمــان بنــدی ماشین آات و مسـیریابی وسـایش نللیـه را بـا درنظرگـرفتنپنجره های زمانی بررسی کـرده اسـت. تومـاس و همکـاران 15[ زمان بندی در زنجیرة تأمین زغـال سـنگ را بـا چنـدفعالیت مستلش که از طریق محدودیت های منابع با هـم درارتباط اند، بررسی کرده اند. سلوارجاه و ژانـگ 16[ درمـوردزمان بندی زنجیرة تأمینی پژوهش انجام داده انـد کـه در آنیک تولیدکننده مواد نیمه سـاخته را از تـأمین کننـدگان در زمان های متفاوت دریافت می کند و کااهای تکمیش شـده را به صورت دسته ای به مشتریان تحویش می دهد.

جدول 1. مقایسة تحقیق حاضر با تحقیقات صورت گرفته
36576-108326

ملاله سطح یکسارچگی درنظرگرفتن ناوگان حمش ونلشزماندارای افق زمانی
* * * Chang and Lee, 2004
* * * Li and Womer, 2008
* * * Sawik, 2009
* * * Averbakh, 2010
* * * Scholz-Reiter et al., 2010
* * * Zegordi and Beheshti Nia, 2009
* * * Archetti et al., 2011
* * * Yeung et al., 2011
* * * Mehravaran and Logendran, 2012
* * * and Osman, 2012 Demirli
* * * Averbakh and Baysan, 2013
* * * Kabra et al., 2013
* * * Shaik and Floudas, 2007
* * * Ullrich, 2013
* * * Thomas et al., 2014
* * * Selvarajah and Zhang, 2014
* * * تحلیق حاضر

تأمین سازنده کنندهتوزیع سازنده کنندهتمرکز ساخت رویترکیبیبله خیر تک پریودی زمان زمان
گسسته پیوسته
هرچند در تحلیلات متعـددی ، زمـان بنـد ی در زنجیـر ةتأمین بررسی شـده اسـت، بسـیاری از محللـان مسـئله رابه صورت کلان بررسی کرده انـد . از بـین تحلیلـات درمـورد
زمان بندی تولید و حمش ونلش و تخصیص سفارش ها در زنجیرة تأمین
مسئلة زمان بنـد ی در زنجیـر ة تـأمین ، پـژوهش ذگـردی وبهشتی نیا 4[ نزدیک ترین مسئله به موضوع مـورد بررسـیدر این پژوهش است. در تحلیـق آن هـا فـرض شـده اسـتتأمین کنندگان در نواحی جغرافیایی از پیش تعیین شـده ای قرار دارند و فاصلة بین تأمین کننـدگان قرارگرفتـه در یـکناحیة جغرافیایی قابش چشم پوشی اسـت. همچنـین، وسـایشنللیه ای که به یـک ناحیـة جغرافیـایی تعلـق دارنـد، فلـ می توانند سفارش های تخصـ یص یافتـه بـه تـأمین کننـدگان همان ناحیـه را حمـش کننـد؛ بـه عبـارت دیگـر، محاسـباتحمش ونلش بین هیچ یک از تأمین کنندگان صورت نمی پذیرد، اما در این تحلیق فرض می شود فاصلة بین تأمین کننـدگان قابش چشم پوشی نیست. تأمین کنندگان در نواحی جغرافیایی مختلف قرار دارند و همچنین وسایش نللیه مجـاز بـه حمـشسفارش ها از تأمین کنندگان در نواحی جغرافیـایی مختلـفدر یک محموله هستند. در جدول 1، تحلیلـات موجـود درادبیات موضوع دسته بندی و ملایسه شده است.
تعریف مسئله
در این بخش، مسئله تعریف و فرضیات آن بیـان مـی شـود.
همچنین، درادامه مدل ریاضی مسئله ارائه می شود.
فرضیات مسئله
همان طورکه بیان شـد ، ایـن پـژوهش زمـان بنـد ی تولیـد و حمش ونلش در یک زنجیـر ة تـأمین دو مرحلـه ای را بررسـیمی کند. مرحلـ ة اول شـامش تـأمین کننـدگان و مرحلـ ة دوم شامش ناوگان حمش ونلـش کااهـا بـه یـک شـرکت سـازندة محصوات نهایی است. سایر فرضیات مسئله به صـورت زیـراست:
تعداد n سـفارش وجـود دارد کـه پـ از پـردازش از طریق m تأمین کنندة مختلف که در نواحی جغرافیایی جداگانــه قــرار دارنــد، بایــد از طریــق یــک ناوگــان حمش ونلش متشکش از تعداد l وسیلة نللیـه بـه سـمتشرکت سازندة محصوات نهایی انتلال داده شوند.
ممکن است برخی از تأمین کنندگان بـه علـت داشـتن تجهیزات و ماشین آات بیشتر، سرعت تولیـد بـااترینسبت به سایر تأمین کنندگان داشته باشـند و مـواد واقلام مورد نیاز کارخانة سازنده را سریع تر تولید کننـدکه این سرعت برحسب ماشین- ساعت بر زمـان بیـانمی شود.
وسایش نللیة تشـک یش دهنـدة ناوگـان حمـش ونلـش نیـزممکن است سرعت حمش متفاوتی داشـته باشـند کـهاین سرعت در کش مسیر ثابت فرض می شود.

شکل 1. ساختار زنجیرة تأمین
سرعت حمش و هرفیت حمش بـرای هـر وسـیلة نللیـهممکن است متفاوت باشد. هرفیت حمش یـک وسـیلة نللیه میزان حجم یا وزنی از کااها تعریف می شود که وسیلة نللیه هر بار حمش می کند.
تأمین کنندگان در مختصات مختلف جغرافیـایی قـراردارند.
فاصلة بین تأمین کنندگان قابش چشـم پوشـ ی نیسـت و هریک از آن ها در فواصش متفـاوتی از شـرکت سـازندهقرار دارند.
هریک از سفارش ها هرفیت متفاوتی از وسایش نللیه را اشغال می کند.
به مجموعة سـفارش هـا یی کـه یـک وسـیلة نللیـه دریک بار حمش به شرکت سازنده انتلـال مـی دهـد یـکمحموله گفته می شود. در این حالت، وسیلة نللیه باید برای حمش محمولـ ة بعـدی بـه سـمت تـأمین کننـد ة موردنظر برود و استفاده شود؛ بنابراین، در زمان بنـد ی باید به زمان برگشت نیز توجه شود.
ه ر وس یلة نللی ه در ی ک محمول ة خ ود م ی توان د سفارش های تأمین کنندگان مختلفی را حمش کند.
زمان تکمیش هـر سـفارش زمـانی اسـت کـه سـفارشمربوطه به شرکت سازنده تحویش داده می شود.

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

زمان بندی تولید و حمش ونلش و تخصیص سفارش ها در زنجیرة تأمین
شکش 1 نمایی از مسئلة مورد بررسی در این تحلیـق رابا 6 سفارش و 4 تأمین کننده نشان می دهد کـه سـفارش 6 به تأمین کنندة 1، سفارش های 2 و 3 بـه تـأمین کننـدة 2، س فارش 1 ب ه ت أمین کنن دة 3 و س فارش ه ای 4 و 5 ب ه تـ أمین کننـ دة 4 اختصـ اص یافتـ ه انـ د. در شـ کش a-1 تأمین کنندگان بـه طـور مسـتلش سـفارش هـا ی خـود را بـهشرکت سازنده منتلش می کنند. شکش b-1 حـالتی را نشـانمی دهد که تأمین کنندگان از ناوگان حمـش ونلـش مشـترکیبرای رساندن سفارش های خود به شرکت سـازنده اسـتفادهمی کنند. نوع همکاری تأمین کنندگان در استفاده از ناوگـانحمش ونلش مشتر ، VRP است.
مدل ریاضی مسئله
در این بخش مدل ریاضی عدد صحیح مختل مسـئل ة مـورد نظر بیان می شود. قبش از ارائة مـدل ریاضـی مسـئله ، ابتـدا نمادهای مورد استفاده معرفی می شوند. پارامترهای مسـئلهعبارت اند از:
:n تعداد سفارش ها
:m تعداد تأمین کنندگان l: تعداد وسایش نللیه w,i: شاخص سفارش (w,i=1,…,n) s: شاخص تأمین کنندگان (s=1,…,m) k: شاخص وسیلة نللیه (k=1,…,l) b: شاخص محموله (b=1,…,n) voli: هرفیت اشغالی توس سفارش i ام
capk: هرفیت حمش وسیلة نللیـ ة k ام برحسـب تعـدادسفارش ها Pis: زمان پردازش سفارش i ام در تأمین کنندة s ام
0ttks: زمان حمـش ونلـش از تـأمین کننـدة s تـا شـرکتسازنده توس وسیلة نللیه k ام
ttk0 s: زمان حمش ونلش از شرکت سازنده تا تأمین کننده s توس وسیلة نللیه k ام
tt
kss: زمان حمش ونلش از تأمین کننده s به تأمین کننده
/s توس وسیلة نللیه k ام Q: یک عدد بسیار بزرگ متغیرهای مدل نیز شامش موارد زیر است:
cji: زمان تکمیش سفارش i در مرحلة j که 2،1j=
ci : زمان بارگذاری سـفارشi ام روی یکـی از وسـایشنللیه به منظور حمش
avkbi: زمانی که وسیلة نللیه k ام، آماده حمش سفارش i در b امین مأموریت خود است.
Finkb: زمانی کـه وسـیلة نللیـهk ام تمـام سـفارش هـاتخصیص یافته به محموله b ام خود را تحویش می دهد.
Readykb: زمانی که وسیلة نللیه k ام، آمادة انجـام دادن مأموریت b ام خود است.
Xsi: اگر سفارش i ام به تأمین کنندة s ام داده شود برابر یک و در غیر ا ینصورت برابر صفر است.
Yiw: اگر در مرحلة اول سفارش i قبش از سفارش w قرار گیرد برابر یک و در غیر ا ینصورت برابر صفر است.
Zkib: اگر سفارش i در b امین حمش به وسـ یلة نللیـهk تخصیص یابد برابر یک و در غیر این صورت برابر صفر است.
Visit kibs: یک متغیر کمکی است. اگر وسـ یلة نللیـ ة k ام در محمولة b ام خود، سـفارشi ام را از تـأم ین کننـده s بارگذاری کند برابر 1 و در غیر این صورت برابر صفر است.
r0kbs: اگر وسیلة نللیة k ام در مأموریـت b ام خـود ازکارخانه به سـمت تـأمین کننـدة s بـرود برابـر 1 و در غیـراین صورت برابر صفر است.
rkbsst: اگر وسیلة نللیة k ام در محمولة b ام خود بـرایبار t ام از تأمین کنندة /s به سمت تأمین کنندة s برود برابـر1 و در غیر ا ینصورت برابر صفر است.
0rkbs: اگر وسیلة نللیة k ام در مأموریـت b ام خـود ازتأمین کنندة s بـه سـمت کارخانـه بـرود برابـر 1 و در غیـراین صورت برابر صفر است.
پ از تعری ف پارامتره ا و متغیره ای مس ئله، م دل برنامه ریزی عدد صحیح مختل برای مسئله به صـورت زیـرارائه می شود:

St:

∀???? )1(
-2203703-303400

-2203703336045

(
∀???? )15(
∀????

(

(
∀????, ????
∀???? )5(
???? < ????
????∀≥????, ???????? )6(
∀????
∀???? ∀???? )7(
∀????
∀????
∀???? )8(
∀????
∀????
∀???? )9(
∀????
∀???? )10(
∀????
∀???? )11(
∀???? ∀????, ???? )12(
∀???? ∀???? ∀???? )13(
∀????
∀????
∀???? )14(
∀????
∀????
????1???? ≥ ???????????? − ????(1 − ????????????)
????1???? + ????∗(2 + ???????????? − ???????????? − ????????????)
≥ ????1???? + ????????????
????1???? + ????∗(3 − ???????????? − ???????????? − ????????????)
≥ ????1???? + ????????????

????????
????0???????????? + ∑ ????????????????ˊ,???? ≥ 1\????∗ ∑ ????????????????????????????????????
????ˊ=1????=1
∀????
∀????)16(
< ???? − 1
∀???? ∀∀???????? )17(
∀???? ∀???? )18(
∀????, ????
???? > ???? ∀???? )19(
∀????, ????ˊ
∀????
????∀????>, ???????? )20(
∀k ∀???? )21(
∀????
∀????
∀????)22(
< ???? − 1
∀????
∀∀???????? )23(
∀b
∀????
∀????, ????ˊ )24( ∀????
∀????, ????
∀???? )25(
∀????, ????ˊ
|???? ≠ ????ˊ

????????ˊ ≥ ???????????????????? − ????∗(1 − ????????????????)
????????ˊ ≥ ????1????
???????????????????? ≥ ????????ˊ + ????????????????ˊ???? − ????∗(5 + ????????????ˊ
− ???????????????? − ???????????????? − ????????????ˊ
− ???????????? − ????????????????ˊ,????)
???????????????????? ≥ ????????ˊ + ????????????????????ˊ − ????∗(6 − ????????????ˊ
− ???????????????? − ???????????????? − ????????????ˊ
− ???????????? − ????????????????,????ˊ)
????????????ˊ= 1 − ????????????ˊ
???????????????????? ≥ ???????????????????????????? + ????????????????0 − ????∗(1
− ????????????????0 )
????????????????????????(????+1) ≥ ????????????????????
???????????????????????????? ≥ ????????ˊ − ????∗(2 − ???????????????? − ????????????)
???????????????????????????? ≥ ????????????????????????????ˊ + ????????????????ˊ???? − ????∗(1
???? − ∑ ????????????????ˊ,????)
????=1
????????????????,????ˊ ≥ ???????????????? + ???????????????? + ???????????? + ????????????ˊ + ????????????
− 4)
37186-256743
3072892-108206) نللی ه در
مجموعة محدودیت 1 بیانگر این مطلـب اسـت کـه هـرسفارش فل باید به یک تأمین کننده تخصـیص داده شـود.
مجموعة محدودیت 2 بیان می کند هر سفارش فل به یک وسیلة نللیه و به یـک محمولـه از آن بایـد تخصـیص یابـد.مجموعة محـدودیت 3 تضـم ین مـ ی کنـد در هـر محمولـهمجموع فضای اشغالی توس سفارش های تخصیص یافته بـهیک وسیلة نللیه نباید از هرفیـت آن وسـیلة نللیـه بیشـترشود. مجموعة محدودیت 4 زمـان تکمیـش هـر سـفارش درمرحلة تأمین کنندگان را با توجه به زمان آمادگی سفارش ها درنظر می گیرد. مجموعة محـدودیت 5 بیـان مـ ی کنـد هـرتأمین کننده نمی تواند در هر لحظه بیش از یـک سـفارش راپردازش کند. مجموعة محدودیت 6 ملـدار ی از متغیرهـایزائد را حذک می کند. مجموعة محدودیت 7 تضمین می کند تعداد دفعات ورود به تأمین کنندة s باید برابر تعداد دفعـاتخروا از آن باشد. مجموعة محدودیت 8 تضـم ین مـ ی کنـد ماشین k ام برای محمولة b ام خود بیش از یـک بـار از هـرتأمین کننده عبـور نکنـد. مجموعـة محـدودیت 9 برخـ ی از متغیرهای زائد مسئله را حذک می کند. مجموعة محدودیت 10 بیان می کند وسـ یلة نللیـ ة k ام در محمولـ ة b ام خـودنم ی توان د ب ه ط ور مس تلیم از کارخان ه ب ه دو ی ا چن دتأمین کننده برود. مجموعـ ة محـدودیت 11 بیـان مـ ی کنـد ماشین k ام برای حمش محمولة b ام فل زمانی می تواند از مبدأ خارا شـود کـه قـرار باشـد سفارشـی را حمـش کنـد.
مجموعة محدودیت 12 تعیین می کند که وسیلة نللیة k ام در محمولــة b ام خــود ســفارشi را از تــأمین کننــدة s بارگذاری کند یا خیر. این امر به کمک تعریـف یـک متغیـرکمکی به نام Visit kibs صورت می پذیرد. همچنین، مجموعـ ة محدودیت 13 بیان می کند وسیلة نللیة k در محمولـ ة b ام خود فل زمانی می تواند به طور مستلیم از کارخانه به یـکتأمین کننده وارد شود یا از یک تأمین کننده به کارخانه وارد شود که قرار باشد سفارشی از آن تأمین کننده را بارگـذاریکنـــد. مجموعـــة محـــدودیت 14 تضـــمین مـــی کنـــد تأمین کنندگانی که براساس متغیـر Visitkibs بایـد توسـ وسیلة نللیـ ة k ام در محمولـ ة b ام خـود بازدیـد شـوند، ازمأموریت b ام خود، حتماً باید از کارخانه خارا شود و حتماً باید از یک تأمین کننـده بـه کارخانـه وارد شـود. مجموعـة محدودیت 16 تضمین می کند اگر به محمولة b ام از وسیلة نللیة k ام سفارشی تخصیص نیابد، نمـ ی تـوان بـه محمولـة 1+b ام آن سفارشی تخصیص داد. مجموعة محـدودیت 17 بین زمان بارگیری هر سفارش با زمـان آمـاده بـودن وسـیلة نللیه ای که باید آن را از تأمین کنندة مربوطـه حمـش کنـد،رابطه برقرار می کنـد . مجموعـ ة محـدودیت 18 بـ ین زمـانبارگذاری هر سفارش با زمان تکمیلش در مرحلة اول رابطه برقرار می کند. مجموعـ ة محـدودیت 19 زمـان آمـاده بـودنوس یلة نللی ة k ام در محمول ة b ام ب رای بارگ ذاری ه ر سفارش، خود را با زمان بارگیری سفارش هـا دیگـر مـرتب م ی کن د. مجموع ة مح دودیت 20 ارتب اط اولوی ت حم ش سفارش ها با یکدیگر را تعیین می کند. مجموعة محـدودیت21 بین زمان اتمام مأموریت b ام وسیلة نللیة k ام و زمانی که این وسیلة نللیه در مأموریت b ام خود از تأمین کنندة s خارا می شود رابطه برقرار می کند. مجموعة محـدودیت 22 بین زمان اتمام مأموریت b ام وسیلة نللیة k ام و زمان آغاز مأموریــت 1+b ام آن رابطــه برقــرار مــ ی کنــد. مجموعــة محدودیت 23 زمانی را که وسیلة نللیة k ام در مأموریـت b ام از ت أمین کنن دة s خ ارا م ی ش ود ب ا زم ان بارگ ذاری سفارش های متعلق به آن محموله مرتب می سازد. مجموعة محــدودیت 24 زمــان هــای خــروا وســ یلة نللیــة k ام از تأمین کننـدگان مختلـف مـرتب بـا محمولـة b ام خـود رانسبت به یکدیگر درنظر می گیرد. مجموعة محـدود یت هـای 25 لزوم پیمایش مسیر بین دو تأمین کننده را توس وسیلة نللیة k ام در مأموریت b ام آن تعیـین مـی کنـد . مجموعـ ة محدودیت 26 رابطة بین زمان تحویش سفارش i به شـرکتسازنده و زمان اتمـام مأمور یـت وسـ یلة نللیـه ای کـه آن راحمش می کند، درنظر می گیرد.
ارائة روش حل
همان طورکه ذکر شد، بـه دلیـش سـاختارNP-hard مسـئله،استفاده از روش های دقیق به منظـور حـش مسـئله در زمـانقابش قبول معلول نیست و باید از روش های ابتکـاری یـا فـراابتکاری برای یافتن جواب در زمان معلول استفاده کـرد. دراین پژوهش، یک الگویتم فرا ابتکاری که تلفیق جدیـدی از الگوریتم های SA و GA را درنظر می گیـرد بـه منظـور حـشمسئله ارائه می شود که الگوریتم GA-SA نامیده مـی شـود .
به منظور بررسی کارایی آن، الگوریتم پیشـنهادی ذگـردی وبهشتی نیا 4[ به نام DGA به همـراه الگـور یتم هـای GA و SA ب رای ح ش مس ئله توس عه داده م ی ش ود و عملک رد الگوریتم پیشنهادی با آن ها ملایسه می شود. به منظور تبیین الگوریتم پیشنهادی، ابتدا هریک از الگوریتم های GA و SA به طـور مختصـر شـرح داده مـی شـود و درادامـه الگـوریتمپیشنهادی تشریح می شود.
الگوریتم ژنتیک
الگوریتم ژنتیک یکی از انواع الگوریتم های جست وجو اسـتکه براساس تکنیک های زیست شناسی مانند وراثت و جهش عمش می کند. جان هالنـد ایـن الگـوریتم را در سـال 1970 ارائه داده است [17]. درادامـه، گـام هـا ی الگـوریتم ژنتیـکمورد استفاده در این مسئله- پ از ایجاد جمعیت اولیه که به صورت تصادفی ایجاد می شود- بیان می شود:
از جمعیت فعلی دو کروموزوم به تصـادک انتخـابکنیــد و از طریــق عمــش تلفیــق کرومــوزوم یــا کروموزوم های فرزند را تولید کنید.
از جمعیت فعلی یک کرومـوزوم تصـادفی انتخـابکنید و از طریق عمش جهش، کرومـوزوم جدیـد راتولید کنید.
با اسـتفاده از عملگـر انتخـاب تعـدادی از اعضـایجمعیت را انتخاب کنید و به نسـش بعـدی انتلـالدهید.
اگر شرط خاتمـه محلـق نشـده اسـت، بـه گـام 1 بازگردید، در غیر این صورت به گام 5 بروید.
بهترین عضو جمعیت فعلی را برای جواب الگوریتم معرفی کنید.
الگوریتم شبیه سازی تبرید
شبیه سازی تبرید یک روش جست وجوی تصادفی است کـه
برای مسائش بهینه سازی به کار می رود. الگوریتم شبیه سـازی تبرید از فرایند سردشدن تدریجی فلزات الهام گرفتـه شـدهاست. فرایند سردسازی تدریجی را آنیش10 کردن می گوینـد .
تبرید یک فرایند برای بهبود خواص کیفی کریسـتال جامـداست. سردسازی بسیار کنـد و تـدریجی موجـب آزادسـازی انرژی و قرارگیری ذرات در یک جهت با بیشـترین پایـداریمــی شــود. در ســال 1983، کریــک پاتریــک و همکــاران شــبیه ســازی فراینــد آنیــش کــردن را بــرای حــش مســائشبهینه سازی ترکیبی پیشنهاد کردند [18]. گام های الگوریتم شبیه سازی تبرید توسعه دادهشده برای مسئله به صورت زیر است:
ی ک دم ای اولی ه ب رای مس ئله درنظ ر بگیری د .
همچنین، یک جـواب اولیـه بـه صـورت تصـادفیتولید کنیـد و ملـدار تـابع هـدک آن را محاسـبهکنید.
گام های زیر را u بار در دمای فعلی تکرار کنید.
تعداد k تا همسایگی برای جواب تولید کنید و در بین همسایگی ها بهترین را انتخاب کنید.
بهترین همسایگی را با جواب اولیه ملایسه کنیـد.
درصورت برتری بهترین همسایگی نسبت بـه جـواب اولیـه، آن را با جواب اولیه جایگزین کنید و در غیر این صورت یک عدد تصادفی بین صفر و یک تولید کنید. درصورتی که عـددتصادفی تولیدشده از ملدار تابع احتمال پذیرش جواب هـا ی بد کمتر بود، بهترین همسایگی را جایگزین کنیـد. در غیـراین صورت، تغییری در جواب فعلی ندهید.
با اسـتفاده از تـابع کـاهش دمـا، دمـای فعلـی راکاهش دهید و جایگزین دمای فعلی کنید.
معی ار خاتم ه را بررس ی کنی د و درص ورت ب ه اتمامنرسیدن به گام 2 بروید در غیـر ایـن صـورتالگوریتم را خاتمه دهید.
الگوریتم GA-SA
همان طورکه اشـاره شـد، الگـوریتم پیشـنهادی بـرای حـشمس ئله ی ک الگ وریتم ف را ابتک اری اس ت ک ه ترکیب ی از الگ وریتم ه ای SA و GA اس ت. نح وة عملک رد الگ وریتم تلفیلی بدین صورت است کـه ابتـدا الگـوریتم ژنتیـک اجـرامی شود و درصـورت بهبودنیـافتن بهتـرین جـواب طـی n1 تکرار متوالی ،الگوریتم SA فعال مـ ی شـود. در ایـن حالـت،
بهترین جواب نسش فعلی GA بهعنوان جواب اولیة الگوریتم SA درنظر گرفته می شود و الگوریتم SA مطابق با گام هـا ی ذکرشده روی آن اجـرا مـ ی شـود . درصـورت بهبـود جـوابتوس SA، جواب بهبودیافته بـه نسـش فعلـی GA منتلـشمی شود و فرایند حش الگوریتم GA ادامه می یابد. درصـورتبهبودنی افتن ج واب توس SA، الگ وریتم GA ب ا هم ان جمعیت قبلی ادامه می یابد. به منظور تبیین بیشتر، گام های الگوریتم پیشنهادی در زیر بیان شده است:
جمعی ت اولی ه ای از کروم وزوم ه ا را ب ه ص ورت تصادفی ایجاد کنید.
الگوریتم ژنتیک با گـام هـا ی گفتـه شـده را اجـراکنید.
اگر در 1n تکرار متوالی در بهترین جواب، بهبودی حاصش نشد، الگوریتم SA را اجرا کنید و بهتـرینجواب حاصش از GA را جواب اولیة الگـوریتمSA درنظر بگیرید.
الگوریتم SA را طبـق گـام هـا ی بیـان شـده اجـراکنید.
اگر 2n2>n1) n) تکرار متوالی است که در بهتـرین

سفارش
1



قیمت: تومان


دیدگاهتان را بنویسید