نشريه تخصصي مهندسي صنايع، دوره۴۴، شماره ۲، مهرماه ۱۳۸۹، از صفحه ۲۲۹ تا ۲۴۲ ۲۲۹ کمينه سازي مجموع بيشينه هاي زودکرد و ديرکرد در مسئله زمان بندي
ماشي ن هاي موازي يکسان

قاس م مصلحي*١ و مهدي مهنام٢
دانشيار دانشکده مهندسي صنايع و سيست م ها‐ دانشگاه صنعتي اصفهان
دانش آموخته کارشناسي ارشد مهندسي صنايع و سيست م ها‐ دانشگاه صنعتي اصفهان
(تاريخ دريافت ۲۲/۴/۸۷ ، تاريخ دريافت روايت اصلاحشده ١٠/٥/٨٩ ، تاريخ تصويب ٢٧/٧/٨٩ )

چكيده
در اين مقاله مسئله کمينه سازي مجموع بيشينه زودکرد و ديرکرد بر ماشينهاي موازي يکسان مورد بررسي قرار گرفته است. در اين مقاله نشان داده شده است که اين مسئله NP-hard است. با استفاده از حدود بالا و پايين و اصول غلبه مناسبي که براي مسئله توسعه داده شده است، يک رويه شاخه و کران براي دستيابي به زمان بندي هاي بهينه ارائه شده است. در ادامه براي حل اين مسئله، از دو روش فراابتكاري شامل الگوريت م ژنتي ك و بهينه سازي گروه ذرات براي يافتن توالي مناسب مسئله در زمان كوتاه استفاده شده است. با توليد ١٩٢٠ نمونه به طور تصادفي، کارآيي روش شاخه وكران و با ٤٤٨٠ نمونه، کارآيي الگوريت م هاي ابتکاري و فراابتکاري مورد بررسي قرار گرفته است. نتايج نشان مي دهند كه الگوريتم شاخه وکران در اندازه هاي کوچک و متوسط و الگوريتم ژنتي ك پيشنهادي در اندازه هاي بزرگ به طور مؤثري عمل ميكنند.

واژه هاي کليدي: زمان بندي، زودکرد/ ديرکرد، ماشينهاي موازي، روش شاخه وکران، الگوريتم هاي فرا ابتکاري

مقدمه
زمانبندي، يک فرآيند تصمي مگيري است که با تخصيص بهينه منابع به فعاليتهاي اصلي توليد در طول زمان در ارتباط است [١]. مسائل زمان بندي را مي توان از دو ديدگاه مديريت و مشتري مورد بررسي قرار داد. از ديد مديريت، کمينهسازي معيارهايي مانند بيشينه زمان تکميل و بارگذاري ماشين، مورد توجه است؛ در حالي که از ديدگاه مشتري تحويل به موقع در موعد تحويل در اولويت قرار دارد که در سيست م توليد به موقع (١ (JIT کاربرد زيادي دارد. بنابراين توجه نکردن به موعد تحويل، ممکن است سبب از دست دادن مشتري يا هزينه تأخير و از طرف ديگر، اتمام كار زودتر از موعد تحويل آن ممكن است سبب هزينه يا فساد محصول شود. به عبارت ديگر، ديركرد بيانكننده رضايت نداشتن مشتري و زودکرد نشان دهنده عملكرد موجودي است.
از طرف ديگر، در بيشتر خطوط توليد و مونتاژ، اغلب براي جلوگيري از توقف خط به ويژه در گلوگاهها از چندين ماشين يا پردازشگر به طور موازي استفاده مي شود. بنابراين بهبود زمانبندي كار ها در گلوگاه توليد
Email: [email protected] ، ۰۳۱۱ ‐۳۹۱۵۵۲۶ : نويسنده مسئول : تلفن : ۳۹۱۵۵۰۹‐ ۰۳۱۱ , فاکس *

به بهبود کل سيستم كمك مي كند. همچنين در محيط هاي خدماتي ميتوان به زمانبندي بارگيري
کشتي ها و تخصيص بيماران به گروه هاي پزشکي اشاره کرد. علاوه بر اين، زمان بندي ماشين هاي موازي يک مبحث مه م در علوم رايانه براي تخصيص کارآيي وظايف به پردازشگرها و استفاده از ريزپردانده هاي موازي است.
در مسئله کلاسيک، زمان بندي ماشين هاي موازي n کار با زمان فرآيند معين بايد روي m ماشين تحت عمليات قرار گيرند. در اين مسئله هر کار مي تواند روي يکي از ماشين هاي بيکار مورد پردازش قرار گرفته و با تکميل کار، ماشين بيکار شده و کار از سيست م خارج ميشود. بنابراين در حالي که در مسئله زمانبندي تک ماشين فقط تعيين ترتيب بهينه کارها مطرح است، در مسائل زمانبندي با ماشين هاي موازي، با دو مرحله تصمي م گيري تخصيص کارها به ماشين ها و تعيين توالي کارها بر هر ماشين رو به رو هستيم. مسائل ماشين هاي موازي مي توانند به سه صورت يکسان۲، يکنواخت٣ و نامرتبط٤ در نظر گرفته شوند. در ماشينهاي يکسان، مدت زمان فرآيند کارها مستقل از ماشين است؛ در حالي که در دو حالت ديگر زمان فرآيند کارها روي ماشين ها بر اساس نوع ماشين تغيير ميکند.
در اين تحقيق به بررسي مسئله زمان بندي ماشينهاي
۲۳۰
موازي با هدف کمينه کردن مجموع بيشينه هاي زودکرد و ديرکرد به عنوان يک معيار جديد و کاربردي پرداخته مي شود. ابتدا از الگوريت م شاخه وکران براي يافتن جواب بهينه در اندازه هاي کوچک و متوسط و الگوريتمهاي ابتکاري براي رسيدن به جواب هاي مناسب در مدت زمان کوتاه استفاده شده است. سپس از الگوريتم هاي فراابتکاري براي دستيابي به جوابهاي مناسب در زمان معقول در مسائل با اندازه بزرگ مورد استفاده قرار گرفتهاند.
ساختار كلي مقاله در ادامه بدين شرح است: در بخش بعدي مروري بر ادبيات موضوع انجام مي گيرد. در بخش سوم تعريف مسئله، فرضيه ها و پيچيدگي آن بررسي مي شود. در بخش چهارم، يک الگوريت م شاخه وكران و در بخش پنج م الگوريتم هاي فراابتکاري براي حل مسئله مورد نظر ارائه ميشود. چگونگي توليد مسائل تصادفي و کارآيي الگوريت م ها در بخش شش م مورد بررسي قرار مي گيرد.
درآخرين بخش نيز به نتيجه گيري و ارائه پيشنهادها براي تحقيقات آتي پرداخته خواهد شد.

مروري بر ادبيات موضوع
مسئله زمان بندي زودکرد/ ديرکرد در طول دهههاي اخير مورد توجه بسياري از محققان بوده است. اين مسئله براي اولين بار توسط سيدني [٢] به شكل کمينه سازي بيشينه جريمه زودکرد يا ديرکرد معرفي شد. پس از آن طيف گستردهاي از مسائل بر اساس انواع جريمهها، موعد تحويل و بيکاري عمدي مورد مطالعه قرار گرفتند. بيکر و اسکودر [٣] مرور جامعي بر انواع اين مسائل داشته اند.
هنگامي كه موعد تحويل کارها مجزا است، زمان بندي بهينه ممكن است شامل زمان هاي بيكاري عمدي باشد. حالتي که امکان اعمال بيکاري وجود نداشته باشد، طيف گسترده اي از کاربردهاي صنعتي را در برميگيرد. اين حالت مي تواند نتيجه محدوديتهاي تکنولوژيکي ناشي از هزينه زياد نگهداري ماشين به صورت بيکار باشد، بدين معني که اين هزينه بيش از سود حاصل از پردازش سريع تر کارها است. در مواردي نيز که ظرفيت ماشين در مقايسه با تقاضا محدود است، ماشين همواره در حالت کار نگه داشته مي شود و در نتيجه بيکاري عمدي مجاز نيست [٤].
تحقيقات متعددي روي مسئله زمانبندي زودکرد/ ديرکرد بدون در نظرگرفتن بيکاري عمدي انجام گرفته وروش هاي حل دقيق و ابتکاري متعددي براي آن ارائه شده است. از بين روش هاي حل دقيق مي توان به مطالعات والنته و آلوس [٤]، عبدالرزاق و پاتس [٥] و عزيزاوغلو و همكاران [٦] اشاره کرد که همگي از روش شاخه وکران استفاده كرده اند. در بين رويکردهاي ابتکاري نيز مطالعات الميدا و سنتنو [٧]، والنته و آلوس [٨] و ام هلاح [٩] اهميت ويژهاي دارند که از روش هاي ابتكاري محلي و روش هاي فراابتكاري تركيبي استفاده كرده اند.
بيشتر مطالعات زمان بندي زودکرد/ديرکرد، معيارهاي کمينه مجموع۵ را مدنظر قرار داده اند. ممكن است در نتايج حاصل از كمينه كردن ميانگين هزينهها، مقادير بزرگ زودكرد يا دير كرد براي بعضي از كارها وجود داشته باشد که سبب اشكال در سيست م توليدي مي شود. اين مشکل با استفاده از اهداف مبتني بر كمينهسازي بيشينه۶ که هدف خود را کاهش واريانس هزينهها قرار دادهاند، مرتفع ميشود. از جمله اين معيارها، ميتوان به مجموع بيشينه هاي زودکرد و ديرکرد ((ETmax اشاره کرد. اين معيار براي اولين بار مورد توجه امين نيري و مصلحي [١٠] قرار گرفت. وي يک الگوريت م شاخه وکران براي اين مسئله در حالت تک ماشين ارائه کرده است. همچنين مصلحي و همکاران [١١] با ارائه اصول غلبه کارآ و يک روش ابتکاري جديد به عنوان حد بالا، الگوريت م شاخه وکران ارائهشده را بهبود بخشيده اند. از آن جا كه ETmax ي ك معيار نامنظ م است، با استفاده از بيكاري عمدي مي توان به جواب هاي بهتري دست يافت. توكلي مقدم و همكاران [١٢] ي ك الگوريت م بهينه براي به دست آوردن مقدار بيكاري عمدي در ي ك توالي معلوم با معيار ETmax ارائه كردند. در ادامه، توكليمقدم و همكاران [١٣] با استفاده از اين الگوريت م ي ك روش شاخه وكران براي اين مسئله توسعه داده اند. به تازگي، مهنام و مصلحي [۱۴] معيار ETmax را در زمانبندي تک ماشين با فرض ورود غيرهمزمان کارها و نکويي مهر و مصلحي [۱۵] اين مسئله را با در نظرگرفتن زمانهاي آماده سازي وابسته به توالي با روشهاي دقيق و ابتکاري مورد بررسي قرار دادهاند.
از طرف ديگر، رويه هاي متعدد حل دقيق و ابتکاري بر مسئله زمانبندي ماشين هاي موازي ارائه شده است. ل م و کينگ [١٦] و موکوتوف [١٧] مرور جامعي بر مطالعات زمان بندي ماشينهاي موازي و معيارها و روش هاي حل به کار رفته در اين مسئله داشته اند. اين مسئله در حالتي که موعد تحويل به شكل مجزا توسط محققان بسياري ازجمله هيدي و زو [١٨]، عزيزاوغلو و کيرکا [١٩]،بالاکريشنان و همکاران [٢٠]، زو و هيدي [٢١] و ونتورا وکي م [٢٢] مورد بررسي قرار گرفته است. کداد‐ سيدهام وهمکاران [٢٣] حدود پايين و بالاي مناسبي براي مسئلهزمان بندي زودکرد / ديرکرد در ماشين هاي موازي ارائه کرده اند. توکلي مقدم و همکاران [٢٤] براي مسئله زمان بندي ماشين هاي موازي نامرتبط با هدف کمينهکردن کل جريمههاي زودکرد و ديرکرد و هزينههاي ماشين يک مدل رياضي و يک الگوريت م ژنتيک ارائه کرده اند. در ادامه، توکلي مقدم و همکاران [۲۵] يک الگوريت م جستجوي پراکنده چند هدفه براي اين مسئله توسعه داده اند. جولاي و همکاران [٢٦] نيز يک الگوريت م ابتکاري براي مسئله زمان بندي ماشين هاي موازي يکسان با هدف کمينه سازي کل ديرکرد با کارهاي قابل تقسي م و زمانهاي راه اندازي وابسته به توالي ارائه و کارآيي آن را با توجه به نتايج مدل رياضي ارائه شده نشان دادهاند.

تعريف مسئله
در مسئله زمان بندي با هدف کمينهکردن مجموع بيشينه زودکرد و ديرکرد بر ماشين هاي موازي يکسان مجموعه {J= { ١، ٢، ٣، …، n شامل n كار بايد روي m ماشين موازي يکسان انجام شوند، به طوري كه هر كار j داراي مدت زمان فرآيند pj و موعد تحويل مشخص dj است. با در نظر گرفتن زمان تکميل کار j به صورت Cj مقادير زودکرد و ديرکرد به ترتيب به صورت زير به دست مي آيند:

Ej= max{٠, dj-Cj} (١) Tj= max{٠, Cj-dj} (٢)
و تابع هدف ETmax به شکل زير تعريف ميشود:

ETmax= Emax + Tmax (٣)
که Emax بيشينه زود كرد و Tmax بيشينه ديركرد كارها است.
در ادامه، فرضيه هاي زير نيز در مسئله در نظر گرفته شده است:
ماشين های موازي، يکسان و همواره در دسترس هستند.
ماشين در هر لحظه فقط قادر به انجام يک کار است.
هر کار فقط شامل يک مرحله بوده و نمي تواند به طورهمزمان روي چند ماشين مورد پردازش قرار گيرد.
همه کارها در لحظه صفر در دسترس بوده و انقطاع کارها مجاز شمرده نميشود.
بيکاري عمدي براي کار و ماشين مجاز نيست.
مدت زمان آمادهسازي مستقل از ترتيب کارها بوده و در زمان پردازش در نظر گرفته شده است.

مسئله مورد بررسي بر اساس نمايش سه جزیي به صورت Pm| |ETmax نشان داده ميشود. اين تابع هدف نامنظ م است، بدين معني که با افزايش زمان تکميل کارها لزوماﹰ معيار مسئله کاهش نمييابد. ماندل و موشيو [٢٧] ثابت کرده اند که مسئله Pm||Emax داراي پيچيدگي NP-hard است. با توجه به رابطه(٣)، با تعيين موعدهاي تحويل در يک نمونه خاص به گونه اي که امکان ديرکرد هيچ کاري وجود نداشته باشد، مسئله Pm||ETmax به Pm||Emax تبديل ميشود. بنابراين مسئله Pm||ETmax که حالت کلي تري از Pm||Emax است، حداقل پيچيدگي NP-hard را دارد.
از آنجايي که بيکاري عمدي بر اساس فرضيههاي مسئله مجاز نيست، مدت زمان بيکاري در بين کارهاي مجاور و يا هنگامي که کاري در دسترس باشد، مجاز شمرده نميشود. شکل (١) حالتي از بيکاري ماشين که در نتيجه تخصيص کارها به ماشين ايجاد مي شود را نشان مي دهد. بنابراين با در نظر گرفتن فرض مجاز نبودن بيکاري عمدي، ترتيب کارها نشان دهنده تخصيص کارها به ماشين ها نيز هست؛ بدين صورت که هر کار به ماشين با کمترين زمان فرآيند اختصاص مييابد[٢٧].

۱ ۳ M۱
M۲ ۱
۲ ۲
۳

M۱ M۲
(الف) نبود بيكاري عمدي (ب) وجود بيكاري عمدي

شكل 1: بررسي تأثير تخصيص كارها در ايجاد بيكاري عمدي.
روش شاخه وکران
در اين بخش، با توجه به پيچيدگي مسئله، يک الگوريت م شاخه وکران براي به دست آوردن جواب بهينه مسئله ارائه شده است. اين روش مبتني بر استراتژي جستجو، حدود پايين و بالا و اصول غلبهاي است که براي مسئله به صورت کارآ توسعه داده شده است.
۲۳۲استراتژي جستجو
در اين الگوريتم، همه ترتيب کارها بررسي شده وجواب بهينه به دست ميآيد. در اين رويه σ نشان دهندهترتيب جزیي کارها و ‘σ مجموعه کارهاي زمان بندينشده است. (ETmax(σ نشان دهنده مقدار تابع هدف حاصل ازترتيب جزیي LB(σ) ،σ حد پايين حاصل از کارهاي زمان بندي نشده و (f(σ برابر بيشينه مقادير (ETmax(σ و (LB(σ است. در اين الگوريت م، ترتيب کارها به صورت پيشرو۷ بررسي شده و از استراتژي عمقي۸ براي انتخاب گره براي شاخه زدن استفاده شده است. در هر مرحله با
داشتن ي ك زمانبندي جزیي از كارها σ=J[ ] [ ]1 J 2 …J[ ]K، با اضافه كردن كارهاي زمان بندي نشده به انتهاي مجموعه σ كه شرايط امکان پذيري و اصول غلبه را ارضا مي كنند، شاخههاي جديد زده ميشود. در نتيجه يک كار از مجموعه کارهاي زمان بندي نشده (‘σ) کاسته و به توالي جزیي σ منتقل ميشود. هنگامي كه هيچ کاري براي زمان بندي باقي نماند، σ ي ك زمان بندي كامل است. در طول رويه جستجو، مقدار تابع هدف بهترين زمان بندي با حد بالا مقايسه و به هنگام ميشود.

حد پايين
چنانچه پيش از اين اشاره شد، معيار ETmax از مجموع بيشينه زودکرد و بيشينه ديرکرد کارها به دست ميآيد. بنابراين ميتوان براي به دست آوردن حد پايين الگوريتم شاخه وکران، مسئله را به دو زيرمسئله كمينه سازي بيشينه زودكرد (Pm||Emax) و ديركرد (Pm||Tmax) تجزيه و با جمع جواب هاي بهينه حاصل، حد پايين را محاسبه كرد. ثابت شده است كه مسئله اول يک مسئله NP-hard است [٢٧] و نشان داده مي شود که مسئله دوم نيز پيچيدگي NP-hard را دارد(پيوست الف)؛ بنابراين حل بهينه هر ي ك از زيرمسئله ها با استفاده از ي ك الگوريتم چندجملهاي9 امكان پذير نيست. در نتيجه از مجموع حد پايين دو زيرمسئله براي محاسبه حد پايين مسئله Pm||ETmax استفاده شده است.

حد پايي ن زيرمسئله Pm| |Emax
در اين زيرمسئله، کارهاي زمانبندي نشده بر اساس قاعده MST مرتب شده و با توجه به اينكه بيكاري عمدي مجاز نيست، پردازش آن ها فقط روي ماشين با کمترينزمان تخصيص يافته در نظر گرفته مي شود. در ترتيب MST کارها بر اساس اختلاف موعد تحويل و مدت زمان پردازش به شکل غيرنزولي مرتب ميشوند. شرايط و نحوه محاسبه حد پايين اين زيرمسئله به طور نمونه در شکل (٢) نشان داده شده است. (σ(k نشاندهنده ترتيب جزیي کارهاي زمانبندي شده روي ماشين kام است.

1

2

3
M
١

M
٢

M
٣

σ
)
2
(

σ
)
1
(

σ
)
3

(

1



قیمت: تومان


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