International Journal of Industrial Engineering & Production Management (2013)

-144144-24523

May 2013, Volume 24, Number 1
pp. 1-11

http://IJIEPM.iust.ac.ir/

An Efficient Hybrid Algorithm for Solving Multi Objective
Linear Programming Model for Single Machine Problems

Y. Zare Mehrjerdi*, S. Fereidouni & L. Emami Maibodi

Yahia Zare Mehrjerdi, Associate Professor, Department of Industrial Engineering, Yazd University, Yazd Iran,
Sepideh Fereidouni, Master Students, Department of Industrial Engineering, Yazd University, Yazd Iran, [email protected]
Leila Emami Maibodi, Master Students, Department of Industrial Engineering, Yazd University, Yazd Iran, [email protected]

Keywords 1ABSTRACT

1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

Sequence of Single Machine
Operation,
Multi Objective Programming,
Lateness,
Weighted Tardiness,
Meta- Heuristic Due to the fact that the determination of an efficient scheduling solution in the sequence of single machine operation for multiple objective programming is important, especially in production planning, we are considering a single machine sequencing problem with minimizing the number of the tasks with lateness and weighted tardiness. In this article, the application of new optimization methods in sequencing problem and scheduling are in order. We propose the mathematical model for the problem under consideration first and then by introducing simulated annealing and genetic algorithm, as solution approaches, we test their efficiency for solving the proposed problem. At the end, to increase the efficiency of the proposed model a hybrid/meta-heuristic algorithm based upon the genetic algorithm is proposed. This method identifies a collection of efficient sequencing tools for objectives minimization.

© 2013 IUST Publication, IJIEPM. Vol. 24, No. 1, All Rights Reserved

*
Corresponding author. Yahia Zare Mehrjerdi Email: [email protected]

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

یحیی زارع مهرجردی*، سپیده فریدونی و لیلی امامی میبدی

کلمات کلیدی چکیده:
-137152266

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

-1371559820

9. مقدمه9
تعیین توالی و زمانبندی در سیستمهای پیشرفته تولیدی از اهمیت ویژهای برخوردار است. اقتصادی بودن این سیستمها مشروط به داشتن یک برنامه تعیین توالی و زمانبندی مناسب میباشد. در واقع زمانبندی نوعی فعالیت تصمیمگیری است که با هدف بهینهسازی یک و یا چند هدف انجام میگیرد. درحالیکه ،توالی در مورد ترتیب ورود کارها در سیستم مورد استفاده قرار
تاریخ وصول: 91/6/19 تاریخ تصویب: 39/5/19
*نویسنده مسئول مقاله: دکتر یحیی زارع مهرجردی، استادیار دانشکده
مهندسی صنایع، دانشگاه یزد، [email protected]
سپیده فریدونی، دانشجوی دوره کارشناسی ارشد، دانشکده مهندسی صنایع،
[email protected] ،دانشگاه یزد
لیلی امامی میبدی، دانشجوی دوره کارشناسی ارشد، دانشکده مهندسی
[email protected] ،صنایع، دانشگاه یزد
1268732040127Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

1268732040127Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

