متن کامل پایان نامه را در سایت منبع fuka.ir می توانید ببینید متن کامل پایان نامه را در سایت منبع 2 fuka.ir می توانید ببینید

*82

متن کامل پایان نامه را در سایت منبع fuka.ir می توانید ببینید

وزارت علوم، تحقیقات و فناوری
دانشگاه علوم و فنون مازندران
پایان نامه
مقطع کارشناسی ارشد
رشته: مهندسی صنایع- صنایع
عنوان: طراحی یک الگوریتم فراابتکاری برای حل مساله زمانبندی ماشینهای موازی نامرتبط با محدودیت زمان دسترسی به کارها
استاد راهنما:
دکتر جواد رضائیان
استاد مشاور:
دکتر ایرج مهدوی
دانشجو :
محمدرضا نقیبی محمودآبادی
زمستان 1391

چکیده :
امروزه با بکارگیری موفقیت آمیز مفهوم تولید به موقع در مفاهیمی چون مدیریت تولید و انبار داری نیاز به تکمیل پردازش کارها در موعد تحویل آن ها یک امر کلیدی در محیطهای صنعتی محسوب می شود.به بیان دیگر تکمیل کارها پیش از موعد تحویل به همان اندازه که دیرکرد در تکمیل آنها اهمیت دارد در کانون توجه قرار میگیرد.زمانبندی ماشینهای موازی نامرتبط حالت عمومی مسائل کلاسیک ماشینهای موازی به شمار می آید.در برخی از کاربردهای زمانبندی ماشینهای موازی نامرتبط ماشینها دارای سطح تکنولوژیکی متفاوتی هستندو لزما قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نمی باشد و در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشین ها به وقوع می پیوندد. تلقی زمان نصب به صورت مجزا از زمان پردازش در بیشتر تکنیکهای مدیریت تولید نو ظهور نظیر تولید به موقع، تکنولوژی گروهی و تولید سلولی مورد استفاده قرار می گیرد.
در این تحقیق مسئله زمانبندی ماشینهای موازی نامرتبط با در نظر گرفتن محدودیت های زمان نصب وابسته به توالی پرداژش کارها و دسترسی محدود به ماشینها و کارها با هدف کمینه سازی زمانهای دیرکرد و زودکرد وزنی کل بررسی میشود.یک مدل برنامه ریزی عدد صحیح برای این مسئله پیشنهادمی شود.همچنین یک روش ترکیبی فرا ابتکاری متشکل از الگوریتم ژنتیک و اگوریتم حرکت جمعی پرندگان برای حل آن ارائه گردیده است.
تقدیم به پدر و مادر عزیزم
تشکر و قدردانی :
سپاس خدای را که سخنوران، در ستودن او بمانند و شمارندگان، شمردن نعمت های او ندانند و کوشندگان، حق او را گزاردن نتوانند. و سلام و دورد بر محمّد و خاندان پاک او، طاهران معصوم، هم آنان که وجودمان وامدار وجودشان است؛ و نفرین پیوسته بر دشمنان ایشان تا روز رستاخیز…
بدون شک جایگاه و منزلت معلم، اجّل از آن است که در مقام قدردانی از زحمات بی شائبه ی او، با زبان
قاصر و دست ناتوان چیزی بنگاریم.
اما از آنجایی که تجلیل از معلم، سپاس از انسانی است که هدف و غایت آفرینش را تامین می کند و سلامت امانت هاییرا که به دستش سپرده اند، تضمین؛ بر حسب وظیفه و از باب
” من لم یشکر المنعم من المخلوقین لم یشکر اللَّه عزّ و جلّ” :ازپدر و مادر عزیزم…این دو معلم بزرگوارم… که همواره بر کوتاهی و درشتی من، قلم عفو کشیده و کریمانه از کنار غفلت هایم گذشته اند و در تمام عرصه های زندگی یار و یاوری بی چشم داشت برای من بوده اند؛
از استاد با کمالات و شایسته؛ جناب آقای دکتر جواد رضائیان که در کمال سعه صدر، با حسن خلق و فروتنی، از هیچ کمکی در این عرصه بر من دریغ ننمودند و زحمت راهنمایی این رساله را بر عهده گرفتند؛از استاد صبور و با تقوا ، جناب آقای دکتر ایرج مهدوی ، که زحمت مشاوره این رساله را در حالی متقبل شدند که بدون مساعدت ایشان، این پروژه به نتیجه مطلوب نمی رسید؛
از استاد گرامی، جناب آقای مهندس مهدیزاده ریاست محترم تحصیلات تکمیلی دانشکده مهندسی صنایع، بخاطر همه زحماتی که در این دوره متحمل شده اند، کمال تشکر و امتنان را دارم.
باشد که این خردترین، بخشی از زحمات آنان را سپاس گوید .
فهرست عنوان ها
فصل 1-کلیات و بیان مسأله…………………………………………………………………………..22-1
1-1- مقدمه…………………………………………………………………………………………………………………………2
1-6- تعریف مسأله زمانبندی مربوط به تحقیق………………………………………………………………………..3
1-7- مفروضات مسئله…………………………………………………………………………………………………………5
1-8- ضرورت انجام تحقیق………………………………………………………………………………………………….6
1-9- جمع بندی………………………………………………………………………………………………………………….7
فصل 2- مروری بر ادبیات موضوع…………………………………………………………………45-8
2-1- مقدمه………………………………………………………………………………………………………………………24
2-2- مروری بر رویکرد و اصول سیستم تولیدی JIT……………………………………………………………26
2-3- توالی ماشین های موازی با معیار دیر کرد…………………………………………………………………….28
2-3-1- حداقل کل دیر کرد……………………………………………………………………………………………..28
2-3-2- حداقل کل دیر کرد وزنی…………………………………………………………………………………….32
2-4- توالی ماشین های موازی با معیارهای زود کرد و دیر کرد……………………………………………….34
2-4-1- مسائل با تمرکز بر زمان آماده سازی بین کارها……………………………………………………….35
2-4-2- مسائل با تمرکز بر موعد تحویل یکسان برای کارها…………………………………………………39
2-4-2-1- موعد تحویل معلوم………………………………………………………………………………………39
2-4-2-2- موعد تحویل نامعلوم…………………………………………………………………………………….44
2-5 دسترسی محدود به ماشینها …………………………………………………………………………………………..45
2-6 جمع بندی ………………………………………………………………………………………………………………….45
فصل 3- ارائه مدل ریاضی…………………………………………………………………………….58-46
3-1- مقدمه………………………………………………………………………………………………………….47
3-2-تعریف مسئله………………………………………………………………………………………………….47
3-3- فرضیات مسئله……………………………………………………………………………………………….48
3-4- مدل ریاضی پیشنهادی………………………………………………………………………………………49
3-4-1- پارامترهای ورودی…………………………………………………………………………………….49
3-4-2- نمادها، تعاریف، پارامترها و متغیر های تصمیم…………………………………………………….50
3-4-3- مدل ریاضی…………………………………………………………………………………………….51
3-5 –اعتبار سنجی مدل……………………………………………………………………………………………53
3-6 –تئوری پیچیدگی و پیچیدگی مساله مورد نظر……………………………………………………………56
3-6- جمعﺑندی……………………………………………………………………………………………………..58
فصل 4- الگوریتم پیشنهادی نتایج محاسباتی…………………………………………………..110-59
4-1 مقدمه……………………………………………………………………………………………………………………………60
4-2 الگوریتم ژنتیک ……………………………………………………………………………………………………………..62
4-2-1 شمای کلی الگوریتم ژنتیک………………………………………………………………………………………….64
4-3) اجزای الگوریتم ژنتیک…………………………………………………………………………………………………66
4-3-1) کروموزوم………………………………………………………………………………………………………….66
4-3-2) جمعیت………………………………………………………………………………………………………………66
4-3-3) مقدار برازندگی……………………………………………………………………………………………………67
6-3-4) کدگذاری……………………………………………………………………………………………………………67
4-3-5) انتخاب……………………………………………………………………………………………………………….68
4-3-6) عملگر تقاطعی……………………………………………………………………………………………………..76
4-3-7) جهش………………………………………………………………………………………………………………….82
4-3-8) جابه‌جایی…………………………………………………………………………………………………………….83
4-3-8) قاعده توقف………………………………………………………………………………………………………..83
4-3 الگوریتم حرکت جمعی پرندگان ……………………………………………………………………………………..84
4-4 حرکت دسته جمعی ذرات ………………………………………………………………………………………………86
4-5 مفاهیم پایه الگوریتم…………………………………………………………………………………………………………88
4-6 رابطه بروز رسانی سرعت…………………………………………………………………………………………………..88
4-7 رابطه بروز رسانی موقعیت………………………………………………………………………………………………….92
4-8 گامهای الگوریتم……………………………………………………………………………………………………………..93
4-9 شبه کد الگوریتم……………………………………………………………………………………………………………….93
4-10)طراحی الگوریتم پیشنهادی………………………………………………………………………………………………94
4-10) تنطیمات پارامترها و شرایط اجرای الگوریتم ها……………………………………………………………………99
4‐11) ساختار مسائل…………………………………………………………………………………………………………………99
4‐12)مسائل با ابعاد کوچک و متوسط…………………………………………………………………………………………100
4-13) نتایج آزمایشات……………………………………………………………………………………………………………..100
4-14 مسائل با ابعاد بزرگ…………………………………………………………………………………………………………107
4-15 جمع بندی………………………………………………………………………………………………………………………109
فصل5- نتیجه گیری و پیشنهادات آتی……………………………………………………………..113-110
5-1) نتیجه گیری……………………………………………………………………………………………………………………..111
5-2) پیشنهادات آتی ………………………………………………………………………………………………………………..113
منابع……………………………………………………………………………………………………………………………………….115
فهرست جداول
جدول 1-1- تعدادی از معیارهای کارایی زمان بندی………………………………………………………………..4
جدول 3-1.موعد تحویل و وزنهای زود کرد و دیرکرد……………………………………………………………54
جدول 3-2 زمان پردازش کارها ………… ………………………………………………………………………………54
جدول3-3 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..54
جدول3-4 زمان آماده سازی کارها روی ماشین 2…………………………………………………………………..55
جدول3-4 زمان آماده سازی کارها روی ماشین 3…………………………………………………………………..55
جدول 3-5- محاسبه تعداد متغیرها و محدودیت ها ………………………………………………………………53
جدول4-1: انتخاب کروموزوم‌ها با استفاده از مدل چرخ رولت………………………………………………..72
جدول4-2: مشکلات ممکن در مدل چرخ رولت…………………………………………………………………..74
جدول4-3 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 5j2m………………100
جدول4-4 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..101
جدول4-5 زمان آماده سازی کارها روی ماشین 2……………………………………………………………………101
جدول4-6 نتایج مربوط به مسئله 5 کار و 2 ماشین به تفکیک روشها………………………………………101
جدول4-7 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 5j3m……………….102
جدول 4-8 زمان آماده سازی کارها روی ماشین 1………………………………………………………………….102
جدول 4-9 زمان آماده سازی کارها روی ماشین 2………………………………………………………………….102
جدول 4-10 زمان آماده سازی کارها روی ماشین 3………………………………………………………………..103
جدول 4-11 نتایج مربوط به مسئله 5 کار و 3 ماشین………………………………………………………………103
جدول4-12 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 8j2m……………….103
جدول4-13 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..104
جدول4-15 زمان آماده سازی کارها روی ماشین 2…………………………………………………………………..105
جدول 4-16 نتایج مسئله 8 کار و 2 ماشین به تفکیک روشها……………………………………………………..105
جدول4-17 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 8 کارو3 ماشین …..105
جدول4-18 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..105
جدول4-19 زمان آماده سازی کارها روی ماشین 2 ………………………………………………………………….105
جدول4-20 زمان آماده سازی کارها روی ماشین 3 ………………………………………………………………….105
جدول 4-21 نتایج مسئله 8 کار و 3 ماشین به تفکیک روشها……………………………………………………..106
جدول 4-22 نتایج مسئله 10 کار و 3 ماشین………………………………………………………………………107
جدول 4-23 نتایج مسئله 50 کار و 10 ماشین……………………………………………………………………..108
جدول 4-24 نتایج مسئله 50 کار و 20 ماشین……………………………………………………………………..108
جدول 4-25 نتایج مسئله 60 کار و 10 ماشین…………………………………………………………………….108
جدول 4-26 نتایج مسئله 50 کار و 20 ماشین……………………………………………………………………..109
فهرست اشکال:
شکل4-1: چرخ رولت………………………………………………………………………………………………………..70
شکل4-2: نمونه‌ای از انتخاب در چرخ رولت…………………………………………………………………………71
شکل4-3: نمونه‌ای از عملگر تقاطع تک نقطه‌ای……………………………………………………………………..77
شکل4-4: نمونه‌ای از عملگر تقاطع دو نقطه‌ای برای آرایه 0-1………………………………………………..79
شکل4-5: نمونه‌ای از عملگر تقاطع دو نقطه‌ای برای آرایه ترتیبی………………………………………………79
شکل4-6: نمونه‌ای از عملگر تقاطع یکنواخت………………………………………………………………………..81
شکل4-7 : ساختار کروموزوم……………………………………………………………………………………………….95
شکل 4-8 : نحوه عملکرد عملگر تقاطع…………………………………………………………………………………97
شکل 4-9: نحوه عملکرد عملگر جهش………………………………………………………………………………….98

