عضو شوید
عضویت سریع
آمار مطالب
آمار بازدید
فهرست مطالب:
عنوان شماره صفحه شماره صفحه
1-6 – فرضیات عمومی و ارائه یک مدل کلی.. 9
فصل دوم: ادبیات و پیشینه تحقیق… 13
2-2- مروری بر محدودیتها در محیط ماشینهای موازی.. 14
2-2-1- زمانهای آمادهسازی وابسته به توالی.. 14
2-3- مروری بر توابع هدف در محیط ماشینهای موازی.. 17
2-4- مروری بر روشهای حل در محیط ماشینهای موازی.. 19
2-6- روشهاي حل مسائل بهينهسازي چندهدفه. 23
2-6-1- مروری بر الگوریتم NSGA-II 26
2-6-2- مروری بر الگوریتم فراابتکاری تکاملی DE. 28
2-7- مروری بر روشهای ارزیابی.. 30
2-7-2- منطقه زير پوشش دو مجموعه. 31
2-7-6- فاصله از نقطه ايده‌آل.. 33
فصل سوم: مدل ریاضی و روش حل پیشنهادی.. 36
3-3- مدل ماشینها و پارامترهای مربوط به آنها 38
3-7- شرح مسأله و ارائه مدل.. 41
3-9- تضاد موجود بین تابع هدفها 44
3-10- روش پیشنهادی حل مسأله مورد نظر. 44
3-10-1- ساختار کلی الگوريتم تکاملی DE. 45
3-10-2- ساختار پيشنهادی الگوريتم DE. 48
3-10-2-1- ساختار كلي روش پيشنهادي DE. 48
3-10-2-4- عملگر انتخاب يا بازسازی.. 53
3-10-2-5- به روز رسانی آرشيو پارتو. 54
3-10-3- ساختار الگوریتم حل NSGA-II 55
3-10-3-1- روش سریع مرتبسازی جوابهای مغلوب NSGA-II 56
فصل چهارم: نتایج محاسباتی.. 61
4-4- تنظیم پارامتر با استفاده از روش سطح پاسخ (RSM) 65
فصل پنجم: نتیجهگیری و پیشنهادها 75
پ 1- مدل ریاضی ارائه شده در نرمافزار GAMS. 84
پ 2- کد نوشته شده در محیط Matlab برای دو روش حل DE و NSGA-II و روشهای مقایسه آنها 88
فهرست جداول:
عنوان شماره صفحه شماره صفحه
جدول 4-1- مفروضات اصلی کد نوشته شده در محیط GAMS. 62
جدول 4-2- اعداد توابع هدف.. 64
جدول 4-3- پارامترهای تعیین شده برای روشهای حل.. 67
جدول 4-4- نتایج مقایسهای دو الگوریتم DE و NSGA-II 70
فهرست اشکال:
عنوان شماره صفحه شماره صفحه
شکل 2-1- محیط متغیرهای تصمیم و فضای هدف… 21
شکل 2-2- مجموعه جوابهای مغلوب و غیرمغلوب… 22
شکل 2-3- بررسی وظیفه اول الگوریتم های چندهدفه. 25
شکل 2-4- بررسی وظیفه دوم الگوریتمهای چندهدفه. 25
شکل 3-1- ساختار کلی الگوريتم. 46
شكل 3-2- نماي كلي الگوريتم DE تلفيقی.. 48
شکل 3-5- میزان مغلوبیت جوابها 56
شکل 3-6- برتری جوابها در سطح اول.. 57
شکل 3-7- برتری جواب با فاصله ازدحام بیشتر. 57
شکل 3-8- محاسبه فاصله ازدحام برای جواب i 58
شکل 3-9- NSGA-II و عملگر مسابقهای دودویی.. 58
شکل 3-10- ساختار کلی الگوریتم NSGA-II 59
شکل 4-1- جواب حل مدل مورد نظر در محیط GAMS. 63
شکل 4-2- جبهه پارتو برای 50 جواب مختلف.. 65
شکل 4-3- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل DE. 66
شکل 4-4- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل NSGA-II 67
شکل 4-5- نمودار مقایسهای شاخص کیفیت برای دو الگوریتم DE و NSGA-II 71
شکل 4-6- نمودار مقایسهای شاخص فاصلهگذاری برای دو الگوریتم DE و NSGA-II 71
شکل 4-7- نمودار مقایسهای شاخص پراکندگی برای دو الگوریتم DE و NSGA-II 72
شکل 4-8- نمودار زمانهای اجرا 73
فصل اول
در جهان رقابتي حاضر، توالي و زمانبندي مناسب، ضرورتي براي بقا در فضاي بازار است. زمانبندي، ابزاري است كه استفاده از منابع در دسترس را بهينه ميكند. منابع و كارها در زمانبندي ممكن است انواع گوناگوني داشته باشد [1]. با توسعه جهان صنعتي، منابع بحرانيتر ميشوند. زمانبندي اين منابع، افزايش كارايي و بهرهبرداري از ظرفيت، كاهش زمان مورد نياز براي تكميل كارها و نهايتاً افزايش سوددهي يك سازمان را به دنبال خواهد داشت. در نتیجه، زمانبندي مناسب و مؤثر منابع مانند ماشينها، نيروي انساني و غيره در محيط به شدت رقابتي امروز الزامیست [1،2].
زمانبندي يك فرآيند تصميمگيري است كه نقش مهمي را در اكثر صنايع توليدي و خدماتي ايفا ميكند. زمانبندي در تداركات، توليد، حمل و نقل، توزيع، پردازش اطلاعات و ارتباطات كاربرد دارد. عمل زمانبندي در يك سازمان، از مدلها و روشهاي رياضي يا روشهاي ابتكاري براي تخصيص منابع محدود به كارهاي در حال جريان استفاده ميكند. تخصيص درست منابع، سازمان را براي بهينه كردن اهداف و به دست آوردن آرمانها توانمند ميسازد. منابع ميتوانند ماشينها در كارگاه توليدي، خطوط هوايي در فرودگاه، كارگران در پروژه ساختماني يا واحدهاي پردازشي در محيط كامپيوتر باشند. كارها نيز ميتوانند عمليات در كارگاه توليدي، پرواز و فرود در فرودگاه، مراحل در يك پروژه ساختماني و برنامههاي كامپيوتري در محيط كامپيوتر باشند. هر كار داراي ويژگيهايي همچون سطح اولويت، زمان آماده به كار بودن و موعد تحويل[1] ميباشد. تابع هدف همچنين ميتواند به صورتهاي مختلفي مانند حداقل كردن زمان اتمام كل كارها يا حداقل كردن تعداد كارهاي داراي ديركرد در نظر گرفته شود [3].
مسأله زمانبندي ماشين، زمينهاي غني و مناسب براي تحقيقات است كه كاربردهاي فراواني در توليد، پشتيباني، معماري كامپيوتر و مانند اين را به همراه خواهد داشت. حوزه مورد بررسي در اين پاياننامه، مسأله ماشينهاي موازي[2] است. زمانبندي ماشينهاي موازي در ارتباط با چگونگي زمانبندي گروهي از كارها بر روي تعدادي از ماشينها به منظور اطمينان از پردازش كارها در مدت زماني منطقي ميباشد. ماشينهاي موازي از دو ديدگاه تئوري و عملي داراي اهميت ميباشند. از ديدگاه تئوري، تعميمي از تك ماشين[3] و حالت خاصي از محيط جريان كارگاهي انعطافپذير[4] است. از ديدگاه عملي به اين جهت كه در دنياي واقعي بسيار معمول هستند داراي اهميت ميباشند [1]. علاوه بر اين، روشهايي كه در محيط ماشينهاي موازي مورد استفاده قرار ميگيرند، قابل استفاده در فرآيندهای تجزيه براي سيستمهاي چند مرحلهاي نیز ميباشد. زمانبندي صنايع به طور كلي از كاربرد مدل ماشينهاي موازي سود برده است. ماشينهاي موازي توانايي انجام عمليات يكسان با داشتن ظرفيتها و استعدادهاي متفاوت را دارا ميباشند. در واقع ماشينهاي موازي، افزايش ظرفيت و انعطافپذيري سيستم را با پردازش كارهاي متفاوت به همراه خواهند داشت.
عموماً ماشينها در محيط موازي قادر به پردازش گروه يكساني از كارها ميباشند، اما بر اساس زمان پردازش كار به سه دسته عمده طبقهبندي ميشوند: ماشينهاي يكسان[5]، ماشينهاي يكنواخت[6] و ماشينهاي نامرتبط[7]. در حالتيكه زمان پردازش كار بر روي همه ماشينها يكسان باشد، ماشينهاي موازي يكسان ناميده ميشوند. اگر ماشينها داراي سرعت متفاوت باشند، يعني زمان پردازش كارها بر روي ماشينها متناسب با ميزان سرعت در نظر گرفته شده باشد، ماشينهاي موازي يكنواخت ناميده ميشوند. در حالتي كه زمانهاي پردازش يك كار بر روي ماشينهاي مختلف به طور دلخواه متفاوت باشند، ماشينهاي موازي نامرتبط ناميده ميشوند [3]. در این پایاننامه، مسأله ماشینهای موازی یکنواخت مورد بررسی قرار میگیرد.
در ادامه به معرفي كار و نظريه زمانبندي و نحوه تعامل آن با برنامهريزي خواهيم پرداخت. با توجه به اين كه مدلهاي زمانبندي معمولاً بر اساس تركيب ماشينها، نوع محدوديتها و معيارهاي در نظر گرفته شده مشخص ميشوند، سپس به معرفي انواع متداولي از موارد بالا خواهيم پرداخت.
زمانبندي شامل برنامهريزي و اولويتدهي فعاليتهايي است كه لازم است به ترتيب عمليات انجام شوند [2]. در بيشتر موارد عمل زمانبندي پس از حل برخي مسائل مربوط به برنامهريزي اصولي مورد توجه قرار ميگيرد و بايد همواره اين نكته را مد نظر داشت كه تصميمات مربوط به زمانبندي اهميت كمتري نسبت به مجموعه وسيعتري از تصميمات مديريتي دارد. براي مثال، در حل مسائل مربوط به ساخت، مسائل اساسي مديريتي مربوط به انتخاب محصولي كه بايد ساخته شود و تعيين ميزان توليد هر محصول اولويت دارد. بعد از بهكارگيري بررسي بازار و تحليلهاي اقتصادي براي حل اينگونه مسائل، برنامهريزي تكنولوژيكي به اين مسأله كه محصول چگونه بايد ساخته شود متمركز ميشود و تنها بعد از اينكه جواب سوالات مربوط به برنامهريزي داده شد و در دسترس بودن منابع دانسته شد، زمان براي توجه به مسائل زمانبندي مناسب است. تصميمات اصولي مديريت به مسائل سه گانه زير مرتبط ميشوند.
1- چه محصول يا خدمتي قرار است عرضه شود؟
2- در چه مقياسي قرار است عرضه شود؟
3- چه منابعي قرار است تأمين شود؟
پاسخ دادن به اين پرسشها كار برنامهريزي است. در مقابل، در كار زمانبندي فرض بر اين است كه جواب پرسشها از پيش فراهم شده است. بنابراين كار زمانبندي صرفاً به وضعيتي مربوط ميشود كه در آن طبيعت كارهايي كه بايد زمانبندي شود توصيف شده و تركيب منابع موجود تعيين شده باشد[4]. در واقع زمانبندي ابزاري است كه استفاده از منابع در دسترس را بهينه ميكند.
در عمل وظيفه برنامهريزي و زمانبندي كاملاً مستقل از هم نيست. برنامهريز ابتدا وظايفي را كه بايد انجام شود مشخص و حدودي براي ميزان منابع دسترسپذير تعيين ميكند. سپس زمانبند اين اطلاعات را ميگيرد و مشخص ميكند كه منابع موجود چگونه به انجام كارهاي تعيين شده تخصيص يابد.
[1] Due Date
[2] Parallel Machines
[3] Single Machine
[4] Flexible Flow Shop
[5] Identical Machines
[6] Uniform Machines
