International Journal of Industrial Engineering & Production Management (2013)

دانلود رایگان پژوهشIUST v23n4p389 fa 1

-144144-24523

دانلود رایگان پژوهشIUST v23n4p389 fa 1

February 2013, Volume 23, Number 4
pp. 389-400

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

Minimizing the Number of Tardy Jobs in a Two-Machine flowshop problem with Non-Simultaneous Job Entrance

G. Moslehi*, A. hakimian & M. Abouei Ardakan

Ghasem Moslehi, Professor Isfahan University of Technology, moslehi@cc.iut.ac.ir
Ali hakimian, M.Sc student Isfahan University of Technology, a.hakimian@in.iut.ac.ir
Mostafa Abouei Ardakan, PhD student Isfahan University of Technology, m.abouei@in.iut.ac.ir

Keywords 1ABSTRACT

1268732040127

دانلود رایگان پژوهشIUST v23n4p389 fa 1

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

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

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

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

به سایت مرجع

www.homatez.com

مراجعه نمایید

 

دانلود رایگان پژوهشIUST v23n4p389 fa 1

Two machine Flowshop,
Number of tardy, NonSimultaneous Job Entrance,
Branch and Bound Algorithm,
Heuristic Algorithm In this paper, minimizing the number of tardy jobs in two-machine flowshop scheduling with non-simultaneous job entrance is discussed. It is proven that the complexity of the problem is NP_hard. Therefore, a heuristic algorithm is proposed to solve the large scale problems. Besides, an exact branch and bound algorithm with utilizing heuristic algorithm as upper bound proposed to achieve optimal solution. Computational results demonstrate that branch and bound method solves problems with 28 jobs in the set High and 20 jobs in the set Low in a reasonable time. Results show the capability of the proposed upper bound, lower bounds and dominance rules. Also, it is shown that the average ratio of optimal solution to the heuristic one with the objective ∑(1-Ui) is at most 1.11 which is smaller in contrast with other researches in the literature. This ratio proves efficacy of the proposed heuristic algorithm. Finally, according to efficiency of the presented approach, sample problems with large dimensions were solved and their results were displayed.

© 2013 IUST Publication, IJIEPM. Vol. 23, No. 4, All Rights Reserved

دانلود رایگان پژوهشIUST v23n4p389 fa 1

*
Corresponding author. Ghasem Moslehi Email: moslehi@cc.iut.ac.ir
-116839-1435396

دانلود رایگان پژوهشIUST v23n4p389 fa 1

حداقل کردن تعداد کارهای دارای دیرکرد در مسئله دو ماشین با ورود غیر همزمان

قاسم مصلحی*، علی حکیمیان و مصطفی ابویی اردکان

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

دانلود رایگان پژوهشIUST v23n4p389 fa 1

فلوشاپ دو ماشین در این مقاله مسئله زمانبندی فلوشاپ دو ماشین با در نظر گرفتن ورود غیر همزمان و با تعداد کارهای دارای دیرکرد هدف کمینه سازی تعداد کارهای دارای دیرکرد بررسی شده است. در ابتدا پیچیدگی مسأله ورود غیر همزمان بررسی و ثابت شده که مسأله NP-hard است. بنابراین برای حل مسئله فوق یک الگوریتم الگوریتم شاخه و کران ابتکاری که قابلیت حل مسائل با ابعاد خیلی بزرگ را دارد، ارائه شده است. همچنین به منظور الگوریتم ابتکاری حل بهینه مسئله از روش شاخه و کران با در نظر گرفتن الگوریتم ابتکاری به عنوان حد بالا بهره گرفته شده است. نتایج محاسباتی نشان میدهد که رویه شاخه و کران مسائل با ابعاد 82 فعالیت در گروه High و 82 فعالیت در گروه Low را در زمان منطقی و به طور کامل حل می کند، که این امر کارآیی حد بالا، حدود پایین و اصول غلبه ارائه شده برای مسئله را نشان می دهد. همچنین نشان داده شد که متوسط نسبت جواب بهینه به الگوریتم ابتکاری با هدف Ui)-1)∑ حداکثر 11/1 برابر میباشد که در مقایسه با الگوریتم های ارائه شده در تحقیقات مرتبط با کارهای دارای دیرکرد نسبت کوچکی میباشد. این نسبت نشان دهنده کارایی بالای الگوریتم ابتکاری است. با توجه به کارآیی بالای الگوریتم ابتکاری، مسائل نمونه با ابعاد بزرگ نیز حل و نتایج آن ارائه شده است.
-1371561216

