دانلود پایان نامه کارشناسی ارشد درباره نظریه زمان بندی

متن کامل پایان نامه مقطع کارشناسی ارشد

عنوان : نظریه زمان بندی

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

چکیده

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

با توجه به وجود تضاد بین دو تابع هدف مذکور، استفاده از روش­های کلاسیک بهینه­سازی جهت دستیابی به جواب­های بهینه، سراسری یا موضعی امری غیرممکن بوده و بنابراین برای حل مسأله، از روشی موسوم به بهینه­سازی چندمعیاره استفاده می­گردد. با توجه به پیچیدگی محاسباتی مسأله فوق، الگوریتم فراابتکاری تکاملی دیفرانسیلی (DE) چندهدفه برای دستیابی به جواب­های بهینه غالب (پارتو) پیشنهاد می­شود. برای صحه­گذاری بر عملکرد الگوریتم پیشنهادی، مسائل متعددی طراحی گردیده است و کارایی این الگوریتم، بر پایه شاخص­های طراحی شده، با رویکرد فراابتکاری مبتنی بر الگوریتم ژنتیک چند هدفه ارائه شده (NSGA-II)، مقایسه می­شود. نتایج محاسباتی نشان می­دهند که الگوریتم پیشنهاد شده DE، جواب­های بهتری به­دست می­آورد.

 

فهرست مطالب:

عنوان                                                                                                                                                          شماره صفحه                                                                                                                                                                                                                                                                                                                                                  شماره صفحه

فصل اول: کلیات تحقیق… 1

1-1- مقدمه. 2

1-2- کار زمانبندی.. 3

1-3- نظریه زمانبندی.. 4

1-4- زمانبندي در كسب و كار 4

1-4-1- زمانبندي در توليد. 5

1-4-2- زمانبندي در خدمات.. 6

1-5- مروری بر مدل­ها 6

1-6 – فرضیات عمومی و ارائه یک مدل کلی.. 9

1-7- ضرورت انجام تحقیق.. 10

1-8- هدف از تحقیق.. 11

1-9- جمع­بندی.. 12

فصل دوم: ادبیات و پیشینه تحقیق… 13

2-1- مقدمه. 14

2-2- مروری بر محدودیت­ها در محیط ماشین­های موازی.. 14

2-2-1- زمان­های آماده­سازی وابسته به توالی.. 14

2-2-2- محیط پویا 16

2-3- مروری بر توابع هدف در محیط ماشین­های موازی.. 17

2-4- مروری بر روش­های حل در محیط ماشین­های موازی.. 19

2-5- مسائل چند هدفه. 20

2-6- روش­هاي حل مسائل بهينه­سازي چندهدفه. 23

2-6-1- مروری بر الگوریتم NSGA-II 26

2-6-2- مروری بر الگوریتم فراابتکاری تکاملی DE. 28

2-7- مروری بر روش­های ارزیابی.. 30

2-7-1- نسبت خطا 31

2-7-2- منطقه زير پوشش دو مجموعه. 31

2-7-3- فاصله عمومي.. 32

2-7-4- نسبت فوق مساحت… 32

2-7-5- فاصله‌گذاري.. 33

2-7-6- فاصله از نقطه ايده‌آل.. 33

2-7-7- گسترش… 34

2-7-8- بیشترین گسترش… 34

2-8- جمع­بندی.. 35

فصل سوم: مدل ریاضی و روش حل پیشنهادی.. 36

3-1- مقدمه. 37

3-2- مدل کارها و عملیات.. 37

3-3- مدل ماشین­ها و پارامترهای مربوط به آن­ها 38

3-4- اهداف.. 38

3-5- مفرضات مسأله. 40

3-6- محدودیت­های مسأله. 40

3-7- شرح مسأله و ارائه مدل.. 41

3-8- مدل ریاضی پیشنهادی.. 42

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-2- عملگر جهش…. 51

3-10-2-3- عملگر تقاطع. 52

3-10-2-4- عملگر انتخاب يا بازسازی.. 53

3-10-2-5- به روز رسانی آرشيو پارتو. 54

3-10-2-6- رويه بهبود. 54

3-10-2-7- انتخاب جواب.. 55

3-10-3- ساختار الگوریتم حل NSGA-II 55

3-10-3-1- روش سریع مرتب­سازی جواب­های مغلوب NSGA-II 56

3-11- جمع­بندی.. 60

فصل چهارم: نتایج محاسباتی.. 61

4-1- مقدمه. 62

4-2- اعتبار سنجی مدل.. 62

4-3- جبهه پارتو. 63

4-4- تنظیم پارامتر با استفاده از روش سطح پاسخ (RSM) 65

4-5- شاخص­هاي مقايسه. 68

4-6- نتايج مقايسه­اي.. 68

4-7- مقايسه زمان اجرا 72

4-8- جمع­بندي.. 74

 

فصل پنجم: نتیجه­گیری و پیشنهادها 75

5-1- نتیجه­گیری.. 76

5-2- پیشنهادهای آتی.. 76