1823085434340فصل اول
00فصل اول

1782445116840کلیات و بیان مسأله
00کلیات و بیان مسأله

1-1-مقدمه:
در جهان رقابتی حاضر، توالی و زمانبندی موثر ضرورتی برای بقا در فضای بازار است. زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه می کند.زمان همواره یک محدودیت اساسی بوده، بنابراین زمانبندی فعالیتها به منظور حداقل کردن این منبع محدود یک الزام است. زمانبندی و توالی عملیات یکی از مهم ترین مسائل برنامه ریزی تولید بوده و کاربردهای زیادی در واحدهای تولیدی و غیرتولیدی دارد.
عمل زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه است که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می شود. شرکت های تولیدی در تلاش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع(JIT)، پاسخگوی سریع(QR)، تکنولوژی گروهی(GT)و مدیریت کیفیت جامع(TQM)بدست آورند[3].
این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده است. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل شود، که به مسائل زمانبندی با هزینه های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می شود. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیط های تولید متنوع است.
مسائل با تعیین موعد تحویل در 25 سال گذشته بعلت روشهای جدید مدیریت مانند مفاهیمJITمورد توجه بسیار قرار گرفته است.چنگ که کمک زیادی به مسائل زمانبندی و تخصیص موعد تحویل کرد بیان می کند که تکمیل یک کار زودتر از موعد تحویل به معنی تحمیل هزینه های نگهداری موجودی غیر ضروری است ، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به جریمه های قراردادی و از دست دادن اعتبار مشتری می شود[4].
بطور جالب توجه هدف مسئله حداقل دیرکرد و زودکرد(ET) کاملا با سیاست کنترل تولید JITمطابقت دارد.مسئله ماشین های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می باشند. از دیدگاه تئوری به اینخاطر که تعمیمی از حالت تک ماشینه می باشد و از دیدگاه عملی به این جهت که در دنیای واقعی بسیارمعمول است مورد توجه قرار گرفته شده است.
مسئله به کارگیری ماشین های موازی از آنجا مورد توجه است که اگر زمانبندی روی یک ماشین منجر به هزینه زیادی شود ممکن است در نظر گرفتن ماشینهای بیشتر سبب کاهش هزینه شود. ضمن این که مقدار دیرکرد یا زودکرد نیز می تواند با افزایش تعداد ماشین ها کاهش یابد. در این شرایط هزینه به کارگیری ماشین یا نگهداری ماشین اضافه می شود که با حل مسئله بهینه سازی می توان تعیین کرد چه ماشین هایی به کار گرفته شوند و کدام کارها با چه توالی روی این ماشین ها انجام شود.
در عمل، زمانبندی ها با استفاده از الگوریتم های زمانبندی یا قوانین بر پایه دانش ایجاد می شوند. الگوریتم های زمانبندی ، زمانبندی را توسعه می دهد که یک معیار اندازه گیری مانند حداقل کردن انحراف موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد را بهینه می کند.
در این فصل، ابتدا مروری بر انواع مسائل زمانبندی و تعریف بعضی مفاهیم اولیه زمانبندی پرداخته می شود، در ادامه به خصوصیات و مشخصات مسأله مورد بحث این تحقیق، پرداخته می شود. در پایان اهداف، ضرورت و متدولوژی تحقیق بیان شده است.
1-6- تعریف مسأله زمانبندی مربوط به تحقیق :
بیان مسأله:
زمانبندی ماشینهای موازی نامرتبط حالت عمومی مسائل کلاسیک زمانبندی ماشینهای موازیبه شمار می آید.در یک مسئله کلاسیک زمانبندی ماشینهای موازی،مجموعه ای از کارهای مستقل وجود دارد که هر کدام از آنها بر روی یکی از ماشینهای موازی یکسان موجود پردازش می شوند.در حالت کلی ماشینهای موازی به صورت نامرتبط در نظر گرفته می شوند به طوریکه زمان پردازش کار ها بر روی ماشین ها نه تنها به نوع کار بلکه به نوع ماشین نیز وابسته است.در این حالت پیکربندی ماشینها یکسان نیشت و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای موازی مختلف وجود ندارد.
در این تحقیق مسئله زمانبندی ماشینهای موازی نامرتبط با در نظر گرفتن محدودیت های زمان نصب وابسته به توالی پردازش کاره و زمان دسترسی کارها با هدف کمینه سازی زمانهای زودکرد و دیرکرد وزنی کل بررسی می شود.یک مدل برنامه ریزی عدد صحیح برای مسئله پیشنهاد می شود.همچنین یک روش فراابتکاری برای حل آن ارائه می گردد.
نظام تولید بهنگام تفکر و نگرشی نوین در اداره سازمانهای صنعتی است که با اصل تکنیکها و روشهای برخاسته از آن، حذف کامل و جامع اتلاف و افزایش بهره وری در تمامی فعالیتها اعم از داخل و خارج سازمان تعقیب می گردد.
تعاریف بسیاری توسط کارشناسان برای تولید بهنگام ارائه شده است، در زیر به تعدادی از این تعاریف اشاره شده است.
JIT یعنی :
پافشاری بر کیفیت برتر انجام امور خرید و تولید و … دقیقا در زمان مقرر
بهنگام بودن نظام، مستلزم بهنگام بودن همه اجزای آن است
در کل JIT یعنی فقط به هنگام ” نه دیرتر نه زودتر”
در JIT هدف تولید بهنگام است، یعنی اگر مشتری و تولید کننده زمان تحویل کالا را در یک زمان معین توافق کنند، تولید کننده باید تولیدات خود را طوری برنامه ریزی کند که کالا را در حد امکان در زمان مناسب تولید و در زمان مقرر تعیین شده به دست مشتری برساند. اگر این دیرتر از زمان تحویل آماده شود، تولید کننده متحمل جریمه ای به عنوان تأخیر تولید خواهد شد که این جریمه امکان دارد به صورتهای مختلف نمود پیدا کند. همچنین اگر تولید کننده، کالا را زودتر از زمان تحویل، تولید کند، این کالا را باید تا زمان تحویل در انبار نگهداری کند لذا در این صورت نیز متحمل هزینه خواهد شد.
1-7- مفروضات مسئله :
1-زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشینها وجود دارد
2-هر کدام از کارها تنها بر روی زیر مجموعه ای از مجموعه ماشینها می تواند پردازش شوند
3-تمامی کارها در ابتدای افق زمانبندی در دسترس نمی باشد به عبارتی پردازش کار نمی تواند قبل از زمان دسترسی آغاز شود
4-تمامی ماشینها به طور مستمر دسترس هستند و امکان خرابی ماشینها وجود ندارد
5-هر ماشین در هر لحظه قادر به پردازش تنها یک کار می باشد
6-هر کار در طول زمان پردازش خود تنها بر روی یک ماشین پردازش می شود
7-زمانهای پردازش،نصب،موعد تحویل و ضرایب هزینه زود کرد و دیر کرد زمانی معین می باشد
8-بیکاری ماشینها مجاز است
1-8- ضرورت انجام تحقیق :
با توجه به اهمیت روزافزون مسائل ماشین های موازی در نظر گرفتن معیارهای مختلف مورد توجه محققان این علم می باشد.
امروزه در اغلب کارخانجات تولیدی و شرکت های خدماتی تأمین به موقع سفارش مشتری یا خدمت رسانی به موقع حائز اهمیت است. هزینه های زودکرد و دیرکرد در این امور نه تنها مشتری را متضرر می گرداند بلکه به شرکت نیز هزینه وارد شده و علاوه بر آن اعتبار خود را نیز از نظر مشتری از دست می دهد. مسائل تخصیص موعد تحویل زمانی جنبه عملی دارد که یک شرکت یک موعد تحویل به مشتریان در طول مذاکرات فروش پیشنهاد می کند و یک قیمت تقلیل یافته (جریمه) برای زمانیکه موعد تحویل دور از موعد انتظار باشد پیشنهاد می کند.
هر چه موعدهای تحویل ثابت شده تر باشد احتمال اینکه محصول به موقع تحویل داده شود بیشتر است. به منظور نگهداشتن یک وجهه خوب در میان مشتریان بسیاری از شرکت ها برای حفظ موعدهای تحویل ایجاد شده، هزینه های نگهداری معقولی را متحمل می شوند .
تقریبا همه مقالاتی که هدف های زودکرد و دیرکرد را در نظر می گیرند فرض می کنند که زمان آماده سازی ناچیز و یا مستقل از توالی است و همه کارها در زمان صفر در دسترس هستند لیکن زمان در دسترس بودن کار و زمان آماده سازی وابسته به توالی برای برخی صنایع از قبیل سازندگان اتومبیل و صنعت شیمی بسیار مهم است.
با توجه به اهمیت زمان دسترسی و زمان آماده سازی وابسته به توالی در این پایان نامه زمان در دسترس بودن کار و زمان آماده سازی وابسته به توالی در نظر گرفته شده است.
یک مدل ترکیبی بهینه سازی برای این منظور ایجاد شده که از نوع مسائل NP Hard است. که برای مسائل با اندازه کوچک از روشهایی که حل بهینه را می دهند استفاده شده و برای مسائل با اندازه متوسط و بزرگ از یک روش فراابتکاری که جواب بهینه یا نزدیک به بهینه را در یک زمان کوتاهتر می دهد استفاده شده است .
1-8- جمعﺑندی:
دو علم زمانبندی و توالی, امروزه یکی از علوم کاربردی میﺑاشند. طبقهﺑندیﻫای مختلفی برای مسائل مربوط به آنها وجود دارد که به برخی از آنها در این مطالعه بطور مختصر اشاره گردید. از جمله این طبقهﺑندیﻫا, در ارتباط با مسائل ماشینﻫای موازی میﺑاشد. با توجه به مسائلی که اخیرا در زمینه زمانبندی ماشین آلات در محیطﻫای تولید به موقع مطرح شده است, اکثر شرکتﻫای تولیدکننده مجبور به ایجاد زمانبندیﻫایی هستند که نیاز مشتری را در موعد تحویل یا نزدیک به آن رفع سازد. بنابراین در نظر گرفتن همزمان دو معیار مجموع وزنی دیرکرد و زودکرد این مسائل را به واقعیت نزدیکﺗر کرده و آنها را پیچیدهﺗر ساخته است. در این مطالعه, سعی شده است که مساله ماشینﻫای موازی با در نظر گرفتن معیار, بررسی شده و با توجه به پیچیدگی مساله مورد نظر, یک روش فراابتکاری برای حل آن پیشنهاد گردیده است. در فصل بعد به مرور ادبیات در زمینه ماشینﻫای موازی میﭘردازیم.
17183101706245مروری بر ادبیات موضوع
00مروری بر ادبیات موضوع
1901825177165فصل دوم
00فصل دوم