دانلود رایگان پژوهشIUST v23n4p389 fa 1

9. مقدمه9
در بسیاری از صنایع برآورد کردن زمان های تحویل امری حیاتی می باشد .لذا معیارهای وابسته به تاخیر همانند تعداد کارهای دارای دیرکرد از اهمیت ویژه ای برخوردار هستند و به عنوان تاریخ وصول: 91/6/19 تاریخ تصویب: 39/5/19
*نویسنده مسئول مقاله: قاسم مصلحی، استاد، دانشکده مهندسی صنایع و
سیستمها، دانشگاه صنعتی اصفهان moslehi@cc.iut.ac.ir علی حکیمیان، دانشجوی کارشناسی ارشد، دانشکده مهندسی صنایع و
سیستمها، دانشگاه صنعتی اصفهان a.hakimian@in.iut.ac.ir مصطفی ابویی اردکان، دانشجوی دکتری، دانشکده مهندسی صنایع و سیستمها، دانشگاه صنعتی اصفهان m.abouei@in.iut.ac.ir
معیارهای ارزیابی زمان بندی ها مورد استفاده قرار میگیرند] 1[.
1268732040127

دانلود رایگان پژوهشIUST v23n4p389 fa 1

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

در این مقاله مسئله زمان بندی فلوشاپ دو ماشین با زمان های ورود غیر همزمان و با هدف حداقل کردن تعداد کارهای دارای دیرکرد در حالت فلوشاپ جایگشتی8 مورد بررسی قرار می گیرد .
در این حالت هر کاری که روی ماشین اول زودتر پردازش شود ،روی ماشین دوم نیز زودتر پردازش می شود. به عبارت دیگر هیچ کاری مانند j وجود ندارد که پردازش آن روی ماشین اول بعد از i باشد ولی پردازش آن روی ماشین دوم قبل از i صورت پذیرد .
کاربردهایی از این مسئله را می توان در کارخانه های نساجی و یا کارخانه های تولید آینه یافت. در فرایند تولید پارچه، پارچه ها
)کارها( بر روی دو ماشین رنگ زنی و خشک کن و به صورت
2.Permutation Flowshop
متوالی پردازش می شوند. در فرایند نقره کاری برای تولید آینه نیز از دو ماشین متوالی استفاده می شود. ماشین اول کار پوشش دادن پشت آینه ها )کارها( توسط رنگ را بر عهده دارد و ماشین دوم عملیات خشک کردن را انجام می دهد.
اکثر پژوهش ها در مسائل فلوشاپ برروی حداقل سازی زمان اتمام کل1 تمرکز داشتهاند] 8و3[ و تاکنون بررسیهای کمتری برای حداقل سازی تعداد کارهای دارای دیرکرد برروی مسئله فلوشاپ انجام پذیرفته است. پیچیدگی حداقل سازی تعدادکارهای دارای دیرکرد در یک فلوشاپ دو ماشین حتی موقعی که تمام کارهای دارای زمان تحویل یکسان باشند نیز NP_hard است] 4[. حالت بدون وزن و تک ماشین این مسئله، با الگوریتم مورO(nLogn) قابل حل می باشد] 5[ و الگوریتم های بهینه فقط برای حالت های خاص توسعه داده شده اند.
لین ]6[ یک الگوریتم از(O(n را برای حل حالتهای خاص مسئله فلوشاپ دوماشین وقتی که همه کارها زمانهای پردازش یکسان روی ماشین اول داشته و زمان های تحویل با زمان های پردازش سازگاری دارند ارائه کرد. لاولر و مور ]7[ یک الگوریتم بهینه برنامه ریزی پویا را برای همین مسئله با موعد تحویل یکسان F2|dj=D|ΣUj( D( ارائه کردند که از (2O(nD می باشد .
حریری و پتس ]2[ مسئله حداقل کردن تعداد کارهای دارای دیرکرد در فلوشاپ جایگشتی با M ماشین را با الگوریتم شاخه و کران حل کردند، در این مسئله کلیه کارها در زمان صفر در دسترس هستند. آنها مسائل با ابعاد حداکثر 85 کار را برای دو و سه ماشین حل کردند. مصلحی و همکاران ]9[، مسئله حداقل کردن مجموع حداکثر دیرکردها و زودکردها برروی یک فلوشاپ دو ماشین را بررسی کردند. آنها برای حل مسئله از روش شاخه و کران استفاده کردند و برای افزایش کارایی روش شاخه و کران از لم هایی برای یافتن جواب های غالب استفاده کردند.
وان و ین ]12[، مسئله حداقل کردن توام تعداد کارهای دارای دیرکرد و حداقل کردن مجموع زودکردهای وزن دار را در یک ماشین بررسی کردند. آنها برای حل مسئله از روش شاخه و کران استفاده کرده و برای حل مسائل بزرگ از یک الگوریتم ابتکاری با رتبه (3O(n بهره جستند.
باپتیست و همکاران ]11[ یک الگوریتم شاخه وکران را برای مسئله حداقل سازی تعداد کارهای دارای دیرکرد در تک ماشین و با محدودیت زمان در دسترس بودن ارائه کردند. در این تحقیق، حد پایین از ساده سازی لاگرانژی به دست آمده و با ارائه یک الگوریتم شاخه و کران قادر به حل مسئله تا اندازه 822 کار شدند .
1.Makespan
319
سادیکف ]18[ یک روش شاخه و کنترل4 را برای حل مسئله حداقل سازی وزنی تعداد کارهای دارای دیرکرد بر روی تک ماشین و با محدودیت زمان در دسترس بودن ارائه کردند. آنها در تحقیق خود از برنامه ریزی اعداد صحیح برای حل روش شاخه و کنترل استفاده کرده اند و جواب های امکان ناپذیر را توسط الگوریتم جدا کرده اند. هلاه و بولفین ]13[ نیز برای حل همین مسئله یک روش شاخه وکران که در آن یک ساده سازی جانشینی که منجر به یک مسئله کوله پشتی چند انتخابه می شود پیشنهاد دادند. آنها از همین روش برای حداقل کردن وزنی تعداد کارهای دارای دیرکرد برروی پردازشگرهای موازی نیز استفاده کردند ]14[.
هی و همکاران ]15[ رویکردی دوگانه از الگوریتم حریصانه روبه جلو6 را برای حداقل کردن تعداد کارهای دارای دیرکرد در مسئله تک ماشین ارائه کردند. آنها برای هر کار یک ضرب العجل7 نیز در نظرگرفتند. الگوریتم ارائه شده از رتبه O(nlogn) می باشد .
بولفین و هلاه] 1[ با استفاده از مسئله کوله پشتی در حدود روش شاخه و کران مسئله حداقل سازی وزنی تعداد کارهای دارای دیرکرد در یک فلوشاپ دو ماشین، توانستند مسائلی تا 122 کار حل نمایند. لودری و همکاران ]16[ الگوریتمی ابتکاری برای حداقل سازی تعداد کارهای دارای دیرکرد در یک فلوشاپ پویا ارائه کرده اند.آنها فرض کردندکه زمان ورود کارها متفاوت باشد .
رویز تورس و سنتنو ]17[ ، مسئله حداقل کردن تعداد کارهای دارای دیرکرد برروی یک فلوشاپ جایگشتی و با منابع ثانویه2 را مورد بررسی قرار دادند. آنها برای تخصیص منابع ثانویه و تخصیص کارها به توالی از الگوریتم های ابتکاری مانند جستجو همسایگی و SA استفاده کردند. رویز تورس و همکاران ]12[ در سال 8212 از روشی که در سال 8222 استفاده کرده بودند بار دیگر برای حل مسئله حداقل کردن تعداد کارهای دارای دیرکرد در یک فلوشاپ با منابع و عملیات انعطاف پذیر بهره بردند.
1268732040127

دانلود رایگان پژوهشIUST v23n4p389 fa 1

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

چوی و کیم ]19[ ، فلوشاپ دو ماشینی را در نظر گرفتند که در آن هر کار دومرتبه به فلوشاپ وارد می شود. یعنی هر کار باید یک مرتبه روی ماشین یک و سپس ماشین دو پردازش شود و دوباره تکرار شود. آنها میزان مجموع دیرکرد را در این مسئله با استفاده از روش شاخه و کران حداقل کردند. چوی و لی] 82[ ، مسئله حداقل کردن تعداد کارهای دارای دیرکرد در یک هیبرید فلوشاپ دو مرحله ای را با استفاده از روش شاخه و کران حل کردند. آنها برای حل مسئله در اندازه های بزرگ یک الگوریتم ابتکاری دو
4.Branch-and-Check
1268732040127

دانلود رایگان پژوهشIUST v23n4p389 fa 1

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

316
مرحله ای معرفی کردند. فلوشاپ آنها شامل دو مرحله بود که در مرحله اول 1M ماشین موازی و یکسان و مرحله دوم 2M ماشین موازی و یکسان وجود داشت.
موشیف و ساریگ] 81[ ، مسئله فلوشاپی را مطالعه کردند که در آن کارها نیاز به دو عملیات داشتند. عملیات اول برروی تک ماشین مرحله اول )ماشین بحرانی( و عملیات دوم بر روی یکی از M ماشین مرحله دوم صورت می پذیرد. آنها برای حل مسئله مورد نظر یک الگوریتم برنامه ریزی پویای چند جمله ای کاذب و یک الگوریتم ابتکاری موثر ارائه کردند. هدف این مقاله حداقل کردن وزنی تعداد کارهای دارای دیرکرد بود.
همانطور که مشاهده شد، مسئله حداقل سازی تعداد کارهای دارای دیرکرد برروی فلوشاپ جایگشتی با دو ماشین و زمان های ورود غیر همزمان کارها در ادبیات موضوع مشاهد نگردید. لذا در این مقاله این مسئله مورد بررسی قرار می گیرد و برای حل سریع آن یک روش ابتکاری و برای پیدا کردن جواب بهینه یک روش شاخه و کران ارائه می شود.
ادامه مقاله به این صورت سازماندهی شده است. در بخش دوم مسئله مورد نظر معرفی می شود، در بخش سوم رویکرد حل مسئله بیان می شود، در بخش چهارم نتایج محاسباتی ارائه می شود و در پایان در بخش پنجم نتیجه گیری و تحقیقات آینده ارائه می شوند.

6. تعریف و پیچیدگی مسئله
در این بخش، مسئله حداقل سازی تعداد کارهای دارای دیرکرد برروی فلوشاپ جایگشتی با دو ماشین و ورود غیر همزمان کارها به همراه پارامترها، متغیرها و فرضیات مسئله ارائه می شود.
همانطور که در مقدمه اشاره شد، این مسئله با تاکید بر روی دو ماشین در ادبیات موضوع مشاهده نشده است، لذا در این مقاله مسئله مذکور مورد بررسی قرار می گیرد. مجموعه N شامل n کار مستقل {N={1,2,3,…,n می باشد. این کارها باید برروی دو ماشین پردازش شوند .
تمام کارها ابتدا بر روی ماشین اول و سپس بر روی ماشین دوم پردازش می شوند. همچنین هرکاری که برروی ماشین اول زودتر پردازش شود بر روی ماشین دوم هم زودتر پردازش می شود. به عبارت دیگر برنامه کاری دو ماشین مشابه هستند .
کارها دارای ورود غیر همزمان هستند و هر کار در زمان خاصی برای انجام پردازش در اختیار می باشد که به آن زمان در دسترس گفته می شود. هدف پیدا کردن یک توالی از کارها می باشد که در آن تعداد کارهایی که دارای دیرکرد هستند حداقل شوند. این مسئله با فرض ورود غیر همزمان کارها تاکنون به صورت بهینه در بیشتر از یک ماشین حل نشده است، در این مقاله این مسئله بر روی فلوشاپ دو ماشین و به صورت بهینه حل و الگوریتمی ابتکاری نیز برای حل مسائل با اندازه بزرگ ارائه می شود. این مسئله از این به بعد با نماد P2|rj|ΣUj نمایش داده می شود .
نمادهای مورد نیاز این مسئله در زیر بیان شده است:
N: مجموعه کارها ،{N={1,2,3,…,n که n تعداد کل کارها است.
mام
j=1,2,3,…,n & m=1,2 Pm[j] : زمان پردازش کار در موقعیت jام روی ماشین mام
j=1,2,3,…,n dj : موعد تحویل کار jام
j=1,2,3,…,n & m=1,2 Cmj : زمان تکمیل کار jام روی ماشین mام
j=1,2,3,…,n & m=1,2 Cm[j] : زمان تکمیل کار در موقعیت jام روی ماشین mام

m=1,2 اندیس ماشین : m j=1,2,3,…,n امj زمان در دسترس کار : rj j=1,2,3,…,n & m=1,2 ام روی ماشینj زمان پردازش کار :Pmj C[j]=Max(C1[j]+ P2[j], C2[j-1]+ P2[j]) )1(
T[j] : میزان دیرکرد8 کار در موقعیت jام j=1,2,3,…,n

T[j]=Max{0, C2[j]- dJ[j]} )8(

Uj: اگر dj ≥ C2j برابر با 2 و در غیر این صورت j=1,2,3,…,n برابر با 1
σL: توالی جزئی از کارهای چیده شده در گره L
σL: مجموعه کارهای چیده نشده در گره L
[J[i : کار چیده شده در موقعیت iام توالی
(NT(σL : تعداد کارهای دارای دیرکرد در توالی جزئی σL که از رابطه زیر به دست می آید

1268732040127

دانلود رایگان پژوهشIUST v23n4p389 fa 1

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

NT(σL)=

دانلود رایگان پژوهشIUST v23n4p389 fa 1

)1(

(NT(σ′L: تعداد دیرکرد برای کارهایی که در توالی جزئیσL قرار ندارند:
NT(σ′L)=

دانلود رایگان پژوهشIUST v23n4p389 fa 1

)8(

σ′L-MOORE m: توالی جزئی حاصل از مجموعه σL با استفاده از الگوریتم مور بر روی ماشین m=1,2 ، m.
در این مقاله فرض شده است که تمام کارها بدون انقطاع انجام میشوند. همچنین بیکاری عمدی برای ماشین مجاز میباشد، به عبارت دیگر میتوان انجام کاری را که در دسترس است به صورت عمدی به تعویق انداخت و ماشین برای مدتی بیکار بماند تا کار دیگری برای پردازش برسد.
فرض بیکاری عمدی موقعی که کارها دارای زمان ورود غیر همزمان هستند می تواند باعث کاهش تعداد کارهای دارای دیرکرد شود هرچندکه حل مسئله را دشوارتر می کند. باپتیست و همکاران نشان دادند که مسئله 1|rj|ΣUj مسئله NP_hard است ]11[. از آنجا که این مسئله تقلیل یافته مسئله P2|rj|ΣUj میباشد، بنابراین آن هم حداقل دارای پیچیدگی NP_hard است .

9-6. مدل برنامه ریزی خطی
در این بخش مدل برنامه ریزی خطی عدد صحیح مختلط مسئله مورد نظر ارائه می شود. در ابتدا متغیرها و پارامتر مورد استفاده در مدل شرح داده می شوند. سپس مدل طراحی شده ارائه و تابع هدف و محدودیت های مدل تشریح می شوند.
[xi[j اگر کار i در موقعیت jام پردازش شود n
,i,j=1,2,3,…یک و در غیر این صورت صفر است .

M : یک عدد بزرگ

9-9-6. مدل برنامه ریزی عدد صحیح مختلط
Minimize NT=

دانلود رایگان پژوهشIUST v23n4p389 fa 1

)3(

s.t.
927100

دانلود رایگان پژوهشIUST v23n4p389 fa 1

دانلود رایگان پژوهشIUST v23n4p389 fa 1


دانلود رایگان پژوهشIUST v23n4p389 fa 1
قیمت: تومان