منابع و مراجع.. 78

پیوست­ها 83

پ 1- مدل ریاضی ارائه شده در نرم­افزار GAMS. 84

پ 2- کد نوشته شده در محیط Matlab برای دو روش حل DE و NSGA-II و روش­های مقایسه آن­ها 88

چکیده لاتین.. 106

 

فهرست جداول:

عنوان                                                                                                                                                          شماره صفحه                                                                                                                                                                                                                                                                                                                                                  شماره صفحه

جدول 4-1- مفروضات اصلی کد نوشته شده در محیط GAMS. 62

جدول 4-2- اعداد توابع هدف.. 64

جدول 4-3- پارامترهای تعیین شده برای روش­های حل.. 67

جدول 4-4- نتایج مقایسه­ای دو الگوریتم DE و NSGA-II 70

جدول 4-5- زمان­های اجرا 73

 

 

فهرست اشکال:

عنوان                                                                                                                                                          شماره صفحه                                                                                                                                                                                                                                                                                                                                                  شماره صفحه

شکل 2-1- محیط متغیرهای تصمیم و فضای هدف… 21

شکل 2-2- مجموعه جواب­های مغلوب و غیرمغلوب… 22

شکل 2-3- بررسی وظیفه اول الگوریتم های چندهدفه. 25

شکل 2-4- بررسی وظیفه دوم الگوریتم­های چندهدفه. 25

شکل 3-1- ساختار کلی الگوريتم. 46

شكل 3-2- نماي كلي الگوريتم DE تلفيقی.. 48

شكل 3-3- نحوه نمايش جواب.. 49

شکل 3-4- ساختار کلی VNS. 55

شکل 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- مقدمه

در جهان رقابتي حاضر، توالي و زمانبندي مناسب، ضرورتي براي بقا در فضاي بازار است. زمانبندي، ابزاري است كه استفاده از منابع در دسترس را بهينه مي­كند. منابع و كارها در زمانبندي ممكن است انواع گوناگوني داشته باشد [1]. با توسعه جهان صنعتي، منابع بحراني­تر مي­شوند. زمانبندي اين منابع، افزايش كارايي و بهره­برداري از ظرفيت، كاهش زمان مورد نياز براي تكميل كارها و نهايتاً افزايش سوددهي يك سازمان را به دنبال خواهد داشت. در نتیجه، زمانبندي مناسب و مؤثر منابع مانند ماشين­ها، نيروي انساني و غيره در محيط به شدت رقابتي امروز الزامیست [1،2].

زمانبندي يك فرآيند تصميم­گيري است كه نقش مهمي را در اكثر صنايع توليدي و خدماتي ايفا مي­كند. زمانبندي در تداركات، توليد، حمل و نقل، توزيع، پردازش اطلاعات و ارتباطات كاربرد دارد. عمل زمانبندي در يك سازمان، از مدل­ها و روش­هاي رياضي يا روش­هاي ابتكاري براي تخصيص منابع محدود به كارهاي در حال جريان استفاده مي­كند. تخصيص درست منابع، سازمان را براي بهينه كردن اهداف و به دست آوردن آرمان­ها توانمند مي­سازد. منابع مي­توانند ماشين­ها در كارگاه توليدي، خطوط هوايي در فرودگاه، كارگران در پروژه ساختماني يا واحدهاي پردازشي در محيط كامپيوتر باشند. كارها نيز مي­توانند عمليات در كارگاه توليدي، پرواز و فرود در فرودگاه، مراحل در يك پروژه ساختماني و برنامه­هاي كامپيوتري در محيط كامپيوتر باشند. هر كار داراي ويژگي­هايي همچون سطح اولويت، زمان آماده به كار بودن و موعد تحويل[1] مي­باشد. تابع هدف همچنين مي­تواند به صورت­هاي مختلفي مانند حداقل كردن زمان اتمام كل كارها يا حداقل كردن تعداد كارهاي داراي ديركرد در نظر گرفته شود [3].

مسأله زمانبندي ماشين، زمينه­اي غني و مناسب براي تحقيقات است كه كاربردهاي فراواني در توليد، پشتيباني، معماري كامپيوتر و مانند اين را به همراه خواهد داشت. حوزه مورد بررسي در اين پايان­نامه، مسأله ماشين­هاي موازي[2] است. زمانبندي ماشين­هاي موازي در ارتباط با چگونگي زمانبندي گروهي از كارها بر روي تعدادي از ماشين­ها به منظور اطمينان از پردازش كارها در مدت زماني منطقي مي­باشد. ماشين­هاي موازي از دو ديدگاه تئوري و عملي داراي اهميت مي­باشند. از ديدگاه تئوري، تعميمي از تك ماشين[3] و حالت خاصي از محيط جريان كارگاهي انعطاف­پذير[4] است. از ديدگاه عملي به اين جهت كه در دنياي واقعي بسيار معمول هستند داراي اهميت مي­باشند [1]. علاوه بر اين، روش­هايي كه در محيط ماشين­هاي موازي مورد استفاده قرار مي­گيرند، قابل استفاده در فرآيندهای تجزيه براي سيستم­هاي چند مرحله­اي نیز مي­باشد. زمانبندي صنايع به طور كلي از كاربرد مدل ماشين­هاي موازي سود برده است. ماشين­هاي موازي توانايي انجام عمليات يكسان با داشتن ظرفيت­ها و استعدادهاي متفاوت را دارا مي­باشند. در واقع ماشين­هاي موازي، افزايش ظرفيت و انعطاف­پذيري سيستم را با پردازش كارهاي متفاوت به همراه خواهند داشت.

