sdf169

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

تقدیم به
پدر و مادر عزیزم
و تمام کسانی که ساخته شدنم را مدیون زندگی و دوستی با آنها هستم.
تقدیر و تشکر
نگارنده بر خود لازم می داند تا بدین وسیله از تمامی عزیزانی که همواره در راه کسب علم و دانش یاریگر و مشوقش بودهاند، تشکر نماید .از زحمات بی دریغ و راهنمایی های روشنگرانه و ارزشمند اساتید عزیز آقایان دکتر جواد رضاییان و دکتر ایرج مهدوی که همکاری با ایشان تجربه ای کم نظیر بود,تشکر و قدردانی می نماید.
چکیده
در طول دهه گذشته، گسترش الگوریتمهای فراابتکاری بهینه سازی چند معیاره توجه بسیاری را به خود جلب کرد. مسائل برنامه ریزی تولید بهنگام به عنوان مهمترین مسئله برنامهریزی بهینه سازی نیز مستثنی نبود. البته بسیاری از الگوریتمهای بهینه سازی که برای مسائل گوناگون به کار برده میشدند رویکردی نامناسب داشتند. به زبان دیگر بسیاری از آنها هدف ها را ترکیب میکردند و مسائل را با رویکرد تک هدفه حل میکردند. البته بعضی از محققان الگوریتمهای پارتویی به کار میبرند. در این تحقیق یک برنامه ریزی ماشینهای موازی نامرتبط با زمان آماده سازی وابسته به توالی، زمان دسترسی پویا به کارها، زمان تحویل متفاوت کارها و محدودیت مجموعه پردازشی نشان داده شده است. توابع هدف مورد نظر، مجموع وزنی زمانهای زودکرد و دیرکرد کارها و همچنین مجموع زمان تکمیل کارها را کمینه میکنند. برای حل مدل و اعتبار سنجی آن از الگوریتم مجموع وزنی و الگوریتم محدودیت اپسیلون استفاده شده است. همچنین نشان داده شده است که الگوریتمهایی که از روش شاخه و کران برای حل استفاده میکنند قادر به حل مسائل بزرگ در زمان معقول نمیباشند. بنابراین برای حل این مسئله برنامه ریزی چند معیاره که از نوع چند جملهای سخت (NP-Hard) میباشد الگوربتم فراابتکاری (CENSGA)معرفی شده است. الگوریتم ارائه شده را با استفاده از شاخصهای آماری با الگوریتم فراابتکاری (NSGA-II) مورد مقایسه و تحلیل قرار داده شده است که نتایج نشان دهنده کارایی بهتر الگوریتم فراابتکاری (CENSGA) میباشد. کلمات کلیدی: تولید بهنگام; زمان آمادهسازی وابسته به توالی; کنترل نخبهگرایی; بهینه سازی چند هدفه; الگوریتم مرتب سازی نامغلوب.
فهرست
TOC o “1-3″ h z u فصل اول مقدمه و کلیات PAGEREF _Toc378581848 h 11-1.مقدمه PAGEREF _Toc378581849 h 21-2. تعریف مسأله زمانبندی PAGEREF _Toc378581850 h 51-3. ضرورت انجام تحقیق PAGEREF _Toc378581851 h 71-4. اهداف تحقیق PAGEREF _Toc378581852 h 81-5. مفروضات مسئله PAGEREF _Toc378581853 h 91-6. جنبه های نوآوری تحقیق PAGEREF _Toc378581854 h 101-7. محتوای تحقیق PAGEREF _Toc378581855 h 10فصل دوم ادبیات و پیشینه تحقیق PAGEREF _Toc378581856 h 112-1. مقدمه PAGEREF _Toc378581857 h 122-2. طبقه بندی محیط های زمانبندی PAGEREF _Toc378581858 h 152-3. مسائل ماشینهای موازی PAGEREF _Toc378581859 h 192-3-1. زمان نصب و آماده سازی PAGEREF _Toc378581860 h 202-3-2. دسترسی محدود به ماشینها PAGEREF _Toc378581861 h 262-3-3. زمان دسترسی متفاوت به کارها PAGEREF _Toc378581862 h 272-4. مسائل با تمرکز بر موعد تحویل برای کارها PAGEREF _Toc378581863 h 272-4-1. زمان تکمیل کارها PAGEREF _Toc378581864 h 292-4-2. زمانهای زودکرد و دیرکرد PAGEREF _Toc378581865 h 292-5. مروری بر رویکرد و اصول سیستم تولیدی بهنگام PAGEREF _Toc378581866 h 312-6. توالی ماشینﻫای موازی با معیارهای زودکرد و دیرکرد PAGEREF _Toc378581867 h 332-7. جمع بندی PAGEREF _Toc378581868 h 34فصل سوم مدل ریاضی و بهینه سازی چند هدفه PAGEREF _Toc378581869 h 363-1. مقدمه PAGEREF _Toc378581870 h 373-2. تعریف مسئله PAGEREF _Toc378581871 h 373-2-1. مفروضات مسئله PAGEREF _Toc378581872 h 393-3. مدل پیشنهادی PAGEREF _Toc378581873 h 393-3-1.نمادها، تعاریف، پارامترها و متغیر های تصمیم PAGEREF _Toc378581874 h 403-3-2. پارامترهای ورودی PAGEREF _Toc378581875 h 403-3-3. توابع هدف PAGEREF _Toc378581876 h 413-3-4. محدودیتها PAGEREF _Toc378581877 h 413-4. اعتبارسنجی مدل PAGEREF _Toc378581878 h 433-5. پیچیدگی مسئله PAGEREF _Toc378581879 h 453-6 بهینه سازی چند معیاره PAGEREF _Toc378581880 h 473-6-1. ارتباط غالب PAGEREF _Toc378581881 h 473-6-2. نقاط بهینه موضعی PAGEREF _Toc378581882 h 483-6-3. نقاط بهینه سراسری PAGEREF _Toc378581883 h 483-6-4. مرز بهینه PAGEREF _Toc378581884 h 483-7. روشهای بهینه سازی PAGEREF _Toc378581885 h 493-7-1. روشهای اسکالر PAGEREF _Toc378581886 h 493-7-2. روش مجموع وزنی PAGEREF _Toc378581887 h 513-7-2-1. طراحی روش مجموع وزنی برای حل مسأله مورد نظر PAGEREF _Toc378581888 h 543-7-3. روش محدودیت-ε PAGEREF _Toc378581889 h 553-7-3-1. طراحی روش محدودیت – ε برای حل مسأله PAGEREF _Toc378581890 h 573-7-4. روشهای عکس العملی PAGEREF _Toc378581891 h 573-7-5. روش های مبتنی بر منطق فازی PAGEREF _Toc378581892 h 583-7-6. روش های فرا ابتکاری PAGEREF _Toc378581893 h 593-7-7. الگوریتم NSGA-II PAGEREF _Toc378581894 h 603-7-7-1. مرتب سازی سریع PAGEREF _Toc378581895 h 613-7-7-2. عملگر گزینش تورنمنت تراکمی PAGEREF _Toc378581896 h 633-7-7-3. فاصله تراکمی PAGEREF _Toc378581897 h 633-7-8. طراحی روش فراابتکاری NSGA-II برای حل مسأله PAGEREF _Toc378581898 h 653-7-9. طراحی روش فراابتکاری CENSGA برای حل مسأله PAGEREF _Toc378581899 h 703-8. مقایسه روش های بهینه سازی چند هدفه PAGEREF _Toc378581900 h 713-8-1. شاخص متوسط فاصله از نقطه ایدهآل PAGEREF _Toc378581901 h 733-8-2. شاخص نرخ دستیابی به توابع هدف PAGEREF _Toc378581902 h 743-8-3. شاخص گستردگی جواب های غیر مغلوب (SNS) PAGEREF _Toc378581903 h 743-8-4. شاخص یکنواختی فضا PAGEREF _Toc378581904 h 743-9. جمعﺑندی PAGEREF _Toc378581905 h 75فصل چهارم محاسبات و نتایج تحقیق PAGEREF _Toc378581906 h 774‐1. مقدمه PAGEREF _Toc378581907 h 784‐2. تنطیمات پارامترها و شرایط اجرای الگوریتم ها PAGEREF _Toc378581908 h 794-3. الگوریتمهای NSGA-II,CENSGA PAGEREF _Toc378581909 h 804-4. روش مجموع وزنی PAGEREF _Toc378581910 h 804-5. روش محدودیت-ε PAGEREF _Toc378581911 h 814‐6. ساختار مسائل PAGEREF _Toc378581912 h 824‐7. معیارهای ارزیابی الگوریتمها PAGEREF _Toc378581913 h 834‐8. مسائل با ابعاد کوچک و متوسط PAGEREF _Toc378581914 h 834-8-1. نتایج آزمایشات مسائل کوچک و متوسط PAGEREF _Toc378581915 h 834‐9. مسائل با ابعاد بزرگ PAGEREF _Toc378581916 h 904‐10. نتایج محاسباتی PAGEREF _Toc378581917 h 904‐11. جمعﺑندی PAGEREF _Toc378581918 h 96فصل پنجم نتیجه گیری و پیشنهادات PAGEREF _Toc378581919 h 975‐1. مقدمه PAGEREF _Toc378581920 h 985‐2. نتیجهﮔیری PAGEREF _Toc378581921 h 995‐3. پیشنهادهای آتی PAGEREF _Toc378581922 h 100فهرست منابع و مراجع PAGEREF _Toc378581923 h 102
فهرست جداول
جدول 2-1. محیطهای کارگاهی (نماد α) 13
جدول 2-2. توابع هدف رایج در ادبیات 15
جدول 3-1. زمانهای پردازش،موعدهای تحویل و زمان دسترسی44
جدول 3-2. زمان نصب ماشین یک و دو برای کارهای مختلف 44
جدول 4-1. حدهای بالا برای مسائل مختلف 82
جدول 4-2. جوابهای نامغلوب مربوط به مسأله 5j2m به تفکیک روش ها84
جدول 4-3. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j2m 85
جدول 4-4. جوابهای نامغلوب مربوط به مسأله 5j3m به تفکیک روش ها85
جدول 4-5. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j3m 86
جدول 4-6. جوابهای نامغلوب مربوط به مسأله 8j2m به تفکیک روش ها87
جدول 4-7. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j2m88
جدول 4-8 . جوابهای نامغلوب مربوط به مسأله 8j3m به تفکیک روش ها 89
جدول 4-9. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j3m 90
جدول 4-10 نتایج شاخصهای متریک برای الگوریتم CENSGAوNSGA-II 91
جدول 4- 11. ارزیابی آماری الگوریتمهای فراابتکاری بکار گرفته شده 94
فهرست شکلها و نمودارها
شکل 2-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید 19
شکل 3-1. سلسلهمراتب پیچیدگی محیطهای کارگاهی در مسائل زمانبندی46
شکل 3-2. سلسلهمراتب پیچیدگی توابع هدف در مسائل زمانبندی46
شکل 3-3. نقاط بهینه موضعی 48
شکل 3-4. رابطه فضای جواب و ارتباط غالب 48
شکل 3-5. نمایش روش مجموع وزنی با مرز بهینه پارتو محدب 52
شکل 3-6. نمایش روش مجموع وزنی با مرز بهینه پارتو غیر محدب 54
شکل 3-7. روش محدودیت- ε 56
شکل 3-8. نمایش الگوریتم NSGAII61
شکل 3-9. محاسبه فاصله تراکمی 64
شکل 3-10. ساختار کروموزوم66
شکل 3-11. نحوه ایجاد جمعیت اولیه 67
شکل 3-12. نحوه عملکرد عملگر تقاطع 69
شکل 3-13. عملگر تقاطع تک نقطه ای با نقطه برش 369
شکل 3-14. نحوه عملکرد عملگر جهش 70
شکل 3-15. استراتژی انتخاب در الگوریتم CENSGA و NSGA-II 71
شکل 3-16. دو هدف در بهینه سازی چند هدفه72
شکل 3-17. یک مجموعه ایده آل از جواب های نامغلوب72
شکل 3-18. همگرائی خوب، اما تنوع ضعیف (الگوریتم 1)73
شکل 3-19. همگرائی ضعیف، اما تنوع خوب (الگوریتم 2)73
شکل 4-1. نمایش جوابهای نامغلوب ε-محدودیت مسأله 5j2m 84
شکل 4-2. نمایش جوابهای نامغلوب روش وزنی مسأله 5j2m 84
شکل 4-3. نمایش جوابهای نامغلوب روش وزنی مسأله 5j3m86
شکل 4-4. نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 5j3m86
شکل 4-5 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j2m88
شکل 4-6 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j2m 88
شکل 4-7 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j3m 89
شکل 4-8 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j3m89
شکل 4- 9 نمودار نتایج محاسباتی شاخص های متریک در مسائل مختل92
شکل 4-10. نمودارجعبه ای (BoxPlot) نتایج ارزیابی الگوریتمهای CENSGA,NSGA-II 93
شکل 4-11. نمودار میانگین و فواصل اطمینان (سطح اطمینان 95%)نتایج ارزیابی الگوریتم ها 95
4486275628650
فصل اول مقدمه و کلیاتمقدمه زمانبندی، فرایند تخصیص منابع به فعالیتها با درنظر گرفتن دورههای زمانی مربوط به آنها به منظور بهینهسازی یک یا چند هدف میباشد. این فرایند به عنوان یک فرایند تصمیمگیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. زمانبندی کارای فعالیتها زمینهساز بهبود عملکرد سیستمهای تولیدی میباشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار میآید.
تئوری زمانبندی در ارتباط با مدلهای ریاضی است که فرایند زمانبندی را تشریح میکنند. چشمانداز تئوریک یک نگرش کمی برای بدست آوردن ساختار مسائل در چهارچوب مدلهای ریاضی بهدست میدهد که این امر با تشریح منابع و فعالیتها و تبدیل اهداف تصمیمگیری به یک تابع هدف، صورت میپذیرد. عمل زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه است که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می شود. در نتیجه، منابع، فعالیتها و توابع هدف عناصر کلیدی مدلهای زمانبندی محسوب میشوند.
منابع بر حسب قابلیتهای کمی و کیفی خود مشخص میشوند، بطوریکه هر مدل نشان دهنده نوع و میزان منابع بکار رفته در آن میباشد. از سوی دیگر، فعالیتها بر حسب اطلاعاتی از قبیل منابع مورد نیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف میشوند. توابع هدف نیز دربرگیرنده هزینههای سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیتها میباشند. تصمیمات عمده در فرایند زمانبندی شامل بهرهبرداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمانهای تحویل با موعدهای تحویل تعیینشده میشوند. شرکت های تولیدی در تلاش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع (JIT) ، پاسخگوی سریع (QR) ، تکنولوژی گروهی (GT) و مدیریت کیفیت جامع (TQM) بدست آورند[58].
این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده است. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل شود، که به مسائل زمانبندی با هزینه های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می شود. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیط های تولید متنوع است.
مسائل با تعیین موعد تحویل در 25 سال گذشته بعلت روشهای جدید مدیریت مانند مفاهیم JIT مورد توجه بسیار قرار گرفته است. چنگ که کمک زیادی به مسائل زمانبندی و تخصیص موعد تحویل کرد بیان می کند که تکمیل یک کار زودتر از موعد تحویل به معنی تحمیل هزینه های نگهداری موجودی غیر ضروری است ، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به جریمه های قراردادی و از دست دادن اعتبار مشتری می شود[33].
بطور جالب توجه هدف مسئله حداقل دیرکرد و زودکرد (ET) کاملا با سیاست کنترل تولید JIT مطابقت دارد.مسئله ماشین های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می باشند. از دیدگاه تئوری به این خاطر که تعمیمی از حالت تک ماشینه می باشد و از دیدگاه عملی به این جهت که در دنیای واقعی بسیارمعمول است مورد توجه قرار گرفته شده است.
مسئله به کارگیری ماشین های موازی از آنجا مورد توجه است که اگر زمانبندی روی یک ماشین منجر به هزینه زیادی شود ممکن است در نظر گرفتن ماشین های بیشتر سبب کاهش هزینه شود. ضمن این که مقدار دیرکرد یا زودکرد نیز می تواند با افزایش تعداد ماشین ها کاهش یابد. در این شرایط هزینه به کارگیری ماشین یا نگهداری ماشین اضافه می شود که با حل مسئله بهینه سازی می توان تعیین کرد چه ماشین هایی به کار گرفته شوند و کدام کارها با چه توالی روی این ماشین ها انجام شود.
در عمل، زمانبندی ها با استفاده از الگوریتم های زمانبندی یا قوانین بر پایه دانش ایجاد می شوند. الگوریتم های زمانبندی ، زمانبندی را توسعه می دهد که یک معیار اندازه گیری مانند حداقل کردن انحراف موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد را بهینه می کند. انگیزه بسیاری از توسعهها و پیشرفتهای علمی در حوزه زمانبندی برخاسته از محیطهای صنعتی است و بهطور طبیعی در بیان مفاهیم زمانبندی از واژههای بکار رفته در صنعت استفاده میشود. به همین خاطر منابع با عنوان ماشین بهکار میروند و به هر کدام از فعالیتها، کار اطلاق میشود بطوریکه کارها اغلب به وسیله مجموعهای از ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند.
بطور کلی، مسائل زمانبندی به صورت مسائل بهینهسازی محدودیتدار بیان میشوند که در آنها به بررسی تصمیمات مربوط به تخصیص ماشینها وتوالی پردازش کارها پرداخته میشود. درحالتی که تنها یک ماشین موجود است، تعیین توالی پردازش کارها یک برنامه زمانی کامل را تشکیل میدهد. مسائل تکماشینه با وجود سادگی ذاتی، سنگبنای درک فراگیر مفاهیم زمانبندی را تشکیل میدهند. درمقابل، زمانبندی مسائل چندماشینه شامل سیستمهای موازی، سیستمهای متوالی و سیستمهای ترکیبی میباشد. در سیستمهای موازی، هر یک از کارها با انجام یک عملیات همانند مسائل تکماشینه بر روی یکی از ماشینهای موازی موجود پردازش میشوند و به دنبال آن تخصیص ماشینها به کارها موضوعیت پیدا میکند. این درحالی است که در سیستم های متوالی و ترکیبی، کارها با انجام چند عملیات بر روی ماشینها پردازش میشوند و مسائل مربوطه ساختار نسبتا پیچیدهتری را تجربه میکنند.
در این تحقیق، به بررسی مسئله زمانبندی ماشینهای موازی نامرتبط به عنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطهنظر تئوری و تجربی است، پرداخته میشود. مسائل ماشینهای موازی نامرتبط حالت عمومیتیافته مسائل تکماشینه و حالت خاصی از مسائل ماشینهای متوالی منعطف محسوب میشوند. تکنیکهای بهکار رفته در بهینهسازی این نوع مسائل با اعمال رویههای ترکیبی در مسائل زمانبندی پیچیدهتر استفاده میشوند. در بخشهای آتی این فصل، شرح تفصیلی مسئله مورد بررسی این تحقیق ارائه میشود.
1-2. تعریف مسأله زمانبندی
زمانبندی ماشینهای موازی نامرتبط حالت عمومی مسائل کلاسیک ماشینهای موازی بهشمار میآید. در یک مسئله کلاسیک زمانبندی ماشینهای موازی، مجموعهای از کارهای مستقل وجود دارد که هر کدام از آنها بر روی یکی از ماشینهای موازی یکسان موجود پردازش میشوند. در حالت کلی، ماشینهای موازی به صورت نامرتبط درنظر گرفته میشوند بطوریکه زمان پردازش کارها بر روی ماشینها نهتنها به نوع کار بلکه به نوع ماشین نیز وابسته است. در این حالت پیکربندی ماشینها یکسان نیست و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای مختلف وجود ندارد. محیطهای کارگاهی شامل ماشینهای موازی نامرتبط در صنایع تولیدی گوناگون نظیر صنایع نساجی، الکترونیک، شیمیایی و همچنین صنایع خدماتی به وفور بهچشم میخورد [59].
در برخی از کاربردهای زمانبندی ماشینهای موازی نامرتبط، ماشینها دارای سطوح تکنولوژیکی متفاوتی هستند و لزوما قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نمیباشند. در نتیجه، هرکدام از کارها تنها بر روی زیرمجموعهای از مجموعه ماشینها میتوانند پردازش شوند و اصطلاحا پردازش کارها با دسترسی محدود به ماشینها صورت میپذیرد.
مسائل زمانبندی غالبا به محیطهای کارگاهی میپردازند که در آنها زمان نصب ماشین نادیده گرفته میشود و یا به عنوان بخشی از زمان پردازش کارها تلقی میشود. اینگونه محیطهای کارگاهی با این فرض مدلسازی میشوند که زمانهای نصب در مقایسه با زمانهای پردازش کوچک هستند بنابراین میتوان آنها را نادیده گرفت و یا این که زمانهای نصب مستقل از توالی پردازش کارها بر روی ماشینها هستند، در نتیجه میتوان آنها را به زمانهای پردازش اضافه نمود. با این وجود، در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد [55]. در این شرایط، زمان نصب به عنوان بخشی مجزا از زمان پردازش درنظر گرفته میشود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به نوع کار قبلی که بر روی آن ماشین پردازش شده نیز بستگی دارد. تلقی زمان نصب به صورت مجزا از زمان پردازش در بیشتر تکنیکهای مدیریت تولید نوظهور نظیر تولید به موقعو تکنولوژی گروهی مورد استقاده قرار میگیرد.
امروزه با بکارگیری موفقیتآمیز مفهوم تولید به موقع در مفاهیمی چون مدیریت تولید و انبارداری، نیاز به تکمیل پردازش کارها در موعد تحویل آنها یک امر کلیدی در محیطهای صنعتی محسوب میشود. به بیان دیگر، تکمیل کارها پیش از موعد تحویل به همان اندازه که دیرکرد در تکمیل آنها اهمیت دارد، در کانون توجه قرار میگیرد. هزینههای مرتبط با زمانهای زودکرد و دیرکرد کارها، محققان را بر میانگیزاند که این هزینهها را در قالب معیارهای بهینهسازی گوناگون در مسائل زمانبندی بکار گیرند.
در این پایان نامه به مسأله زمانبندی دو معیاره ماشین های موازی با سرعت متفاوت با هدف کمینه کردن مجموع وزنی دیرکردها و زودکردها و نیز کمینه کردن مجموع زمان تکمیل کارها به طور همزمان در حالتی که کارها دارای زمان آماده سازی وابسته به توالی و زمان دسترسی متفاوت و دسترسی محدود به ماشین آلات می باشد می پردازیم.
نظام تولید بهنگام تفکر و نگرشی نوین در اداره سازمانهای صنعتی است که با اصل تکنیکها و روشهای برخاسته از آن، حذف کامل و جامع اتلاف و افزایش بهره وری در تمامی فعالیتها اعم از داخل و خارج سازمان تعقیب می گردد.
تعاریف بسیاری توسط کارشناسان برای تولید بهنگام ارائه شده است، در زیر به تعدادی از این تعاریف اشاره شده است.
JIT یعنی :
پافشاری بر کیفیت برتر انجام امور خرید و تولید و … دقیقا در زمان مقرر
بهنگام بودن نظام، مستلزم بهنگام بودن همه اجزای آن است
در کل JIT یعنی فقط به هنگام ” نه دیرتر نه زودتر”
در JIT هدف تولید بهنگام است، یعنی اگر مشتری و تولید کننده زمان تحویل کالا را در یک زمان معین توافق کنند، تولید کننده باید تولیدات خود را طوری برنامه ریزی کند که کالا را در حد امکان در زمان مناسب تولید و در زمان مقرر تعیین شده به دست مشتری برساند. اگر این دیرتر از زمان تحویل آماده شود، تولید کننده متحمل جریمه ای به عنوان تأخیر تولید خواهد شد که این جریمه امکان دارد به صورتهای مختلف نمود پیدا کند. همچنین اگر تولید کننده، کالا را زودتر از زمان تحویل، تولید کند، این کالا را باید تا زمان تحویل در انبار نگهداری کند لذا در این صورت نیز متحمل هزینه خواهد شد.
در ادبیات زمان بندی تولید بهنگام هدف کمینه کردن معیارهای زودکرد و دیرکرد به صورت توأم می باشد، که در این پایان نامه علاوه بر این هدف معیار مجموع زمان تکمیل کارها را نیز کمینه می شود و از آنجا که زمان آماده سازی وابسته به توالی و زمان در دسترس بودن کارها در مسئله زمانبندی ماشین های موازی حائز اهمیت می باشد از این نظر در این تحقیق روی مسئله ماشین های موازی با زمان آماده سازی وابسته به توالی و زمان دسترسی متفاوت به کار متمرکز شده است.
1-3. ضرورت انجام تحقیق
با توجه به اهمیت روزافزون مسائل ماشین های موازی در نظر گرفتن معیارهای مختلف مورد توجه محققان این علم می باشد.امروزه در اغلب کارخانجات تولیدی و شرکت های خدماتی تأمین به موقع سفارش مشتری یا خدمت رسانی به موقع حائز اهمیت است. هزینه های زودکرد و دیرکرد در این امور نه تنها مشتری را متضرر می گرداند بلکه به شرکت نیز هزینه وارد شده و علاوه بر آن اعتبار خود را نیز از نظر مشتری از دست می دهد. مسائل تخصیص موعد تحویل زمانی جنبه عملی دارد که یک شرکت یک موعد تحویل به مشتریان در طول مذاکرات فروش پیشنهاد می کند و یک قیمت تقلیل یافته (جریمه) برای زمانیکه موعد تحویل دور از موعد انتظار باشد پیشنهاد می کند. هر چه موعدهای تحویل ثابت شده تر باشد احتمال اینکه محصول به موقع تحویل داده شود بیشتر است. به منظور نگهداشتن یک وجهه خوب در میان مشتریان بسیاری از شرکت ها برای حفظ موعدهای تحویل ایجاد شده، هزینه های نگهداری معقولی را متحمل می شوند .
در بحث زمانبندی ماشین های موازی ، هزینه برای هر ماشین وجود دارد که در واقع هزینه به کارگیری ماشین است که با زمان تکمیل کارها رابطه مستقیم دارد و لذا با توجه به این که زمان بکارگیری ماشین چه مقدار است توالی های مختلفی روی ماشین با مقدار زودکرد و دیرکرد می کند. در این پایان نامه مسأله حداقل کردن مجموع زمان تکمیل کارها و هم چنین مجموع هزینه های دیرکرد و زودکرد به طور همزمان در نظر گرفته شده است.
تقریبا همه مقالاتی که هدف های زودکرد و دیرکرد را در نظر می گیرند فرض می کنند که زمان آماده سازی ناچیز و یا مستقل از توالی است و همه کارها در زمان صفر در دسترس هستند لیکن زمان در دسترس بودن کار و زمان آماده سازی وابسته به توالی برای برخی صنایع از قبیل سازندگان اتومبیل و صنعت شیمی بسیار مهم است. با توجه به اهمیت زمان دسترسی و زمان آماده سازی وابسته به توالی در این پایان نامه زمان در دسترس بودن کار و زمان آماده سازی وابسته به توالی در نظر گرفته شده است.
یک مدل ترکیبی بهینه سازی برای این منظور ایجاد شده که از نوع مسائل NP Hard است. که برای مسائل با اندازه کوچک از روشهایی مستقیم که حل بهینه را می دهند استفاده شده و برای مسائل با اندازه متوسط و بزرگ از روش فراابتکاری که جواب بهینه یا نزدیک به بهینه را در یک زمان کوتاه می دهد استفاده شده است .
1-4. اهداف تحقیق تحقیق حاضر با هدف کاهش فاصله میان پیشرفتهای تئوریک و کاربردهای صنعتی در حوزه علم زمانبندی صورت گرفته است. در این راستا، یک مدل جدید برای مسئله زمانبندی ماشینهای موازی نامرتبط با محدودیتهای زمان نصب وابسته به توالی پردازش کارها و دسترسی محدود به ماشینها وزمان دسترسی به کارها با معیارهای بهینهسازی زمانهای زودکرد و دیرکرد وزنی کل و نیز مجموع زمان تکمیل کارها ارائه میشود. از اهداف این تحقیق علاوه بر مروری بر مطالعات صورت گرفته در حوزه زمانبندی و مسائل ماشینهای موازی تک هدفه، چند هدفه و چند معیاره ارائه مدل ریاضی دو هدفه و استفاده از روش فرا ابتکاری برای حل مسئله مطرح شده مد نظر میباشد. به همین منظور از الگوریتمهای فراابتکاری چند هدفه بر پایه الگوریتم ژنتیک به منظور حل این مدل در مقیاس کاربردی استفاده میگردد. در این مطالعه برای حل و اعتبار سنجی مدل و نشان دادن کارایی الگوریتمهای مطرح شده با دو تابع هدف برای مسائل کوچک از روش های حل دقیق، الگوریتم مجموع وزنی و الگوریتم محدودیت-ε استفاده شده است و برای مسائل متوسط و بزرگ الگوریتم NSGA-II و CENSGA توسعه داده شده است.
1-5. مفروضات مسئله مفروضات زیر در ارائه مدل مسئله درنظر گرفته میشود:
ماشینها به صورت موازی و نامرتبط با یکدیگر قرار گرفتهاند و زمان پردازش کارها بر روی ماشینها متفاوت میباشد.
شکست یا وقفه در کارها مجاز نمی باشد(هر عملی بر روی ماشین نمی تواند بیش از یک بار شروع شود).
کارها دارای زمان نصب و آماده سازی وابسته به توالی هنگام تعویض کارها بر روی ماشینها می باشند.
تمامی کارها در لحظه زمانی صفر در دسترس نمیباشند به عبارتی پردازش کار نمیتواند قبل از زمان دسترسی آغاز شود.
زمانهای پردازش، نصب ماشین، موعد تحویل و ضرایب هزینه زودکرد و دیرکرد زمانی معین میباشند.
کار مجازی نوع صفر مفروض است. این کار همواره در اولین موقعیت بر روی تمامی ماشینها پردازش میشود. زمان پردازش این کار صفر منظور میشود و شروع پردازش آن نیازی به انجام عملیات نصب ماشین ندارد.
تمامی ماشین ها به طور مستمر دسترس هستند و امکان خرابی ماشین وجود ندارد.
هرکار در طول زمان پردازش خود فقط بر روی یک ماشین پردازش میشود.
هر کاری تنها بر روی زیر مجموعه ای از ماشینها قابل پردازش است.
هر ماشین در هر لحظه قادر به پردازش تنها یک کار میباشد.
تمام پارامترها قطعی هستند و هیچ پارامتر تصادفی نداریم.
1-6. جنبه های نوآوری تحقیق تحقیق موجود از دو جنبه صورت مسئله و روش حل نسبت به تحقیقات پیشین دارای نوآوری میباشد. در این تحقیق یک مدل ریاضی جدید برای مسئله زمانبندی ماشینهای نامرتبط با توابع هدف زمانهای زودکرد و دیرکرد وزنی کل و نیز مجموع زمان تکمیل کارها و محدودیتهای زمان نصب وابسته به توالی پردازش کارها و دسترسی محدود به ماشینها و زمان دسترسی متفاوت به کارها ارائه داده شده است. همچنین، یک رویکرد فراابتکاری با استفاده از الگوریتمهای چند هدفه ژنتیک برای حل مسئله ارائه شده است.
1-7. محتوای تحقیقاین پایان نامه دارای ساختار زیر است. در فصل دوم به منظور آشنایی خواننده مروری تقریبا جامع بر ادبیات موضوع در بخش های مختلف اعم از ادبیات موضوع مسئله زمانبندی ماشینهای موازی با معیارهای مختلف و زمانبندی این سیستم ها با زمان های آماده سازی وابسته به توالی صورت گرفته است. فصل سوم به توسعه مدل ریاضی و کلیات، اعتبار سنجی مدل و همچنین مکانیزم روش های دقیق و فرا ابتکاری توضیح داده شده و جزیئات الگوریتم تکاملی چند هدفه توسعه داده شده. به انضمام معیارهای اندازه گیری عملکرد روش های فرا ابتکاری نشان داده میشود. در فصل چهارم پس از بیان نحوه تولید مسائل نمونه، مسائلی کوچک که الگوریتمهای دقیق قادر به حل آن در زمان معقول میباشند را تولید نمودهایم و با استفاده از روشهای دقیق حل نمودهایم و و در ادامه برای مسائل بزرگ پارامترهای الگوریتم های فرا ابتکاری توسعه داده شده را تنظیم کرده و برای هر حالت با استفاده از معیارهای کارایی معرفی شده است. کارایی الگوریتم ها جداگانه در مقایسه با روش های موجود اندازه گیری شده است و نمایش گرافیکی آن با استفاده از نمودار و شکل نشان داده شده است. در پایان در فصل پنجم بعد از نتیجه گیری کلی، چند زمینه تحقیق برای مطالعات آتی به خوانندگان پیشنهاد شده است.
4486275628650
فصل دوم ادبیات و پیشینه تحقیق2-1. مقدمه مقاله های مربوط به مسائل زمانبندی برای اولین بار در اواسط دهه 1950 به چاپ رسیدند و پس از آن مقالات زیادی با در نظر گرفتن جنبه های مختلف آن به چاپ رسیدند. البته در اوایل قرن گذشته با مطالعات صورت گرفته توسط هنری گانت و سایر پیشگامان در کانون توجه قرار گرفته بود که این مطالعات منجر به ارائه الگوریتمهای مهمی چون قاعده جانسون برای مسئله سیستم کارگاه جریانی، قاعده زودترین موعد تحویل برای کمینهسازی زمان تاخیر بیشینه و قاعده کوتاهترین زمان پردازش با هدف کمینهسازی زمان جریان میانگین شد. برای حل مسائل پیچیدهتر تحقیقات به سمت حل با روشهای دقیق چون برنامهریزی خطی و برنامهریزی پویا معطوف شد. پس از انتشار مقاله مشهور ریچارد کارپ [29] در زمینه نظریه پیچیدگی، محققان به این نتیجه رسیدند که روشهای دقیق قادر به حل مسائل بزرگ و با دادههای بزرگ نیستند و نمیتوانند درمدت زمان معقول به جواب بهینه برسند .همچنین تا دهه 1980 محققان مسائل زمانبندی بر روی بهینه سازی تک معیاره تمرکز داشتند.اما همانطور که میدانیم در مسائل دنیای واقعی، همواره چند معیار به طور همزمان بر روی بهینه سازی تاثیر دارد.به گونهای که ممکن است علاوه بر معیارهایی که برای بهینه سازی مهم هستند معیارهای متفاوتی از طرف صاحبان صنایع و یا جامعه و ناظرین کیفی نیز افزوده شود.در دهههای هشتاد و نود میلادی توجه محققین به حل مسائل زمانبندی در زمان محاسباتی معقول با الگوریتمهای غیر دقیق نظیر تبرید شبیهسازی شده، جستجوی ممنوع، الگوریتم ژنتیک و سایر تکنیکهای محاسبات تکاملی معطوف شد. اما پس از آن در دهه نود و در ابتدای قرن بیستویکم میلادی نسل جدیدی از الگوریتمهای چند هدفه معرفی شدند.این الگوریتمها هدفها را به یک هدف تبدیل نمیکردند.]27[ و بسیار موثرتر از دیگر الگوریتمها در بهینه سازی برای مدلهای چند هدفه هستند. برخی از معیارهایی که مورد بررسی قرار می گیرند عبارتند از :
حداکثر زمان تکمیل، کل زمان گردش کار، حداکثر دیرکرد، کل دیرکرد، حداکثر زودکرد، کل زودکرد، مجموع دیرکرد و زودکرد و تعداد کارهای با تأخیر. بهینه سازی چند هدفه با کشاکشی بین توابع هدف، معمولا به جای یک جواب بهینه، یک مجموعه جواب بهینه ارائه می دهند که بهینه پارتویی نامیده میشوند. این مجموعه جواب پارتویی شامل جوابهایی است نزدیکترین جواب به جواب بهینه که هیچ جواب دیگر بهتر از آنها نمی توان یافت که همزمان تمام توابع هدف را بهبود دهد.
گراهام و همکارانش [21] با استفاده از سیستم سه نمادی γ|β|α مسائل زمانبندی را بر اساس پیکربندی ماشینها و محدودیتهای پردازش کارها طبقهبندی کردند. این مسائل بر اساس پیکربندی و شکل کارگاه (α)، محدودیت ها و فرضیات (β) و تابع هدف (γ) دسته بندی می شوند. پس هر مسئله میتواند بر اساس سه گانه α|β|γ بیان می شود. پارامتر α ساختار کارگاه را تعریف می کند که شامل تعداد مراحل و تعداد و ویژگی ماشین های داخل هر مرحله می شود. جدول زیر لیست نمادهای متداول بکار رفته در این سیستم را نمایش میدهند:
جدول 2-1 محیطهای کارگاهی (نماد α)
سادهترین شکل و حالت خاص تمامی محیطهای کارگاهی ممکن. تکماشینه 1m ماشین کاملا یکسان به موازات هم قرار میگیرند؛ هرکدام از کارها نیاز به یک عملیات دارد و بر روی یکی از ماشینهای موجود پردازش میشود. ماشینهای موازی یکسان Pmحالت کلیتر ماشینهای موازی یکسان؛ ماشینها دارای سرعت پردازش متفاوت هستند. ماشینهای موازی یکنواخت Qmحالت کلیتر ماشینهای موازی یکنواخت؛ سرعت پردازش ماشینها هم به نوع ماشین و هم به نوع کار بستگی دارد. ماشینهای موازی نامرتبط Rmm ماشین به صورت متوالی وجود دارد؛ هر کدام از کارها بر روی تمامی ماشینها پردازش میشوند، تمامی کارها مسیر پردازش یکسانی دارند. کارگاه جریانی Fmحالت کلیتر کارگاه جریانی؛ m ایستگاه پردازش به صورت متوالی وجود دارد؛ در هر ایستگاه یکی از حالات سهگانه ماشینهای موازی برای پردازش یک کار رخ میدهد. کارگاه جریانی منعطف FFmهر کدام از کارها دارای مسیر پردازش متمایز بر روی m ماشین موجود میباشند. تولید کارگاهی Jmحالت کلیتر تولید کارگاهی؛ m مرکز پردازش وجود دارد؛ در هر ایستگاه یکی از حالات سهگانه ماشینهای موازی برای پردازش یک کار رخ میدهد. تولید کارگاهی منعطف FJmm ماشین وجود دارد؛ هر کدام از کارها بر روی هر کدام از ماشینها یک یا چند بار پردازش میشود؛ محدودیتی برای مسیر پردازش کارها وجود ندارد. کارگاه باز Omپارامتر دوم، β، محدودیت و فرضیاتی مازاد بر مسئله استاندارد را بیان می کند که معمول ترین آنها در اینجا لیست شده اند:
rj بیانگر این مطلب است که کار j نمی تواند قبل از روز ترخیصش rj شروع به پردازش کند.
prmu نشان دهنده ترتیب یکسان پردازش کارها در هر مرحله است.
prec بیانگر این مطلب است که محدودیت های تقدم بین عملیات های کارهای مختلف وجود دارد.
Mj نشان دهنده این مطلب است که پردازش کار j محدود به مجموعه ای از ماشین ها Mj در مرحله k شده است.
Ssd بیانگر این مطلب است که زمان های پردازش وابسته به توالی عملیات ها هستند.
prmp بیانگر آنست که کارها بطور پیوسته و بدون هیچ اختلالی انجام می شوند.
block نشاندهنده ظرفیت محدود بافر(محل ذخیره) بین مراحل است. در واقع کار بایستی در مرحله قبل منتظر بماند تا فضای کافی آزاد شود.
recrc نشان میدهد که کارها می توانند بیش از یک بار نیز روی مراحل پردازش شوند.
unavail نشان میدهد که ماشین در همه زمان ها در دسترس نیست.
no-wait بیانگر این مطلب است که کارها نمی توانند بین دو مرحله متوالی منتظر بمانند و کارگاه تحت سیاست اولین ورودی اولین خروجی (FIFO) عمل می کند.
pj=p نشان دهنده برابر بودن تمام زمان های پردازش با p است.
sizejk بیانگر این مطلب است که ojk بایستی روی ماشین های sizejk بطور همزمان پردازش شوند.
در مسائل زمان بندی Cjk بیانگر زمان تکمیل کار j در مرحله k است و Cj زمان تکمیل کار j را در آخرین مرحله نمایش می دهد. زمان در جریان بودن کار j را با Fj نمایش می دهیم که زمانی است که کار j در سیستم صرف می کند، Fj=Cj-rj. دیرشدگی کار j با Lj ، Cj-dj نمایش داده می شود که ممکن است مقدار منفی نیز بگیرد.
دیرکرد، Tj=maxCj-dj,0 و زودکرد، Ej=maxdj-Cj,0 غیر منفی هستند. Uj∈0,1 معیاری برای جریمه کردن هر کار با تاخیر است. همچنین معمول است که وزنی مانند wj به کار j اختصاص می هند تا به کمک آن اهمیت آن را مدل کنند. نماد گذاری های بیشتر به همراه توضیحات در جدول زیر آمده است.
جدول 2-2. توابع هدف رایج در ادبیات
Notation Description Meaning
Cmax MaxjCj Maximum Complletion time
Fmax Maxj(Cj-rj) Maximum flow time
Lmax Maxj(Lj) Maximum lateness
Tmax Maxj(Tj) Maximum tardiness
Emax Maxj(Ej) Maximum earliness
CCjTotal/average completion time
CwwjCjTotal/average weighted completion time
FFjTotal/average flow time
FwWjFjTotal/avarage weighted flow time
TTjTotal/average tardiness
TwWjTjTotal/average weighted tardiness
UUjNumber of late jobs
UwWjUjTotal weighted number of late jobs
EEjTotal/average earliness
EwWjEjTotal/average weighted earliness
2-2. طبقه بندی محیط های زمانبندی
توالی عملیات و زمانبندی در واقع نوعی فرایند تصمیم گیری است که نقشی اساسی در ارتقای بهره وری درصنایع تولیدی و خدماتی دارد. در واقع تعیین توالی زمانی و تخصیص سفارشات مشتریان به منابع موجود تولید (اعم از پرسنل، ماشین آلات، ابزار و …) به منظور انجام مجموعه ای از عملیات های مربوط به آن را زمانبندی تولید تعریف میکنند. معمولا زمانبندی با توجه به اهدافی نظیر: دستیابی به موعدهای تعهد شده، کمینه سازی زمان کار، موجودی کار در جریان ساخت، بیشینه سازی خروجی و بهره برداری بیشتر از مراکز کاری اهدافی هستند که معمولا زمانبندی با توجه به آنها انجام میشود. قابل ذکر است که این اهداف با یکدیگر در تناقض هستند، لذا در مسائل زمانبندی ممکن است به لحاظ تکنیکی مشکلاتی رخ دهد.
مسائل واقعی زمانبندی تولید عموما تعدادی زیاد فعالیت و منابع داشته که مجموعه گوناگونی از اهداف و محدودیت بهره برداری از منابع در مورد آنها مطرح می شود. طبیعی است که روش های حل برنامه ریزی ریاضی و یا حتی فرموله نمودن آنها نسبتا سنگین و پر زحمت باشد. در بعضی موارد از طریق قواعد یا روش های ابتکاری ساده مبتنی بر قواعد تجربی یا آزمایشات شهودی می توان این مشکلات را برطرف نمود، اما در برخی دیگر از موارد تکنیک های مدلسازی منطقی یا بهینه سازی پیچیده تری لازم است.
مسائل زمانبندی را می توان به شیوه های مختلفی طبقه بندی نمود. بعنوان مثال میتوان مسائل زمانبندی را بصورت پویا یا ایستا، قطعی یا احتمالی، تک محصولی یا چند محصولی، تک پردازنده یا چند پردازنده و … دسته بندی نمود. نوع دیگری از طبقه بندی، بر اساس محیط منابع است. بسته به تعداد عملیات های مورد نیاز برای پردازش یک کار و نیز تعداد ماشین های موجود برای پردازش هر عملیات، الگوهای جریان گوناگونی را می توان برشمرد. مواقعی که تکمیل یک کار فقط به یک عملیات نیاز دارد به آن کار تک عملیاتی و در غیر اینصورت به آن کار چند عملیاتی گفته می شود که در آن مفاهیم مسیر تولید ممکن است مطرح شود. بر این اساس مسائل زمانبندی را می توان به صورت زیر دسته بندی نمود.
کارگاه تک ماشین : فقط یک ماشین در دسترس بوده و هر کار فقط به یک عملیات نیاز دارد.
کارگاه جریان کاری یا کارگاه جریان کاری مرتب : تعداد g ماشین متوالی وجود دارد و هر کار می بایست روی هر ماشین با همان توالی (یک مسیر تولید) پردازش شود.
کار کارگاهی: هر کار به چند عملیات نیاز دارد. جمعا به تعداد g ماشین متوالی وجود دارد و هر کار مسیر تولید خاص خود را دارد.
کارگاه عمومی : هر کار به چند عملیات نیاز دارد. جمعا به تعداد g ماشین وجود دارد، اما الگوی جریان معین نیست. به عبارت دیگر در انجام یک کار ممکن است از یک ماشین چندبار استفاده شود.
ماشین های موازی: هر کار تک عملیاتی بوده و در هر مرحله چندین ماشین برای انجام فرایند در دسترس است. در این حالت ماشین ها می توانند یکسان (I)، یکنواخت (U)، و یا نا مرتبط (R) باشند.
ماشین های یکسان در حالت موازی:چندین ماشین یکسان بصورت موازی می توانند کار کنند. فرض می شود که کار j بایستی توسط یکی از این ماشین ها انجام شود. این حالت با عنوان ماشین های یکسان در حالت موازی نامیده می شود. (مثال بانک های خصوصی مانند سامان و پارسیان). اگر یک کار تنها باید به روی یکی از ماشین ها پردازش شود، آنگاه نماد Mj در قسمت β نمایش داده می شود. مثال هایی دیگر در این زمینه صفوف بازرسی بدنی و یا سیستم های بانک و یا سیستم کنترل گذرنامه در فرودگاه ها می باشند.
ماشین های موازی با سرعت های متفاوت: سرعت پردازش ماشین iام بصورت vi نمایش داده می شود. زمان پردازش کار j ام به روی ماشین i ام بصورت Pij=Pjvi محاسبه می شود. چنین مسایلی متعلق به ماشین های مشابه می باشند. این مسایل با عنوان ماشین های موازی با سرعت های متفاوت تعریف می شوند. مثالی در این زمینه: تعمیرکاران مختلف ماشین که سرعت آنها بستگی به مهارت آنها دارد (مشتریان ثابت و منابع متحرک). در این حالت سرعت پردازش هر ماشین مستقل از نوع کار است.
ماشین های غیر مرتبط در حالت موازی:در این حالت ماشین هایی متفاوت بصورت موازی وجود دارند. ماشین i می تواند کار j را با سرعتی معادل vij پردازش نماید. زمان پردازش بصورت Pij=Pjvij محاسبه می شود. اگرسرعت پردازش کارهامستقل کارها باشد، مساله به حالت قبلی تبدیل می شود. این حالت با نام ماشین های غیر مرتبط در حالت موازی معروف هستند. در این حالت هر کار ممکن است توسط یکی از ماشین ها با سرعت بالاتری پردازش شود.
کارگاه جریان کاری مختلط: این حالت تعمیم یافته حالت محیط کارگاه جریان کاری و ماشین های موازی است. در اینجا g کارگاه متوالی وجود دارد که در مرحله t آن به تعداد mt ماشین بطور موازی کار می کنند. در هر کارگاه، یک کار حداکثر روی یک ماشین می تواند انجام شود.
کار کارگاهی با ماشین های دوتایی (کارگاهی منعطف): این حالت تعمیم یافته محیط کار کارگاهی و ماشین های موازی است. در اینجا g کارگاه وجود دارد که mtماشین موازی در کارگاه t کار می کنند. در هر کارگاه، یک کار حداکثر روی یک ماشین می تواند پردازش شود.
پردازش انباشته ای :در این فرایند، کارها در قالب انباشته هایی به صورت همزمان پردازش می شوند. پردازش هر انباشته، نیازمند زمان مشخصی است و ممکن است یک محدودیت ظرفیتی در مورد تعداد کارهایی که می توانند به صورت همزمان پردازش شوند وجود داشته باشد.
سیستم ساخت انعطاف پذیر :در این سیستم هر ماشین ممکن است قادر به انجام بیش از یک عملیات باشد. بنابراین هر دو ماشین در انجام یک سری از عملیات ممکن است حکم دو ماشین موازی را داشته باشند و در مورد یکسری از عملیات با یکدیگر اشتراکی نداشته باشند.
سیستم کارگاهی وابسته :یک محیط کار کارگاهی است که در آن، زمان شروع و پایان یکسری از کارها، به هم وابسته است. مثال بارز این سیستم، خطوط مونتاژ است. در مورد هر یک از سیستم های تولیدی فوق، وابستگی زمان و هزینه راه اندازی وابسته به توالی، می تواند دو سیستم مختلف را پدید آورد. از طرفی، سیستم های تولیدی در دنیای واقعی با پدیده های تصادفی بسیاری روبرو هستند که موجب قطع یا شکست سیستم می گردد. این رویدادها به عنوان رویدادهای زمان واقعی شناخته می شوند.
Permutation Flow Shop
Open Shop
Job Shop With Duplicate Machine
Job Shop
Hybrid Flow Shop
Parallel Machine
Flow Shop
Single Machine Shop
g=1
g=1
g=1
g=1
g=1, mt =1
mt=1
mt =1
mt=1
No Passing
مسیرهای تولید مشخص و یکسان
وجود یک مسیر تولید برای تمام کارها
وجود یک مسیر تولید برای تمام کارها
مسیرهای تولید مشخص
Permutation Flow Shop
Open Shop
Job Shop With Duplicate Machine
Job Shop
Hybrid Flow Shop
Parallel Machine
Flow Shop
Single Machine Shop
g=1
g=1
g=1
g=1
g=1, mt =1
mt=1
mt =1
mt=1
No Passing
مسیرهای تولید مشخص و یکسان
وجود یک مسیر تولید برای تمام کارها
وجود یک مسیر تولید برای تمام کارها
مسیرهای تولید مشخص

شکل 2-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید ]1[
2-3. مسائل ماشینهای موازی در یک مدل کلاسیک ماشینهای موازی اینگونه بیان میشود که یک سری کارهای مستقل باید بر روی چند ماشین یکسان که به صورت موازی قرار گرفتهاند پردازش شوند. هرماشین فقط میتواند یک کار را در یک زمان مشخص پردازش کند، و هر کار فقط میتواند توسط یک ماشین پردازش شود. تمامی کارها در ابتدای افق زمانی در دسترس میباشند و هرکدام از کارها زمان پردازش و موعد تحویل متفاوتی دارند ]10[. فرض میشود که ماشینها یکسان هستند و زمان دسترسی به کارها متفاوت نمیباشد و همه آنها با زمان تحویل متعارف در ابتدای زمانبندی در دسترس هستند. در مواردی نیز به خاطر تفاوت بین تکنولوژی ماشینهای به کارگرفته شده،ماشینها دارای سرعت متفاوتی هستند،به همین دلیل زمان کارهایی که باید بر روی این ماشینها زمانبندی شوند یکسان نیست. همچنین ممکن است همه کارها در ابتدای افق زمانی در دسترس نباشند و در زمانهای متفاوتی برسند و دارای زمانهای دسترسی پویا باشند به همین دلیل ممکن است که کارها با زمانهای تحویل متفاوت در نظر گرفته شود. در تمامی محیطهای صنعتی محدودیتهای پیشنیازی برای زمانبندی و توالی کارها بسیار مهم میباشند.در یک محیط واقعی ممکن است ما به زمان شروع یک کار برای تکمیل کار بعدی نیاز داشته باشیم و تا وقتی که کار قبلی تکمیل نشود نمیتوانیم کار بعدی را شروع کنیم.زمانبندی کارها بر روی ماشینهای موازی با محدودیت هایی چون محدودیتهای گفته شده، فضای حل را کوچک میکند، البته این به این معنا نیست که دستیابی به جواب بهینه آسان میشود و برعکس افزایش محدودیتها باعث سختتر شدن دستیابی به جواب بهینه میشود ]41[.
2-3-1. زمان نصب و آماده سازی زمان نصب و آماده سازی ماشین نمایانگر کلیه عملیاتی میباشد که به منظور آمادهسازی یک ماشین برای پردازش کارها بر روی آن صورت میپذیرد. عملیاتی نظیر تنظیم و اصلاح ابزارها، نصب جیگها و فیکسچرها، تمیزکاری و … از این قبیل محسوب میشوند. در بسیاری از تحقیقات فرض شده است که زمان آماده سازی ماشینها ناچیز است و یا آنرا جزئی از زمان پردازش در نظر گرفتهاند. با اینکه این فرض مدل و تحلیل آن را ساده میکند ولی بازتاب مشخصی در کاربرد دارد، تاثیر سوء بر روی کیفیت کارهای کاربردی که نیازمند عملیات مشخص برای آماده سازی هستند، دارد و باعث میشود که مدل در دنیای واقعی کاربردی نباشد. این وضعیت شاید در برخی از موارد قابل توجیه باشد اما بسیاری از مسائل زمانبندی نیازمند در نظر گرفتن زمان نصب به صورت مجزا از زمان پردازش میباشند. به طور معمول، مسائل تولیدی مرتبط با زمان آماده سازی به دو دسته تقسیم میشوند:1) زمان آماده سازی مستقل از توالی 2) زمان آماده سازی وابسته به توالی در دسته اول زمان نصب تنها به نوع کاری که بر روی ماشین پردازش میشود بستگی دارد که اصطلاحا زمان نصب مستقل از توالی نامیده میشود و در دسته دوم زمان نصب علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به کار قبلی که بر روی آن ماشین پردازش شده و ماشینی که کار بر روی آن پردازش میشود نیز بستگی دارد و به آن زمان نصب وابسته به توالی اطلاق میشود.]41[به عنوان مثال در یک کارخانه تولیدی رنگ هر جا تغییر رنگ نیاز باشد یک زمان آمادهﺳازی برای تمیز کردن دستگاه لازم است این زمان آماده سازی هم به رنگی که از ماشین پاک شود بستگی دارد هم به رنگی که قرار است پس از آن تولید شود بستگی دارد. در صنعت پلاستیک محصولات با رنگﻫای متفاوت به ماشینﻫای اکستروژن متفاوتی تخصیص داده میﺷوند. وقتی که تغییر رنگ لازم است، زمان مشخصی لازم است که پلاستیک خروجی رنگ مورد نظر را بگیرد. همچنین این مسئله در کارخانه تولید شیشه، شیشه مذاب قبل از پردازش در داخل خمره های بسیار بزرگ قرار دارند.وقتی که رنگ شیشه مذاب و یا مشخصات آن باید تغییر کند به یک زمان آماده سازی زیادی نیاز دارد.همچنین در کارخانه های تولیدی نوشیدنی، هنگامی که در خطوط تولیدی حین پر کردن شیشه های نوشیدنی بخواهیم قوطی را جایگزین شیشه کنیم به زمان آماده سازی نیاز داریم. در یک شرکت تولید کاغذ هر کجا ماشین بین دو نوع کاغذ تعویض انجام دهد، از آنجا که زمان آمادهﺳازی وابسته به درجه تشابه کاغذهای تولیدی متوالی است، این زمان وابسته به توالی میﺑاشد. در صنعت تولید بطری،زمان آمادهﺳازی وابسته به اندازه و شکل بطریﻫا میﺑاشد.]41[
اهمیت در نظر گرفتن زمان نصب به صورت مجزا از زمانهای پردازش کارها در تحقیقات مختلفی بررسی شده است. فلین [16] در تحقیق خود تاثیر زمانهای نصب وابسته به توالی را در افزایش ظرفیت تولید بررسی نموده است.یو و جایجین[60] مجموع وزنی دیرکرد را بر روی تک ماشین را با در نظر گرفتن زمان نصب و آماده سازی را حداقل کردند.آنها به این مسئله اشاره کردهاند که زمان نصب به دو دسته زمان نصب متوالی و زمان نصب تفکیک پذیر تقسیم میشوند.و از هر دو حالت زمان نصب برای مدل خود استفاده کرده اند.
در ادامه، مهمترین مطالعات صورت گرفته در زمینه مسائل زمانبندی با محدودیت زمان نصب وابسته به توالی کارها در هرکدام از محیطهای کارگاهی تکماشینه، کارگاه جریانی و ماشینهای موازی بررسی میشود.
در مسائل تک ماشینه کارها بر روی یک ماشین برای مدت زمان مشخص پردازش میشوند و هر کدام از کارها دارای خصوصیات مختص به خود مانند زمان پردازش، زمان تحویل، زمان نصب ماشین و وزن نسبی میباشند. هدف از حل این نوع مسائل یافتن توالی مشخصی است که یک یا چند معیار عملکردی را بهینه میکند.
مسائل تک ماشینه با محدودیت زمان نصب ماشین وابسته به توالی کارها و تابع هدف کمینه سازی زمان تکمیل کار بیشینه، معادل کمینه سازی زمان نصب کل میباشند و معمولا از این نوع مسائل با عنوان مسئله فروشنده دورهگرد یاد میشود. در یکی از اولین تحقیقات گیلمور و گوموری [19] مسئله تکماشینه را با تابع هدف هزینه نصب کل و محدودیت زمان نصب ماشین وابسته به توالی کارها مدلسازی و حل نمودند. در جدیدترین تحقیقات صورت گرفته در مسائل تک ماشینه با محدودیت زمان نصب، آرویو و همکارانش [6] سه الگوریتم چندهدفه بر مبنای روش جستجوی همسایگی متغیر را برای حل مسئلهای با تابع هدف زمانهای زودکرد و دیرکرد وزنی مقایسه نمودند. آنها دو رویه شمارشی برای بهبود روش جستجوی همسایگی متغیر ارائه نمودند و جوابهای به دست آمده از این روش را بهبود بخشیدند. سیود و همکارانش [47] ترکیبی از الگوریتم ژنتیک، الگوریتمهای تکاملی چند هدفه و الگوریتم کلونی مورچگان را برای حل مسئلهای با تابع هدف زمان تاخیر کل بهکار گرفتند. نتایجی محاسباتی در این تحقیق کارایی الگوریتم ترکیبی ارائه شده نسبت به بسیاری از روش های موجود در تحقیقات دیگر را نشان میدهد.
در یک مسئله کارگاه جریانی m ماشینه، تعداد m مرحله عملیات به صورت متوالی بر روی کارها صورت میگیرد. هر کدام از کارها بر روی همه ماشینها با توالی یکسان پردازش میشوند. زمانبندی جریان کارگاهی با چندین ماشین در هر مرحله را معمولا با نام جریان کارگاهی مختلط شناخته می شود، یک مسئله ترکیباتی پیچیده است که در بسیاری از مسائل دنیای واقعی کاربرد دارد. ملاحظه عملیات نصب درصنایع مختلف تولیدی یا خدماتی نظیر الکترونیک، شیمیایی، نساجی، داروسازی، سرامیک، پردازش اطلاعات و … به چشم میخورد. آندرس و همکارانش [5] یک مسئله تولید گروهی را در صنعت سرامیکسازی بررسی و آن را در سیستم زمانبندی کارگاه جریانی منعطف با محدودیت زمان نصب وابسته به توالی مدلسازی نمودند. آنها خاطر نشان مینمایند که هدف این نوع مسائل کاهش زمانهای نصب به منظور کاهش زمان تولید میباشد. مطالعات مشابهی [9،41،51] در تولید نیمههادیها، صنایع شیمیایی و داروسازی وجود دارد.
مسئله کارگاه جریانی برای اولین بار توسط جانسون [26] با دو ماشین و تابع هدف زمان تکمیل کار بیشینه بررسی شد. تمامی مدلها موجود در تحقیقات بعدی توسعه این مدل بهشمار میآیند. در مسائل کلاسیک یک بافر نامحدود که کارها روی ماشینها یا در بین دو ماشین متوالی در حال انتظار باشند، مفروض است. در یکی از آخرین تحقیقات صورت گرفته در مسائل کارگاه جریانی منعطف جانگواتاناکیت و همکاران]25[ ابتدا مسئله جریان کارگاهی مختلط با ماشین های غیر مرتبط و زمان های آماده سازی را به صورت برنامه ریزی عدد صحیح به منظور کمینه کردن ترکیب محدب دو معیار حداکثر زمان تکمیل و تعدا کارهای با تاخیر فرموله نموده و الگوریتم ژنتیکی برای حل مسئله پیشنهاد نموده اند. بهنامیان و همکاران ]24[ مسئله زمانبندی ماشین های موازی را با زمان های اماده سازی وابسته به توالی با دو هدف حداکثر کردن زمان تکمیل و مجموع زمان زودکرد و دیرکرد کارها مورد بررسی قرار دادند و روش سه مرحله ای برای در ایجاد مجموعه جواب های پارتو ارائه دادند.
با وجود اینکه مطالعات فراوانی در زمینه ماشینهای موازی یکسان صورت گرفته است، مسائل زمانبندی ماشینهای موازی نامرتبط کمتر مورد توجه قرار گرفتهاند. این موضوع با در نظر گرفتن محدودیت زمان نصب ماشین نیز محدوده به ندرت در میان تحقیقات به چشم میخورد. در ادبیات تحقیق زمانبندی ماشینهای موازی روشهای ابتکاری و فراابتکاری مختلفی به چشم میخورد که بخش زیادی از آن به ماشین های موازی یکسان و یکنواخت مربوط میشود. در ادامه تعدادی از مهمترین تحقیقات ارائه شده در زمینه ماشینهای موازی اشاره خواهند شد:
ژو و هیدی]62[یک فرمولبندی مختلط عدد صحیح برای حداقل کردن زودکرد و دیرکرد در یک مساله زمانبندی ماشینهای موازی ایجاد کردهﺍند.آنها فرض کردهﺍند که زمانﻫای آمادهﺳازی وابسته به توالی بوده و زمانﻫای پردازش به کار و ماشین اختصاص داده شده با آن کار بستگی دارد. آنها یک مدل برنامهریزی عددصحیح برای این مسئله پیشنهاد میکنند که با اندازه نه کار و سه ماشین در زمان محاسباتی معقول به جواب بهینه میرسد. توفان و همکارانش]53[مسئله برنامه ریزی ماشینهای موازی را با در نظر گرفتن زمان نصب و آماده سازی به جهت کمینه کردن مجموع تاخیرها با الگوریتم ژنتیک حل کردند. آنها به این نتیجه رسیدند که یک رابطه بین تعداد کارها و مجموع تاخیرها وجود دارد به نحوی که با افزایش تعداد کارها در برنامه ریزی ماشینهای موازی مجموع تاخیرها نیز افزایش مییابد. آکیول و همکارانش]3[ به مسئله ماشینهای موازی نامرتبط با فرض زمان نصب آماده سازی و موعدهای تحویل متفاوت با تابع هدف زمانهای زودکرد و دیرکرد وزنی پرداختند و با استفاده از شبکههای عصبی مصنوعی و روش تابع جریمه جواب بهینه مسئله را به دست آوردند. نتایج بدستآمده نشان میدهد که این روش به جواب بهینه مناسبی دست مییابد بطوریکه انگیزه کاربرد آن در مسائل با اندازه بزرگتر را ایجاد میکند. رادهاکریشنان و ونتورا]44[یک فرمولبندی ریاضی و یک الگوریتم بازپخت شبیهﺳازی شده بمنظور یافتن جوابﻫای نزدیک به بهینه برای مساله زیر ارائه کردهﺍند:
“N کار و M ماشین در دسترس هستند و بین کارها زمانﻫای آمادهﺳازی وابسته به توالی وجود دارد. همچنین هر کار زمان عملیات و موعد تحویل مجزایی دارد. هدف یافتن بهترین زمانبندی به گونهﺍی است که کل دیرکرد و زودکرد را حداقل کند. مساله را میﺗوان بطور خلاصه بصورت رابطه 2-1نمایش داد.”
lefttop(2-1)
آنها بمنظور تولید جمعیت اولیه از یک روش ابتکاری موثر بهره گرفتهﺍند.سپس با استفاده از نتایج محاسباتی حاصل از مسائل ایجاد شده بصورت تصادفی،نشان دادهﺍند که الگوریتم بازپخت شبیهﺳازی شده, بهبود قابل ملاحظهﺍی در جوابﻫای بدست آمده از روش ابتکاری ایجاد میﮐند. وای و وانگ]58[یک مدل برای زمانبندی کارهای گروهی روی ماشینﻫای موازی مشابه در نظر گرفتهﺍند. مدل فرض میﮐند که زمان آمادهﺳازی وقتی ایجاد میﺷود که یک ماشین از پردازش یک نوع به نوع دیگری بپردازد. هدف در این مدل, حداقل کردن کل جریمهﻫای زودکرد و دیرکرد میﺑاشد. محیط خاص در نظر گرفته شده در اینجا, یک کار تولیدی است کهMماشین موازی مشابه اجزای مختلفی را پردازش میﮐنند.اگر بخشی که باید روی ماشین تولید شود از همان نوعی باشد که قبلا تولید شده است،هیچ زمان آمادهﺳازی مورد نیاز نیست. لیکن اگر این بخش از نوع متفاوتی باشد،آمادهﺳازی ماشین قبل از پردازش لازم است.
توکلی مقدم و همکارانش طی چندین تحقیق به مسئله ماشینهای موازی با وجود فرض زمان نصب و آماده سازی پرداخته اند. یک مدل برنامهﺭیزی ریاضی برای مساله زمانبندی ماشینﻫای موازی نامرتبط با معیارهای کل زودکرد ودیرکرد و هزینهﻫای ماشین ارائه دادهﺍند]40[. آنها بمنظور حل مساله, با استفاده از تعریف عملگر جدید در الگوریتم ژنتیک به یک بهبودی موثری در کیفیت حل رسیدند. در تحقیقی دیگر]2[ مسئله ماشینهای موازی چند هدفه به منظور کمینه کردن تعداد کارهای دارای دیرکرد و مجموع مدت زمان تکمیل کارها پرداختهاند. آنها در این تحقیق زمان آماده سازی و زمان دسترسی و موعد تحویل متفاوت برای کارها در نظر گرفتهاند و با یک برنامه ریزی عدد صحیح مختلط دو سطحی برای مسئله مورد نظر به حل آن پرداخته اند و نتیجه آن دستیابی به جواب بهینه برای مسائل کوچک و متوسط میباشد.در تحقیق دیگرشان]42[ یک برنامه ریزی دو سطحی برای مسئله ماشینهای موازی چند هدفه با توابع هدف تعداد کاهای دارای دیرکرد و مجموع زمان تکمیل کارها ارائه دادندو در ادامه با استفاده از الگوریتم ژنتیک مسئله چند هدفه را حل نموده اند و کارایی الگوریتم و مدل خود رااثبات کردند.
در تحقیقات اخیر در این زمینه میتوان به یانگ کویی و همکارانش]57[ اشاره کرد که دو الگوریتم ابتکاری و الگوریتم ژنتیک را برای بدست آوردن جوابهای نامغلوب مسئله چند هدفه ماشینهای موازی نامرتبط به کار بردهاند. آنها سه معیار زمان آخرین کار،مجموع وزنی زمان تکمیل کارها و مجموع وزنی دیرکرد را مد نظر قرار دادند. الگوریتمهای ابتکاری این معیارها را دوبه دو مورد برسی قرار میدهند ولی الگوریتم ژنتیک همه آنها را همزمان کمینه میکند. در این تحقیق کارایی الگوریتم ژنتیک در مقابل دیگر الگوریتمهای ابتکاری اثبات میشود. همچنین رودریگز و همکارانش ]17[ با استفاده از یک الگوریتم فراابتکاری به حل مسائل بزرگ ماشینهای موازی پرداختهاند. مقیاس پذیری برای مسائل بزرگ در الگوریتمهای مدرن ضروری میباشد. آنها در تحقیق خود به این مسئله اشاره میکنند و کارایی الگوریتم خود را با الگوریتمهای موجود مقایسه میکنند.
2-3-2. دسترسی محدود به ماشینها زمانبندی با محدودیت مجموعههای پردازشی، محدودیت دسترسی و دسترسی محدود به ماشینها عناوینی هستند که برای مسائل زمانبندی با محدودیت دسترسی محدود به ماشینها به کار برده میشوند]31[. در این مسائل به هر یک از کارها یک زیرمجموعه از مجموعه ماشینها با عنوان مجموعه پردازشی نسبت داده میشود. هرکار فقط بر روی ماشینهای موجود در مجموعه پردازشی خود میتواند پردازش شود. به طور کلی در محدودیت دسترسی محدود به ماشینها، کارها دارای ویژگیهایی هستند که که نمیتوانند توسط همه ماشینها پردازش شوند و تنها بخشی از ماشینها قادر به پردازش آنها میباشند. تاراکیس و کای ]54[ یکی از این نوع مسائل را به منظور مدیریت بازدهی اتاقهای عمل بیمارستان مدلسازی نمودند. یک اتاق عمل معمولا با تجهیزات مدرنی با ارزش میلیونها دلار تجهیز میشود. با توجه به تجهیزات موجود در هراتاق که مربوط به یک بیماری خاص میباشد، هر اتاق تنها برای بخشی از بیماران قابل دسترس است. گلاس و کلرر ]20[ یک مسئله تخصیص سلولهای پردازندههای یک رایانه به برنامههای کاربردی را مدل سازی کردند و از محدودیت مجموعههای پردازشی استفاده نمودند. پردازندهها دارای سرعت یکسان و ظرفیت حافظه متفاوت هستند. هرکدام از برنامهها برای اجرا به میزان مشخصی از حافظه پردازنده نیاز دارند و همچنین تنها توسط تعداد سلول محدودی در پردازنده میتوانند پردازش شود.
مسائل ماشینهای موازی با محدودیت مجموعههای پردازشی در کلاس مسائل NP-hard قرار دارند [31]. به همین دلیل ، بهینه سازی این نوع مسائل با چنین محدودیتی نیازمند الگوریتمهای ابتکاری و فراابتکاری هستند. لیونگ و لی [30] زمانبندی ماشینهای موازی نامرتبط را با محدودیت دسترسی محدود به ماشینها با تمرکز بر روی تابع هدف زمان پایان کار بیشینه بررسی نمودند. ژانگ و همکارانش [61] یک الگوریتم فراابتکاری را در مسئله مشابهی با تابع هدف متوسط وزنی تاخیرها بکارگیری و عملکرد آن را به صورت تجربی ارائه نمودند.
2-3-3. زمان دسترسی متفاوت به کارها فرض در دسترس بودن همه کارها در زمان صفر یک انحراف مهم از واقعیت میﺑاشد. بنابراین, در این مقاله این فرض حذف شده است.از طرفی هنگامی که هر کار زمان ورود مجزایی داشته باشد, پیچیدگی مساله حتی برای حالت تک ماشینه نیز بسیار بالا میﺭود.بنابراین تلاش در یافتن جوابﻫای نزدیک به بهینه در این شرایط امری معقول میﺑاشد.توکلی مقدم و همکارانش]6[یک مدل عدد صحیح مختلط را با استفاده از برنامهریزی هدف را برای ماشینهای موازی با زمانهای دسترسی متفاوت به کارها ارائه دادند که باعث نزدیکی مدل به دنیای واقعی شده است.آنها زمانهای دسترسی قطعی برای کارها در نظر گرفتند ولی این زمانها متفاوت میباشند و کارها در زمانهای متفاوتی برای انجام پردازش در دسترس قرار میگیرند. مینگ لویی و همکارانش [34] مسئله تک ماشینه که توسط کلاماس [11] معرفی شده بود را مورد بررسی قرار دادند. آنها تمرکز خود را بر روی مدل با زمان دسترسی متفاوت برای کارها قرار دادند به این معنا که همه کارها در ابتدای افق زمانی در دسترس نمیباشند و دارای زمان دسترسی متفاوت میباشند.آنها هردو حات مدل با امکان قطع کار و بدون قطع کار را در نظر گرفتهاند.آنها برای مدل با قطع کارکه هر کاری میتواند در طول پردازش خود قطع شود وبعدا از آنجایی که قطع شده دوباره ادامه پردازش خود را از سر گیرد. همچنین پس از اثبات NP-hardبودن مدل بدون امکان قطع کار یک الگویتم دیگر برای حل آن ارائه دادند.
2-4. مسائل با تمرکز بر موعد تحویل برای کارها مسائل تعیین موعد تحویل در سالﻫای اخیر به دلیل توجه صنعتی به فلسفه تولید بهنگام مورد توجه خاصی قرار گرفتهﺍند. در بسیاری از محیطﻫای عملی از جمله صنعت نساجی ،صنایع مکانیکی و صنایع الکترونیکی، مقدار موعد تحویل در طول مذاکرات فروش با مشتری تعیین میﮔردد. در نظر گرفتن موعد تحویل بالا، مساله زمانبندی را آسان نموده و هزینهﻫای دیرکرد و زودکرد را کاهش میﺩهد اما نتایج درآمدی مهمی را در پی دارد. رسیدن به موعد تحویل تعیین شده یکی از اهداف اولیه مدیریت میﺑاشد. مدل موعد تحویل یکسان, مطابق با یک سیستم مونتاژ می باشد که در آن اجزای محصول بایستی در یک زمان آماده باشند یا در یک کارخانه که چند محصول تشکیل سفارش مشتری را میﺩهند. تخصیص زمان تحویل در مسائل زمانبندی توجه شایانی را به خود جلب کرده است. جستجو رویکرد موثر با در نظر گرفتن زمان تحویل و همچنین زمانبندی کارها به نحوی که در موعد تحویل انجام شده باشند همیشه یکی از مهمترین اهداف در زمانبندی و مدیریت زنجیره تامین بوده است. موعد تحویل یک زمان مطلوبی است که در آن کارها باید انجام شده باشند. در دنیای واقعی هنگامی کارها زودتر از موعد تحویل و یا دیرتر از آن آماده شوند جریمهای به آن تعلق میگیرد. این جریمه میتواند شامل کارهایی که زودتر از موعد تحویل آماده شده اند شود، زیرا ممکن است موجب هزینههای موجودی و نگهداری شود.و همچنین شامل کارهایی که دیرکرد دارند و بعد از موعد تحویل تکمیل میشوند است.به گونه که این دیرکرد موجب تخطی از قرارداد و نارضایتی مشتری میشود.]23[
لین و همکارانش]57[در مقاله ای با عنوان الگوریتم فراابتکاری برای برنامهریزی ماشنهای موازی ازفورمولی که پات و ون ]12[برای تولید زمانهای تحویل برای کارها استفاده کردند.آنها از (P(1-T-R/2),P(1-T+R/2) برای تولید زمان دسترسی استفاده کردند که در آن P=i=1mj=1npij/m میباشد و T میانگین عامل تاخیر و R محدوده تغییر زمان تحویل است.
سان و وانگ[52]یک الگوریتم برنامهﺭیزی پویا به منظور حل مساله ماشینﻫای موازی یکسان با وزنﻫای نسبی ارائه کردهﺍند. n کار مستقل بایستی روی m ماشین موازی یکسان انجام شوند. کار Ji دارای زمان عملیات pi و وزن wi میﺑاشد. تمام کارها موعد تحویل یکسان d دارند.هدف, حداقل کردن عبارت زیر میﺑاشد:
6350019685(2-2)
آنها نشان داده اند که مساله NP-hard میﺑاشد. سپس یک الگوریتم برنامهﺭیزی پویا بمنظور حل آن ارائه کردهﺍند. موشیو و یاول[37] مساله ای از توالی یک مجموعه کارهای مستقل روی یک مجموعه از ماشینﻫای موازی یکسان و تخصیص موعد تحویل به کارها را با هدف حداقل کردن مجموع دیرکرد وزنی و زودکرد وزنی و هزینه موعد تحویل در نظر میﮔیرند.

این نوشته در مقالات ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.

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

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