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

–146

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

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

سپاس خدای را که سخنوران در ستودن او ناتوان بمانند و شمارندگان شمردن نعمتهای او ندانند…
بدون تردید جایگاه معلم والاتر از آن است که در مقام قدردانی از زحمات دلسوزانه او، با زبان قاصر و دست ناتوان، چیزی بنگارم. انسان ارزشمند کسی است که بسی بیش از آنچه از زندگی میگیرد بدان میبخشد که این شایستهترین توصیف از مقام والای آموزگاری است. فرصت را غنیمت شمرده و مراتب سپاس و قدردانی خود را از اساتید محترم و ارجمند آقایان دکتر جواد رضائیان و دکتر بابک شیرازی به پاس زحمات و راهنماییهای روشنگر ایشان در راه تهیه این پایان‌نامه ابراز مینمایم.

تقدیم به مهربان فرشتگانی که
لحظات ناب باور بودن، لذت و غرور دانستن، جسارت خواستن، عظمت رسیدن، شکوه آفرینش و تمام تجربههای یکتا و زیبای زندگیم، مدیون حضور سبز آنهاست
تقدیم به خانواده عزیزم.

چکیده
زمانبندی و توالی عملیات نوعی فرآیند تصمیمگیری است که با هدف بهینهسازی یک یا چند معیار، بهدنبال تخصیص بهینه منابع محدود به تعدادی کار در طول افق زمانبندی است و نقشی حیاتی در بقای سیستمهای تولیدی و خدماتی ایفا میکند. در تحقیق پیش رو، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض دسترسی محدود به ماشینها، زمانهای نصب وابسته به توالی و وابسته به نوع ماشین و احتمال تولید اقلام فاقد کیفیت مورد بررسی قرار میگیرد. از فرآیندهای دوبارهکاری با هدف رساندن سطح کیفی اقلام معیوب به یک سطح قابل قبول استفاده میشود. بهمنظور مدلسازی مسئله یاد شده، یک مدل ریاضی پیشنهاد و از معیار بیشینه زمان تکمیل کارها بهعنوان تابع هدف در مسئله موردنظر استفاده شده است. از آنجایی که این مسئله از لحاظ پیچیدگی در دسته مسائل Strongly NP-hard جای میگیرد، در نتیجه الگوریتمهای دقیق از کارایی لازم برای حل مسائل در ابعاد متوسط و بزرگ برخوردار نیستند. بنابراین، بهمنظور یافتن جوابهای بهینه و یا نزدیک به بهینه از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم زنبورعسل استفاده شده است. در حل مسائل با ابعاد کوچک که حتی در بعضی موارد از پیچیدگی بالایی برخوردار هستند، مقادیر بدست آمده از الگوریتمهای ژنتیک و زنبورعسل با جوابهای بهینه مقایسه شده است که نتایج حاکی از آن است که الگوریتمهای یاد شده قادر به تولید جوابهایی به خوبی جوابهای بدست آمده از الگوریتمهای دقیق در یک زمان محاسباتی بسیار کوتاهتر میباشند.
واژههای کلیدی: ماشینهای موازی نامرتبط، فرآیندهای دوبارهکاری، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشین، دسترسی محدود به ماشینها

TOC o “2-3” h z t “Heading 1,1,Style1,1,Style2,1” فصل اول PAGEREF _Toc374706664 h 1کلیات تحقیق PAGEREF _Toc374706665 h 11-1. مقدمه PAGEREF _Toc374706666 h 21-2. تعریف مسئله PAGEREF _Toc374706667 h 31-3. اهداف تحقیق PAGEREF _Toc374706668 h 61-4. مفروضات عمومی مسئله PAGEREF _Toc374706669 h 61-5. ضرورت انجام تحقیق PAGEREF _Toc374706670 h 61-6. محتویات تحقیق PAGEREF _Toc374706671 h 7فصل دوم PAGEREF _Toc374706672 h 8مرور ادبیات و پیشینه تحقیق PAGEREF _Toc374706673 h 82-1. مقدمه PAGEREF _Toc374706674 h 92-2. محیطهای کارگاهی PAGEREF _Toc374706675 h 112-2-1. تک ماشینه PAGEREF _Toc374706676 h 112-2-2 . ماشینهای موازی PAGEREF _Toc374706677 h 112-2-2-1. ماشینهای موازی یکسان PAGEREF _Toc374706678 h 112-2-2-2. ماشینهای موازی یکنواخت PAGEREF _Toc374706679 h 112-2-2-3. ماشینهای موازی نامرتبط PAGEREF _Toc374706680 h 122-2-3 . جریان کارگاهی PAGEREF _Toc374706681 h 122-2-4 . جریان کارگاهی منعطف PAGEREF _Toc374706682 h 122-2-5 . کار کارگاهی PAGEREF _Toc374706683 h 122-2-6 . کار کارگاهی منعطف PAGEREF _Toc374706684 h 122-2-7 . سیستم کارگاهی باز PAGEREF _Toc374706685 h 132-2-8 . سیستم ساخت انعطاف پذیر PAGEREF _Toc374706686 h 132-2-9. سیستم کارگاهی وابسته PAGEREF _Toc374706687 h 132-3. جزئیات و محدودیتهای نحوه پردازش کارها PAGEREF _Toc374706688 h 132-3-1. زمان دسترسی به کار rj PAGEREF _Toc374706689 h 132-3-2. زمان نصب وابسته به توالی Sijk PAGEREF _Toc374706690 h 142-3-3. شکست در کارها prmp PAGEREF _Toc374706691 h 142-3-4. اولویت در پردازش کارها prec PAGEREF _Toc374706692 h 142-3-5. خرابی ماشین brkdwn PAGEREF _Toc374706693 h 142-3-6. دسترسی محدود به ماشینها Mj PAGEREF _Toc374706694 h 142-3-7. جایگشت prmu PAGEREF _Toc374706695 h 142-3-8. بلوکه شدن block PAGEREF _Toc374706696 h 152-3-9. بدون انتظار nwt PAGEREF _Toc374706697 h 152-3-10. گردش مجدد rcrc PAGEREF _Toc374706698 h 152-3-11. گروههای کاری fmls PAGEREF _Toc374706699 h 152-3-12. پردازش دستهای batch(b) PAGEREF _Toc374706700 h 152-4. توابع هدف PAGEREF _Toc374706701 h 162-4-1. بیشینه زمان تکمیل کارها Cmax PAGEREF _Toc374706702 h 162-4-2. بیشینه زمان تاخیر کارها Lmax PAGEREF _Toc374706703 h 162-4-3. مجموع زمان تکمیل کارها Cj PAGEREF _Toc374706704 h 162-4-4. مجموع وزنی زمان تکمیل کارها WjCj PAGEREF _Toc374706705 h 162-4-5. مجموع زمان دیر کرد کارها Tj PAGEREF _Toc374706706 h 162-4-6. مجموع وزنی زمان دیرکرد کارها WjTj PAGEREF _Toc374706707 h 162-4-7. مجموع تعداد کارهای با تاخیر Uj PAGEREF _Toc374706708 h 172-4-8. مجموع وزنی تعداد کارهای با تاخیر WjUj PAGEREF _Toc374706709 h 172-4-9. مجموع زمانهای زودکرد و دیرکرد کارها Ej+Tj PAGEREF _Toc374706710 h 172-4-10. مجموع وزنی زمانهای زودکرد و دیرکرد کارها WjEj+W’jTj PAGEREF _Toc374706711 h 172-5. پیشینه تحقیق PAGEREF _Toc374706712 h 172-6. ماشینهای موازی نامرتبط PAGEREF _Toc374706713 h 182-7. دوبارهکاری PAGEREF _Toc374706714 h 212-8. زمان نصب وابسته به توالی کارها PAGEREF _Toc374706715 h 242-9. دسترسی محدود به ماشینها PAGEREF _Toc374706716 h 272-10. جمع بندی PAGEREF _Toc374706717 h 29فصل سوم PAGEREF _Toc374706718 h 30مدل ریاضی پیشنهادی PAGEREF _Toc374706719 h 303-1. مقدمه PAGEREF _Toc374706720 h 313-2. تعریف مسئله PAGEREF _Toc374706721 h 313-2. مفروضات مسئله PAGEREF _Toc374706722 h 323-3. مدل ریاضی پیشنهادی PAGEREF _Toc374706723 h 333-3-1. اندیسها و پارامترهای ورودی به مدل PAGEREF _Toc374706724 h 343-3-2. متغیرهای تصمیمگیری PAGEREF _Toc374706725 h 343-3-3. تابع هدف PAGEREF _Toc374706726 h 353-3-4. محدودیتها PAGEREF _Toc374706727 h 363-4. اعتبار سنجی مدل PAGEREF _Toc374706728 h 403-5. پیچیدگی مسئله PAGEREF _Toc374706729 h 433-6. الگوریتم ژنتیک PAGEREF _Toc374706730 h 463-6-1. تاریخچه الگوریتم ژنتیک PAGEREF _Toc374706731 h 473-6-2. واژگان ژنتیک PAGEREF _Toc374706732 h 483-6-3. ساختار الگوریتم ژنتیک PAGEREF _Toc374706733 h 493-6-4. کدگذاری PAGEREF _Toc374706734 h 503-6-5. ایجاد جمعیت اولیه PAGEREF _Toc374706735 h 513-6-6. اعمال ژنتیک PAGEREF _Toc374706736 h 523-6-6-1. عملگرهای تقاطعی PAGEREF _Toc374706737 h 523-6-6-1-1. یک نقطه برش PAGEREF _Toc374706738 h 533-6-6-1-2. دو نقطه برش PAGEREF _Toc374706739 h 543-6-6-2. عملگرهای جهشی PAGEREF _Toc374706740 h 543-6-6-2-1. جابجایی PAGEREF _Toc374706741 h 553-6-6-2-2. وارونگی PAGEREF _Toc374706742 h 563-6-6-2-3. الحاق یا جاسازی PAGEREF _Toc374706743 h 563-6-7. عمل تحول PAGEREF _Toc374706744 h 573-6-7-1. فضای نمونه گیری PAGEREF _Toc374706745 h 573-6-7-2. فضای نمونه گیری عادی PAGEREF _Toc374706746 h 573-6-7-3. مکانیسم نمونه گیری PAGEREF _Toc374706747 h 573-6-7-4. احتمال انتخاب PAGEREF _Toc374706748 h 583-6-8. تابع برازش PAGEREF _Toc374706749 h 593-6-9 . استراتژی برخورد با محدودیت PAGEREF _Toc374706750 h 593-6-9-1. استراتژی اصلاح عملگرهای ژنتیک PAGEREF _Toc374706751 h 603-6-9-2. استراتژی ردی PAGEREF _Toc374706752 h 603-6-9-3. استراتژی اصلاحی PAGEREF _Toc374706753 h 603-6-9-4. استراتژی جریمه ای PAGEREF _Toc374706754 h 603-6-10. معیار توقف PAGEREF _Toc374706755 h 613-7. الگوریتم زنبور عسل PAGEREF _Toc374706756 h 623-7-1. مراحل اجرای الگوریتم PAGEREF _Toc374706757 h 633-7-2. پارامتر های الگوریتم PAGEREF _Toc374706758 h 643-7-3. فلوچارت الگوریتم زنبور عسل PAGEREF _Toc374706759 h 643-7-4. شرح مراحل اجرای الگوریتم PAGEREF _Toc374706760 h 653-8. جمعبندی PAGEREF _Toc374706761 h 66فصل چهارم PAGEREF _Toc374706762 h 67نتایج محاسباتی و تحلیل آن PAGEREF _Toc374706763 h 674-1.مقدمه PAGEREF _Toc374706764 h 684-2. پیادهسازی الگوریتم ژنتیک PAGEREF _Toc374706765 h 684-2-1. ساختار کروموزوم PAGEREF _Toc374706766 h 694-2-2. جمعیت اولیه PAGEREF _Toc374706767 h 704-2-3. ارزیابی برازندگی تابع هدف PAGEREF _Toc374706768 h 714-2-4. استراتژی انتخاب PAGEREF _Toc374706769 h 714-2-5. اپراتورهای ژنتیک PAGEREF _Toc374706770 h 734-2-6. همگرایی الگوریتم ژنتیک PAGEREF _Toc374706771 h 754 -2-7. معیار توقف PAGEREF _Toc374706772 h 754-3. پیادهسازی الگوریتم زنبور عسل( شماره یک) PAGEREF _Toc374706773 h 764-3-1. مراحل اجرای الگوریتم زنبورعسل (شماره یک) PAGEREF _Toc374706774 h 764-3-2. پارامترهای الگوریتم زنبورعسل (شماره یک) PAGEREF _Toc374706775 h 774-3-3. روابط حاکم بر مقادیر پارامترها در الگوریتم زنبورعسل (شماره یک) PAGEREF _Toc374706776 h 774-4. پیادهسازی الگوریتم زنبور عسل(شماره دو) PAGEREF _Toc374706777 h 784-4-1. مراحل اجرای الگوریتم زنبورعسل (شماره دو) PAGEREF _Toc374706778 h 784-4-2. پارامترهای الگوریتم زنبورعسل (شماره دو) PAGEREF _Toc374706779 h 794-5. مجموعه دادهها PAGEREF _Toc374706780 h 814-6. تنظیم پارامترهای کنترلی الگوریتمها PAGEREF _Toc374706781 h 814-7. طراحی آزمایشات چندعاملی برای مسائل با ابعاد متوسط PAGEREF _Toc374706782 h 844-7-1.تحلیل نتایج آماری PAGEREF _Toc374706783 h 884-8. طراحی آزمایشات چندعاملی برای مسائل باابعاد بزرگ PAGEREF _Toc374706784 h 924-8-1.تحلیل نتایج آماری PAGEREF _Toc374706785 h 964-9. نتایج محاسباتی PAGEREF _Toc374706786 h 994-10. جمعبندی PAGEREF _Toc374706787 h 108فصل پنجم PAGEREF _Toc374706788 h 109نتیجه گیری و پیشنهادات PAGEREF _Toc374706789 h 1095-1. مقدمه PAGEREF _Toc374706790 h 1105-2. نتیجه گیری PAGEREF _Toc374706791 h 1105-3. پیشنهادات آتی PAGEREF _Toc374706792 h 1115-3-1. پیشنهادات در زمینه ماهیت مسئله طرح شده در تحقیق PAGEREF _Toc374706793 h 1115-3-2. پیشنهادات در زمینه روش حل مسئله PAGEREF _Toc374706794 h 112فهرست منابع PAGEREF _Toc374706795 h 113پیوست PAGEREF _Toc374706796 h 119