عموماً ماشين­ها در محيط موازي قادر به پردازش گروه يكساني از كارها مي­باشند، اما بر اساس زمان پردازش كار به سه دسته عمده طبقه­بندي مي­شوند: ماشين­هاي يكسان[5]، ماشين­هاي يكنواخت[6] و ماشين­هاي نامرتبط[7]. در حالتي­كه زمان پردازش كار بر روي همه ماشين­ها يكسان باشد، ماشين­هاي موازي يكسان ناميده مي­شوند. اگر ماشين­ها داراي سرعت متفاوت باشند، يعني زمان پردازش كارها بر روي ماشين­ها متناسب با ميزان سرعت در نظر گرفته شده باشد، ماشين­هاي موازي يكنواخت ناميده مي­شوند. در حالتي كه زمان­هاي پردازش يك كار بر روي ماشين­هاي مختلف به طور دلخواه متفاوت باشند، ماشين­هاي موازي نامرتبط ناميده مي­شوند [3]. در این پایان نامه ، مسأله ماشین­های موازی یکنواخت مورد بررسی قرار می­گیرد.

در ادامه به معرفي كار و نظريه زمانبندي و نحوه تعامل آن با برنامه­ريزي خواهيم پرداخت. با توجه به اين كه مدل­هاي زمانبندي معمولاً بر اساس تركيب ماشين­ها، نوع محدوديت­ها و معيارهاي در نظر گرفته شده مشخص مي­شوند، سپس به معرفي انواع متداولي از موارد بالا خواهيم پرداخت.

 

1-2- کار زمان­بندی

زمانبندي شامل برنامه­ريزي و اولويت­دهي فعاليت­هايي است كه لازم است به ترتيب عمليات انجام شوند [2]. در بيشتر موارد عمل زمانبندي پس از حل برخي مسائل مربوط به برنامه­ريزي اصولي مورد توجه قرار مي­گيرد و بايد همواره اين نكته را مد نظر داشت كه تصميمات مربوط به زمانبندي اهميت كمتري نسبت به مجموعه وسيع­تري از تصميمات مديريتي دارد. براي مثال، در حل مسائل مربوط به ساخت، مسائل اساسي مديريتي مربوط به انتخاب محصولي كه بايد ساخته شود و تعيين ميزان توليد هر محصول اولويت دارد. بعد از به­كارگيري بررسي بازار و تحليل­هاي اقتصادي براي حل اين­گونه مسائل، برنامه­ريزي تكنولوژيكي به اين مسأله كه محصول چگونه بايد ساخته شود متمركز مي­شود و تنها بعد از اينكه جواب سوالات مربوط به برنامه­ريزي داده شد و در دسترس بودن منابع دانسته شد، زمان براي توجه به مسائل زمانبندي مناسب است. تصميمات اصولي مديريت به مسائل سه گانه زير مرتبط مي­شوند.

1- چه محصول يا خدمتي قرار است عرضه شود؟

2- در چه مقياسي قرار است عرضه شود؟

3- چه منابعي قرار است تأمين شود؟

پاسخ دادن به اين پرسش­ها كار برنامه­ريزي است. در مقابل، در كار زمانبندي فرض بر اين است كه جواب پرسش­ها از پيش فراهم شده است. بنابراين كار زمانبندي صرفاً به وضعيتي مربوط مي­شود كه در آن طبيعت كارهايي كه بايد زمانبندي شود توصيف شده و تركيب منابع موجود تعيين شده باشد[4]. در واقع زمانبندي ابزاري است كه استفاده از منابع در دسترس را بهينه مي­كند.

در عمل وظيفه برنامه­ريزي و زمانبندي كاملاً مستقل از هم نيست. برنامه­ريز ابتدا وظايفي را كه بايد انجام شود مشخص و حدودي براي ميزان منابع دسترس­پذير تعيين مي­كند. سپس زمانبند اين اطلاعات را مي­گيرد و مشخص مي­كند كه منابع موجود چگونه به انجام كارهاي تعيين شده تخصيص يابد.

[1] Due Date

[2] Parallel Machines

[3] Single Machine

[4] Flexible Flow Shop

[5] Identical Machines

[6] Uniform Machines

[7] Unrelated Machines

تعداد صفحه : 117

قیمت : 14700 تومان

———–

——-

پشتیبانی سایت :               serderehi@gmail.com

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

--  --