میگیرد. مشکلات تعیین توالی و زمانبندی قطعات در محیطهای مختلف صنعتی یکسان نیست. چنانچه عمل کردن به قراردادها در موعد تحویل موردنظر باشد، باید کمینه کردن تعداد قطعات دیرکرددار یا کمینه کردن متوسط دیرکرد، موردتوجه قرار گیرد ]2،2[. مطالعه جریمههای دیرکرد در مدل برنامهریزی زمانبندی به عنوان یک زمینه تحقیقاتی جدید مطرح شده است. قبل از آن ،سالها تحقیقات موضوع زمانبندی تنها بر روی یک شاخص اندازهگیری باقاعده متمرکز بود]3[. در این مطالعه، بادرنظر گرفتن مطلب فوق و اهمیت مسایل برنامهریزی زمانبندی از مدل برنامهریزی خطی چندهدفه، جهت حداقل کردن مجموع دیرکرد وزنی و تعداد کارهای دارای تاخیر در مسائل زمانبندی تک ماشین استفاده شده است. در این مقاله، ابتدا به بیان تاریخچه مسئله و جمعبندی از تحقیقات و مطالعات انجام شده پرداخته شده است. مشخص کردن اطلاعات ورودی، خروجی و تابع هدف در قسمت سوم مورد توجه قرار میگیرد. در ادامه، به معرفی الگوریتمهای ژنتیک، شبیهسازی آنیلینگ و روش پیادهسازی آنها برای حل مسأله پرداخته و نتایج حاصل از اجرای این الگوریتمها روی مثال نمونه مورد بررسی و تحلیل واقع میشود. لازم بذکر است که الگوریتمها در محیط MTLAB R2009a در کامپیوتر شخصی با ،2.66GHz کدنویسی و آزموده شد.

9-9. طرح مساله
مساله توالی عملیات و ترتیب چیدن کارها درحالت تک ماشین بهمنظور کمینه کردن تعداد کارهای دارای تاخیر و دیرکرد وزنی از مهمترین مسایل زمانبندی کارها است. این دومعیار دارای اهمیت زیادی ازنظر تولیدکنندگان و مشتریان است .در دنیای واقعی تعداد کارهای دارای تاخیر، معیاری است که به عنوان نرخ عملکرد مدیران مورد توجه قرار میگیرد و مجموع دیرکرد وزنی به علت اینکه، هزینههایی که در اثر دیرکرد به سیستم تحمیل میگردند را اندازهگیری میکند، نسبت به توابع دیگر همچون مجموع وزنی زمانهای تکمیل حالت عمومیتری دارد و بیشتر مورد استفاده قرار میگیرند .از سوی دیگر، در مسائل واقعی معمولاًمعمولا به جای درگیر شدن با یکی از معیارها با هردوی آنها سروکار داریم. از اینرو در این مطالعه سعی خواهد شد که از تصمیمگیری دو هدفه استفاده شود. درچنین حالتی امکان ارائه توالی که هر دو پارامتر را بهینه نماید، مگر در مواقع خاص ،ناممکن است .لذا سعی میشود توالیهای کارا برای مساله تعیین گردد .

6. ادبیات و پیشینه موضوع
زمانبندی شامل برنامهریزی و مرتب کردن کارها در یک توالی از کارها به منظور برآورده کردن نیازهای مشتریان است[4]. محیط تک ماشین خیلی ساده و نیز حالت خاصی از سایر مدلها همچون ماشینهای موازی و سری هستند. در این مدل، تنها از یک ماشین برای فرآیند بهینه تمام کارها و اندازهگیری عملکرد سیستم همچون زمان تکمیل، تاخیر، تعداد کارهای دارای تاخیر ،زمان بیکاری، ماکزیمم زودکرد و دیرکرد و سایر معیارها استفاده میشود]4[.
اغلب محققین در مسائل تک ماشین حداقل کردن یکی از معیارهای گفته شده را مورد بررسی قرار دادهاند. با این وجود مسایل زمانبندی اغلب شامل بیش از یک معیار هستند، بنابراین به تحلیلهای چندهدفه نیاز خواهد بود . Nelson et al (1986)]5[ و Emmons (1975)]6[ مسائل با میانگین زمان در جریان ساخت و تعداد کارهای دارای تاخیر را مورد بررسی قرار دادند .
Emmons (1975)، یک الگوریتم شاخه و حد را برای حداقل کردن میانگین زمان درجریان ساخت وقتی حداقل کارهای دارای تاخیر با استفاده از الگوریتم Moore تعیین شده باشد، ارائه داد .
در مطالعهای که Nelson et al انجام دادند، مقدار حداقل تعداد کارهای دارای تاخیر برای محدوده مشخص شده با استفاده از قاعده کوتاهترین زمان پردازش ،2(SPT)، و الگوریتم Moore (6891) تعیین شدند. آنها نوع دیگری از الگوریتم Emmons را برای توسعه روشی جهت تولید همه جوابهای بهینه پاراتو فراتر از محدوده مشخصی مورد استفاده قرار دادند.Azizoglu et al (3002) ]7[ مساله زمانبندی دوهدفه حداقل کردن حداکثر زودکرد و تعداد کارهای دارای تاخیر را بر روی یک ماشین مورد مطالعه قرار دادند. آنها فرض کردند زمان بیکاری مجاز نمیباشد .ابتدا، مساله حداقل کردن حداکثر زودکرد را درحالیکه تعداد کارهای دارای تاخیر در حداقل مقدار خود بودند، آزمودند.
Eren & Guner (2006) ]8[ مساله تک ماشین دو معیاره با زمانهای آمادهسازی وابسته به ترتیب را مطالعه کردند. تابع هدف مورد بررسی کمینه کردن مجموع وزنی زمانهای تکمیل و دیرکرد بود. مساله با استفاده از رنامهریزی عدد صحیح مدل شد .مساله موردنظر NP-Hard بود. به همین دلیل برای حل مسایل با کارهای زیاد، از روشهای هیوریستیک استفاده گردید .
Tavakkoli-Moghaddam et al (2006) ]9[ رویکرد برنامه-ریزی آرمانی فازی را برای حل مدل برنامهریزی مختلط عدد صحیح مسائل تک ماشین با اهداف حداقل کردن زمان درجریان ساخت موزون و مجموع دیرکرد وزنی ارائه دادند. بهعلت تناقض میان اهداف، آنها رویکرد برنامهریزی آرمانی فازی را برای مدل ریاضی توسعه داده شده پیشنهاد دادند. این رویکرد برپایه درجه
تمایل تصمیمگیرنده 2(DM) استوار بود .Chen & Sheen (7002)]21[، مساله تک ماشین را با هدف حداقل کردن مجموع زودکرد و دیرکرد وزنی، در رابطه با تعداد کارهای دارای تاخیر مورد بررسی قرار دادند. آنها n کار با موعدهای تحویل مشترک و وزنهای متفاوت را برای زودکرد و دیرکرد درنظر گرفتند و یک الگوریتم بهینه پارتو پیشنهاد دادند .Huo et al (7002)]22[ مساله زمانبندی تک ماشین با دومعیار حداکثر دیرکرد وزنی و تعداد کارهای دارای تاحیر را مورد مطالعه قرار دادند. آنها اثباتهای شدیداً NP-Hard برای مسایل زمانبندی هرگاه یکی از این دو معیار، ضابطه اصلی و دیگری معیار فرعی باشد، ارائه دادند .Keha, et al (2009) ]22[ در مقالهای، کارایی
محاسباتی چهار برنامهریزی عدد صحیح مختلط مختلف،

1 Shortest Processing Time
2. Decision maker
4
2(MIP)، را در مسائل گوناگون زمانبندی تک ماشین مورد مطالعه قرار دادند. نتایج حاصل از الگوریتمها نشان داد، فرمولبندی MIP برای مسائل چندمعیاره کارایی بیشتری دارد. همچنین نتایج نشان داد برنامهریزی عدد صحیح برای مسائل خاص بیشتر از مسائل عمومی مورد استفاده قرار گرفته و درعمل دارای کارایی بیشتری است. علاوه براین، آنها دو مجموعه از نامعادلات را که میتوانند برای بهبود فرمولبندی مورد استفاده قرار بگیرند، ارائه دادند.
لازم بذکر است که، قواعد گوناگونی برای توالی بهینه مدلهای تک معیاره با اهداف متمایز وجود دارد )به عنوان نمونه، برای سادهترین مدل مسائل تک ماشین بدون هیچ محدودیتی، قاعده کوتاهترین زمان فرآیند 2(SPT) برای حداقل کردن میانگین زمان درجریان ساخت، توالی بهینه را میدهد، درحالیکه قاعده زودترین موعد تحویل (EDD) ترتیب بهینه را برای حداقل کردن ماکریمم تاخیر ،Tmax، بدست میدهد(. در حقیقت، هر تصمیمگیرنده براساس معیاری که درنظر دارد روشی متفاوت اتخاذ میکند. به-علاوه، هریک از این اهداف از دیدگاههای گوناگون با اهمیت هستند. باید توجه داشت که گاه این اهداف متضاد یکدیگر بوده و جواب مناسب برای یک هدف ممکن است برای هدف دیگر مناب نباشد، ازاینرو، مسایل زمانبندی اغلب دارای طبیعت چندهدفه هستند]4[.
هدف ازاین مقاله، توسعه یک مدل برنامهریزی خطی چندهدفه،3(MOLP)، بهمنظور حداقل کردن مجموع دیرکرد وزنی و تعداد کارهای دارای تاخیر، برای حل مسائل تک ماشین است .در ادامه از روشهای ابتکاری جهت حل مدل پیشنهادی بهره گرفته شد.

3. مدل ریاضی پیشنهادی
مسایل زمانبندی مدلهای تک ماشین به لحاظ تنوع محدودیت-ها و توابع هدف دارای پیچیدگیهایی است که بعضاً حل آنها با روشهای بهینهسازی معمول امکانپذیر نیست و یا مستلزم صرف وقت و هزینه بسیار است. در چند دهه اخیر گرایش محققان به روشهای فراکاوشی بیشتر گشته است. این روشها اغلب الهام گرفته از طبیعت هستند که برای حل مسائل در زمینههای مختلف از دهه 2961 مورد توجه قرار گرفتند، بهگونه-ای که جوابهای قابل قبول )نزدیک به بهینه( را با یک هزینه محاسباتی معقول جستجو میکنند، بیآنکه قادر به تضمین بهینگی مطلق جواب باشد]23[. در این قسمت ابتدا به بیان تعاریف و نمادها پرداخته و سپس روشهای الگوریتم ژنتیک

1 . Mixed Integer Programming
32 . . Multi Objective Linear Programming the shortest processing time
)GA(4 و شبیهسازی آنیلینگ (SA)5به عنوان روش کاوشی معرفی میشوند.

9-3. تعاریف و نمادها
به منظور شرح مدل ،n را تعداد کار بدون انقطاع روی یک ماشین درنظر بگیرید. کار j بوسیله زمان عملیات، زمان تحویل و یک واحد جریمه دیرکرد تعریف میشود. فرضیات و نمادهای بکارگرفته شده در این مطالعه به صورت زیر است:

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

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

نمادهای بکارگرفته شده
،(j=1 2, …,n) j زمان پردازش کار :Pj
،(j=1 2, …,n) j موعد تحویل کار :dj
،(j=1 2, …,n) j وزن کار :Wj
Cj: زمان تکمیل کار j=1 2, …,n) j)، Rj: زمان در دسترس قرار گرفتن کار،
M: یک مقدار صحیح مثبت بزرگ،
LT: تعداد کاراهای دارای تاخیر، Tj: دیرکرد، بطوریکه {wjTj= wj Max {0, Cj – dj
1268732040127Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

. Genetic Algorithm
. Simulated Annealing
1268732040127Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:17 IRST on Saturday November 4th 2017

Xij = 
0otherwise

تعریف 9. تعداد کارهای دارای دیرکرد ((LT: این تابع هدف به موعد تحویل وابسته بوده و به صورتU j

نشان داده میشود که معادل با درصد کالاهایی میباشد که به موقع ارسال و تحویل مشتری میگردند:

U j 10 otherwiseTjLT jn1 U j )2(

تعریف 6. دیرکرد وزنی کل تکماشینه (SMTWT)2: هنگامیکه زمان تکمیل کار از موعد تحویل آن بزرگتر باشد، دیرکرد روی داده است. برای حل این مساله ،معمولامعمولاً از روش شاخه و حد استفاده میشود )برای مطالعه بیشتر مرجع ]24[ را ببینید(.

6-3. شبیهسازی آنیلینگ
ایدهای که اساس روش SA را شکل داد برای اولین بار توسط متروپلیس و همکاران در 2953 ارائه شد که الگوریتمی برای شبیه-سازی فرآیند انیلینگ بود .31 سال بعد کرک پاتریک و همکاران]25-26[ روشی پیشنهاد کردند که براساس آن میتوان این شبیهسازی را برای جستجوی جواب در مسائل بهینهسازی به کاربرد .در روند این جستجو ،الگوریتم SA با یک 0T )دمای اولیه( و 0S )جواب اولیه( شروع شده که ابتدا، این جواب، اولین (SC) و بهترین جواب (SB) است. یک جواب همسایگی (SN) با تعویض بعضی عناصر SC بدست میآید .چنانچه تابع هدف به ازای SN و SC را با EN و EC نشان دهیم، اگر EN از EC بهتر باشد ،SN به عنوان SC جدید پذیرفته میشود و در تکرار بعد SN جدید تولید میشود. ولی چنانچه EN از EC بدتر باشد، از معیار متروپلیس استفاده شده و SN با احتمال (exp(

TE به عنوان SC جدید پذیرفته میشود. در این رابطه ∆E= EN _ EC است و چنانچه
EC از EB بهتر باشد ،SC به عنوان SB جدید پذیرفته میشود .
wjTj: مجموع دیرکرد، مینیممسازی و علامت مثبت برای مسائل ماکزیممسازی استفاده WjTj: جریمه دیرکرد وزنی کار j. میشود ]27[.

SA اجزاء و پارامترهای الگوریتم. 3-6-91if job j is scheduled after job i
درغیراینصورت SB بدون تغییر باقی میماند .SA این فرآیند را به تعداد Ln )طول زنجیره مارکوف( در هر سطح از دما تکرار و پارامتر T به آرامی با استفاده از تابع کاهش دما تا هنگامیکه شرط توقف برقرار گردد کاهش مییابد. لازم بذکر است که از علامت منفی برای مسائل  نمایش ساختار جواب،
انتخاب جواب اولیه،
مکانیزم ایجاد جواب همسایه: میتوان از دو روش برای ایجاد همسایگی استفاده کرد: انتخاب جواب همسایگی از بین جوابهای امکانپذیر به طور تصادفی، انتخاب جواب همسایگی برطبق ضابطهای خاص براساس روش ابتکاری مخصوص به هر مساله. که روش اول بیشتر مورد استفاده قرار میگیرد )میتوانید مرجع ]28[ را ببینید( .
انتخاب دمای اولیه: چنانچه دمای اولیه پایین باشد، احتمال پذیرش جوابهای بدتر کاهش یافته و ممکن است سیستم در جواب بهینه محلی باقی بماند. اگر بخواهیم جواب نهایی مستقل از جواب شروع باشد، دمای اولیه باید به اندازه کافی زیاد درنظر گرفته شود، تا امکان تعویض تقریباتقریباً آزاد جواب-
های همسایگی وجود داشته باشد، درغیر اینصورت جواب نهایی به سمت جواب شروع نزدیک خواهد شد. وایت نظریه معادل بودن 0T با انحراف استاندارد هزینههای سیستم از میانگین هزینه را مطرح نمود]29[. در این روش دمای اولیه را معادل انحراف استاندارد مقادیر ارزش تابع هدف به تعداد دفعات معین اجرای برنامه در حالت ناپایدار درنظر گرفته و در هر مرحله براساس چند نمونه دمای اولیه محاسبه می-شود )رابطه2(.

256792-1651111
)
)
(
(
1
2




N
Mean
j
obj
N
j

1



قیمت: تومان


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