TOC o “2-3” h z t “Heading 1,1,Style3,1” جدول 4-1. مقادیر دادههای ورودی به مسائل آزمایشی PAGEREF _Toc364238458 h 81جدول 4-2. پارامترهای کنترلی الگوریتم ژنتیک PAGEREF _Toc364238459 h 83جدول 4-3. پارامترهای کنترلی الگوریتم زنبور شماره یک PAGEREF _Toc364238460 h 83جدول 4-4. پارامترهای کنترلی الگوریتم زنبور شماره دو PAGEREF _Toc364238461 h 83جدول 4-5. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک در ابعاد متوسط PAGEREF _Toc364238462 h 84جدول 4-6. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو در ابعاد متوسط PAGEREF _Toc364238463 h 84جدول 4-7. فاکتورها و سطوح آنها در الگوریتم ژنتیک در ابعاد متوسط PAGEREF _Toc364238464 h 84جدول 4-8 . ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد متوسط PAGEREF _Toc364238465 h 85جدول4-9 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط PAGEREF _Toc364238466 h 86جدول4-10. آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط PAGEREF _Toc364238467 h 86جدول 4-11. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط PAGEREF _Toc364238468 h 87جدول 4-12. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط PAGEREF _Toc364238469 h 87جدول 4-13. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط PAGEREF _Toc364238470 h 88جدول4-14. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط PAGEREF _Toc364238471 h 88جدول 4-15. مقادیر پارامترهای کنترلی الگوریتم زنبور 1، ابعاد متوسط PAGEREF _Toc364238472 h 90جدول 4-16.مقادیر پارامترهای کنترلی الگوریتم زنبور 2، ابعاد متوسط PAGEREF _Toc364238473 h 91جدول 4-17. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد متوسط PAGEREF _Toc364238474 h 91جدول 4-18. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک برای ابعاد بزرگ PAGEREF _Toc364238475 h 92جدول 4-19. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو برای ابعاد بزرگ PAGEREF _Toc364238476 h 92جدول 4-20. فاکتورها و سطوح آنها در الگوریتم ژنتیک برای ابعاد بزرگ PAGEREF _Toc364238477 h 92جدول 4-21. ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد بزرگ PAGEREF _Toc364238478 h 93جدول 4-22 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ PAGEREF _Toc364238479 h 94جدول 4-23 . آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ PAGEREF _Toc364238480 h 94جدول 4-24. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ PAGEREF _Toc364238481 h 95جدول 4-25. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ PAGEREF _Toc364238482 h 95جدول 4-26. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ PAGEREF _Toc364238483 h 96جدول4-27. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد بزرگ PAGEREF _Toc364238484 h 96جدول4-28. مقادیر پارامترهای کنترلی الگوریتم زنبور1، ابعاد بزرگ PAGEREF _Toc364238485 h 98جدول4-29. مقادیر پارامترهای کنترلی الگوریتم زنبور2، ابعاد بزرگ PAGEREF _Toc364238486 h 98جدول4-30. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد بزرگ PAGEREF _Toc364238487 h 98جدول4-31. نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک PAGEREF _Toc364238488 h 100جدول4-32. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد کوچک PAGEREF _Toc364238489 h 101جدول4-33. نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط PAGEREF _Toc364238490 h 103جدول4-34. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد متوسط PAGEREF _Toc364238491 h 103جدول4-35. نتایج محاسباتی حاصل از حل مسائل با ابعاد بزرگ PAGEREF _Toc364238492 h 105جدول4-36. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد بزرگ PAGEREF _Toc364238493 h 105جدول4-37. مقادیر RPD برای الگوریتمهای ژنتیک، رنبور1 و زنبور2 PAGEREF _Toc364238494 h 107

