فرمت فایل : WORD (قابل ویرایش)
تعداد صفحات:114
پایان نامه مقطع کارشناسی ارشد
مهندسی صنایع- مهندسی سیستم های اقتصادی اجتماعی
فهرست مطالب:
فصل اول مقدمه و کلیات 1
1-1. مقدمه 2
1-2. تعریف مسأله زمانبندی 5
1-3. ضرورت انجام تحقیق 7
1-4. اهداف تحقیق 8
1-5. مفروضات مسئله 9
1-6. جنبه های نوآوری تحقیق 10
1-7. محتوای تحقیق 10
فصل دوم ادبیات و پیشینه تحقیق 11
2-1. مقدمه 12
2-2. طبقه بندی محیط های زمانبندی 15
2-3. مسائل ماشینهای موازی 19
2-3-1. زمان نصب و آماده سازی 20
2-3-2. دسترسی محدود به ماشینها 26
2-3-3. زمان دسترسی متفاوت به کارها 27
2-4. مسائل با تمرکز بر موعد تحویل برای کارها 27
2-4-1. زمان تکمیل کارها 29
2-4-2. زمانهای زودکرد و دیرکرد 29
2-5. مروری بر رویکرد و اصول سیستم تولیدی بهنگام 31
2-6. توالی ماشینﻫای موازی با معیارهای زودکرد و دیرکرد 33
2-7. جمع بندی 34
فصل سوم مدل ریاضی و بهینه سازی چند هدفه 36
3-1. مقدمه 37
3-2. تعریف مسئله 37
3-2-1. مفروضات مسئله 39
3-3. مدل پیشنهادی 39
3-3-1.نمادها، تعاریف، پارامترها و متغیر های تصمیم 40
3-3-2. پارامترهای ورودی 40
3-3-3. توابع هدف 41
3-3-4. محدودیتها 41
3-4. اعتبارسنجی مدل 43
3-5. پیچیدگی مسئله 45
3-6 بهینه سازی چند معیاره 47
3-6-1. ارتباط غالب 47
3-6-2. نقاط بهینه موضعی 48
3-6-3. نقاط بهینه سراسری 48
3-6-4. مرز بهینه 48
3-7. روشهای بهینه سازی 49
3-7-1. روشهای اسکالر 49
3-7-2. روش مجموع وزنی 51
3-7-2-1. طراحی روش مجموع وزنی برای حل مسأله مورد نظر 54
3-7-3. روش محدودیت-ε 55
3-7-3-1. طراحی روش محدودیت – ε برای حل مسأله 57
3-7-4. روشهای عکس العملی 57
3-7-5. روش های مبتنی بر منطق فازی 58
3-7-6. روش های فرا ابتکاری 59
3-7-7. الگوریتم NSGA-II 60
3-7-7-1. مرتب سازی سریع 61
3-7-7-2. عملگر گزینش تورنمنت تراکمی 63
3-7-7-3. فاصله تراکمی 63
3-7-8. طراحی روش فراابتکاری NSGA-II برای حل مسأله 65
3-7-9. طراحی روش فراابتکاری CENSGA برای حل مسأله 70
3-8. مقایسه روش های بهینه سازی چند هدفه 71
3-8-1. شاخص متوسط فاصله از نقطه ایدهآل 73
3-8-2. شاخص نرخ دستیابی به توابع هدف 74
3-8-3. شاخص گستردگی جواب های غیر مغلوب (SNS) 74
3-8-4. شاخص یکنواختی فضا 74
3-9. جمعﺑندی 75
فصل چهارم محاسبات و نتایج تحقیق 77
4‐1. مقدمه 78
4‐2. تنطیمات پارامترها و شرایط اجرای الگوریتم ها 79
4-3. الگوریتمهای NSGA-II,CENSGA 80
4-4. روش مجموع وزنی 80
4-5. روش محدودیت-ε 81
4‐6. ساختار مسائل 82
4‐7. معیارهای ارزیابی الگوریتمها 83
4‐8. مسائل با ابعاد کوچک و متوسط 83
4-8-1. نتایج آزمایشات مسائل کوچک و متوسط 83
4‐9. مسائل با ابعاد بزرگ 90
4‐10. نتایج محاسباتی 90
4‐11. جمعﺑندی 96
فصل پنجم نتیجه گیری و پیشنهادات 97
5‐1. مقدمه 98
5‐2. نتیجهﮔیری 99
5‐3. پیشنهادهای آتی 100
فهرست منابع و مراجع 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. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j2m 88
جدول 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. نمایش الگوریتم NSGAII 61
شکل 3-9. محاسبه فاصله تراکمی 64
شکل 3-10. ساختار کروموزوم 66
شکل 3-11. نحوه ایجاد جمعیت اولیه 67
شکل 3-12. نحوه عملکرد عملگر تقاطع 69
شکل 3-13. عملگر تقاطع تک نقطه ای با نقطه برش 3 69
شکل 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. نمایش جوابهای نامغلوب روش وزنی مسأله 5j3m 86
شکل 4-4. نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 5j3m 86
شکل 4-5 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j2m 88
شکل 4-6 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j2m 88
شکل 4-7 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j3m 89
شکل 4-8 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j3m 89
شکل 4- 9 نمودار نتایج محاسباتی شاخص های متریک در مسائل مختل 92
شکل 4-10. نمودارجعبه ای (BoxPlot) نتایج ارزیابی الگوریتم¬های CENSGA,NSGA-II 93
شکل 4-11. نمودار میانگین و فواصل اطمینان (سطح اطمینان 95%)نتایج ارزیابی الگوریتم ها 95
چکیده
در طول دهه گذشته، گسترش الگوریتم¬های فراابتکاری بهینه سازی چند معیاره توجه بسیاری را به خود جلب کرد. مسائل برنامه ریزی تولید بهنگام به عنوان مهمترین مسئله برنامه¬ریزی بهینه سازی نیز مستثنی نبود. البته بسیاری از الگوریتم¬های بهینه سازی که برای مسائل گوناگون به کار برده می¬شدند رویکردی نامناسب داشتند. به زبان دیگر بسیاری از آنها هدف¬ ها را ترکیب می¬کردند و مسائل را با رویکرد تک هدفه حل می¬کردند. البته بعضی از محققان الگوریتم¬های پارتویی به کار می¬برند. در این تحقیق یک برنامه ریزی ماشین¬های موازی نامرتبط با زمان آماده سازی وابسته به توالی، زمان دسترسی پویا به کارها، زمان تحویل متفاوت کارها و محدودیت مجموعه پردازشی نشان داده شده است. توابع هدف مورد نظر، مجموع وزنی زمانهای زودکرد و دیرکرد کارها و همچنین مجموع زمان تکمیل کارها را کمینه می-کنند. برای حل مدل و اعتبار سنجی آن از الگوریتم¬ مجموع وزنی و الگوریتم محدودیت اپسیلون استفاده شده است. همچنین نشان داده شده است که الگوریتم¬هایی که از روش شاخه و کران برای حل استفاده می¬کنند قادر به حل مسائل بزرگ در زمان معقول نمی-باشند. بنابراین برای حل این مسئله برنامه ریزی چند معیاره که از نوع چند جمله¬ای سخت (NP-Hard) می¬باشد الگوربتم فراابتکاری (CENSGA)معرفی شده است. الگوریتم ارائه شده را با استفاده از شاخص¬های آماری با الگوریتم فراابتکاری (NSGA-II) مورد مقایسه و تحلیل قرار داده شده است که نتایج نشان دهنده کارایی بهتر الگوریتم فراابتکاری (CENSGA) می¬باشد.
کلمات کلیدی: تولید بهنگام; زمان آماده¬سازی وابسته به توالی; کنترل نخبه¬گرایی; بهینه سازی چند هدفه; الگوریتم مرتب سازی نامغلوب.
یکی از آسانترین ، قدیمی ترین و هنوز قابل استفاده ترین استراتژی های معماری استفاده از دیوارهای موازی و مستقیم است. این استراتژی منطبق بر معماری های قبل از تاریخ است و تا کنون ادامه یافته است. معمارها تمام امکانات آن را درست در اول قرن بیستم جستجو کردند. به نظر نمیآید که پتانسیل این استراتژی خسته کننده و غیر قابل استفاده شده باشد.
جذابیت واقعی این ترتیب و استراتژی کاملاً ساده و غیر پیچیده در سادگی ساختاری آن است و این روش ساده ترین راه برای پوشاندن سقف بین دو دیوار موازی است.
اگر چه این روش ساده و بی تکلف است اما استفاده از دیوارهای موازی هم ظرافت های مربوط به خود را دارد. هنگامی که ما به معماری های قدیمی نگاه می کنیم از وجود آنهمه خلاقیت و ظرافیت و باریک بینی متعجب می شویم. آنچه را که باعث شگفت ما شده است می تواند هنوز مانند الگویی در دسترس و قابل استفاده ای برای طراحی و جستجوی ما باشد.
در فصل «هندسه های وجود» و در بخش ویژه «شش جهت – بعلاوة – مرکز چنین گفته شده است که معماری زمینی (خاکی) از چند جهت به زمین، آسمان، چهار جهت افقی و عقیدة مرکز مربوط می شود.
استراتژی دیوارهای موازی به ویژه مربوط است به چهار جهت افقی. و علت وجود این قدرت، تسلط آن بر این جهت هاست. در روش هایی که می تواند باعث احساس امنیت، جهت و کانون شود. محافظت داخل از باران و نور خورشید توسط سقف فراهم می شود. البته با استفاده از دیوارهای کناری، که میتوان جهت راهرو را به دو سمت “عقب” و “جلو” و یا با افزودن یک دیوار پشتی غیرساختاری به یک – جهت جلو محدود کرد و در نتیجه ساختمانی را بنا کرد که تقریباً مانند یک غار است.
علم جهت و حرکت به وسیلة فضای محدود بین دیوارها مشخص می شود. خط و جهت در هر سوی می تواند قرار بگیرد به صورت مستقیم بین دیوارها، و یا میتوان آن را در ارتفاع داخل ساختمان به اوج رساند و با استفاده از دیوار پشتی خاتمه داد.
تمام مشخصه های استراتژی دیوار موازی را می توان در همة ساختمان های باستان ملاحظه کرد.
در قرن نوزدهم میلادی “هنریش اشلیمان” باستانشانس شهری را کشف کرد که گمان میرفت شهر قدیمی “تروی” باشد که برخواسته های داستانهای مشهور “هنر است. تعدادی از بناها بر طبق دیوار موازی “سمت راست بالای صفحه ” ساخته شده بودند. سر در ساختمان نیز از دیوارهای موازی بنا شده بود.
شامل 19 صفحه فایل word
در این مقاله توضیحی درباره کامپیوترهای موازی میدهیم و بعد الگوریتمهای موازی را بررسی میکنیم. ویژگیهای الگوریتم branch & bound را بیان میکنیم و الگوریتمهای b&b موازی را ارائه میدهیم و دستهای از الگوریتمهای b&b آسنکرون برای اجرا روی سیستم MIMD را توسعه میدهیم. سپس این الگوریتم را که توسط عناصر پردازشی ناهمگن اجرا شده است بررسی میکنیم.
نمادهای perfect parallel و achieved effiency را که بطور تجربی معیار مناسبی برای موازیسازی است معرفی میکنیم زیرا نمادهای قبلی speed up (تسریع) و efficiency (کارایی) توانایی کامل را برای اجرای واقعی الگوریتم موازی آسنکرون نداشتند. و نیز شرایی را فراهم کردیم که از آنومالیهایی که به جهت موازیسازی و آسنکرون بودن و یا عدم قطعیت باعث کاهش کارایی الگوریتم شده بود، جلوگیری کند.
2- معرفی:
همیشه نیاز به کامپیوترهای قدرتمند وجود داشته است. در مدل سنتی محاسبات، یک عنصر پردازشی منحصر تمام taskها را بصورت خطی (Seqventia) انجام میدهد. به جهت اجرای یک دستورالعمل داده بایستی از محل یک کامپیوتر به محل دیگری منتقل میشد، لذا نیاز هب کامپیوترهای قدرتمند اهمیت روز افزون پیدا کرد. یک مدل جدید از محاسبات توسعه داده شد، که در این مدل جدید چندین عنصر پردازشی در اجرای یک task واحد با هم همکاری میکنند. ایده اصل این مدل بر اساس تقسیم یک task به subtaskهای مستقل از یکدیگر است که میتوانند هر کدام بصورت parallel (موازی) اجرا شوند. این نوع از کامپیوتر را کامپیوتر موازی گویند.
تا زمانیکه این امکان وجود داشته باشد که یک task را به زیر taskهایی تقسیم کنیم که اندازه بزرگترین زیر task همچنان به گونهای باشد که باز هم بتوان آنرا کاهش داد و البته تا زمانیکه عناصر پردازشی کافی برای اجرای این sub task ها بطور موازی وجود داشته باشد، قدرت محاسبه یک کامپیوتر موازی نامحدود است. اما در عمل این دو شرط بطور کامل برقرار نمیشوند:
اولاً: این امکان وجود ندارد که هر taskی را بطور دلخواه به تعدادی زیر taskهای مستقل تقسیم کنیم. چون همواره تعدادی زیر task های وابسته وجود دارد که بایستی بطور خطی اجرا شوند. از اینرو زمان مورد نیاز برای اجرای یک task بطور موازی یک حد پایین دارد.
1- خلاصه:
2- معرفی:
7- پارامترهای الگوریتمهای شاخه و قید موازی آسنکرون:
3- کامپیوترهای موازی (Parallel computers):
4- الگوریتمهای موازی (Parallel Algorithm):
5- شاخه و قید (Branch and Bound):
6- الگوریتم شاخه و قید موازی: (Parallel B&B Algorithms):
8- پیچیدگی و تسریع (Complexity & Speedup):
شامل 32 صفحه فایل word
با پیشرفت روز افزون علوم مختلف، نیاز به انجام محاسبات ریاضی سنگین و پردازش حجم زیادی از اطلاعات با سرعت بالا و در زمان کم بوجود آمد. از طرفی رشد تکنولوژی پردازنده ها نسبت به حجم محاسبات بسیار پایین است و نیز بخاطر محدودیت در تولید ابزار نیمه هادی سرعت پردازنده ها نیز دارای محدودیت میباشد. از این رو استفاده از یک کامپیوتر به تنهایی پاسخگوی نیازهای محاسباتی نیست. بنابراین استفاده از چند کامپیوتر برای انجام پردازش های موازی ضروری است. از سوی دیگر به دلیل پیشرفتهای زیاد در زمینه شبکه های کامپیوتری و ابزار آن، روش جدیدی برای انجام محاسبات ارائه گردید که Network-based coputation نام دارد.
در حالت کلی کامپیوترهای موازی شامل واحدهای پردازش و حافظه مختلفی هستند. و بحث مهم در طراحی و آنالیز سیستمهای موازی، روش اتصال اجزاء مختلف به یکدیگر می باشد بنابراین نحوه ارتباط شبکه است که کارائی کل سیستم را معین میکند.
امروزه طیف وسیعی از سیستمهای موازی موجود می باشد. که بعضی از آنها به منظور کاربرد خاص و گروهی نیز به صورت استفاده همه منظوره هستند. برای بررسی این کاربردها و استفاده آنها از شبکه های مختلف در ابتدا نیاز است تا معماری های موازی را دسته بندی کنیم. زیرا معماری های مختلف نیازهای مختلف را برآورده میسازند.
البته تنها افزایش سرعت دلیل استفاده از کامپیوترهای موازی نیست بلکه گاهی برای بالا بردن قابلیت اطمینان از سیستم موازی استفاده می شود و محاسبات به وسیله چند کامپیوتر انجام شده و با هم مقایسه می شود و در واقع کامپیوترهای دیگر نقش Backup را دارند. به این سیستم ها fault telorant گفته می شود.
تا کنون دسته بندی کامل و جامعی برای سیستمهای موازی ارائه نشده است: Flynn روشی برای این دسته بندی ارائه کرده که البته به طور کامل تمام سیستمها را تحت پوشش نمی گیرد. سیستم دسته بندی Flynn براساس تعداد دنباله دستورالعملها و اطلاعات موجود در یک کامپیوتر می باشد که در اینجا منظور از دنباله یا Stream، رشته از دستورات یا اطلاعات است که توسط یک پردازنده پردازش می شود. Flynn هر سیستم را بسته به تعداد دستورات و تعداد اطلاعات به یکی از چهار مجموعه زیر نسبت می دهد که در زیر توضیح مختصری از هر یک از آنها آمده است.
SISD: Sungle Instruction – Single Data
SIMD: Single Instruction – Multiple Data
MISD: Multiple Instruction – Multiple Data
ویژگیهای شبکه:
3- بررسی اجمالی توپولوژیها
1-3- ساختارهای ارتباطی ساده Simple Connection Structures:
2-3- گرافهای الفبایی Graphs on Alphabets:
3-3- ساختارهای فوق مکعبی Hypercube Structures:
4-3- Cayley Graphs:
5-3- Additional Links:
6-3- Generalized Chordal Rings:
7-3- Combinational of Basic Modules:
8-3- Boolean Operations on Graphs:
9-3- Random Graphs:
فصل 4: مقایسه توپولوژیها
فصل 5: Routing in Network
شامل 22 صفحه فایل word
فایل بصورت ورد (قابل ویرایش) و در 28 صفحه می باشد.
“ردیف های موازی از دو سری ساختمان معرف اصطلاحی است که ما به عنوان خیابان شناخته ایم. خیابان مملو از ساختمان هاست. خیابان خانه ها را از هم جدا می کند و آنچه که ما را قادر می کند تا از یک خانه به خانة دیگر برویم. یا در طول خیابان از میان خیابان.
جرج پرک. ترجمه شده توسط استتوروک
انواع فضاها و سایر مقالات، (1974)
صفحه 450 و 1997
عنوان صفحه: در بعضی از ساختمان ها فضا با استفاده از دیوارهای موازی سازماندهی میشود.
یکی از آسانترین ، قدیمی ترین و هنوز قابل استفاده ترین استراتژی های معماری استفاده از دیوارهای موازی و مستقیم است. این استراتژی منطبق بر معماری های قبل از تاریخ است و تا کنون ادامه یافته است. معمارها تمام امکانات آن را درست در اول قرن بیستم جستجو کردند. به نظر نمیآید که پتانسیل این استراتژی خسته کننده و غیر قابل استفاده شده باشد.
جذابیت واقعی این ترتیب و استراتژی کاملاً ساده و غیر پیچیده در سادگی ساختاری آن است و این روش ساده ترین راه برای پوشاندن سقف بین دو دیوار موازی است.
اگر چه این روش ساده و بی تکلف است اما استفاده از دیوارهای موازی هم ظرافت های مربوط به خود را دارد. هنگامی که ما به معماری های قدیمی نگاه می کنیم از وجود آنهمه خلاقیت و ظرافیت و باریک بینی متعجب می شویم. آنچه را که باعث شگفت ما شده است می تواند هنوز مانند الگویی در دسترس و قابل استفاده ای برای طراحی و جستجوی ما باشد.
در فصل «هندسه های وجود» و در بخش ویژه «شش جهت – بعلاوة – مرکز چنین گفته شده است که معماری زمینی (خاکی) از چند جهت به زمین، آسمان، چهار جهت افقی و عقیدة مرکز مربوط می شود.
استراتژی دیوارهای موازی به ویژه مربوط است به چهار جهت افقی. و علت وجود این قدرت، تسلط آن بر این جهت هاست. در روش هایی که می تواند باعث احساس امنیت، جهت و کانون شود. محافظت داخل از باران و نور خورشید توسط سقف فراهم می شود. البته با استفاده از دیوارهای کناری، که میتوان جهت راهرو را به دو سمت “عقب” و “جلو” و یا با افزودن یک دیوار پشتی غیرساختاری به یک – جهت جلو محدود کرد و در نتیجه ساختمانی را بنا کرد که تقریباً مانند یک غار است.
علم جهت و حرکت به وسیلة فضای محدود بین دیوارها مشخص می شود. خط و جهت در هر سوی می تواند قرار بگیرد به صورت مستقیم بین دیوارها، و یا میتوان آن را در ارتفاع داخل ساختمان به اوج رساند و با استفاده از دیوار پشتی خاتمه داد.