چکیده
در یک محیط زمانبندی تولید بهموقع، یک کار اگر زودتر از موعد تحویلش تکمیل شود باید در انبار کالا نگهداری شود در حالیکه یک کار دیرتر از موعد تحویلش تکمیل شود ممکن است باعث از دست رفتن مشتری شود. بنابراین، یک زمانبندی زمانی ایدهال است که همهی کارها دقیقا در موعد تحویلشان به پایان برسد. در این مطالعه، مسئله زمانبندی ماشینهای موازی یکنواخت با محدودیتهای مجموعه پردازش و زمان آماده سازی وابسته به توالی و تاثیر یادگیری برای حداقل کردن مجموع زودکرد ودیرکرد در نظر گرفته شده است. برای مسئله مورد نظر یک مدل ریاضی طراحی کرده و برای حل مدل با اندازه های واقعی، الگوریتمهای ژنتیک و ازدحام ذرات و تبرید شبیهسازیشده را بکار بردیم. سرانجام، نتایج محاسباتی نشان میدهد که الگوریتم بهینهسازی ازدحام ذرات از دو الگوریتم دیگر بهتر عمل می کند.
کلمات کلیدی: زمانبندی بهموقع، ماشینهای موازی یکنواخت، زمان آماده سازی وابسته به توالی، تاثیر یادگیری و محدودیت مجموعه پردازش
فهرست مطالب
.. 1
1-1. مقدمه. 2
1-2. تعریف مسئله. 3
1-3. اهداف تحقیق.. 5
1-4. مفروضات مسئله. 6
1-5. جنبه های نوآوری تحقیق.. 6
1-6. محتویات تحقیق.. 7
… 8
2-1. مقدمه. 9
2-2. زمان آماده سازی وابسته به کار قبلی.. 10
2-3. تاثیر یادگیری.. 13
2-4. محدودیت مجموعه پردازش… 17
2-5. زمانهای زودکرد و دیرکرد 19
2-6. نتیجه گیری.. 20
.. 21
3-1. مقدمه. 22
3-2. تعریف مسئله. 22
3-3. مفروضات مسئله. 23
3-4. مدل پیشنهادی.. 24
3-5. اعتبارسنجی مدل. 27
3-6. پیچیدگی مسئله. 31
3-7. نتیجه گیری.. 33
.. 34
4-1. مقدمه. 35
4-2. الگوریتم ژنتیک… 37
4-2-1. واژگان الگوریتم ژنتیک… 39
4-2-2. کدگذاری.. 40
4-2-3. جمعیت اولیه. 41
4-2-4. تابع شایستگی.. 41
4-2-5. عملگرهای ژنتیک… 41
4-2-5-1. عملگر انتخاب… 41
4-2-5-2. عملگر تقاطع. 43
4-2-5-3. عملگر جهش… 44
4-2-6. شرط توقف… 44
4-3. الگوریتم ازدحام ذرات… 45
4-3-1. ساختار کلی.. 45
4-3-2. مفاهیم پایهای الگوریتم ازدحام ذرات… 47
4-3-3. بهروز رسانی سرعت… 47
4-3-3-1. پارامتر شخصی c1 و پارامتر جمعی c2. 49
4-3-3-2. پارامتر وزن اینرسی.. 49
4-3-4. بهروز رسانی موقعیت… 49
4-4. تبرید شبیهسازیشده 50
4-4-1. مفاهیم الگوریتم تبرید شبیهسازیشده 52
4-5. الگوریتمهای پیشنهادی.. 54
4-5-1. تولید جامعه اولیه و نحوه نمایش کروموزومها 55
4-5-2. اجرای الگوریتم ژنتیک… 56
4-5-2-1. عملگر تقاطع. 57
4-5-2-2. عملگر جهش… 58
4-5-3. اجرای الگوریتم بهینهسازی ازدحام ذرات… 59
4-5-3-1. تعیین سرعت… 61
4-5-3-2. عمل جهش… 61
4-5-3-3. موقعیت جدید. 62
4-5-4. اجرای الگوریتم تبرید شبیهسازیشده 64
4-5-4-1. تعیین دمای اولیه. 65
4-5-4-2. تعیین دمای نهایی.. 66
4-5-4-3. روش کاهش دما 66
4-5-4-4. روش همسایگی.. 66
4-6. مجموعه داده ها 67
4-7. تنظیم پارامترها 68
4-7-1. اندازه جامعه اولیه. 69
4-7-2. تقاطع. 71
4-7-3. نرخ جهش… 71
4-7-4. حداکثر تعداد نسلها 71
4-8. تنظیم پارامتر چندعاملی.. 72
4-9. ارزیابی الگوریتمها 79
4-10. جمعبندی.. 90
… 91
.. 95
فهرست جداول
جدول 3-1. اطلاعات مسئله ساخته شده 28
جدول 3-2. زمانهای آماده سازی مسئله ساخته شده 29
جدول 3-3. زمان پردازش(ثانیه) 29
جدول 3-4. موعدهای تحویل (ثانیه) و هزینه زودکرد و دیرکرد. 30
جدول 3-5. زمان آماده سازی ماشین (ثانیه) 30
جدول 4-1. چیدمان کارها 56
جدول 4-2. خلاصهی داده ها 68
جدول 4-3. پارامترهای کنترل کننده الگوریتم ژنتیک و محدوده موثر آن. 71
جدول 4-4. فاکتورها و سطوح آنها 72
جدول 4-5. ترکیب فاکتورها و سطوح پاسخ مربوطه در آزمایشات چندعاملی.. 73
جدول 4-6. ضرایب همبستگی تخمینی مدل برای نسبتهای SN… 74
جدول4-7. آنالیز واریانس برای نسبتهای SN… 74
جدول 4-8. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها 75
جدول4-9. آنالیز واریانس برای میانگین پاسخها 75
جدول4-10. پاسخ SN… 76
جدول4-11. پاسخ میانگینها 76
جدول 4-12. مقادیر تنظیم شدهی پارامترهای ژنتیک… 78
جدول 4-13. مقادیر تنظیم شدهی پارامترهای تبرید شبیهسازیشده 78
جدول 4-14. مقادیر تنظیم شدهی پارامترهای الگوریتم ازدحام ذرات… 78
جدول 4-15. خلاصه مسائل.. 79
جدول 4-16. مسائل با اندازه کوچک… 80
جدول 4-17. مسائل با اندازه متوسط.. 81
جدول 4-18. مسائل با اندازه بزرگ… 82
جدول 4-19. مقدار PRE و زمان حل برای سطح کوچک… 84
جدول 4-20. مقدار RPD و زمان حل برای سطح متوسط.. 85
جدول 4-21. مقدار RPD و زمان حل برای سطح بزرگ… 86
جدول 4-22. میانگین زمان حل و RPD برای تعداد مختلف کارها 88
جدول 4-23. مجموع مقایسه شدهی پارامتر الگوریتمها 89
جدول 4-24. درصد جوابهای بهتر الگوریتمها 89
فهرست اشکال
شکل 3-1. سلسله مراتب پیچیدگی محیطهای کاری ]57[ 32
شکل 3-2. سلسله مراتب پیچیدگی توابع هدف ]57[ 32
شکل4-1. نمای کلی الگوریتم ژنتیک کلاسیک… 39
شکل 4-2. نمایش کروموزوم. 56
شکل 4-3. عملیات تقاطع. 58
شکل 4-4. جهش نوع اول. 58
شکل 4-5. جهش اول نوع دوم. 59
شکل 4-6. جهش دوم نوع دوم. 59
شکل4-7. تغییر موقعیت ذره 62
شکل4-8. تغییر موقعیت ذره همراه با اصلاحیات… 63
شکل4-9. تغییر موقعیت ذره با توجه به محدودیت پردازشی.. 64
شکل4-10. کیفیت جوابها و اندازه جامعه. 70
شکل4-11. زمان محاسباتی و اندازه جامعه. 70
شکل4-12. پاسخ میانگینها 77
شکل4-13. پاسخ ضرایب SN… 77
شکل 4-14. نمودار میانگین و فواصل LSD… 87
شکل 4-15. RPD برای تعداد مختلف کارها 88
فصل اول
کلیات تحقیق
1-1. مقدمه
برنامه ریزی و زمانبندی[1] یک فعالیت بسیار معمول در صنعت و عملیات غیرصنعتی است. هر روز، جلسات برنامه ریزی میشوند. ضربالعجلهایی برای انجام پروژه ها و کارها تعیین می شود. خدمات تعمیر و نگهداری و عملیات برنامه ریزی میشوند. بازیهای ورزشی برنامه ریزی و زمانبندی میشوند.
برنامه ریزیهای مناسب اجازه میدهد تا فعالیتهای مختلف، شغلها و یا وظایف به شیوهای سازمانیافته اجرا شوند. نمونه ای از این فعالیتها میتوان به مراحل مختلف یک پروژه تحقیقاتی، وظایف یک پرستار در طول یک روز کاری، عملیات تولید و موارد دیگر اشاره کرد که می تواند هدفهایی همچون به حداقل رساندن زمان تکمیل کارها، حداقل کردن تاخیر فعالیتهایی که نمیتوانند به موقع تکمیل شوند و دیگر موارد را به دنبال داشته باشد.
دلیل بسیاری از پیشرفتهای علم زمانبندی بواسطه محیطهای صنعتی و استفاده این علم در صنعت است. به طور طبیعی در بیان مفاهیم زمانبندی از واژه های بکار رفته در صنعت استفاده می شود. که در آن منابع با عنوان ماشین و فعالیتها به عنوان کار شناخته میشوند. بطوریکه کارها اغلب به وسیله مجموعه ای از ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند.
در مسائل زمانبندی تخصیص مناسب کارها به ماشینها با توجه به محدودیتهای موجود و رسیدن به یک جواب مناسب از اهمیت خاصی برخوردار است. کوچکترین مسئله زمانبندی را میتوان مسئله تکماشینه[2] عنوان کرد. در این مسئله یک ماشین وجود دارد که عموما در مسائل به عنوان گلوگاه شناخته می شود و باید کارها را به این ماشین با توجه به محدودیتهای موجود طوری اختصاص داد که به یک جواب معقول و مناسب برسیم و حداکثر کارایی را داشته باشیم. حالت بزرگتر مسائل زمانبندی، زمانبندی مسائل چندماشینه شامل سیستمهای موازی، سیستمهای متوالی و سیستمهای ترکیبی میباشند. در سیستمهای موازی چندین ماشین به صورت موازی در کنار هم قرار گرفتهاند و هر کار بر روی یکی از ماشینها پردازش می شود. ولی در سیستمهای متوالی و ترکیبی، کارها با انجام چند عملیات بر روی ماشینها پردازش میشوند و ساختار پیچیدهتری نسبت به مسائل دیگر دارند.
در این تحقیق، به بررسی مسئله زمانبندی ماشینهای موازی با سرعتهای مختلف[3] پرداخته می شود. مسائل ماشینهای موازی با سرعتهای مختلف حالت عمومی یافته مسائل تکماشینه و حالت خاصی از مسائل ماشینهای متوالی منعطف محسوب میشوند. در بخشهای آتی این فصل، شرح تفصیلی مسئله مورد بررسی این تحقیق ارائه می شود.
1-2. تعریف مسئله
ماشینهای موازی به عنوان یکی از زیرمجموعههای اصلی و پایه در زمانبندی از جایگاه ویژه ومهمی برخوردارند و همواره زمانبندی این مدل بر مبنای معیارهای عملکرد مختلف مورد نظر بوده است. با این توجه که، عموم روشهای حل در مدلهای پیچیده تر مانند مدل ماشینهای متوالی منعطف بر مبنای راهکارهای مدلهای سادهتر از جمله ماشینهای موازی استوار است ]1[.
در کارخانهها وقتی ماشینها و دستگاههای جدید خریداری میشوند و در کنار ماشینهای قدیمی قرار میگیرند، تفاوت سرعت بین ماشینهای جدید و قدیمی بوجود می آید که این تفاوت سرعت، مسئله چندین ماشین با سرعتهای متفاوت را بوجود میآورد.
در برخی از محیطهای کاری زمانبندی ماشینهای موازی با سرعت متفاوت، ممکن است که تمامی ماشینها نتوانند تمامی کارها را پردازش کنند که در این حالت هر کار توسط مجموعه ای از ماشینها می تواند انجام شود که به آن محدودیت مجموعه پردازش[4] میگویند.
در بسیاری از محیطهای کاری انسان به عنوان عنصر اصلی بهشمار میرود. در فعالیتهایی که انسان در آن سهم بسزایی دارد مسئله یادگیری بسیار مهم است و تاکنون در اکثر مقالات فرض رایج بر این بوده که زمان پردازش کارها ثابت و مستقل از توالی است. درحالیکه در بسیاری از موارد عملی با تکرار کارهای مشابه (و یا متفاوت)، توانایی ومهارت اپراتور افزایش و در نتیجه آن، زمان پردازش کارها کاهش مییابد. این امر باعث بهبود مستمر عملکرد تسهیلات تولیدی مخصوصا نیروی انسانی می شود که به آن تأثیر یادگیری[5] میگویند. که از جمله این فعالیتها میتوان به تمامی کارهایی که سیستم دستی را شامل می شود مثلا راهاندازی ماشینآلات، تمیز کردن ماشین و زمان آماده سازی[6] اشاره کرد .
در مسائل زمانبندی کلاسیک عموما با درنظر گرفتن این فرض که زمانهای آماده سازی در مقایسه با زمان پردازش کوچک و یا اینکه مستقل از توالی پردازش کارها بر روی ماشینها هستند، زمان آماده سازی را نادیده گرفته و یا آن را به زمان پردازش اضافه میکردند. اما با اینوجود، در بسیاری از محیطهای صنعتی یک زمان آماده سازی وابسته به توالی[7] هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد ]17[. در این شرایط، زمان آماده سازی به عنوان بخشی مجزا از زمان پردازش در نظر گرفته می شود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به نوع کار قبلی که بر روی ماشین پردازش شده نیز بستگی دارد. تلقی زمان آماده سازی به صورت مجزا از زمان پردازش در بیشتر تکنیکهای مدیریت تولید نوظهور نظیر تولید بهموقع[8]، تکنولوژی گروهی[9] و تولید سلولی[10] مورد استفاده قرار میگیرد.
در محیطهای کسب و کار حاضر، رقابت شرکتهای تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع زمینه تجاری و تولید محصولات با کیفیت بالاتر و هزینهای کمتر تعیین می شود. یکی از راههای رسیدن به این منظور استفاده از مفهوم تولید بهموقع است ]2[. در محیط تولید بهموقع، شرکتها تمایل دارند که تا حدامکان زمان تکمیل کارهایشان به موعد تحویل نزدیک باشد تا از جریمههای زودکرد و دیرکرد بکاهند. در صورتی که یک کار قبل از موعد تحویل تکمیل شود، باید تا موعد تحویل در انبار نگهداری شود لذا هزینه زودکرد به سیستم تحمیل می شود. جریمههای زودکرد به آن دلیل مورد توجه هستند که تا زمانیکه موعد تحویل مشتری فرا برسد، هزینه نگهداری شامل هزینه فساد مواد اولیه (در حالیکه کالاها فاسد شدنی هستند) به سیستم تحمیل می شود. و اگر یک کار بعد از موعد تحویل تکمیل شود، جریمه دیرکرد ناشی از نارضایتی مشتری، جریمه قراردادی یا جریمه از دست دادن اعتبار ایجاد می شود.
در این تحقیق، مسئله ماشینهای موازی با سرعتهای مختلف با در نظر گرفتن محدودیتهای زمان آماده سازی وابسته به کار قبلی، محدودیت مجموعه پردازش و تأثیر یادگیری با هدف کمینهسازی زمانهای زودکرد و دیرکرد کل بررسی می شود. یک مدل برنامه ریزی عدد صحیح برای این مسئله پیشنهاد می شود. همچنین الگوریتمهای ژنتیک[11] و بهینهسازی ازدحام ذرات[12] و تبرید شبیهسازیشده[13] برای حل آن ارائه میگردد.
1-3. اهداف تحقیق
تحقیق حاضر با هدف کاهش فاصله میان پیشرفتهای تئوریک و کاربردهای صنعتی در حوزه علم زمانبندی صورت گرفته است. دراین راستا، یک مدل جدید برای مسئله ماشینهای موازی با سرعتهای متفاوت با محدودیتهای زمان آماده سازی وابسته به توالی، محدودیت مجموعه پردازش و تأثیر یادگیری و معیار بهینهسازی زمانهای زودکرد و دیرکرد کل ارائه می شود. بهعلاوه سه الگوریتم ژنتیک، ازدحام ذرات و تبرید شبیهسازیشده به منظور حل این مدل ارائه میگردد.
1-4. مفروضات مسئله
مفروضات زیر در ارائه مدل مسئله در نظر گرفته می شود:
- تأثیر یادگیری بر زمان پردازش کارها در نظر گرفته شده است.
[دوشنبه 1399-10-01] [ 01:32:00 ب.ظ ]
|