TOC o “2-3” h z t “Heading 1,1,Style4,1” شکل3-1. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط فعال نبودن محدودیت دسترسی به ماشینها PAGEREF _Toc375088021 h 40شکل3-2. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط اعمال محدودیت دسترسی به ماشینها PAGEREF _Toc375088022 h 41شکل3-3. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط افزایش در زمان نصب کار شماره 3 PAGEREF _Toc375088023 h 42شکل3-4. سلسله مراتب پیچیدگی محیطهای کارگاهی در مسائل زمانبندی ]4[ PAGEREF _Toc375088024 h 44شکل 3-5. سلسله مراتب پیچیدگی جزئیات نحوه پردازش و محدودیتها در مسائل زمانبندی ]4[ PAGEREF _Toc375088025 h 44شکل 3-6. سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ]4[ PAGEREF _Toc375088026 h 44شکل 3-7. سلسله مراتب پیچیدگی تعدادی از مسائل زمانبندی با تابع هدف Makespan ]4[ PAGEREF _Toc375088027 h 45شکل 3-8 .مقایسه فضاهای ژنوتیپ و فنوتیپ PAGEREF _Toc375088028 h 48شکل 3-9. فضای موجه، ناموجه و غیرقانونی PAGEREF _Toc375088029 h 51شکل3-10 . نحوه عملکرد اپراتور تقاطع یک نقطه برش PAGEREF _Toc375088030 h 53شکل3-11. اپراتور تقاطع تک نقطهای PAGEREF _Toc375088031 h 54شکل 4-1. رویه کلی الگوریتم ژنتیک PAGEREF _Toc375088032 h 68شکل4-2. روش نمایش جواب PAGEREF _Toc375088033 h 70شکل 4-3. عملیات تقاطع PAGEREF _Toc375088034 h 74شکل 4-4. پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط PAGEREF _Toc375088035 h 89شکل 4-5. میانگین نسبت SN، الگوریتم زنبور1، ابعاد متوسط PAGEREF _Toc375088036 h 90شکل 4-6 . پاسخ میانگینها، الگوریتم زنبور1 ، ابعاد بزرگ PAGEREF _Toc375088037 h 97شکل 4-7 . میانگین نسبت SN، الگوریتم زنبور 1، ابعاد بزرگ PAGEREF _Toc375088038 h 97شکل 4-8. میانگین زمان محاسباتی الگوریتمها در ابعاد کوچک (2ماشین) PAGEREF _Toc375088039 h 102شکل 4-9. میانگین زمان محاسباتی الگوریتمها در ابعاد متوسط PAGEREF _Toc375088040 h 104شکل 4-10. میانگین زمان محاسباتی الگوریتمها در ابعاد بزرگ PAGEREF _Toc375088041 h 106شکل 4-11. نمودار LSD در سطح اطمینان 95% برای معیار RPD PAGEREF _Toc375088042 h 107
فصل اولکلیات تحقیق1-1. مقدمهمسائل زمانبندی یکی از مهمترین مسائل دنیای امروز میباشند که تاثیر شگرفی در افزایش بهرهوری سیستمهای تولیدی و خدماتی دارند. زمانبندی در عمل بهمعنای تخصیص منابع محدود به فعالیتهایی است که به آن منبع نیاز دارند و در واقع نوعی فعالیت تصمیمگیری است که با هدف بهینهسازی یک و یا چند معیار انجام میگیرد. باید به این نکته توجه داشت که در دنیای رقابتی کنونی، برای موسسهها، داشتن بهترین توالی انجام عملیات و زمانبندی مناسب فعالیتها یک نیاز اساسی به منظور بقاء تعریف میشود و بهعنوان یک فرآیند تصمیمگیری، مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. به بیان بهتر، زمانبندی را میتوان تخصیص منابع محدود در طول زمان بهمنظور اجرای مجموعهای از وظایف تعریف کرد. در دنیای امروز، زمان همواره یک محدودیت اساسی بوده است. بنابراین، زمانبندی صحیح فعالیتها بهمنظور حداقل کردن این منبع با توجه به هزینههای تولیدی و خدماتی در واحد زمان، امری ضروری به نظر میرسد.
با پیشرفت علم و بهدنبال آن توسعه و شکوفایی صنایع تولیدی و خدماتی، نقش منابع و نحوه تخصیص آنها از اهمیت دو چندانی برخوردار شده است. امروزه منابع در دسترس مانند نیروی انسانی، ماشینآلات، مواد اولیه و … به عنوان منابع بحرانی در تولید و فعالیتهای خدماتی در نظر گرفته میشوند و زمانبندی و تخصیص به موقع و مناسب این منابع منجر به ارتقاء کارایی، بهرهوری و در نهایت سودآوری بیشتر میشود. از آنجا که خواستگاه بسیاری از مسائل زمانبندی و توالی عملیات محیط های صنعتی میباشد، در بیان بسیاری از مفاهیم زمانبندی از واژههای بکار رفته در صنعت استفاده میشود. به عنوان مثال، در مباحث زمانبندی و توالی عملیات از منابع با عنوان ماشین و از فعالیتها با عنوان کار یاد میشود به نحوی که کارها اغلب بوسیله ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند.
در مسائل زمانبندی، هدف از یافتن توالی انجام کارها میتواند متفاوت باشد. تعدادی از اهداف مورد استفاده در مسائل زمانبندی عبارتند از : کمینهسازی بیشترین زمان تکمیل کارها، کمینهسازی مجموع زمان تکمیل کارها، کمینهسازی بیشترین زمان دیرکرد و کمینهسازی تعداد کارهایی که دیرکرد دارند. همچنین بر حسب شرایط حاکم بر محیط مورد مطالعه، محدودیتهای گوناگونی در مسئله لحاظ میشود. تعدادی از محدودیتهای حاکم بر مسائل زمانبندی عبارتند از : زمانهای نصب وابسته به توالی ، محدودیت دسترسی به ماشینها، زمانهای دسترسی به کار، برش در کارها، خرابی ماشینها و محدودیت در اندازه صف کارها که مورد آخر در سیستمهای جریان کارگاهی می تواند لحاظ شود . در ابتدای فصل دوم، مسائل زمانبندی به تفکیک محیطهای کارگاهی، محدودیتهای پردازش و توابع هدف بصورت مختصر معرفی میشوند. یک مسئله زمانبندی بصورت یک مسئله بهینهسازی بیان میشود که با توجه به محدودیتهای موجود، به دنبال ارضاء کردن هدف (اهداف) مورد نظر میباشد.
در مباحث زمانبندی، بررسی مدلهای تک ماشینه به علت سادگی و به دلیل اینکه حالت خاصی از سایر مدلها میباشد از اهمیت بالایی برخوردار است. در مقابل، نظریه زمانبندی سه نوع اساسی از مدلهای چند ماشینی را پوشش میدهد: سیستمهای موازی، سیستمهای جریان کارگاهی و سیستمهای تولید کارگاهی. در سیستم ماشینهای موازی همانند مدلهای تک ماشینی، هر یک از کارها با انجام یک عملیات بر روی یکی از ماشینهای موازی موجود پردازش میشوند اما در سیستمهای جریان کارگاهی و ترکیبی ساختار مسائل پیچیدهتر است.
در ادامه به تعریف مسئله مورد بحث این تحقیق و مفروضات آن پرداخته میشود. در پایان اهداف و ضرورت تحقیق بیان میشود.
1-2. تعریف مسئلهمسئله زمانبندی ماشینهای موازی نامرتبط، بهعنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است شناخته میشود. مسائل ماشینهای موازی نامرتبط حالت عمومیت یافته مسائل تک ماشینه و مسائل کلاسیک ماشینهای موازی و حالت خاصی از مسائل ماشینهای متوالی منعطف محسوب میشوند. در مسائل کلاسیک ماشینهای موازی، مجموعهای از کارهای مستقل وجود دارد که هر کدام از آنها بر روی یکی از ماشینهای موازی یکسان موجود پردازش میشود و زمان پردازش کار نوع j بر روی تمامی ماشینها یکسان است ولی در حالت نامرتبط بودن ماشینها، زمان پردازش کارها بر روی ماشینها نه تنها به نوع کار بلکه به نوع ماشین نیز وابسته است و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای مختلف وجود ندارد.
در بسیاری از تحقیقات و مقالات ارائه شده در زمینه مسائل زمانبندی فرض بر این است که محصولات تولیدی توسط ماشینها دارای کیفیت قابل قبول هستند. ولی در دنیای واقعی این فرض چندان منطبق بر شرایط تولیدی نمیباشد و تولید اقلام معیوب به دلایل متعدد امری اجتناب ناپذیر است. از جمله این دلایل عبارتند از:
کارا نبودن سیستم تولیدی
از رده خارج بودن ماشینهای تولید
نداشتن یک سیستم تعمیرات و نگهداری مناسب و کارا
خطاهای انسانی
شرایط غیر قابل پیش بینی در تولید و …
در مسئله زمانبندی ماشینهای موازی نامرتبط از آنجایی که ممکن است دلیل نامرتبط بودن ماشینها، تفاوت میان عملیات قابل پردازش توسط آنها باشد و هر ماشین لزوما قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نباشد، بنابراین دور از منطق نیست که محدودیت دسترسی به ماشینها در مسئله مورد بررسی در نظر گرفته شود. این محدودیت تضمین میکند که هر کار تنها توسط زیرمجموعهای از ماشینها قابل پردازش باشد و اصطلاحا پردازش کارها با دسترسی محدود به ماشینها صورت میپذیرد.
در بسیاری از مسائل زمانبندی فرض بر این بوده است که تمام کارها در ابتدای افق زمانبندی در دسترس هستند. واضح است که در دنیای واقعی لزوما این موضوع صحیح نیست و ممکن است کارها به تدریج وارد سیستم شوند و از ابتدا در دسترس نباشند. در نتیجه محدودیت زمان دسترسی به کارها در مدل پیشنهادی لحاظ خواهد شد.
مسائل زمانبندی غالبا به محیطهای تولیدی و خدماتی میپردازند که در آنها زمان نصب ماشین نادیده گرفته میشود و یا به عنوان بخشی از زمان پردازش کارها تلقی میشود. این نوع محیطهای تولیدی و یا خدماتی با این فرض مدلسازی میشوند که زمانهای نصب در مقایسه با زمانهای پردازش کوچک هستند، بنابراین میتوان آنها را نادیده گرفت و یا اینکه زمانهای نصب مستقل از توالی پردازش کارها بر روی ماشینها هستند، در نتیجه میتوان آنها را به زمان پردازش اضافه نمود. با این وجود در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد ]3[. در این شرایط زمان نصب بهعنوان بخشی مجزا از زمان پردازش در نظر گرفته میشود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به نوع کار قبلی که بر روی آن ماشین پردازش شده است نیز بستگی دارد. بهعنوان مثال، در سوراخکاری صفحات فلزی، اگر دو پردازش متوالی از دو الگوی متفاوت پیروی کنند، آنگاه برای انجام پردازش بعدی باید زمانی صرف شود و تغییرات لازم به منظور آمادهسازی ماشین صورت پذیرد.
یکی از پرکاربرد ترین توابع هدف در مسائل بهینهسازی ماشینهای موازی، کمینهکردن بیشترین زمان تکمیل کارها میباشد. چرا که رسیدن به این هدف سبب میشود کارها تا حد ممکن با یکنواختی بیشتری بین ماشینها توزیع شوند و به نحوی از ظرفیت کاری تمام ماشینها تا حد مطلوب استفاده شود و در نتیجه از تجمع کارها بر روی یک یا تعدادی از ماشینها جلوگیری بهعمل میآورد. از این رو معیار بیشترین زمان تکمیل کارها به عنوان معیار بهینهسازی در مدل پیشنهادی مورد استفاده قرار گرفته است.
در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب به همراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشین و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها معرفی و مورد بررسی قرار میگیرد. در ادامه، برای مسئله یاد شده یک مدل برنامه ریزی عدد صحیح ارئه میشود. همچنین از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم زنبور عسل برای حل آن استفاده میشود.
از جمله کاربردهای مدل پیشنهادی در تحقیق پیش رو را میتوان در یک سیستم خدماتی همانند بانک مشاهده نمود. در یک بانک، چند اپراتور به صورت موازی وجود دارند که هر کدام مسئول رسیدگی به بخشی از امور بانکی هستند. بر فرض مثال اپراتور اول وظیفه بازگشایی حساب، باز گشایی ال سی، صدور انواع حوالههای بانکی و انجام امور مرتبط با انتقال وجه را بهعهده دارد و اپراتور دوم به سایر امور بانکی نظیر رسیدگی به درخواستهای وام مشتریان ، صدور گواهی سپرده، خرید و فروش اوراق مشارکت، تنظیم صورتحسابها و … میپردازد. در این سیستم خدماتی بهدنبال آن هستیم که بهترین توالی از انجام امور بانکی مشتریان را بهنحوی بدست آوریم که بیشترین زمان تکمیل امور بانکی کمینه شود.
1-3. اهداف تحقیقدر تحقیق پیش رو بهدنبال آن هستیم که با ارائه یک مدل ریاضی جدید برای مسئله ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای ذکر شده در بخش تعریف مسئله، به اهداف حاصل از طرح مسئله نظیر استفاده کارآمد از منابع و زمان، کاهش هزینههای تولیدی و خدماتی، جلب رضایت مشتریان و حفظ آنها و در نهایت نزدیکتر کردن مسئله زمانبندی ماشینهای موازی نا مرتبط به مسائل دنیای واقعی نائل شویم.
1-4. مفروضات عمومی مسئلهکارها مستقل از یکدیگر میباشند.
در سیستم تولیدی، احتمال تولید اقلام معیوب وجود دارد.
تعداد دوبارهکاری برای هر قلم کالا محدود است.
امکان شکست در کارها وجود ندارد.
زمان آمادهسازی وابسته به توالی کارها و وابسته به نوع ماشینآلات وجود دارد.
بیکاری ماشینها مجاز است.
تمام ماشینها بطور مستمر در دسترس هستند و امکان خرابی ماشینها وجود ندارد.
برای هر قلم کالا، محدودیت دسترسی به ماشینها وجود دارد.
محدودیت زمان دسترسی به کارها وجود دارد.(تمام کارها در لحظه صفر در دسترس نیستند)
زمان پردازش کارهای اصلی، زمان نصب ماشین، ضرایب کاهنده زمان، احتمالات معیوب بودن اقلام تولیدی و زمانهای دسترسی به کارها معین میباشند. فرض بر این است که دادههای فوق با توجه به اطلاعات جمعآوری شده مربوط به گذشته از محیط مورد بررسی گردآوری شدهاند.
1-5. ضرورت انجام تحقیقمسائل زمانبندی ماشینهای موازی نامرتبط، یکی از کاربردی ترین مسائل در سیستمهای تولیدی و خدماتی میباشد که در مقایسه با انواع دیگر مسائل ماشینهای موازی، با توجه کمتری از سوی محققین روبرو بوده است. همچنین، موضوع کاهش هزینههای تولید همواره بهعنوان یکی از اهداف عملیاتی بیشتر واحدهای تولیدی مطرح بوده است و یکی از موثرین روشها در تحقق این هدف، دوبارهکاری اقلام معیوب میباشد. لذا در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام معیوب مورد بررسی قرار میگیرد. همچنین در مسئله فوق، بدلیل اهمیت زمانهای آمادهسازی وابسته به توالی در بسیاری از صنایع، فرض وابسته بودن زمان آمادهسازی ماشین به توالی کارها و نوع ماشینآلات در مسئله لحاظ شده است. با تحقیقات صورتگرفته در زمینه مسائل زمانبندی ماشینهای موازی، جای خالی تحقیقی که در آن مسئله ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام فاقد کیفیت و محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی و وابسته به نوع ماشین و دسترسی محدود به ماشینها مورد بررسی قرار گرفته باشد، احساس میشد. لذا در تحقیق پیش رو، مسئله یاد شده مورد مطالعه قرار گرفته است و یک مدل بهینهسازی برای آن ارائه میشود و از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم زنبور عسل بهمنظور حل مدل در اندازههای کاربردی استفاده می شود.
1-6. محتویات تحقیقمطالب ارائه شده در این تحقیق در پنج فصل سازماندهی میشوند: کلیات تحقیق در فصل اول ارائه شده است. در فصل دوم، مروری بر ادبیات تحقیق مسائل زمانبندی ماشینهای موازی بویژه ماشینهای موازی نامرتبط صورت میگیرد. در فصل سوم، مدل پیشنهادی برای مسئله مورد بررسی در این تحقیق ارائه و تشریح میگردد و کلیاتی راجع به الگوریتمهای ژنتیک و زنبور عسل بیان میشود. شرح نحوه پیادهسازی الگوریتمهای یاد شده بههمراه نتایج محاسباتی حاصل از حل مسائل معیار توسط هر کدام از الگوریتمها در فصل چهارم صورت میگیرد و در پایان، فصل پنجم شامل نتیجهگیری و پیشنهادات برای انجام تحقیقات آتی میباشد.
فصل دوممرور ادبیات و پیشینه تحقیق2-1. مقدمهتحقیق در زمینه مباحث زمانبندی در اوایل دهه پنجاه میلادی شکل جدیتری به خود گرفت و اولین مقالههای علمی در این زمینه، در اوایل این دهه به چاپ رسید. با این وجود، یکی از اولین مطالعات در زمینه مسائل زمانبندی به سالها قبل و در حین جنگ جهانی اول باز میگردد. هنری لارنس گانت یکی از پیشگامان مباحث زمانبندی میباشد که یک مهندس صنایع و از پیروان نظریات فردریک تیلور در این زمینه بود. وی در زمان جنگ جهانی اول نمودار معروف خود که به نمودار گانت معروف است را طراحی کرد. نموداری که در آن محور افقی نشان دهنده زمان و محور عمودی نشان دهنده منابع و یا فعالیت ها میباشد ]4[.
تحقیق در زمینه مسائل زمانبندی در طی پنجاه سال گذشته به شکل گستردهتری دنبال شده و تکامل یافته است و به موضوعی با تاریخچه تحقیقاتی غنی از قواعد و الگوریتمهای ساده و پیچیده نظیر قاعده جانسون ، قاعده زودترین موعد تحویل ، الگوریتم مور ، روش شاخه و حد، روشهای برنامهریزی پویا، و بسیاری از روشهای ابتکاری و فراابتکاری تبدیل شده است.
در دهه شصت میلادی در اغلب مقالهها از تکنیکهای برنامهریزی پویا و یا مدلسازی برنامهریزی عدد صحیح برای حل مسایل زمانبندی و توالی عملیات استفاده میشد. پس از انتشار مقاله ریچارد کارپ ]5[ در اوایل دهه هفتاد میلادی در زمینه نظریه پیچیدگی، بسیاری از مطالعات انجام شده در این دهه بر روی سلسله مراتب پیچیدگی مسائل زمانبندی متمرکز شد. نتایج مطالعات حاکی از آن بود که طیف گستردهای از مسائل زمانبندی دارای پیچیدگی ساختاری میباشند و به همین دلیل الگوریتم های دقیق قادر نخواهند بود که در یک زمان محاسباتی قابل قبول جواب بهینه این مسائل را بیابند. از این رو در سالهای بعد تلاشهای جدی به منظور ایجاد و توسعه الگوریتمهای ابتکاری و فراابتکاری صورت پذیرفت. یکی از اولین و در عین حال معروفترین الگوریتمهای فراابتکاری، الگوریتم ژنتیک میباشد که اصول اولیه آن توسط هالندو همکارانش در زمینه مدلسازی فرآیند سازگاری سیستمهای طبیعی در قالب سیستمهای مصنوعی ارائه شد و ایده اصلی آن مبتنی بر نظریه تکاملی داروین میباشد. از جمله دیگر الگوریتمهای فراابتکاری شناخته شده در حل مسائل بهینهسازی میتوان به الگوریتمهای شبکه عصبی، ایمنی مصنوعی، شبیهسازی تبرید ، اجتماع مورچگان و جستجوی ممنوع اشاره کرد. در راستای همین تلاشها در سالهای اخیر نیز الگوریتمهای متعددی به منظور حل مسائل بهینهسازی در یک زمان محاسباتی قابل قبول ارائه شده است که از آن جمله میتوان از الگوریتم زنبورعسل، الگوریتم رقابت استعماری، الگوریتم کرم شبتاب، الگوریتم جستجوی هارمونی و چند الگوریتم دیگر یاد کرد.
الگوهای زیادی در تعریف مسائل زمانبندی و طبقهبندی آنها مطرح هستند. برای مسائل زمانبندی از نظر فرآیند تولید محصولات و بسته به تعداد عملیات مورد نیاز برای پردازش یک کار و نیز تعداد ماشینهای موجود برای پردازش هر عملیات الگوهای زیادی را میتوان برشمرد. در کل یک مسئله زمانبندی عمومی میتواند با استفاده از سه نماد بصورتα/β/γ تعریف شود که α بیانگر وضعیت و شرایط ماشین یا منبع است و معمولا دارای یک نماد است، β خصوصیات و جزئیات نحوه پردازش و محدودیتهای موجود را بیان میکند و ممکن است شامل هیچ نمادی نباشد و یا چندین نماد باشد، γ بیانگر تابع هدف مسئله است و معمولا شامل تنها یک نماد است. در ادامه مبحث به بیان شرایط متداول برای هر نماد بصورت خلاصه پرداخته میشود.
2-2. محیطهای کارگاهی2-2-1. تک ماشینهسادهترین حالت ممکن است که معمولا حالت خاص سایر مسایل در نظر گرفته میشود. در این حالت فقط یک ماشین در دسترس بوده و این ماشین قادر به پردازش تنها یک کار در هر لحظه میباشد و هر کار فقط به یک عملیات برای تکمیل شدن نیاز دارد. این مدل، مبنا و اساس کار برای ایجاد قوانین و قواعد زمانبندی برای استفاده در سایر مدلها میباشد. بهعبارت دیگر، عموما روشها و راهکارها ابتدا برای یک مدل تک ماشینه تبیین میگردد و سپس برای سایر مدلها بسط داده میشوند.
2-2-2 . ماشینهای موازیدر این سیستم تعدادی ماشین بصورت موازی در دسترس هستند. هر کار تک عملیاتی میباشد و بر روی یکی از ماشینهای موجود پردازش میشود. این سیستم، از لحاظ ویژگیهای ماشین از قبیل سرعت پردازش، کیفیت محصولات تولیدی و هزینه تولید به سه دسته ماشینهای موازی یکسان، ماشینهای موازی یکنواخت و ماشینهای موازی نامرتبط تقسیم میشوند.
2-2-2-1. ماشینهای موازی یکسانحالتی است که در آن ماشینهای کاملا یکسان به موازات یکدیگر قرار میگیرند. در این حالت زمان پردازش کار نوع j روی تمامی ماشینها یکسان است.
2-2-2-2. ماشینهای موازی یکنواختحالتی است که در آن ماشینها دارای سرعتهای متفاوتی هستند ولی هر ماشین با یک نرخ ثابت کار میکند.
2-2-2-3. ماشینهای موازی نامرتبطحالتی است که در آن ماشینها دارای سرعتهای متفاوتی هستند و هیچ رابطه مشخصی بین سرعت پردازش ماشینها وجود ندارد. در این حالت زمان مورد نیاز برای پردازش هر کار هم به نوع کار و هم به نوع ماشین وابسته است.
2-2-3 . جریان کارگاهیدر این سیستم تولیدی، هر کار به چند عملیات برای تکمیل شدن نیاز دارد. کارها روی چند ماشین در یک توالی یکسان پردازش میشوند، اما زمان پردازش هر کار روی هر ماشین ممکن است متفاوت با زمان پردازش سایر کارها روی همان ماشین باشد.
2-2-4 . جریان کارگاهی منعطفاین حالت تعمیمیافته حالت جریان کارگاهی و ماشینهای موازی میباشد. در این سیستم تعدادی کارگاه بهصورت متوالی وجود دارد که در هر کارگاه، تعدادی ماشین به طور موازی کار میکنند و در هر کارگاه، یک کار حداکثر روی یک ماشین میتواند انجام شود. اغلب مسائل دنیای واقعی، سازگار با محیط جریان کارگاهی منعطف میباشند.
2-2-5 . کار کارگاهیهر کار به چند عملیات نیاز دارد، تعدادی ماشین مختلف در کارگاه وجود دارند. هر کار ممکن است به برخی یا تمام ماشینها در یک توالی مشخص مربوط به خود، نیاز داشته باشد. یک کار میتواند برای پردازش به یکی از ماشینها یک و یا چند مرتبه مراجعه نماید.
2-2-6 . کار کارگاهی منعطف این حالت تعمیمیافته حالت جریان کارگاهی و ماشینهای موازی میباشد. در این حالت تعدادی مرکز کاری برای پردازش کارها موجود است که در هر مرکز کاری، تعدادی ماشین بصورت موازی کار میکنند. هر کار باید بهترتیب در هر مرحله توسط یکی از ماشینهای موجود پردازش شده و به مرحله بعد برود.
2-2-7 . سیستم کارگاهی بازاین محیط تولیدی، مشابه سیستم کار کارگاهی است، با این تفاوت که یک کار میتواند روی ماشینها به هر توالی دلخواهی پردازش شود. به عبارت دیگر هیچ تقدم و تأخر عملیاتی در فرآیند تولید محصولات وجود ندارد. معمولا هدف در این سیستم تولیدی، حداقلسازی زمان اتمام کلیه کارها است.
2-2-8 . سیستم ساخت انعطاف پذیردر این سیستم هر ماشین ممکن است قادر به انجام بیش از یک عملیات باشد. بنابراین هر دو ماشین در انجام یک سری از عملیات ممکن است حکم دو ماشین موازی را داشته باشند و در مورد یکسری از عملیات با یکدیگر اشتراکی نداشته باشند.
2-2-9. سیستم کارگاهی وابستهیک محیط سیستم کار کارگاهی است که در آن، زمان شروع و پایان یکسری از کارها، به هم وابسته است. مثال بارز این سیستم، خطوط مونتاژ است. در مورد هر یک از سیستمهای تولیدی فوق، وابستگی زمان و هزینه نصب وابسته به توالی، میتواند دو سیستم مختلف را پدید آورد. از طرفی، سیستمهای تولیدی در دنیای واقعی با پدیدههای تصادفی بسیاری روبرو هستند که موجب قطع یا شکست سیستم میگردد. این رویدادها به عنوان رویدادهای زمان واقعی شناخته میشوند.
2-3. جزئیات و محدودیتهای نحوه پردازش کارها2-3-1. زمان دسترسی به کار rjاین محدودیت بدان معنی است که پردازش کار نوع j نمیتواند پیش از زمان دسترسی آن آغاز شود و در شرایطی برقرار است که تمام کارها در ابتدای افق زمانبندی در دسترس نباشند.
2-3-2. زمان نصب وابسته به توالی Sijkنشان دهنده زمان مورد نیاز برای آمادهسازی ماشین نوع i می باشد هنگامیکه پردازش کار نوع jتمام شده و قرار است پردازش کار نوع k شروع شود.
2-3-3. شکست در کارها prmpدر این حالت برنامهریز می تواند پردازش یک کار را بر روی یک ماشین پیش از تکمیل شدن آن قطع و کار دیگری را بر روی ماشین جایگزین کند.
2-3-4. اولویت در پردازش کارها precاین محدودیت بدان معنی است که آغاز پردازش یک یا چند کار وابسته به این است که کار دیگری پیش از آنها انجام شده باشد.
2-3-5. خرابی ماشین brkdwnزمانی در قالب یک محدودیت مشاهده میشود که ماشینها بطور مستمر در دسترس نباشند.
2-3-6. دسترسی محدود به ماشین ها Mjاین حالت زمانی رخ می دهد که m ماشین بطور موازی در دسترس باشند ولی تنها تعدادی از ماشینها قادر به پردازش کار نوع j باشند. مجموعه Mj شامل ماشینهایی است که قابلیت پردازش کار نوع j را دارند.
2-3-7. جایگشت prmuدر شرایطی برقرار است که ترتیب پردازش کارها روی تمامی ماشینها یکسان است. غالبا در مسائل جریان کارگاهی برقرار است.
2-3-8. بلوکه شدن blockدر مسائل جریان کارگاهی با ظرفیت محدود برای بافر، هنگامی که ظرفیت صف بین دو ماشین متوالی تکمیل میشود، کار تکمیل شده بر روی ماشین بالادستی باقی میماند و از پردازش کار بعدی بر روی آن جلوگیری میشود.
2-3-9. بدون انتظار nwtدر مسائل جریان کارگاهی، یک کار نبایستی در حین پردازش میان دو ماشین متوقف شود.
2-3-10. گردش مجدد rcrcدر شرایطی برقرار است که در مسائل کار کارگاهی و یا کار کارگاهی منعطف، حداقل یکی از کارها بتواند از یکی از ماشینها و یا یکی از مراکز کاری بیش از یک مرتبه عبور کند.
2-3-11. گروه های کاری fmlsحالتی است که در آن کارهای تخصیص یافته برای پردازش متعلق به خانوادههای مختلف هستند. زمان پردازش اعضای هر گروه میتواند متفاوت باشد اما آنها میتوانند بصورت متوالی بر روی یک ماشین بدون نیاز به زمان نصب پردازش شوند.
2-3-12. پردازش دسته ای batch(b)در این فرآیند، کارها به صورت دستهایی بصورت همزمان پردازش میشوند. پردازش هر دسته، نیازمند زمان مشخصی است و ممکن است برای تعداد کارهایی که میتوانند در یک زمان پردازش شوند یک محدودیت ظرفیتی وجود داشته باشد.
2-4. توابع هدف2-4-1. بیشینه زمان تکمیل کارها Cmaxبه مفهوم زمان تکمیل آخرین کاری است که سیستم را ترک میکند. این ضابطه بهرهوری ماشینآلات را به طرز چشمگیری افزایش میدهد.
2-4-2. بیشینه زمان تاخیر کارها Lmaxبیشترین انحراف زمانی از موعدهای تحویل کارها را نشان میدهد.
2-4-3. مجموع زمان تکمیل کارها Cjمجموع زمانهای تکمیل کارها را اندازهگیری میکند و سعی بر کمینه کردن آن موجب کاهش هزینههای نگهداری میشود. در ادبیات زمانبندی از کمینهسازی مجموع زمانهای تکمیل کارها با عنوان کمینهسازی مجموع زمانهای در جریان ساخت نیز یاد میشود.
2-4-4. مجموع وزنی زمان تکمیل کارها WjCjحالت کلیتر تابع هدف مجموع زمان تکمیل کارها میباشد. در این حالت به کارهای با هزینه نگهداری بیشتر، وزن بالاتری داده میشود.
2-4-5. مجموع زمان دیرکرد کارها Tjمجموع انحرافهای زمانی کارها از موعدهای تحویل را محاسبه مینماید.
2-4-6. مجموع وزنی زمان دیرکرد کارها WjTjمجموع انحرافهای زمانی وزنی کارها از موعدهای تحویل را محاسبه مینماید.
2-4-7. مجموع تعداد کارهای با تاخیر Ujتعداد کارهایی که موعد تحویل آنها گذشته است را نشان میدهد.
2-4-8. مجموع وزنی تعداد کار های با تاخیر WjUjحالت کلیتر تابع هدف مجموع تعداد کارهای با تاخیر میباشد. در این حالت به کارهایی که از لحاظ اهمیت تحویل در موعد مقرر از درجه اهمیت بالاتری برخوردار هستند، ضرایب وزنی بالاتری داده میشود.
2-4-9. مجموع زمان های زودکرد و دیرکرد کارها Ej+Tjاین تابع هدف از نوع توابع هدف معمولی که در بالا به آنها اشاره شد نمیباشد چرا که در آنها با اتمام کارها مقدار تابع هدف بصورت غیر نزولی افزایش مییابد ولی تابع هدف مجموع زمانهای زودکرد و دیرکرد از این جنس نمیباشد. در این تابع هدف بهدنبال آن هستیم که کارها تا حد امکان در موعد تحویل مربوطه آماده شوند. از کاربردهای آن می توان به صنایع تولید مواد فاسد شدنی اشاره کرد.
2-4-10. مجموع وزنی زمانهای زودکرد و دیرکرد کارها WjEj+W’jTjحالت کلیتر تابع هدف مجموع زمانهای زودکرد و دیرکرد کارها میباشد که در آن با توجه به اهمیت هر کار و میزان بحرانی بودن زودکرد و دیرکردد آن نسبت به موعد تحویل، به هر کار دو ضریب وزنی اختصاص مییابد.
2-5. پیشینه تحقیقاز اواسط قرن گذشته مباحث زمانبندی و توالی عملیات بصورت فزایندهای مورد توجه محققین و دانشمندان قرار گرفت و تحقیقات گستردهای در این حیطه صورت پذیرفت. از آنجایی که این مسائل در دنیای واقعی عموما دارای تعداد زیادی فعالیت و منبع میباشند، در نتیجه یک مجموعه گوناگون از اهداف و محدودیت بهرهبرداری از منابع در مورد آنها مطرح میشود. به همین دلیل است که تلاشهای انجام شده بهمنظور حل برنامهریزی ریاضی و یا حتی فرموله نمودن آن ها وقت گیر و پر زحمت میباشد. یکی از انواع مسائل مورد بررسی در این زمینه، مسئله زمانبندی ماشینهای موازی میباشد که از نقطه نظر تئوری و تجربی دارای اهمیت فراوانی میباشد. از دیدگاه آکادمیک، اهمیت مسئله زمانبندی ماشینهای موازی از آنجایی است که این مسئله حالت عمومیت یافته مسئله زمانبندی تک ماشینه و حالت خاصی از مسائل زمانبندی جریان کارگاهی منعطف و کار کارگاهی منعطف میباشد. از نقطه نظر تجربی نیز اهمیت این مسئله در آن است که در بسیاری از محیطهای تولیدی و خدماتی وضعیت قرار گیری ماشینها (اپراتورها) نسبت به یکدیگر بصورت یکی از انواع سه گانه مسائل ماشینهای موازی میباشد.
در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشینآلات و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها مورد مطالعه قرار میگیرد. در ادامه به منظور مروری بر ادبیات و مطالعات صورت پذیرفته، تحقیقات مرتبط با مسئله مورد بررسی در این تحقیق به تفکیک نوع محیط کارگاهی و محدودیتهای قید شده در صورت مسئله در بخشهای جداگانهای آدرسدهی میشوند. بدلیل گستردگی مطالب در ادبیات زمانبندی، در این تحقیق سعی بر آن است که در بخش بررسی محدودیتها، تحقیقاتی مورد بررسی قرار بگیرند که در حیطه مسائل زمانبندی ماشینهای موازی بویژه ماشینهای موازی نامرتبط میباشند.
2-6. ماشینهای موازی نامرتبط
مسئله زمانبندی ماشینهای موازی، یکی از پرکاربرد ترین مسائل زمانبندی در سیستمهای تولیدی و خدماتی میباشد و در سه گروه ماشینهای موازی یکسان، ماشینهای موازی یکنواخت و ماشینهای موازی نامرتبط دستهبندی میشود. در یک تعریف ساده، مسئله زمانبندی ماشینهای موازی بدین صورت بیان میشود که یک مجموعه از n کار متمایز، N=1,2,…,n، بر روی مجموعه ای از m ماشین موجود و در دسترس، M =1,2,…,m ، که بصورت موازی نسبت به هم قرار گرفتهاند پردازش میشوند. هر کار تنها بر روی یک ماشین پردازش میشود و هر ماشین در هر لحظه قادر به انجام تنها یک کار میباشد.
در سالهای اخیر، یک مطالعه جامع و کامل بر روی مسائل زمانبندی توسط الله وردی و همکاران ]6[ صورت پذیرفت. آنها یک مرور کامل بر مسائل تک ماشینه، ماشینهای موازی، جریان کارگاهی، جریان کارگاهی بدون تاخیر ، جریان کارگاهی منعطف، کار کارگاهی و سیستم کارگاهی باز انجام دادند و آنها را در دو قالب پردازش دستهای و غیر دستهای و زمان نصب وابسته به توالی و زمان نصب مستقل از توالی واکاوی کردند. یکی از اولین تحقیقات در زمینه مسائل زمانبندی ماشینهای موازی توسط مک ناتن ]7[ در اواخر دهه پنجاه میلادی صورت پذیرفت. همچنین محققان دیگری همچون موکوتوف ]8[ ،لام و ژینگ ]9[ و چنگ و سین ]10[ بررسیها و مطالعاتی بر روی مسائل ماشینهای موازی انجام دادند ولی بیشتر این تحقیقات در زمینه مسائل ماشینهای موازی یکسان بود و مسائل ماشینهای موازی نامرتبط در حجم بسیار کمتری مورد مطالعه قرار میگرفت. در ادامه این بخش، تعدادی از تحقیقات صورت پذیرفته در زمینه مسائل ماشینهای موازی نامرتبط آدرسدهی میشوند.
مسئله زمانبندی ماشینهای موازی نامرتبط با هدف کمینهسازی بیشینه زمان تکمیل کارها حجم گسترده ای از تحقیقات در زمینه مسائل ماشینهای موازی نامرتبط را به خود اختصاص داده است. گلس و همکاران ]11[ مسئله Rm||Cmax را مورد مطالعه قرار دادند و از سه الگوریتم فراابتکاری ژنتیک، تبرید شبیهسازی شده و جستجوی ممنوع به منظور یافتن تخصیص بهینه کارها به ماشینها و توالی بین کارها روی هر ماشین استفاده نمودند و در نهایت الگوریتمها را از نظر کیفیت تولید جواب با یکدیگر مقایسه کردند. سریواستاوا ]12[ مسئله مشابهی را مورد بررسی قرار داد و برای حل آن از الگوریتم جستجوی ممنوع استفاده نمود و ادعا کرد که الگوریتم ارائه شده قادر است برای مسائلی در مقیاسهای کاربردی، جوابهای با کیفیت خوب در یک مدت زمان قابل قبول محاسبه نماید. قیرادی و پاتز ]13[ برای حل مسئله Rm||Cmax از یک روش ابتکاری استفاده نمودند و نشان دادند که الگوریتم ابتکاری مورد استفاده آنها قادر است برای مسائل با اندازه بزرگ (بیشتر از 50 ماشین و بیشتر از 1000 کار) نتایج خوبی بدست آورد. هاروویتز و ساهنی ]14[ از رویکرد برنامهریزی پویا برای مسئله زمانبندی دو ماشین موازی نامرتبط با هدف کمینهسازی بیشینه زمان تکمیل کارها استفاده کردند. لانیکا ]15[ مسئله زمانبندی روی دو ماشین موازی نامرتبط با فرض اینکه تمام کارها در ابتدای افق زمانبندی در دسترس نیستند را با هدف کمینهسازی بیشینه زمان تکمیل کارها مورد مطالعه قرار داد و به منظور دستیابی به جوابهای بهینه از روش شاخه و حد استفاده نمود. فانجول پیرو و روئیز ]16[ مسئله زمانبندی ماشین های موازی نامرتبط با هدف کمینه کردن بیشینه زمان تکمیل کارها را با تکیه بر نظریه کاهش تعداد مسائل اصلی تخصیص کارها به ماشینها مطالعه کرده و بر همین اساس چند روش فراابتکاری برای حل مسئله ارائه کردند. ایده اصلی این نظریه مبتنی بر در نظر گرفتن تنها تعدادی از بهترین تخصیصهای ممکن بهجای تمام حالات ممکن از تخصیص کارها به ماشینها است که منجر به کوچک شدن فضای جواب و در نتیجه کاهش زمان محاسباتی الگوریتمهای حل میشود. آنها به منظور حصول اطمینان از کیفیت جوابهای تولیدی توسط الگوریتمهای پیشنهادی، خروجی الگوریتمها را با تعداد زیادی از مسائل موجود در ادبیات مقایسه کردند. گزارش شده است که در اکثر موارد جوابهایی بهتر نسبت به جوابهای موجود بدست آمده است. فانجول پیرو و روئیز ]17[ مسئله Rm||Cmax را در دو وضعیت متفاوت بررسی و برای هر دو شرایط، مدل برنامهریزی ریاضی عدد صحیح آمیخته ارائه نمودند. وضعیت اول بدین صورت است که در آن نیازی نیست که از تمام ماشینهای در دسترس به منظور پردازش کارها استفاده کرد و میتوان به جای تمام آنها، از زیرمجموعهای از ماشینها استفاده نمود. برای مثال میتوان به شرایطی اشاره کرد که یا ظرفیت تولید بیشتر از تقاضای موجود است و یا اینکه بخشی از فرآیند تولید توسط واحد تولیدی دیگری انجام میپذیرد. وضعیت دوم شرایطی است که در آن هیچ الزامی وجود ندارد که تمام کارهای در دسترس پردازش شوند و تنها بخشی از آنها پردازش میشوند.
لیا و همکاران ]18[ مسئله زمانبندی ماشینهای موازی نامرتبط با هدف کمینهسازی مجموع وزنی زمان دیرکرد کارها را مورد بررسی قرار دادند و برای حل آن از یک روش حل دقیق به نام روش شاخه و حد استفاده نمودند. رودریگز و همکاران ]19[ مسئله زمانبندی ماشینهای موازی نامرتبط با هدف کمینهکردن مجموع وزنی زمان تکمیل کارها را مورد مطالعه قرار داده و برای حل آن در ابعاد بزرگ از الگوریتم جستجوی مکرر حریصانه استفاده نمودند. آن ها به دلایلی از جمله اصول ساده الگوریتم، سهولت در پیادهسازی آن و کارایی مناسب الگوریتم در بدست آوردن جوابهای بهینه به عنوان معیارهای انتخاب این الگوریتم اشاره کرده اند.
لین و همکاران ]20[ چند روش ابتکاری بههمراه الگوریتم ژنتیک را برای حل مسائل زمانبندی ماشینهای موازی نامرتبط به منظور کمینهسازی توابع هدف بیشینه زمان تکمیل کارها، مجموع وزنی زمان تکمیل کارها و مجموع وزنی زمان دیرکرد کارها در قالب مسائل جداگانه مورد استفاده قرار دادند. نتایج محاسباتی حاکی از آن بود که در در صورت تنظیم بودن پارامترهای الگوریتم، در هر سه مسئله مورد مطالعه، الگوریتم ژنتیک عملکرد بهتری نسبت به روشهای ابتکاری دارد. لین و همکاران ]21[ مسئله مشابهی را بصورت یک مسئله زمانبندی چند هدفه با توابع هدفی که در بالا به آنها اشاره شد بررسی نمودند. آن ها از دو روش ابتکاری و یک روش فراابتکاری در قالب الگوریتم ژنتیک پیشنهادی خود برای یافتن جوابهای نامغلوب مسئله بهره بردند. از الگوریتمهای ابتکاری به منظور پیدا کردن جوابهای نامغلوب سه مسئله دو هدفه که حاصل ترکیب دو از سه اهداف میباشند و از الگوریتم ژنتیک برای پیدا کردن جواب های نامغلوب مسئله زمانبندی با هدف کمینه کردن همزمان هر سه هدف استفاده کردند.
یانگ و همکاران ]22[ یک مدل ریاضی برای مسئله زمانبندی ماشینهای موازی نامرتبط ارائه نمودند که در آن تاثیر گذشت زمان بر عملکرد ماشینها و فعایتهای نگهداری و تعمیرات را لحاظ کردند. آنها فرض نمودند که هر ماشین ممکن است در طول افق زمانبندی، تحت تعمیرات و یا فرآیندهای مربوط به نگهداری قرار بگیرد و پس از هر مرحله از فعالیتهای نگهداری و تعمیرات، ماشین به مثابه یک ماشین نو میماند. هدف آنها در این تحقیق، تعیین بهترین زمانهای تعمیرات و نگهداری، تعیین بهترین موقعیت آن و تعیین بهترین توالی از کارها به نحوی که مجموع حجم کاری که روی هر ماشین پردازش میشود حداقل شود میباشد و برای تحقق این امر از قاعده توازن گروهی استفاده نمودند. چنگ و همکاران ]23[ مسئله تا حدی مشابه را در دو قالب کمینهکردن مجموع زمانهای تکمیل کارها و مجموع حجم کاری که روی هر ماشین پردازش میشود مورد مطالعه قرار دادند. آن ها فرض کردند که فعالیتهای نگهداری و تعمیرات بر روی هر ماشین در طول افق زمانبندی تنها یکبار میتواند صورت پذیرد و طول مدت زمان انجام این فعالیتها با گذشت زمان و نزدیک شدن به انتهای افق زمانبندی به صورت خطی افزایش مییابد.
2-7. دوبارهکاریموضوع کاهش هزینههای تولید همواره یکی از اهداف و استراتژیهای عملیاتی بیشتر واحدهای تولیدی بوده و هست. برای نیل به این هدف، شرکت باید بطور موثر از منابع موجود استفاده کرده و هزینههای خود را کاهش دهد. در محیطهای تولیدی به دلایل متفاوت از جمله کارا نبودن سیستم تولیدی، از رده خارج بودن ماشینهای تولید، نداشتن یک سیستم تعمیرات و نگهداری مناسب و کارا، خطاهای انسانی، شرایط غیر قابل پیش بینی در تولید و … تولید اقلام معیوب امری اجتناب ناپذیر است. در نتیجه یکی از موثرترین راهکارهای موجود برای کاهش هزینههای مربوط به تولید، دوبارهکاری اقلام فاقد کیفیت، کاهش ضایعات و کم کردن دورریز محصولات است. فرآیندهای دوبارهکاری به مجموعه فعالیتهایی گفته میشود که با هدف بالا بردن کیفیت کالای معیوب و رساندن آن به یک سطح کیفی قابل قبول انجام میپذیرد.
با کمی توجه به تاریخچه مسائل زمانبندی و توالی عملیات این موضوع نمود پیدا میکند که در بسیاری از تحقیقات و مقالات ارائه شده تا به کنون فرض بر این است که تمام محصولات تولیدی توسط ماشینها دارای کیفیت قابل قبول هستند، ولی در دنیای واقعی این موضوع عملا صحیح نیست و به دلایلی که در بالا به آنها اشاره شد، تولید کالای بی کیفیت امری غیر قابل اجتناب است. از جمله کاربردهای عملی فرآیندهای دوبارهکاری در محیطهای صنعتی میتوان به صنایع تولید اجسام نیمه رسانا، صنعت شیشه و صنایع فولاد اشاره کرد ]24[. لذا در این تحقیق تصمیم بر آن است که فرض دوبارهکاری اقلام معیوب به عنوان یک فرض مهم در دستور کار قرار بگیرد. در ادامه این بخش، تعدادی از تحقیقات صورت گرفته در این زمینه ارائه خواهد شد.
یکی از آخرین مطالعات انجام شده در زمینه مسئله زمانبندی ماشینهای موازی یکسان با فرض وجود دوبارهکاری توسط لیو و ژو ]25[ انجام پذیرفته است. آن ها در تحقیق خود از دو معیار مجموع زمان تکمیل کارها و تعداد کارهای تخصیص داده شده به هر ماشین به ترتیب به عنوان معیارهایی برای سنجش میزان کارایی و میزان پایداری سیستم استفاده نمودند. درنهایت یک مسئله زمانبندی دومعیاره توسط آنها مورد بررسی قرار گرفت و برای آن دو الگوریتم حل با زمانهای چند جملهای پیشنهاد کردند.
رمضانیان و سعیدی مهرآباد ]26[ برای مسئله زمانبندی ماشینهای موازی نامرتبط چندمحصولی با فرض امکان دوبارهکاری اقلام معیوب و با هدف کمینهسازی بیشترین زمان تکمیل کارها، یک مدل برنامه ریزی غیرخطی عددصحیح آمیخته ارائه نمودند. آن ها برای حل مسئله در ابعاد متوسط و بزرگ از پنج روش که مبتنی بر قوانین توزیع میباشند استفاده کردند. این روش ها عبارتند از: روش تصادفی، قاعده کوتاهترین زمان پردازش، قاعده طولانیترین زمان پردازش، قاعده کوتاهترین زمان پردازش اصلاح شده و قاعده طولانیترین زمان پردازش اصلاح شده. در نهایت نتایج محاسباتی حاکی از آن بود که روش کوتاهترین زمان پردازش اصلاح شده هم از لحاظ زمان محاسباتی و هم از لحاظ کیفیت جواب نسبت به سایر روشهای مورد استفاده در این تحقیق از کارایی بیشتری برخوردار است.
کانگ و همکاران ]27[مسئله زمانبندی ماشینهای موازی را با فرض امکان دوبارهکاری و با در نظر گرفتن موعد تحویل برای کارهای موجود و زمان آمادهسازی وابسته به توالی مورد مطالعه قرار دادند. آنها برای حل این مسئله در یک زمان محاسباتی معقول، یک الگوریتم توزیع به نام حداقل احتمال دوبارهکاری با درنظر گرفتن موعدهای تحویل (MRPD) که بر فرآیندهای دوبارهکاری تمرکز دارد پیشنهاد دادند. بهمنظور ارزیابی عملکرد این الگوریتم، تعداد زیادی مسئله آزمایشی تولید و از شش معیار مجموع زمان دیرکرد، بیشینه زمان تاخیر کارها، میانگین زمان در جریان ساخت، میانگین زمانهای تاخیر، تعداد فرآیندهای دوبارهکاری و تعداد کارهای با تاخیر استفاده شد. آنها مدعی شدند که برای مسائل آزمایشی تولید شده، الگوریتم پیشنهادی آنها نسبت به تمام الگوریتمهای توزیع بهتر عمل میکند.
در رابطه با تحقیقات انجام گرفته در زمینه دوبارهکاری محصولات فاقد کیفیت، مطالعات فراوانی وجود دارند که بر مباحث تعیین اندازه های انباشته و دستهبندی کارها با هدف تعیین تعداد اقتصادی دستههای کاری تمرکز کردهاند. اکثر این مطالعات محیطهایی را بررسی میکنند که در آنها فرآیندهای کاری و فرآیندهای دوبارهکاری روی یک نوع ماشین انجام میگیرند ]34-28[. برای مثال، ایندرفورت و همکاران ]32[ مسئلهای را بررسی کردند که در آن محصولات یکسان در قالب دستههای کاری بر روی یک ماشین تولید میشوند. فرآیند پردازش هر دسته به دو مرحله تقسیم میشود. در مرحله اول، تمام کارهای یک دسته پردازش میشوند و محصولات با سطح کیفی قابل قبول وارد انبار میشوند. در مرحله دوم، محصولات معیوب متعلق به همان دسته، دوبارهکاری میشوند. آنها همچنین برای پردازش مجدد اقلام بی کیفیت یک محدودیت زمانی در نظر گرفتند. در مقابل، گریبکوفسکایا و همکاران ]34[ مسئله تولید محصولات مشابه بر روی دو ماشین را مورد بررسی قرار دادند. بدین صورت که فرآیندهای کاری روی ماشین اول صورت میپذیرد. سپس، محصولات تولیدی توسط ماشین اول در قالب دستههای متشکل از محصولات از لحاظ کیفیت کنترل میشوند. در نهایت اقلامی که سطح کیفی قابل قبولی نداشته باشند بر روی ماشین دوم دوبارهکاری میشوند.
2-8. زمان نصب وابسته به توالی کارهابهعنوان یک تعریف کلی، زمان نصب برای هر ماشین به مفهوم زمان مورد نیاز برای آمادهسازی ماشین بهمنظور پردازش کارهای تخصیص یافته به آن میباشد. به طور معمول، مسائل زمانبندی با در نظر گرفتن زمانهای نصب ماشین در دو گروه کلی طبقهبندی میشوند. در گروه اول زمان نصب تنها به نوع کاری که روی ماشین پردازش میشود بستگی دارد و اصطلاحا به آن زمان نصب مستقل از توالی گفته میشود. در گروه دوم زمان نصب علاوه بر نوع کاری که بر روی ماشین پردازش میشود، به کار قبلی که بر روی ماشین پردازش شده است نیز بستگی دارد و از آن با عنوان زمان نصب وابسته به توالی یاد میشود. مسائل زمانبندی مربوط به گروه دوم خود به دو دسته تقسیم می شوند. دسته اول شامل مسائلی هستند که در آنها زمان نصب، وابسته به توالی کارها و مستقل از نوع ماشینآلات است و در دسته دوم زمان نصب، هم وابسته به توالی کارها و هم وابسته به نوع ماشینآلات میباشد.
در بسیاری از تحقیقات صورت گرفته در حیطه مسائل زمانبندی فرض بر این بوده است که نیازی به صرف زمان بهمنظور آمادهسازی ماشینها جهت پردازش کارها نیست و یا این زمان را به عنوان بخشی از زمان پردازش کارها در نظر گرفتهاند. اگرچه هر کدام از این فرضیات منجر به ساده شدن تحلیل و بررسی مسائل میشود، در بسیاری از موارد که نیاز است زمانهای آمادهسازی بهصورت جداگانه در نظر گرفته شوند، به شدت بر روی کیفیت جواب تاثیر منفی میگذارد و در عمل منجر به این میشود که مدل با بسیاری از محیطهای تولیدی غیر قابل تطبیق باشد. به عنوان مثال در بسیاری از صنایع همچون صنعت پلاستیک، صنعت تولید شیشه، صنعت نفت، تسهیلات مربوط به رنگآمیزی خوردو، صنعت چاپ، صنعت نساجی و بسیاری از صنایع دیگر نیاز است که زمان آمادهسازی ماشین بصورت جداگانه در مسئله لحاظشود ]37-35[. در رابطه با اهمیت این موضوع میتوان به تحقیقات صورت گرفته توسط برخی از محققین اشاره کرد. بر اساس گزارش پانوالکار ]38[ که در دهه هفتاد میلادی به چاپ رسید، نزدیک به 70% افراد شاغل در زمینه زمانبندی اذعان کردند که در حداقل یک چهارم کارهایی که توسط آنها زمانبندی میشوند، نمیتوان نقش زمانهای آمادهسازی برای ماشینها را نادیده گرفت. همچنین، فلین ]39[ تاثیر فرآیندهای نصب وابسته به توالی را در افزایش ظرفیت تولید و ورتمن ]40[ اهمیت آن ها را در مدیریت ظرفیت تولید بررسی نمودند.
در ادامه این بخش، تعدادی از مطالعات انجام گرفته در زمینه مسائل زمانبندی ماشینهای موازی که با فرض وجود زمان نصب وابسته به توالی کارها صورت پذیرفته است، مورد بررسی قرار میگیرند.
با وجود اهمیت زمانهای آمادهسازی وابسته به توالی در مسائل زمانبندی، در بسیاری از تحقیقات انجام گرفته این موضوع لحاظ نشده است و در تعداد کمی از مطالعات صورت گرفته در زمینه زمانبندی ماشینهای موازی، زمانهای نصب وابسته به توالی در نظر گرفته شده است. این نقیصه در رابطه با ماشینهای موازی نامرتبط بیشتر به چشم میآید.
دریزل و مانچ ]41[ مسئله زمانبندی ماشینهای موازی یکسان را با وجود محدودیتهای پیشنیازی و زمانهای نصب وابسته به توالی با هدف کمینهسازی مجموع وزنی زمان های دیرکرد مورد بررسی قرار دادند و برای حل آن از روش جستجوی همسایگی متغیر استفاده نمودند و عملکرد آن را از لحاظ کیفیت جواب تولیدی با یک روش ابتکاری که مبتنی بر رویهATCSR میباشد مقایسه نمودند. آن ها گزارش دادند که روش جستجوی همسایگی متغیر در بیشتر موارد کیفیت جواب بهتری نسبت به روش ابتکاری مبتنی بر رویه ATCSR برای مسائل آزمایشی مورد استفاده دارد. گوینت و داساچوی ]42[ مسئله زمانبندی ماشینهای موازی یکسان را با در نظر گرفتن زمانهای نصب وابسته به توالی با هدف کمینهسازی بیشینه زمان تکمیل کارها با استفاده از یک روش ابتکاری بر مبنای روش مجارستانی بررسی کردند. کیم و شین ]43[ مسئله مشابهی را با هدف کمینهسازی بیشترین زمان تاخیر کارها بررسی نموده و برای حل آن از الگوریتم جستجوی ممنوع بهره بردند. فاولر و همکارانش ]44[ یک الگوریتم ژنتیک ترکیبی را در مسئله مشابهی برای توابع هدف مختلف شامل بیشینه زمان تکمیل کارها، مجموع وزنی زمان تکمیل کارها و مجموع وزنی زمان دیرکرد کارها مطالعه نمودند. این الگوریتم کارها را به ماشینها اختصاص میدهد و از قوانین توزیع برای زمانبندی ماشینها استفاده میکند. نتایج محاسباتی الگوریتم برای هر سه معیار ذکر شده، عملکرد بهتر آن را نسبت به الگوریتمهای قبلی نشان میدهد. ینگ و چنگ ]45[ از روش ابتکاری جستجوی مکرر حریصانه به منظور حل مسئله زمانبندی ماشینهای موازی پویا با فرض وجود زمانهای نصب وابسته به توالی استفاده کردند.
کیم و همکاران ]46[ مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود زمانهای نصب وابسته به توالی و مستقل از نوع ماشین را با هدف کمینهسازی مجموع زمان دیر کرد کارها بررسی نمودند و برای حل این مسئله، تعدادی روش ابتکاری بر پایه الگوریتم شبیهسازی تبرید ارائه نمودند. کیم و همکاران ]47[ مسئله مشابهی را با هدف کمینهسازی مجموع وزنی زمان دیر کرد کارها که در آن، کارها در قالب دستههایی پردازش میشوند مورد بررسی قرار دادند. در این مسئله فرض بر این است که تمام کارهای موجود در قالب یک دسته، دارای زمان پردازش و موعد تحویل یکسان میباشند و زمانهای آمادهسازی ماشین، وابسته به توالی دستهها و مستقل از نوع ماشینآلات میباشد. آن ها در این تحقیق از چهار رویه جستجوی ابتکاری به نامهای زودترین موعد تحویل وزنی، کوتاهترین زمان پردازش وزنی، روش ابتکاری زمانبندی دستهای دو سطحی و رویه شبیهسازی تبرید استفاده نمودند.
ونگ و همکاران ]48[ مسئله زمانبندی ماشینهای موازی نامرتبط را با فرض وجود زمانهای نصب وابسته به توالی و با هدف کمینهسازی مجموع وزنی زمان تکمیل کارها مطالعه نمودند. آن ها هفت روش ابتکاری ساده را از نظر نتایج محاسباتی با یکدیگر مقایسه نمودند و در نهایت یکی از آن ها را به عنوان بهترین روش انتخاب مینمایند. این روش هر یک از کارها را بر اساس کوچکترین نرخ زمان پردازش بعلاوه زمان نصب نسبت به وزن کار در تابع هدف به ماشینها اختصاص میدهد. لاگندارن و ساپوترا ]49[ مسئله را با تابع هدف مجموع وزنی دیرکرد کارها مورد بررسی قرار دادند. آنها در این تحقیق از الگوریتم جستجوی ممنوع استفاده کردند در شرایطی که یک جواب اولیه برای الگوریتم توسط یک قاعده توزیع ساده تولید میشود. ژو وهیدی ]50[ یک مدل برنامهریزی عدد صحیح برای مسئله مشابه با تابع هدف کمینهسازی زمانهای زودکرد و دیرکرد کارها ارائه نمودند. آن ها گزارش کردند که مدل پیشنهادی برای یک مسئله با اندازه نه کار و سه ماشین در زمان قابل قبول به جواب میرسد. روچا و همکاران ]51[ مسئله زمانبندی ماشینهای موازی نامرتبط را با فرض وجود زمانهای نصب وابسته به توالی و با هدف کمینهکردن بیشینه زمان تکمیل کارها و مجموع وزنی زمان های دیرکرد مورد بررسی قرار دادند. آنها برای این مسئله یک روش شاخه و حد استفاده نمودند و از روش فراابتکاریGRASP بهمنظور تولید یک جواب به عنوان حد بالای مسئله استفاده نمودند. آنها همچنین برای این مسئله، دو مدل برنامه ریزی عدد صحیح آمیخته ارائه کردند و نشان دادند که روش شاخه و حد مورد استفاده، عملکرد بهتری نسبت به دو مدل یاد شده دارد. والادا و روئیز ]3[ برای مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود زمانهای نصب وابسته به توالی و با تابع هدف بیشینه زمان تکمیل کارها یک الگوریتم ژنتیک به همراه یک الگوریتم جستجوی محلی ارائه کردند و آن را برای مسائلی با اندازههای متوسط و بزرگ آزمایش کردند. آنها ادعا کردند که این الگوریتم در مقایسه با سایر روشهای موجود در ادبیات تحقیق دارای بهترین عملکرد است.

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

« (Previous Post)
(Next Post) »

پاسخ دهید

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