2-1- مقدمه:
زمانبندی در اوایل قرن گذشته با مطالعات صورت گرفته توسط هنری گانت و سایر پیشگامان در کانون توجه قرار گرفت.با این وجود سالها به طول انجامید تا اولین تحقیقات در حوزه زمانبندی انتشار یابد.در سالهای آغازین دهه پنجاه میلادی مطالعاتی در زمینه توالی عملیات که انگیزه آنها از زمانبندی تولید ناشی می شد منجر به ارائه الگوریتمهای مهمی چون قاعده جانسون برای مسئله سیستم کارگاه جریانی ، قاعده زودتر موعد تحویل برای کمینه سازی زمان تاخیر بیشینه و قاعده کوتاه ترین زمان پردازش با هدف کمینه سازی زمان جریان میانگین شد.در طول دهه شصت با پدید آمدن مسائل پیچیده تر تعداد قابل ملاحظه ای از تحقیقات به روشهای دقیق چون برنامه ریزی خطی و برنامه ریزی پویا معطوف شد.پس از انتشار مقاله مشهور ریچارد کارپ]1[در زمینه نظریه پیچیدگی ،محققان دریافتند که الگوریتم دقیق در مدت زمان معقول قادر به یافتن جواب بهینه در مسائل پیچیده نیستند و در نتیجه در طول دهه هفتاد میلادی بخش عمده تحقیقات بر روی سلسله مراتب پیچیدگی مسائل زمانبندی متمرکز شد
اخیرا مطالعه در زمینه جریمه دیر کرد و زود کرد در مدلهای زمانبندی، بطور وسیعی مورد توجه محققان بوده است. تحقیق های گذشته بیشتر بر روی معیارهای منظم مانند حداکثر زمان تکمیل، حداکثر دیر کرد و یا میانگین دیر کرد، متمر کز بوده اند. ولی امروزه به دلیل جریمه های حاصل از زود کرد، این معیار نامنظم، نیز مورد توجه محققان علم زمانبندی قرار گرفته است. همه تولید کنندگان برای مقابله با فشارهای رقابتی بطور افزاینده ای خودشان را با عقیده JIT و حداقل هزینه موجودی، مطابقت می دهند که این مستلزم در نظر گرفتن زود کرد کارها می باشد. در واقع در JIT زود کرد کارها به اندازه دیر کرد آنها اهمیت دارد. گرچه فرض بر این است که موعد تحویل یک متغیر خارجی بوده و کنترل آن خارج از عهده مدیران است، ولی اهمیت تحویل در موعد به خوبی روشن است. کانوی[10]، برای اولین بار این نظریه را مطرح کرد که موعد تحویل قسمتی از مسأله زمانبندی است. از کسانی که در این زمینه مطالعه کردند می توان از وبستر و بیکر[11]، راگاتز و مابرت[12]، کریستی و کانت[13]، نام برد. مطالعات زیادی در زمینه مسائل زمانبندی مختلف با معیارهای دیر کرد و زود کرد (E/T) ، صورت گرفته است. وبستر، بیکر و جاگ[14]، مسأله تک ماشینه (E/T) را با در نظر گرفتن موعد تحویل یکسان و نامعین به عنوان یک متغیر تصمیم، برای دو حالت زمان های آماده سازی مستقل و وابسته به توالی با روش الگوریتم ژنتیک حل کرده اند. کریستوفر بک و فیلیپ رفالو[15]، یک روش ترکیبی با استفاده از برنامه ریزی خطی و برنامه ریزی مفید برای مسأله زمانبندی با معیار هزینه زود کرد و دیر کرد ارائه کردند. سوریا د.لیمان، شریکانت س.پالواکر و سانسرن دونگمی[16]، مسأله زمانبندی تک ماشینه با موعد تحویل محدود شده به یک فاصله و زمان پردازش قابل کنترل را ارائه کردند. آنها جریمه کلی که شامل جریمه های زود کرد، دیر کرد، زودترین موعد تحویل، طول فاصله مربوط به موعد تحویل و مقدار واقعی کاهش زمان پردازش می باشد را با یک روش ابتکاری کمینه می کنند.
ون-کیانگ زایو و چانگ لانلی[17]، به بررسی روشهای تقریبی برای تخصیص موعد تحویل مشترک به کارها و زمانبندی آنها در مسأله ماشین های موازی پرداختند. هدف، تخصیص موعد تحویل کارها می باشد، بطوریکه مجموع وزنی موعد تحویل، کل زود کرد و کل دیر کرد کمینه گردند.
زایو کینگ کی و زایان زو[18]، مسأله زمانبندی تک ماشینه با زمان پردازش احتمالی با توزیع نمایی و موعد تحویل احتمالی، با هدف کمینه کردن مجموع هزینه های وزنی دیر کرد و زود کرد را بررسی کرده اند. در این مسأله خرابی ماشین جزو فرضها بوده و مسأله با روش برنامه ریزی پویا حل شده است.
محسن الحافی[19] مسأله زمان انتظار بهینه را در سیستم های تولیدی جزء به جزء، با معیار هزینه های زود کرد و دیر کرد را بررسی کرد. مسأله مذکور شامل N مرحله است که زمان انتظار پشت هر مرحله احتمالی است. هدف در اینجا پیدا کردن زمان های انتظار بهینه بوده، بطوریکه هزینه های دیر کرد و زود کرد کمینه شوند. سانجی رادها کریشنان و جزی ا.ونتورا[20]، مسأله زمانبندی ماشین های موازی با معیار هزینه زود کرد و دیر کرد با زمان های آماده سازی وابسته به توالی با رویکرد فراابتکاری پازپخت شبیه سازی شده حل کرده اند.
شریکانت س.پالواکر و سوریا د.لیمان[21]، مسأله زمانبندی با n کار که هر کدام شامل یک عملیات بر روی هر ماشین بوده را با معیار هزینه های دیر کرد و زود کرد بررسی کرده اند. در این مسأله شکستگی کار مجاز نبوده و پارامترهای موعد تحویل و زمان پردازش معین می باشند. هدف در اینجا تعیین تعداد ماشین ها می باشد، بطوریکه هزینه های زود کرد و دیر کرد کمینه گردد.
2-2- مروری بر رویکرد و اصول سیستم تولیدی JIT
امروزه با پیشرفت روز افزون تکنولوژی، متنوع شدن نیازها و خواسته های مشتریان حرکت به سوی ساخت و تولید بر اساس سفارش مشتری، محیط رقابتی را در بین شرکت های تولیدی ایجاد و بالطبع مشکلاتی را گریبان گیر آنها نموده است. تولید کنندگان به دنبال سیستم های تولیدی هستند که نیازهای مشتریان نظیر کاهش قیمت، تنوع محصولات، دقت و کیفیت بالا را برآورده سازند. موفق بودن JIT بستگی زیادی به میزان ضایعات ایجاد شده طی فرایند تولید دارد؛ اگر در مرحله ای از تولید ضایعاتی رخ دهد، فرایند های بعدی با مشکل روبرو خواهند شد و کل سیستم دچار اختلال خواهد شد. لذا لازمه ی این سیستم این است که خود کارگران اصلاح کننده سیستم باشند و ضایعات را در حین تولید کشف کرده و نسبت به اصلاح سیستم چه مربوط به ماشین آلات باشد و چه مربوط به کارگران اقدام نمایند[22].
سرعت تولید یک عامل بسیار مهم در سیستم تولید JIT است که هم از لحاظ رویکرد موجودی ها و هم از لحاظ رویکرد کیفیت حائز اهمیت است به عبارتی همیشه اقدام به تولید زیاد و وجود داشتن تعداد زیادی محصول طی فرایند تولید باعث می شود که قسمتی از محصول تکمیل و قسمتی به عنوان کار در جریان ساخت باقی بماند “رویکرد موجودی ها” از طرفی اقدام به تولید زیاد و به جریان انداختن محصولات زیاد باعث می شود که اگر یک نقص در ابتدای فرایند تولید وجود داشته باشد و این نقایص در مراحل بعد کشف شود مقادیر زیادی از محصولات تولید شده مشمول این نقص شود.
تقاضا برای تولید یک عامل بسیار مهم دیکر در سیستم تولید JIT است. تولید زمانی انجام خواهد شد که سفارش از مشتری گرفته شود به همین خاطر این سیستم تولید را اصطلاحا سیستم کشش تولید “تقاضا” نیز نامیده اند، زیرا تا مشتری تقاضا نکند تولیدی انجام نمی شود و لذا عکس سیستم تولیدی سنتی است که در آن مواد تا حد ممکن به فرایند تولید تزریق می شود و فرایند نیز تا حد ممکن تولید می کرد. زیرا هدف این است که مواد خام و قطعات تولیدی فقط در زمان مصرف این مواد و قطعات در فرایند تولید، از فروشندگان تحویل گرفته می شود.
میزان موجودی ها اعم از مواد اولیه، موجودی های نیمه ساخته، کالا و مواد ساخته شده باید تا حد ممکن در سطح بسیار پایین “حتی در حد صفر” نگه داشته شود. مواد فقط زمانی که به آن نیاز است از فروشندگان مواد دریافت شود. میزان اقدام به تولید به نحوی انتخاب می شود که از به وجود آمدن کار در جریان ساخت جلوگیری شود. سیستم تولید JIT بر این اساس بوده که در تولید یک محصول یکسری فعالیتهایی وجود دارد که هیچ گونه ارزشی به محصول تولید شده نمی دهند بلکه فقط هزینه های آن را بالا می برند و از طرفی بعضی از فعالیتها هستند که از ابتدا تا انتها در جهت افزایش ارزش محصول هستند، فعالیتهای غیر ارزشی مثل هزینه های انبارداری، هزینه های راه اندازی دستگاهها و ماشین آلات، فعالیتهای مربوط به بازرسی مواد و کنترل کیفیت محصول، زمانی که کارگران و ماشین آلات بیکار هستند و فعالیتهای ارزشی همان فعالیتهایی است که مستقیما بر روی محصول و در جهت پردازش و تکمیل آن انجام می شود. این فعالیتها اگر انجام نشود محصول نیز به وجود نخواهد آمد، در صورتیکه در خصوص فعالیتهای نوع اول “غیر ارزشی” وجود یا حذف آن اثری بر به وجود آمدن یا نیامدن محصول ندارد.
رویکرد پایانی که می خواهیم به آن اشاره کنیم، رویکرد مدیریت کیفیت در سیستم JIT است. این رویکرد بر این امر اشاره دارد که سیستم تولیدی JIT صرف نظر از سایر رویکردهایش گامی اثر بخش در کنترل هزینه های محصول است بدون اینکه از کیفیت محصول کاسته شود. این امر تا حدی از طریق ارتباط دائمی با تعدادی محدود از فروشندگان منتخب میسر می شود. این ارتباط از این جهت مهم است که برای رسیدن به کیفیت بالا و بلند مدت، لازم است مواد با کیفیت و بدون نقص دریافت شود حتی اگر قیمت خرید این مواد کم ترین نباشد. بنابراین اگر کیفیت مطرح است هزینه مواد خام نباید فاکتور مهم و تعیین کننده ای در انتخاب فروشندگان مواد اولیه باشد. در حقیقت قیمتهای خرید بالاتر، در بلند مدت باعث بهبود کیفیت و صرفه جویی در هزینه ها می شود. برای نمونه اگر یک فروشنده مواد اولیه توانایی تحویل مواد با کیفیت را به طور دائمی تضمین کند از این بابت تولید کننده می تواند زمان صرف شده و به تناسب آن هزینه هایش در بازرسی و آزمایش مواد را کم کند. از طرفی بالا بردن کیفیت علاوه بر برقراری ارتباط با فروشندگان، با عامل مهمتری همچون استقرار موفق سیستم JIT نیز بستگی دارد.
به طور کلی، توابع هدفی که محققان در ادبیات تولید بهنگام به کار می برند را می توانیم به دو دسته اصلی تقسیم کنیم؛ مدل کلاسیک و مدل غیر کلاسیک. بعضی از محققان این تقسیم بندی را به این صورت توضیح داده اند که اگر در محیط JIT، حین انجام کارها، شکست در کارها مجاز نباشد(زمانبندی بدون قطعی کار) مدل مربوطه جزو مدلهای کلاسیک به حساب می آید و اگر شکست در کار مجاز باشد، این مدل از زمانبندی جزو مدلهای غیر کلاسیک به حساب می آید.
در زیر تعدادی از تابع هدف هایی که در محیط کلاسیک JIT، محققان از آن استفاده کرده اند، آورده شده است.
(2-1) E+T(2-2) αE+βT(2-3) Eα+Tβ(2-4) E+T2(2-5) i=1nj=i+1nCi-Cj(2-6) i=1nj=i+1nCi-Cj2(2-7) i=1nCi-C2(2-8) αi=1nEi2+βi=1nTi2(2-9) i=1nαiEi2+i=1nβiTi2۲-3- توالی ماشینﻫای موازی با معیار دیرکرد
۲-3-۱- حداقل کل دیرکرد
مساله کلاسیک کل تاخیر ماشین های موازی(PMTP) میﺗواند بصورت زیر بیان شود:
“یک مجموعه کارهای مستقل باید روی تعدادی ماشین موازی مشابه در دسترس بطور پی در پی پردازش شود. هر ماشین تنها یک کار در یک زمان میﺗواند انجام دهد و هر کار میﺗواند روی یک ماشین پردازش شود. هر کار در شروع افق برنامه ریزی حاضر می باشد. هر کار زمان پردازش مجزا و موعد تحویل مجزا دارد. هدف, تعیین زمانبندی است که کل تاخیر را حداقل کند.”
بایلژ و همکاران[23]مساله توالی مجموعهﺍی از کارهای مستقل با زمانﻫای آمادهﺳازی وابسته به توالی را روی مجموعهﺍی از ماشینﻫای موازی یکنواخت با هدف حداقل کردن کل دیرکرد در نظر میﮔیرند.در صورتیکه زمان تکمیل کارi با ci نشان داده شود, میزان تاخیر کار i برابر باTi=max{0,ci-di}میﺑاشد. هدف, یافتن ترتیب پردازش کارها به گونه ای است که مجموع تاخیر کارها حداقل گردد. آنها یک رویکرد جستجوی ممنوع (TS) برای مساله تعریف شده در بالا ارائه کردهﺍند. الگوریتم تعریف شده توسط آنها برای حل مساله داده شده توسط سیوریکایا و اولسوی [24] به کار برده شده است (آنها برای مساله حداقل کردن کل هزینهﻫای زودکرد و دیرکرد یک الگوریتم ژنتیک(GA) با یک اپراتور تقاطعی جدید ارائه کردهﺍند). تفاوت در این است که در این مقاله وزن جریمه دیرکرد برابر با صفر در نظر گرفته شده است. نتایج نشان می دهد که الگوریتم ارائه شده توسط آنها به جوابﻫای بهتری نسبت به الگوریتم ژنتیک میﺭسد.
در بررسی کاو و همکاران [25] به مساله انتخاب و زمانبندی همزمان ماشینﻫای موازی بمنظور حداقل کردن هزینه نگهداری ماشین آلات و هزینه دیرکرد کارها اشاره شده است. مساله بصورت زیر میﺑاشد:
“N کار مستقل بایستی روی تعدادی ماشین موازی که از مجموعه ای از K ماشین موجود انتخاب می گردند، زمانبندی شوند. اگر ماشینی برای انجام کار انتخاب گردد، هزینه مربوط به نگهداری ماشین را بایستی پرداخت. یک کار می تواند بوسیله بیش از یکی از ماشینﻫای انتخابی انجام شود. زمان انجام کار روی ماشینﻫای مختلف متفاوت میﺑاشد. انقطاع کارها مجاز نمیﺑاشد. موعد تحویل کارها مشخص میﺑاشد. هدف, حداقل کردن هزینه نگهداری ماشین آلات و هزینه دیرکرد کارها میﺑاشد.”
آنها از یک مدل بهینه سازی ترکیبی استفاده کرده اند. از آنجا که مساله NP-hard می باشد, آنها یک روش ابتکاری برای حل مساله معرفی کردهﺍند. نتایج, بیانگر کارایی الگوریتم فوق میﺑاشند.
تاپان و همکاران [26] مسائل کل دیرکرد و کل دیرکرد وزنی را بررسی کردهﺍند. در حالت تک ماشینه بیشترین تحقیقات انجام شده روی دو مساله کل (میانگین) دیرکرد و کل (میانگین) دیرکرد وزنی میﺑاشد. در این مقاله روشﻫای فراابتکاری و تکنیکﻫای بهینهﺳازی برای محیط تک ماشینه با تابع هدف دیرکرد بازنگری شدهﺍند. برخی تعمیمﻫای مسائل کل دیرکرد و کل دیرکرد وزنی برای محیطﻫای چند ماشینه نیز در این بررسی نشان داده شده است.
سینگ و زانگ [27]مساله توالی ماشینﻫای موازی با کارهای قابل شکست را در نظر گرفته اند. آنها فرض می کنند که کارها به زیر دستهﻫای پیوسته تقسیم شده و هر بخش از یک کار میﺗواند بطور همزمان روی هر یک از m ماشین موجود پردازش شود. Mماشینبمنظور پردازش n کار موجود میﺑاشند.
سینگ و زانگ [27] به زیر دستهﻫا با عنوان بخشﻫای تقسیمﺷده میﻧگرند. این مساله تقسیم, در محاسبه سیستمﻫای کامپیوتری چند پردازشگر موازی نیز روی میﺩهد. در این مقاله ابتدا چند مثال ساده ارائه گردیده که بصورت چند جملهﺍی قابل حل هستند. سپس یک حل ابتکاری ML به همراه تحلیل بدترین حالت آن برای مساله P/Split/cmax با زمانﻫای آمادهﺳازی مستقل معرفی شده است.
سو [28] مسئله زمان بندی ماشین های موازی یکسان را مورد بررسی قرار داده که در آن هدف کمینه کردن (E+T)/Cj می باشد.آنها یم مدل برنامه ریزی عدد صحیح باینری ساده و موثر برای حلCjp||Cmax/وp||(E+T)/Cjتوسعه دادند.
عزیزقلو و کیرکا [29] مساله زمانبندی کارها روی ماشینﻫای موازی مشابه را بمنظور حداقل کردن کل دیرکرد در نظر میﮔیرند. مساله شامل زمانبندی n کار با زمان های پردازش p1,…,pnروی m ماشین موازی مشابه میﺑاشد. همه کارها در زمان صفر آماده پردازش میﺑاشند. بریدگی برای کارها مجاز نمیﺑاشد. ماشینﻫا بطور پیوسته در دسترس بوده و هر کار باید به یک ماشین تخصیص یابد. کار j موعد تحویلdj را دارد. آنها مدلی شرح دادهﺍند که دو ویژگی را بمنظور ایجاد یک زمانبندی پیچیده ترکیب میﮐند. یکی مفهوم پردازش موازی است که موضوع تخصیص منبع را ترقی میﺩهد. دیگری, صحت زمانبندی از طریق مقیاس کل هزینه دیرکرد است. این دو ویژگی در عمل از عناصر اساسی بسیاری از مسائل زمانبندی میﺑاشند لیکن ادبیاتی که این دو ویژگی را بطور همزمان در نظر بگیرد, بسیار کمیاب میﺑاشد. آنها خصوصیاتی را بیان میﮐنند که ساختار یک زمانبندی بهینه را توصیف میﮐند. سپس یک الگوریتم شاخه و حد معرفی کردهﺍند که این خصوصیات را با یک رویه حد پایین مناسب ترکیب میﮐند. آنها درمیﻳابند که راه حلﻫای بهینه میﺗواند در زمانی معقول برای مسائل تا ۱۵ کار بدست آید. بعلاوه آنها بسط مدل خود به ماشینﻫای موازی یکنواخت را نیز در نظر میﮔیرند.
لاموس و همکاران [30] مسأله زمانبندی ماشین های موازی با زمان آماده سازی و محدودیت زمانی برای انجام کارها را مورد بررسی قرار دادند. آنها از روش تبرید شبیه سازی شده به منظور کمینه سازی کل دیر کردها استفاده کردند.
یالوی و چو [31] یک روش دقیق برای حل مساله ماشینﻫای موازی یکسان با تابع هدف کل دیر کرد ارائه دادهﺍند. مساله بصورت زیر میﺑاشد:
” مجموعه ای از N کار بایستی بدون انقطاع روی M ماشین موازی مشابه زمانبندی شوند. هر ماشین در یک زمان حداکثر یک کار را میﺗواند پردازش کند. کارها در زمان صفر در دسترس هستند. هر کار i یک زمان انجام pi و یک موعد تحویل di دارد. کارiدر صورتی دیرکرد دارد که زمان تکمیل آن بیش از موعد تحویلش باشد. هدف, تعیین زمانبندی است که کل دیرکرد کارها را حداقل کند.”
آنها از یک الگوریتم شاخه و کران به منظور حل مساله بالا استفاده کردهﺍند. بمنظور هرس کردن درخت جستجو،آنها چند خاصیت را اثبات کرده و به کمک این خواص حد بالا و پایین مناسبی برای مساله یافتهﺍند. این الگوریتم روی یک مجموعهﺍی از مسائل ایجاد شده بصورت تصادفی با اندازه متوسط آزمایش شده است. نتایج کامپیوتری نشان دادهﺍند که این الگوریتم برای مسائلی با ۳۰ کار و دو ماشین در زمان محاسباتی معقولی به جواب بهینه میﺭسد. این الگوریتم کاراتر از روشﻫای موجود برای حل این مساله عمل میﮐند.
مسئله کمینه سازی کل دیرکردها در ماشین های موازی توسط بیسکاپ و همکاران [32] مورد مطالعه قرار گرفت. به دلیل Nphard بودن مسأله یک رویکرد فراابتکاری جدید برای مسأله پیشنهاد شد، که نتایج محاسبات انجام شده نشان داد الگوریتم پیشنهادی برای حل مسأله بسیار موثر است.
2-3-2- حداقل کل دیرکرد وزنی:
پارک و همکاران [33] مساله زیر را در نظر گرفتهﺍند:
“n کار و m ماشین موازی در زمان صفر در دسترس هستند. کار j دارای زمان انجامpj، وزنwj و موعد تحویل dj میﺑاشد. اگر کار k بعد از کار j انجام شود، زمان آمادهﺳازی وابسته به توالیsjk نیاز میﺑاشد. Cjنشانﺩهنده زمان تکمیل کار j میﺑاشد. همچنین دیرکرد کار j باj-dj} Tj=max{0,c نمایش داده میﺷود. هدف, حداقل کردن مقدار میﺑاشد.”
آنها مساله زمانبندی را تحت شرایطی بررسی کردهﺍند که مجموعهﺍی از کارها در یک صف منتظر میﺑاشند. بین اتمام یک کار و شروع کار بعد زمان آمادهﺳازی وجود دارد که وابسته به توالی میﺑاشد. هدف, یافتن توالی از کارها روی ماشینﻫا است که حاصلضرب دیرکرد در وزنﻫای داده شده را حداقل کند. وزن مربوط به کارهای مختلف متفاوت میﺑاشد. از آنجا که مساله مورد بررسی حتی برای تک ماشین NP-hard میﺑاشد, تعدادی روش ابتکاری بمنظور یافتن توالی کارها روی ماشینﻫا با اهداف مختلف توسعه داده شدهﺍند. یک روش ابتکاری معروف برای مساله کل دیرکرد وزنی از قواعد توزیع امکانات استفاده کرده و سپس یک مقدار اولویت به هر کار تخصیص میﺩهد. اولویت یک کار میﺗواند بصورت تابعی از پارامترهای مربوط به آن کار از قبیل زمان انجام, موعد تحویل و وزن محاسبه گردد. دو قاعده EDD و WSPT سادهﺗرین قواعد بکار گرفته شده هستند. این دو قاعده در مسالهﻫای با شرایط خاص, جوابﻫای خوبی تولید نمیﮐنند. قواعدی که بمنظور حل مساله کل دیرکرد وزنی استفاده گردیدهﺍند عبارتند از: COVERT،ATC وATCS[33].
اولین قاعده توزیع امکانات مرکب که برای مساله کل دیرکرد بکار برده شده قاعده COVERTمیﺑاشد. این قاعده توسط کارول مورد استفاده قرار گرفته است [34]. در ابتدا این قاعده برای مساله تک ماشینه و مساله ماشینﻫای موازی طراحی شده است، اما میﺗواند برای مساله تولید کارگاهی نیز استفاده شود. لی و همکاران [35]قاعده ATCS را توسعه دادند که مشابه قاعده ATC بود با این تفاوت که مقدار زمانآمادهﺳازی را نیز در نظر میﮔرفت. در این مقاله یک بسط از قاعده ATCS ارائه گردیده است که بمنظور محاسبه مقدار اولویت هر کار برخی پارامترهای پیشﻧگر را استفاده میﮐند.پارامترهای پیشﻧگر که به عنوان یک مکانیسم میزانﺳازی مورد استفاده قرار میﮔیرند،نرخ تنزیل مورد استفاده برای محاسبه اولویت را بر حسب مشخصات مساله داده شده تعدیل میﮐنند. آنها برای تعیین مقادیر مناسب پارامترهای پیش نگر یکسری مقادیر را بمنظور توصیف مشخصات مساله مشخص کردهﺍند. آنها چهار فاکتور برای توضیح خواص مساله نمونه پیشنهاد کردهﺍند.
پارک و همکاران [33] یک فاکتور اضافی برای اندازهﮔیری مشخصات مساله معرفی کردهﺍند. سپس آنها از یک شبکه عصبی بمنظور رسیدن به مقادیر دقیقﺗری از پارامترهای پیشﻧگر استفاده کردهﺍند. نتایج کامپیوتری نشان میﺩهد که روش ارائه شده در این مقاله بهتر از سایر روشﻫای ارائه شده تا کنون میﺑاشد.
ژانگ و همکاران [36] مسأله کمینه کردن میانگین وزنی دیر کردها در ماشین های موازی مرتبط را مورد بررسی قرار دادند.
کیم و همکاران [37] چهار الگوریتم ابتکاری بمنظور حل مساله ماشینﻫای موازی با تابع هدف کل دیرکرد وزنی توسعه دادهﺍند. فرض می شود M ماشین موازی غیر مرتبط و B دسته وجود دارد. هر دسته شامل R کار مشابه میﺑاشد. کارهای موجود در دستهﻫای مختلف ممکن است از انواع متفاوتی باشند. زمان پردازش یک دسته وابسته به گروه ماشینی است که روی آن انجام میﺷود. کارهای موجود در یک دسته در صورتیکه روی یک گروه ماشین پردازش گردند, زمان پردازش مشابهی دارند. یک گروه ماشین ترکیبی از ماشینﻫای مشابه میﺑاشد که کارایی عملیاتی مشابهی دارند. ماشینﻫا در لحظه صفر در دسترس بوده و میﺗوانند حداکثر یک کار را در یک زمان انجام دهند. کارها دارای انقطاع نمیﺑاشند ولی کارهای موجود در یک دسته میﺗوانند بطور همزمان روی ماشینﻫای مختلف پردازش گردند. یک گروه از دستهﻫا شامل دستهﻫایی با کارهای مشابه میﺑاشد.
جگلت و ساوری [38] به ارائه یک سری قوانین چیره در مسأله زمانبندی ماشین های موازی با زمان دسترسی به کارها به هدف کمینه کردن کل دیر کرد وزنی پرداختند.
۲-4- توالی ماشینﻫای موازی با معیارهای زودکرد و دیرکرد
با استناد به فلسفه JITشرکتﻫا سعی در انجام کارها در زمانی نزدیک به موعد تحویلشان دارند.عدم تحقق این هدف منجر به تحمیل هزینهﻫایی به شرکت میﮔردد.بنابراین در اغلب مسائل زمانبندی هدف, یافتن طرح بهینهﺍی است که ترکیبی از دو هدف دیرکرد و زودکرد را حداقل سازد.به عنوان هزینهﻫای زودکرد می توان به هزینهﻫای نگهداری و یا خراب شدن کالاهای فاسدﺷدنی اشاره کرد.جریمه پرداختی به مشتری در ازای تحویل کار دیرتر از موعد تحویل نیز میﺗواند به عنوان جریمه دیرکرد در نظر گرفته شود.این جریمه وابسته به عواملی از قبیل میزان اهمیت کار/مشتری میﺑاشد.
تسای و وانگ [39] 3 مدل برنامه ریزی عددمختلط را برای مسئله ماشینهای موازی نامرتبط با موعدهای تحویل متفاوت پیشنهاد نمودند. هدف این مدلسازی کمینه سازی مجموع زودکرد و دیرکرد می باشد. دراین تحقیق آنها بهترین استفاده از زمان بیکاری ماشینها جهت افزایش انعطاف پذیری زمانبندی کارها را مدنظر قرار دادند.با وجود اینکه این مدلها در زمانی قابل توجیه جوابگو می باشند، زمانهای بیکاری ایجاد شده در تنظیم برنامه زمانبندی استفاده می گردد، زمانیکه موعدهای تحویل باز بالا باشند کارها بسیار بهتر قابل زمانبندی هستند، زمان بیکاری موجود انعطاف پذیری زمانبندی کارها را افزایش می دهد، اما این مدلها محدودیت برنامه ریزی را در تعداد کارها و ماشینها دارد و برای تمامی حالات قابل کاربری نیستند.
سنتیل کومارو همکاران [40]از متد فراابتکاری بهینه سازی بخشی دسته و کلونی مورچه برای ایجاد نتایج بهینه براساس معیارهای متفاوت زودکرد و دیرکرد استفاده می نمودند، و روش فازی برای انتخاب بهترین ترکیب وزنی زودکرد و دیرکرد در مورد ماشین موازی غیرمرتبط بکار بردند.
نیکوفرد و همکاران[41]یک مدل ریاضی را برای زمانبندی ماشینهای موازی یکسان با کارهای مانع در فضای کار به موقع که میزان زودکرد و دیرکرد را کمینه می نماید بکار بردند.
دمیرل و همکاران[42]از الگوریتم ژنتیک برای زمانبندی ماشینهای موازی استفاده نمودند. آنها برنامه بهبود و اپراتور عملکردی مناسب را توسعه دادند و با الگوریتم ژنتیک تلفیق نمودند.
کداک سیدهوم و همکاران [43] یک حد پایین برای مسئله زمانبندی زودکرد و دیرکرد در سیستم ماشین های موازی ارائه دادند.
دروبوچویچ و سیدنی [44] مسأله زمانبندی می نیمم سازی جریمه زودکرد و دیرکرد و موعد تحویل روی ماشین های موازی یکسان را مورد مطالعه قرار دادند. آنها یک الگوریتم دو فازی برای حل مسئله پیشنهاد کردند.
۲-4-۱- مسائل با تمرکز بر زمان آمادهﺳازی بین کارها
اکثرتحقیقات زمانبندی مقدار زمان آمادهﺳازی را ناچیز یا جزئی از زمان پردازش در نظر میﮔیرند.با وجود اینکه این فرض تحلیل را آسان نموده و منعکسﮐننده برخی کاربردهای بخصوص میﺑاشد، در برخی کاربردها که در نظر گرفتن زمان آمادهﺳازی امری لازم میﺑاشد،این فرض در جهت مخالف با کیفیت حل عمل میﮐند.بطور کلی دو نوع زمان آمادهﺳازی وجود دارد.نوع اول, فقط به کاری که بایستی انجام گردد وابسته است.این نوع زمان آمادهﺳازی مستقل از توالی نام دارد.نوع دیگر به کار انجام شده و کاری که بایستی انجام گردد وابسته بوده و زمان آمادهﺳازی وابسته به توالی نام دارد [45].
مثالهایی برای زمان آماده سازی وابسته به توالی:عبارتند از:
در یک محل تولیدی که رنگ تولید میﺷود، هر جا تغییر رنگ نیاز باشد یک زمان آمادهﺳازی برای تمیز کردن دستگاه لازم است.این زمان هم وابسته به رنگ قبلی است که روی دستگاه تولید شده و هم وابسته به رنگی که دستگاه برای تولید آن آماده میﺷود.
۲-در صنعت پلاستیک محصولات با رنگﻫای متفاوت به ماشینﻫای اکستروژن متفاوتی تخصیص داده میﺷوند.هنگامیکه تغییر رنگ نیاز باشد. مقداری طول میﮐشد تا پلاستیک بیرون آمده از قالب به رنگ دلخواه برسد.
در صنعت نوشابه, زمان آمادهﺳازی بالایی برای تغییر شیشهﻫای نوشابه به بطری نیاز میﺑاشد.
در یک شرکت تولید کاغذ هر کجا ماشین بین دو نوع کاغذ تعویض انجام دهد، از آنجا که زمان آمادهﺳازی وابسته به درجه تشابه کاغذهای تولیدی متوالی است،این زمان وابسته به توالیمیﺑاشد.
۵-در صنعت تولید بطری،زمان آمادهﺳازی وابسته به اندازه و شکل بطریﻫا میﺑاشد.
بلکریشنان و همکاران[46] یک مدل برنامهﺭیزی مخلوط عدد صحیح فشرده را برای حل مساله ماشینﻫای موازی یکنواخت بکار بردهﺍند.به دلیل اختلافﻫای موجود بین ماشینﻫا،زمان مورد نیاز برای پردازش یک کار از ماشینی به ماشین دیگر تفاوت میﮐند.آنها زمانﻫای آماده سازی وابسته به توالی را نیز در مدل خود در نظر گرفتهﺍند.همچنین آنها فرض کردهﺍند که هر کار زمانﻫای تحویل،زمانﻫای رهاسازی و جریمهﻫای زودکرد و دیرکرد مجزایی دارد.هدف, حداقل کردن کل دیرکرد وزنی و زودکرد وزنی میﺑاشد.آنها نشان دادهﺍند که این مدل قادر به ارائه حل بهینه برای مسائلی با اندازه کوچک(تا۱۰کار) میﺑاشد. آنها برای مسائل با اندازه بزرگ(بیش از۱۰کار) نیز روشی بر اساس قانون تجزیه بندرارائه کرده اند[46].
سیوریکایا و اولسوی[24]یک الگوریتم ژنتیک موثر به منظور حل مساله ماشینﻫای موازی با تابع هدف حداقل کل دیرکرد وزنی و زودکرد وزنی ارائه کردهﺍند.برای مدلسازی واقعیﺗر مساله،آنها فرض کردهﺍند که هر کار زمانﻫای تحویل و زمانﻫای ورود مجزایی دارد.جریمهﻫای زودکرد و دیرکرد با یکدیگر متفاوت بوده ولی برای تمام کارها یکسان در نظر گرفته شدهﺍند((Wj=WE,Vj=WTآنها زمانﻫای آمادهﺳازی وابسته به توالی را نیز در مدل خود در نظر گرفتهﺍند.آنها مساله زمانبندی ماشینﻫای موازی با جریمهﻫای زودکرد و دیرکرد را بصورت PMSP-E/Tنشان دادهﺍند.همچنین آنها فرض کردهﺍند کهMماشین موجود یکی از دو نوع ماشین میﺑاشند. ماشینﻫای متعلق به یک نوع مشابه و ماشینﻫای متعلق به انواع مختلف یکنواخت هستند.تابع هدف مساله عبارت است از:
-32385220345
(2-10)
در تساوی بالاJ نشان دهنده مجموعه کارها وWEوWTبه ترتیب وزنﻫای زودکرد و دیرکرد هستند. Ej=max {0,dj-cj} زودکرد کار jوTj=max {0,dj-cj}دیرکرد کارj می باشد.همچنین cj ,djبه ترتیب موعد تحویل و زمان تکمیل کارj میﺑاشند.دو رویکرد الگوریتم ژنتیک برای این مساله بکار برده شده است،یکی با عملگر تقاطعی که برای حل مسائل بهینهﺳازی ترکیبی چند جزئی ایجاد شده است(مسالهPMSP-E/T نیز یک نمونه از این مسائل است) و دیگری بدون عملگر تقاطع.نتایج آزمایش روی۹۶۰مساله ایجاد شده بصورت تصادفی نشان میﺩهند که الگوریتم ژنتیک یک الگوریتم کارا برای حل مسالهPMSP-E/T میﺑاشد[24].
رادهاکریشنان و ونتورا[20]یک فرمولبندی ریاضی و یک الگوریتم بازپخت شبیهﺳازی شده بمنظور یافتن جوابﻫای نزدیک به بهینه برای مساله زیر ارائه کردهﺍند:
“Nکار وM ماشین در دسترس هستند.بین کارها زمانﻫای آمادهﺳازی وابسته به توالی وجود دارد.همچنین هر کار زمان عملیات و موعد تحویل مجزایی دارد.هدف یافتن بهترین زمانبندی به گونهﺍی است که کل دیرکرد و زودکرد را حداقل کند.مساله را میﺗوان بطور خلاصه بصورت رابطه 2-11نمایش داد.”
lefttop(2-11)
آنها بمنظور تولید جمعیت اولیه از یک روش ابتکاری موثر بهره گرفتهﺍند.سپس با استفاده از نتایج محاسباتی حاصل از مسائل ایجاد شده بصورت تصادفی،نشان دادهﺍند که الگوریتم بازپخت شبیهﺳازی شده, بهبود قابل ملاحظهﺍی در جوابﻫای بدست آمده از روش ابتکاری ایجاد میﮐند.
زو و هدی[47]یک فرمولبندی مخلوط عدد صحیح برای حداقل کردن زودکرد و دیرکرد در یک مساله زمانبندی چند ماشینه ایجاد کردهﺍند.آنها فرض کردهﺍند که زمانﻫای آمادهﺳازی وابسته به توالی بوده و زمانﻫای پردازش, وابسته به ترکیب کار-ماشین باشند.موعدهای تحویل و هزینهﻫای جریمه برای کارهای مختلف متفاوت میﺑاشند.مدل به آسانی برای مسائلی با نه کار و سه ماشین حل بهینه را فراهم میﮐند.بنابراین، فرمولسازی نشان داده شده می تواند راه حلﻫای بهینه لازم برای ایجاد و تعیین اعتبار مقیاس صنعتی،روشﻫای فراابتکاری زودکرد/دیرکرد چند ماشینه فراهم کند که تا این زمان تنها در مقابل سایر روشﻫای فراابتکاری آزموده شده است. آنها پس از بازنگری مقالات تک ماشینه چندین فرض محدودکننده کلیدی بکار برده شده در ادبیات را خلاصه کرده و یک رویکرد چند ماشینه برای مساله زمانبندی ایجاد میﮐنند.آنها اشاره میﮐنند که در نظر گرفتن یک موعد تحویل برای همه کارها برای انواع سیستمﻫای ساخت که همه قطعات ساخته شده باید در یک زمان از قبل تعیین شده برای ساخت آماده باشند،قابل بکارگیری است.
وای و وانگ[3]یک مدل برای زمانبندی کارهای گروهی روی ماشینﻫای موازی مشابه در نظر گرفتهﺍند.مدل فرض میﮐند که زمان آمادهﺳازی وقتی ایجاد میﺷود که یک ماشین از پردازش یک نوع به نوع دیگری بپردازد.هدف در این مدل, حداقل کردن کل جریمهﻫای زودکرد و دیرکرد میﺑاشد. محیط خاص در نظر گرفته شده در اینجا, یک کار تولیدی است کهMماشین موازی مشابه اجزای مختلفی را پردازش میﮐنند.اگر بخشی که باید روی ماشین تولید شود از همان نوعی باشد که قبلا تولید شده است،هیچ زمان آمادهﺳازی مورد نیاز نیست. لیکن اگر این بخش از نوع متفاوتی باشد،آمادهﺳازی ماشین قبل از پردازش لازم است.
توکلی مقدم و همکاران[48] یک مدل برنامهﺭیزی ریاضی برای مساله زمانبندی ماشینﻫای موازی نامرتبط با معیارهای کل زودکرد ودیرکرد و هزینهﻫای ماشین ارائه دادهﺍند. آنها بمنظور حل مساله, از یک الگوریتم ژنتیک موثر استفاده کردهﺍند. عملگرهای جدید تعریف شده در این مقاله, برای الگوریتم مورد نظر, منجر به بهبود زیادی در کیفیت حل میﮔردد. نتایج محاسباتی روی مسائل محققان پیشین, نشان میﺩهند که الگوریتم پیشنهادی به نحو موثری عمل میﮐند.
در یکی از تحقیقات صورت گرفته در زمینه ماشینهای موازی نامرتبط،چن]59[یک الگوریتم ابتکاری بر مبنای atcs، یک الگوریتم تبرید شبیه سازی شده و یک رویه ابتکاری بهبود جوابها برای مسئله ماشینهای موازی نامرتبط با تابع هدف زمانهای دیرکرد کل با محدودیت زمان نصب ماشین وابسته به توالی کارها ارائه نموده است. رویه ATCS توسط لی و پیندو ]60[برای حل مسئله ماشینهای موازی با محدودیت زمان نصب طراحی گردیده است.
یک الگوریتم ژنتیک به همراه یک الگوریتم جستجوی محلی توسط والادا و رویز]61[برای مسئله با تابع هدف زمان پایان کار ماکسیمم ارائه شده و با استفاده از مسائل معیار تولید شده برای اندازه های کوچک و بزرگ مسئله،آزمایشات جامعی صورت گرفته است.نتایج محاسباتی نشان می دهد که این الگوریتم بهترین عملکرد در مقایسه با سایر روشها ی موجود در ادبیات تحقیق این نوع مسائل را داراست
.
2-4-۲- مسائل با تمرکز بر موعد تحویل یکسان برای کارها
مسائل تعیین موعد تحویل در سالﻫای اخیر به دلیل توجه صنعتی به فلسفهJITمورد توجه خاصی قرار گرفتهﺍند.در بسیاری از محیطﻫای عملی از جمله صنعت نساجی،صنایع مکانیکی و صنایع الکترونیکی،مقدار موعد تحویل در طول مذاکرات فروش با مشتری تعیین میﮔردد. در نظر گرفتن موعد تحویل بالا، مساله زمانبندی را آسان نموده و هزینهﻫای دیرکرد و زودکرد را کاهش میﺩهداما نتایج درآمدی مهمی را در پی دارد.رسیدن به موعد تحویل تعیین شده یکی از اهداف اولیه مدیریت میﺑاشد.مدل موعد تحویل یکسان, مطابق با یک سیستم مونتاژ می باشد که در آن اجزای محصول بایستی در یک زمان آماده باشند یا در یک کارخانه که چند محصول تشکیل سفارش مشتری را میﺩهند.
2-4-2-1 موعد تحویل معلوم
چن و پاول[49]یک الگوریتم تجزیه دقیق بر اساس تولید ستونی برای مساله زمانبندیnکار با یک موعد تحویل یکسان غیر محدود کننده روی mماشین موازی یکسان به منظور حداقل کردن کل دیرکرد وزنی و زودکرد وزنی ارائه کردهﺍند. مساله بطور خلاصه بصورت معادله 12-2 نمایش داده میﺷود.آنها ابتدا مساله را بصورت یک برنامه عدد صحیح فرمولبندی کردند.سپس با استفاده از روش تجزیه دانتزیگ_والف مساله را دوباره بصورت دستهﺍی از مسائل جزء بندی شده با محدودیتﻫای مساله اولیه فرمولبندی کردهﺍند.بر اساس این مجموعه مسائل جزء بندی شده، یک الگوریتم حل دقیق شاخه و کران برای مساله توسعه داده شده است.در درخت شاخه و کران هر گره بیانگر یک مساله از مجموعه مسائل جزء بندی شده میﺑاشد. پس مساله موجود در هر گره با استفاده از روش تولید ستونی حل گردیده است.در این روش, ستونﻫا بیانگر طرحﻫای جزئی روی تک ماشین بوده و با استفاده از حل دو زیر مساله تولید میﮔردند.نتایج محاسباتی بیانگر این هستند که این الگوریتم تجزیه قادر به حل مسائلی با ۶۰کار در زمانی معقول می باشد.
lefttop(2-12)
بنک و ورنر[50]روش حل دقیقی برای مساله زمانبندیm ماشین موازی نامرتبط ارائه کردهﺍند.مساله بدین صورت می باشد که مجموعه ای از nکار بایستی بدون انقطاع روی یکی ازm ماشین نامرتبط انجام شوند.هر کار, یک زمان ورود و یک زمان انجام عملیات دارد.زمان عملیات هر کار بستگی به ماشینی که کار روی آن انجام می شود،دارد. هدف،توزیع کارها روی ماشینﻫا و زمانبندی کارهای تخصیص داده شده به هر ماشین به گونه ای است که مجموع دیرکرد وزنی و زودکرد وزنی حداقل گردد.
فرض در دسترس بودن همه کارها در زمان صفر یک انحراف مهم از واقعیت میﺑاشد. بنابراین, در این مقاله این فرض حذف شده است.از طرفی هنگامی که هر کار زمان ورود مجزایی داشته باشد, پیچیدگی مساله حتی برای حالت تک ماشینه نیز بسیار بالا میﺭود.بنابراین تلاش در یافتن جوابﻫای نزدیک به بهینه در این شرایط امری معقول میﺑاشد. به این علت, آنها تعدادی خواص بنیادی بمنظور بدست آوردن یک حل تقریبی برای مساله ارائه کردهﺍند.سپس آنها تعدادی الگوریتم سازنده و بهبود دهنده عرضه کردهﺍند.کارایی این الگوریتمﻫا روی مسائلی با۲۰ماشین و۵۰۰کار تست شده است.
سان و وانگ[51]یک الگوریتم برنامهﺭیزی پویا به منظور حل مساله ماشینﻫای موازی یکسان با وزنﻫای نسبی ارائه کردهﺍند.n کار مستقل بایستی رویm ماشین موازی یکسان انجام شوند.کار Ji دارای زمان عملیاتpi و وزن wi میﺑاشد. تمام کارها موعد تحویل یکسان d دارند.هدف, حداقل کردن عبارت زیر میﺑاشد:
0-48260(2-13)
آنها نشان داده اند که مساله NP-hardمیﺑاشد.سپس یک الگوریتم برنامهﺭیزی پویا بمنظور حل آن ارائه کردهﺍند.
مونچ و آنبهان[52]سه روش ابتکاری تجزیه ای برای حل مساله pm/di=d,batch/ET ارائه کردهﺍند.
مساله مورد بررسی توسط آنها عبارت است از:
2813050692785″n کار بایستی روی m کوره پخت موازی یکسان انجام شوند. زمان انجام کار j باp j نشان داده می شود. همه کارها یک موعد تحویل یکسان غیرمحدودکننده d دارند که مقدار آن معلوم می باشد. بنابراین فرض می شود رابطه برقرار باشد.
بمنظور حل مساله آنها یک الگوریتم تجزیه شامل دو فاز اصلی معرفی کردهﺍند. فاز اول,مرحله تخصیص میﺑاشد. در این مرحله, کارها یا به یک تک ماشین تخصیص داده میﺷوند (در این شرایط هر کار میﺗواند دیرکرد یا زودکرد داشته باشد)یا به مجموعه کارهای دارای دیرکرد یا زودکرد روی هر ماشین تقسیمﺑندی میﺷوند. فاز دوم،مرحله دستهﺑندی و زمانبندی کارها میﺑاشد. دستهﺑندی و زمانبندی کارها بطور هم زمان رخ میﺩهد. آنها, سه روش ابتکاری مختلف ارائه کرده و سپس کارایی آنها را با یکدیگر مقایسه کردهﺍند. روش ابتکاری اول, داخلی بوده و بر اساس نتایج بنیادین بیان شده در مقاله ایجاد شده است. در این روش, پس از تخصیص کارها به ماشینﻫا از یک فرمولبندی برنامهﺭیزی پویا بمنظور تشکیل دستهﻫا استفاده شده و سپس با استفاده از نتایج بنیادین اثبات شده در مقاله, یک توالی از دستهﻫا روی ماشینﻫا تعیین میﮔردد. این روش ابتکاری PBHPنامیده میﺷود. روشﻫای ابتکاری دوم و سوم, از الگوریتم ژنتیک بمنظور تجزیه مساله دستهﺑندیm ماشین موازی به m مساله دستهﺑندی تک ماشینه استفاده میﮐنند. روش ابتکاری دوم, با عنوان روش GAPBHمعرفی شده است. این روش, ابتدا کارها را به ماشینﻫا تخصیص داده و سپس با توجه به این امر که هر کار روی هر ماشین دیرکرد دارد یا زودکرد کارها را به دو دسته کارهای دارای دیرکرد و کارهای دارای زودکرد تقسیمﺑندی میﮐند. سپس از این کارها دستهﻫای دارای دیرکرد و دارای زودکرد را تشکیل داده و سپس به تعیین توالی دستهﻫا روی ماشینﻫا میﭘردازد. سپس از الگوریتم ژنتیک بمنظور بهبود توالی ارائه شده و در نتیجه مقدار تابع هدف استفاده میﮐند. روش ابتکاری سوم که تحت عنوان GABABSHمعرفی گردیده, ابتدا کارها را به مجموعهﻫای دارای دیرکرد و زودکرد تخصیص داده و سپس از این مجموعهﻫا دستهﻫای دارای دیرکرد یا زودکرد را تشکیل میﺩهد. پس از آن, عملکرد روش سوم دقیقا مشابه روش دوم میﺑاشد.بطور کلی روش اول, برای اندازه کارهای بزرگ بهتر از دو روش دیگر عمل میﮐند. اما هنگامی که اندازه کارها کوچک یا متوسط باشد, روشﻫای دوم و سوم بدلیل امکانات جستجوی بهتر به نتایج بهتری دست می یابند[52].
2-4-2-2- موعد تحویل نامعلوم
پانوالکر و همکاران[53]مساله کلاسیک زمانبندی تک ماشینه و تخصیص موعد تحویل)این مساله بصورت خلاصه مسالهpss گفته می شود که خلاصه ای از اسامی پایه گذاران آن می باشد(را بصورت زیر تعریف می کنند:
“n کار موجود یک موعد تحویل یکسان دارند که بایستی تعیین گردد.کارها قبل یا بعد از تعیین یک موعد تحویل روی یک ماشین تکمیل می گردند.این موعد تحویل جزئی از تابع هزینه میﺑاشد.مقدار جریمه مربوط به موعد تحویل خطی بوده و مستقل از کارها میﺑاشد. هدف, یافتن مقدار بهینه موعد تحویل و توالی بهینه کارها روی ماشین به گونه ای است که مجموع دیرکرد و زودکرد و هزینه مربوط به موعد تحویل حداقل گردد.”
آداموپولوس و پاپیس[54]مساله زمانبندیn کار مستقل را روی m پردازنده موازی غیریکسان تحت یک موعد تحویل یکسان و نامعلوم برای کارها بررسی کردهﺍند.موعد تحویل یک متغیر تصمیممیﺑاشد.هدف, تخصیص کارها به ماشینﻫا و تعیین موعد تحویل به گونهﺍی است که کل هزینه حداقل شود.این هزینه ترکیبی از موعد تحویل نامعلوم و کل دیرکرد و زودکرد میﺑاشد.از آنجا که مساله NP-hard میﺑاشد, یک روش ابتکاری چندجمله ای بر حسب زمان برای حل آن توسعه داده شده است.این روش راه حلﻫای موثری برای مساله میﻳابد.این روش, روی یک مساله نمونه تولید شده بصورت تصادفی تست گردیده و کارایی آن نشان داده شده است.
بیسکپ و چنگ[55]مساله زمانبندیn کار مستقل را رویm ماشین موازی بررسی کردهﺍند.آنها فرض کردهﺍند که شرکتﻫا دو هدف را در نظر دارند.یکی رسیدن به انحراف کم از موعد تحویل یکسان برای همه کارها و دیگری حداقل کردن زمان تکمیل کل کار.بنابراین هدف یافتن زمانبندی بهینه کارها روی ماشینﻫا و موعد تحویل یکسان بهینه برای تمامی کارها به گونهﺍی است که ترکیبی از کل دیرکرد و زودکرد وزنی و زمان اتمام حداقل شود.آنها نشان دادهﺍند که مساله NP-hardبوده و سپس یک نمونه قابل حل چند جملهﺍی بر حسب زمان برای آن ارائه دادهﺍند.سپس یک روش ابتکاری بمنظور یافتن جوابهای نزدیک به بهینه برای این مساله توسعه داده شده و کارایی آن با استفاده از نتایج محاسباتی بدست آمده از چند مساله نمونه اثبات گردیده است.
موشیو[56]مساله زمانبندی کارها و تخصیص موعد تحویل را برای ماشینﻫای موازی یکسان حل کرده است.مساله بصورت زیر می باشد.
“Nکار قرار است رویMماشین موازی یکسان انجام شوند.همه کارها در زمان صفر در دسترس بوده و همگی دارای موعد تحویل dمیﺑاشند که بایستی مقدار بهینه آن تعیین گردد.زمان بیکاری برای ماشینﻫا مجاز بوده ولی انقطاع کارها مجاز نمیﺑاشد.هدف یافتن زمانبندی و موعد تحویل به گونه ای است که مقدار Z(q,d)=min{WEmaxEj,WTmaxTj,Wdd} بهینه گردد.
تابع هدف از نوع minmaxمیﺑاشد. آنها روی معرفی یک الگوریتم ابتکاری برای حل این مساله NP-hard متمرکز شده اند.این الگوریتم ابتکاری شامل دو مرحله می باشد.در مرحله اول, یک زمانبندی بر اساس قاعده LPTبرای کارها ارائه گردیده و در مرحله دوم, مساله تخصیص موعد تحویل برای زمانبندی ایجاد شده در مرحله اول بررسی میﮔردد. سپس آنها یک حد پایین برای تابع هزینه یافتهﺍند. سپس نشان دادهﺍند که این روش ابتکاری(حد پایین) تحت چندین فرض عمومی مجانبا بهینه میﺑاشد. سپس آنها با استفاده از یکسری مطالعه عددی وسیع نشان دادهﺍند که الگوریتم ابتکاری و حد پایین ایجاد شده توسط آنها نتایج اجرایی بسیار خوبی را نشان میﺩهند.
موشیو و یاول[57]مساله ای از توالی یک مجموعه کارهای مستقل روی یک مجموعه از ماشینﻫای موازی یکسان و تخصیص موعد تحویل به کارها را با هدف حداقل کردن مجموع دیرکرد وزنی و زودکرد وزنی و هزینه موعد تحویل در نظر میﮔیرند.آنها مسالهGPSS(UJ) را در نظر میﮔیرند.این مساله برای حالت تک ماشینه میﺗواند بصورت زیر بیان شود:
“nکار مستقلJبایستی روی یک ماشین پردازش گردند.کارها در زمان صفر در دسترس هستند.موعد تحویل همه کارها که یک متغیر تصمیم میﺑاشد یکسان بوده و باdنمایش داده میﺷود.زمان عملیات کارj با pj نشان داده می شود. فرض میﮔردد که این مقدار برای همه کارها برابر با واحد باشد.سه جزء هزینه در نظر گرفته میﺷود.یکی برای زودکرد،یکی برای دیرکرد و دیگری برای موعد تحویل.هزینه هر واحد زودکرد کارj و هزینه هر واحد دیرکرد آن به ترتیب با Bj ,ajنشان داده میﺷود.جریمه هر واحد تعویق موعد تحویل بانشان داده میﺷود.تابع هدفی که بایستی حداقل گردد،بصورت رابطه 2-14می باشد.با استفاده از روش استاندارد سه پارامتری مساله بصورتمعادله2-15بیان می گردد

(2-14)
(2-15)
آنها نشان دادهﺍند که کل زمان مورد نیاز برای حل مساله GPSS(UJ) برای تک ماشین O(n2) میﺑاشد.این مقدار برایm ماشین موازی یکسان نیز صدق میﮐند.آنها همچنین مسالهTWET(UJ) را در نظر میﮔیرند.این مساله مشابه مساله GPSS(UJ) میﺑاشد با این تفاوت که در آن مقداربرابر با صفر در نظر گرفته میﺷود.با استفاده از روش استاندارد سه پارامتری مساله بصورترابطه 2-16بیان میﮔردد.آنها یک الگوریتم( O(n3برای حالت تک ماشینه و یک الگوریتمO(n3) برای حالت mماشین موازی یکسان ارائه کردهﺍند.
(2-16)
آنها یک الگوریتم O(n4(n*logn)) برای حالت تک ماشینه برای حل مسالهGMWAL(UJ) ارائه کرده اند.این مساله مشابه مسالهGPSS(UJ) می باشد با این تفاوت که در آن تابع هدف بصورتminmax در نظر گرفته میﺷود.با استفاده از روش استاندارد سه پارامتری مساله برای حالت تک ماشین بصورت معادله 2-17بیان میﮔردد:

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

« (Previous Post)
(Next Post) »

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *