International Journal of Industrial Engineering & Production Management (2013)

-144144-24523

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, [email protected]
Ali hakimian, M.Sc student Isfahan University of Technology, [email protected]
Mostafa Abouei Ardakan, PhD student Isfahan University of Technology, [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

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

*
Corresponding author. Ghasem Moslehi Email: [email protected]
-116839-1435396

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

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

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

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

9. مقدمه9
در بسیاری از صنایع برآورد کردن زمان های تحویل امری حیاتي مي باشد .لذا معیارهای وابسته به تاخیر همانند تعداد کارهای دارای دیرکرد از اهمیت ویژه ای برخوردار هستند و به عنوان تاریخ وصول: 91/6/19 تاریخ تصویب: 39/5/19
*نویسنده مسئول مقاله: قاسم مصلحی، استاد، دانشکده مهندسي صنایع و
سیستمها، دانشگاه صنعتي اصفهان [email protected] علی حکیمیان، دانشجوی کارشناسي ارشد، دانشکده مهندسي صنایع و
سیستمها، دانشگاه صنعتي اصفهان [email protected] مصطفی ابویی اردکان، دانشجوی دکتری، دانشکده مهندسي صنایع و سیستمها، دانشگاه صنعتي اصفهان [email protected]
معیارهای ارزیابي زمان بندی ها مورد استفاده قرار ميگیرند] 1[.
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

در این مقاله مسئله زمان بندی فلوشاپ دو ماشین با زمان های ورود غیر همزمان و با هدف حداقل کردن تعداد کارهای دارای دیرکرد در حالت فلوشاپ جایگشتي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

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

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

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)=

)1(

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

)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=

)3(

s.t.
927100



قیمت: تومان


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