عنوان : نظریه زمان بندی
(در فایل دانلودی نام نویسنده موجود است)
تکه هایی از متن پایان نامه به عنوان نمونه :
(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)
چکیده
در دنیای رقابتی امروز برای بقا باید با زمان حرکت کرد. برای این منظور باید کلیه فعالیتها برای رسیدن بهموقع به هدف نهایی زمانبندی و ترتیبدهی شوند. توالی عملیات، نقش بسیار مهمی در مسائل امروزی شرکتها دارد. بنابراین بررسی توالی عملیات در محیطهای مختلف و با معیارهای مختلف یک گام مثبت جهت حفظ بقا میباشد. در این پایان نامه ، یک مدل ریاضی جدید برای حل مسأله زمانبندی پویا ماشینهای موازی یکنواخت با اهداف میانگین وزنی زمان تکمیل کارها و مجموع جریمه های زودکرد و دیرکرد معرفی گردیده است. کارها به مرور زمان وارد میشوند و به دلیل اهمیت زمانهای آماده سازی وابسته به توالی در بحث ماشینهای موازی، این محدودیت نیز در مدل مذکور در نظر گرفته شده است.
با توجه به وجود تضاد بین دو تابع هدف مذکور، استفاده از روشهای کلاسیک بهینه سازی جهت دستیابی به جوابهای بهینه، سراسری یا موضعی امری غیرممکن بوده و بنابراین برای حل مسأله، از روشی موسوم به بهینه سازی چندمعیاره استفاده میگردد. با توجه به پیچیدگی محاسباتی مسأله فوق، الگوریتم فراابتکاری تکاملی دیفرانسیلی (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
قیمت 70 هزار تومان
70,000 تومانافزودن به سبد خرید