چکیده:نگهداری ماشین در تولید اغلب برای ممانعت از شکست ماشین به منظور حفظ راندمان تولید انجام میشود. در این پایاننامه مسئله کمینه سازی بیشترین زمان تکمیل بر روی ماشینهای موازی غیرمرتبط باتوجه به تاثیرات استهلاک بر زمان کارها و فعالیتهای نگهداری و اثر یادگیری در افق زمانبندی مورد بررسی قرار گرفت. یک ماشین بعد از عملیات نگهداری به شرایط اولیه خود بازمیگردد و اثر استهلاک از نو، آغاز میگردد. هدف در این مسئله پیدا کردن دفعات بهینه، بهترین زمان انجام عملیات نگهداری و توالی بهینه کارها روی ماشینها به طوری که بیشترین زمان تکمیل کارها کمینه گردد. برای مسئله مطرح شده یک مدل ریاضی خطی ارائه شد و بعد از اشاره به NP-hard بودن مسئله به ارائه روش فرا ابتکاری ژنتیک و رقابت استعماری جهت حل مسئله در ابعاد موجود در واقعیت پرداخته شد و در نهایت نتایج بدست آمده مورد بررسی و تحلیل قرار گرفت.کلمات کلیدی: ماشینهای موازی غیرمرتبط، اثر یادگیری، اثر استهلاک،فعالیتهای نگهداری.فهرستعنوان شماره صفحهچکیده فصل اول: مقدمه و کلیات تحقیق1-1. مقدمه 21-2. تعریف مسئله 31-3. فرضیات مسئله ماشینهای موازی این مطالعه 3 1-4. اهداف تحقیق 4 1-5. جنبههای نوآوری تحقیق 41-6. محتویات تحقیق 4 1-7. جمعبندی 4فصل دوم: ادبیات نظری و پیشینه تحقیق2-1. مقدمه 72-2. تعربف اثر یادگیری در فن زمانبندی 72-3. تعریف نگهداری و تعمیرات در زمانبندی 92-4. ادبیات و پیشینه تحقیق 102-4-1. مسائل ماشینهای موازی 102-4-2. مروری بر مطالعات زمانبندی با اثر یادگیری 112-4-3. مروری بر مطالعات اثر همزمان یادگیری و زوال در زمانبندی 11 2-4-4. مروری بر مطالعات زمانبندی با اثر استهلاک 122-5. جمعبندی 13فصل سوم: ارائه مدل ریاضی3-1. مقدمه 143-2. تعریف مسئله 14 3-3. فرضیات مسئله 143-4. مدل ریاضی پیشنهادی 153-4-1. اندیسها 153-4-2. پارامترهای مسئله 153-4-3. متغیرهای تصمیم 153-4-4. مدل ریاضی 163-4-5. توضیحات مدل 173-5. تحلیل حساسیت 17 3-6. پیچیدگی مسئله 223-7. مقدمهای بر الگوریتم ژنتیک 243-7-1. شمای کلی الگوریتم ژنتیک 25 3-7-2. واژگان الگوریتم ژنتیک 263-7-3. جامعه اولیه 263-7-4. عملیات ژنتیک 27 3-7-4-1.عملگر انتخاب 273-7-4-2.عملگر تقاطع 283-7-4-3. عملگر جهش 293-7-4-4.تابع برازش 30 3-7-4-5. شرط توقف 30 3-8 .معرفی الگوریتم رقابت استعماری3-8-1. مقدمه 303-8-2. شکلدهی امپراطوری اولیه 303-8-3. سیاست جذب، حرکت کشور مستعمره به سمت استعمارگر 333-8-4. انقلاب 353-8-5. جابهجایی قدرت بین استعمارگر و مستعمره 353-8-6. رقابت استعماری 36 3-8-7. همگرایی 37 فصل چهارم: یافتههای تحقیق4-1. مقدمه 414-2. ساختار الگوریتم ژنتیک پیشنهادی 414-2-1. ساختار کروموزوم 414-2-2. جمعیت اولیه 424-2-3. تابع برازش 424-2-4. عملگر تقاطع 43 4-2-5. عملگر جهش 444-2-6. ارزیابی فرزندان 454-2-7. جست و جوی محلی 454-2-8. معیار توقف 45 4-3. ساختار الگوریتم رقابت استعماری پیشنهادی 464-4. نتایج محاسباتی 474-4-1. تنظیم پارامترها 47 4-4-2. روش تاگوچی 474-4-3. روش تاگوچی برای تنظیم الگوریتم ژنتیک 494-4-4. روش تاگوچی برای تنظیم الگوریتم رقابت استعماری 504-5. معیارهای عملکرد4-5-1. شاخص زمان محاسباتی 524-5-2. روشهای اندازهگیری عملکرد الگوریتمها 524-5-3. تحلیل نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری 55 4-6. جمعبندی 56فصل پنجم: نتیجهگیری و پیشنهادات آتی5-1. جمعبندی 595-2. پیشنهادات آتی 59ضمیمه یک 60ضمیمه دو 65 منابع و مراجع 71 لیست جدولهاعنوانشماره صفحهجدول 3-1. دادههای مسئله اول برای کار و زمان 18 جدول 3-2. دادههای مسئله اول برای نرخ یادگیری 18جدول 3-3. دادههای مسئله اول برای نرخ استهلاک 18جدول 3-4. دادههای مربوط به زمان نگهداری برای مسئله اول 18 جدول 3-5. دادههای مسئله دوم برای کار و زمان 19جدول 3-6. دادههای مسئله دوم برای نرخ یادگیری 19جدول 3-7. دادههای مسئله دوم برای نرخ استهلاک 20 جدول 3-8. دادههای مربوط به زمان نگهداری برای مسئله دوم 20 جدول 3-9. دادههای مسئله سوم برای کار و زمان 21جدول 3-10. دادههای مسئله سوم برای نرخ یادگیری 21 جدول 3-11. دادههای مربوط به زمان نگهداری برای مسئله سوم 21جدول 3-12. دادههای مسئله سوم برای نرخ استهلاک 22 جدول 4-1. پارامترهای الگوریتم ژنتیک در سه سطح 49جدول 4-2. مقادیر بهینه برای پارامترهای GA50جدول 4-3. پارامترهای الگوریتم ICAدر سه سطح 50جدول 4-4. مقادیر بهینه برای پارامترهای ICA51جدول 4-5. نتایج بدستآمده از روش دقیق، الگوریتم ژنتیک و رقابت استعماری 53 لیست شکلهاعنوان شماره صفحهشکل 2-1. رویکردهای مدلسازی اثر یادگیری 9شکل 3-1. سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی 24شکل 3-2. تقاطع تکنقطهای 29شکل 3-3. تقاطع دو نقطهای 29شکل 3-4. نحوه تخصیص کشورهای مستعمره به کشور استعمارگر 32شکل 3-5. حرکت خطی مستعمره در راستای استعمارگر 34شکل 3-6. زاویه انحراف رسیدن کشور مستعمره به امپریالیسم 34شکل 3-7. مسیر انقلاب در یک کشور مستعمره 35شکل 3-8 .جابهجایی قدرت مابین کشورهای استعمارگر و مستعمره 36شکل 3-9. سقوط امپراطوریهای ضعیفتر 37شکل 4-1. ساختار دو بخش و نحوه کدگشایی کروموزوم 42شکل 4-2. نحوه عملکرد عملگرهای تقاطع 44شکل 4-3. نمایش و نحوه عملگر جهش 45شکل 4-4. مقادیر سطوح مختلف پارامترهای الگوریتم GA در نسبت S/N 49شکل 4-5. مقادیر سطوح مختلف پارامترهای الگوریتم ICA در نسبت S/N 51شکل 4-6. نمودار RPD مربوط به الگوریتم ژنتیک و رقابت استعماری 55شکل 4-7. نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری 56 فصل اولکلیات تحقیق 1- نگاهی به مسئله ی زمان بندی1-1.مقدمه:زمانبندی[1] فرآیند تخصیص منابع به فعالیتها با درنظرگرفتن دورههای زمانی مربوط به آنها به منظور بهینهسازی یک یا چند هدف میباشد. این فرآیند به عنوان یک فرآیند تصمیمگیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. زمانبندی کارای فعالیتها زمینه ساز بهبود عملکرد سیستمهای تولیدی میباشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار میآید. تئوری زمانبندی در ارتباط با مدلهای ریاضی است که فرآیند زمانبندی را تشریح میکنند. چشم انداز تئوریک یک نگرش کمی برای بدستآوردن ساختار مسائل در چهارچوب مدلهای ریاضی بدست میدهد که این امر با تشریح منابع و فعالیتها و تبدیل اهداف تصمیمگیری به یک تابع هدف، صورت میپذیرد. درنتیجه، منابع، فعالیتها و توابع هدف عناصر کلیدی مدلهای زمانبندی محسوب میشوند. منابع برحسب قابلیتهای کمی و کیفی خود مشخص میشوند. به طوری که هر مدل نشاندهنده نوع و میزان منابع به کاررفته در آن میباشد. از سوی دیگر، فعالیتها برحسب اطلاعاتی از قبیل منابع موردنیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف میشوند. توابع هدف نیز دربرگیرنده هزینههای سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیتها میباشند. تصمیمات عمده در فرآیند زمانبندی شامل بهره برداری کار از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمان های تحویل با موعدهای تحویلی تعیین شده می شوند.انگیزه بسیاری از توسعهها و پیشرفتهای علمی در حوزه زمانبندی برخاسته از محیطهای صنعتی است و به طورطبیعی در بیان مفاهیم زمانبندی از واژههای به کار رفته درصنعت استفاده میشود. به همین خاطر منابع با عنوان ماشین به کار میروند و به هرکدام از فعالیتها، کار اطلاق می شود بطوری که کارها اغلب به وسیله مجموعهای از ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند.به طورکلی، مسائل زمانبندی به صورت مسائل بهینهسازی محدودیتدار بیان میشوند که در آنها به بررسی تصمیمات مربوط به تخصیص ماشینها و توالی پردازش کارها پرداخته میشود. درحالتی که تنها یک ماشین موجود است، تعیین توالی پردازش کارها یک برنامه زمانی کامل را تشکیل میدهد. مسائل تک ماشینه با وجود سادگی ذاتی، سنگ بنای درک فراگیر مفاهیم زمان بندی را تشکیل میدهند. در مقابل، زمانبندی مسائل چند ماشینه شامل سیستمهای موازی، سیستمهای متوالی و سیستمهای ترکیبی میباشد. در سیستمهای موازی، هریک از کارها با انجام یک عملیات همانند مسائل تک ماشینه بر روی یکی از ماشینهای موازی موجود پردازش میشوند و مسائل مربوطه ساختار نسبتاً پیچیده تری را تجربه میکنند.1-2. تعریف مسئله:مسئله زمانبندی ماشینهای موازی نامرتبط ، به عنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است شناخته میشود. مسائل ماشینهای موازی نامرتبط[2] حالت عمومیت یافته مسائل تکماشینه و مسائل کلاسیک ماشینهای موازی محسوب میشوند.در مسائل کلاسیک ماشینهای موازی ، مجموعهای از کارهای مستقل وجود دارد که هرکدام از آنها بر روی یکی از ماشینهای موازی یکسان پردازش میشود و زمان پردازش کار j بر روی تمامی ماشینها یکسان است ولی در حالت نامرتبط بودن ماشینها، زمان پردازش کارها بر روی ماشینها نه تنها به نوع کار بلکه به نوع ماشین نیز وابسته است و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای مختلف وجود ندارد.در بسیاری از محیطهای کاری انسان به عنوان عنصر اصلی به شمار میرود. در فعالیتهایی که در آن انسان سهم بسزایی دارد مسئله یادگیری مهم است و تاکنون در اکثر مقالات فرض رایج بر این بوده که زمان پردازش کارها ثابت و مستقل از توالی است، در حالی که در بسیاری از موارد عملی با تکرار کارهای مشابه توانایی و مهارت اپراتور افزایش و در نتیجه آن ، زمان پردازش کارها کاهش مییابد. این امر باعث بهبود مستمر عملکرد تسهیلات تولیدی مخصوصا نیروی انسانی میشودکه به آن تاثیر یادگیری میگویند، که از جمله این فعالیتها میتوان به تمام کارهایی که سیستم دستی را شامل میشود اشاره کرد.یکی از پرکاربرد ترین توابع هدف در مسائل بهینهسازی ماشینهای موازی ، کمینه کردن بیشترین زمان تکمیل کارها [3]میباشد. چرا که رسیدن به این هدف سبب میشود کارها تا حد ممکن با یکنواختی بیشتری بین ماشینها توزیع شوند و به نحوی از ظرفیت کاری تمامی ماشینها تا حد مطلوب استفاده شود و در نتیجه از تجمع کارها بر روی یک یا تعدادی از ماشینها جلوگیری به عمل آید . از اینرو معیار بیشترین زمان تکمیل کارها به عنوان معیار بهینه سازی در مدل پیشنهادی مورد استفاده قرار گرفته است.در این تحقیق ، مسئله زمانبندی ماشینهای موازی نامرتبط با در نظر گرفتن اثر یادگیری و استهلاک به طور همزمان و در نظر گرفتن فعالیت نگهداری با هدف کمینه سازی بیشترین زمان تکمیل کارها معرفی و مورد بررسی قرار میگیرد. در ادامه برای مسئله بیان شده یک مدل ریاضی ارائه میشود. همچنین از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم رقابت استعماری برای حل آن استفاده میشود.از جمله کاربردهای مدل پیشنهادی در تحقیق پیش رو را میتوان در یک سیسنم خدماتی همانند بانک مشاهده نمود. در یک بانک، چند اپراتور به صورت موازی وجود دارند که هر کدام مسئول رسیدگی به بخشی از امور بانکی هستند. بر فرض مثال اپراتور اول وظیفه بازگشایی حساب ، صدور انواع حوالههای بانکی و انجام امور مرتبط با انتقال وجه را بر عهده دارد و اپراتور دوم به سایر امور بانکی نظیر رسیدگی به درخواستهای وام مشتریان، صدور گواهی سپرده ، خرید و فروش اوراق مشارکت و .. میپردازد. در این سیستم بانکی به دنبال این هستیم که بهترین توالی از انجام امور بانکی مشتریان را به نحوی بدست آوریم که بیشترین زمان تکمیل امور بانکی کمینه شود.1-3. اهداف این تحقیق:اهداف این تحقیق عبارتند از:- بررسی اثر استهلاک و یادگیری به طور همزمان در ماشینهای موازی غیر مرتبط- مروری بر مطالعات صورت گرفته ئر محیط ماشینهای موازی غیر مرتبط، نگهداری و تعمیرات، اثر یادگیری و اثر استهلاک- توسعه مدل ریاضی برای مسئله مطرحشده- توسعه روش فراابتکاری برای حل مدل مطرحشده1-4. فرضیات مسئله ماشین های موازی این مطالعه:فرضیاتی که در این مطالعه زمانبندی لحاظ شده است در زیر لیست شدهاند:1-5. جنبه های نوآوری تحقیق:تحقیق موجود از دوجنبه صورت مسئله و روش حل نسبت به تحقیقات پیشین دارای نوآوری میباشد. در این تحقیق یک مدل ریاضی جدید برای مسئله زمانبندی ماشینهای نامرتبط هدف حداقل کردن بیشترین زمان تکمیل و درنظرگرفتن اثر یادگیری و استهلاک بطور همزمان و فعالیتهای نگهداری توسعه داده شده است. همچنین یک رویکرد ابتکاری با استفاده از الگوریتم ژنتیک و الگوریتم رقابت استعماری برای حل مسئله ارائه شده است.مطالب ارائه شده در اين تحقيق در پنج فصل سازماندهي ميشوند: کليات تحقيق در فصل اول ارائه شده است. در فصل دوم به مرور ادبيات تحقيق زمانبندي پرداخته ميشود. درفصل سوم مدل رياضي پيشنهادي تشريح و اعتبارسنجي ميشود و سپس به معرفی الگوریتم ژنتیک و الگوریتم رقابت استعماری برای مسئله مذکور پرداخته میشود. نتايج محاسباتي الگوريتمهای پيشنهادي در فصل چهارم ارائه ميشود و نهايتا، فصل پاياني تحقيق شامل نتيجهگيري و پيشنهادات تحقيقات آتي ميباشد. فصل دومادبیات نظری و پیشینه تحقیق فصل دوم: مرور ادبیات و پیشینه تحقیق2-1. مقدمهدر این بخش به بررسی کارهای گذشته و طبقهبندی مسائل زمانبندی پروژه که در مقالات مختلف ارائه شده است میپردازیم. در این فصل سعی شده است تا یک دید کلی و جامع نسبت به طبقهبندی مسائل و کارهای انجامشده در زمینه زمانبندی پروژه با نرخهای یادگیری و استهلاک و فعالیتهای تعمیرات و نگهداری ارائه شود. از آنجا که هر یک از کارهای انجامگرفته در مرجعی که به آن اشاره شده است ، به طور کامل توضیح داده شده است، در اینجا فقط در مورد هرکدام توضیحاتی کلی ارائه میگردد.2-2.مروری بر مسائل زمانبندیالگوهای زیادی در تعریف مسائل زمانبندی و طبقهبندی آنها مطرح هستند: مسائل زمانبندی از نظر فرایند تولید محصولات و بسته به تعداد عملیاتهای مورد نیاز برای پردازش یک کار و نیز تعداد ماشینهای موجود برای پردازش هر عملیات دارای الگوهای زیادی میباشند. در کل یک مسئله زمانبندی عمومی را میتوان با استفاده از سه نماد که توسط گراهام و همکارانش ]36[ ارائه شد توصیف نمود که بیانگر وضعیت و شرایط ماشین یا منبع است و معمولا دارای یک نماد است، خصوصیات و جزئیات نحوه پردازش و محدودیتهای موجود را بیان میکند و ممکن است شامل هیچ نمادی نباشد و یا چندین نماد باشد، بیانگر تابع هدف مسئله است و معمولا شامل تنها یک نماد است.جدول 2-1. محيطهاي کارگاهي (نماد α)سادهترين شکل و حالت خاص تمامي محيطهاي کارگاهي ممکن.تکماشينهm ماشين کاملا يکسان به موازات هم قرار ميگيرند؛ هرکدام از کارها نياز به يک عمليات دارد و بر روي يکي از ماشينهاي موجود پردازش ميشود.ماشينهاي موازي يکسانحالت کليتر ماشينهاي موازي يکسان؛ ماشينها داراي سرعت پردازش متفاوت هستند.ماشينهاي موازي يکنواختحالت کليتر ماشينهاي موازي يکنواخت؛ سرعت پردازش ماشينها هم به نوع ماشين و هم به نوع کار بستگي دارد.ماشينهاي موازي نامرتبطm ماشين به صورت متوالي وجود دارد؛ هر کدام از کارها بر روي تمامي ماشينها پردازش ميشوند، تمامي کارها مسير پردازش يکساني دارند.کارگاه جريانيحالت کليتر کارگاه جرياني؛ m ايستگاه پردازش به صورت متوالي وجود دارد؛ در هر ايستگاه يکي از حالات سهگانه ماشينهاي موازي براي پردازش يک کار رخ ميدهد.کارگاه جرياني منعطفهر کدام از کارها داراي مسير پردازش متمايز بر رويm ماشين موجود ميباشند.توليد کارگاهيحالت کليتر توليد کارگاهي؛ m مرکز پردازش وجود دارد؛در هر ايستگاه يکي از حالات سهگانه ماشينهاي موازي براي پردازش يک کار رخ ميدهد.توليد کارگاهي منعطفm ماشين وجود دارد؛ هر کدام از کارها بر روي هر کدام از ماشينها يک يا چند بار پردازش ميشود؛ محدوديتي براي مسير پردازش کارها وجود ندارد.کارگاه باز جدول 2-2. جزئيات و محدوديتهاي پردازش کارها (نماد β)کار نوع j نميتواند قبل از زمان آمادهسازي خود () پردازش خود را آغاز کند.زمان آمادهسازي غير صفر کارهاپردازش يک کار بر روي يک ماشين ميتواند قبل از زمان تکميل کار قطع شود و کار ديگري بر روي آن ماشين پردازش شود.شکست کارهاقبل از اينکه يک کار پردازش خود را آغاز کند يک يا چند کار ديگر بايد پردازش شود.اولويت پردازش کارهازمان نصب وابسته به توالي بين پردازش کار i و j بر روي ماشين k منظور ميشود.زمان نصب وابسته به توالي کارها , n کار موجود به f گروه کاري تعلق دارند. اعضاي هر گروه زمانهاي پردازش متفاوتي دارند ولي آنها ميتوانند به صورت متوالي بر روييک ماشين بدون زمان نصب پردازش شوند.گروههاي کارييک ماشين مي تواند دستهاي از کارها را به طور همزمان پردازش کند و زمانهاي پردازش يک دسته لزوما برابر نيست.پردازش دستهاييک ماشين ممکن است به طور مستمر در دسترس نباشد.خرابي ماشينمجموعه شامل ماشينهاي ميباشد که قادر به پردازش کار نوع j هستند.دسترسي محدود به ماشينهادر مسائل کارگاه جرياني، ترتيبي که کارها بر روي ماشين اول پردازش ميشوند، در کل سيستم حفظ ميشود.جايگشتدر مسائل کارگاه جرياني با بافر محدود، هنگاميکه ظرفيت بافر کامل ميشود، کار تکميل شده بر روي ماشين بالادست باقي ميماند و از پردازش کار بعدي بر روي آن ممانعت ميشود.بلوکه شدندر مسائل کارگاه جرياني، کارها نميتوانند بين دو ماشين متوالي در حالت انتظار قرار گيرند.بدون انتظاردر مسائل توليد کارگاهي يک کار ميتواند در يک مرکز کاري بيشتر از يک بار پردازش شود.گردش مجدد جدول 2-3. تابع هدف مسئله (نمادγ)زمان تکميل آخرين کاري که سيستم را ترک ميکند.زمان تکميل بيشينهبيشترين انحراف زماني از موعدهاي تحويل کارها را نشان ميدهد.زمان تاخير بيشينهمجموع زمانهاي تکميل کارها را اندازهگيري ميکند.زمان تکميل کلمجموع انحرافهاي زماني کارها از موعدهاي تحويل را محاسبه ميکند.زمان ديرکرد کلتعداد کارهاي داراي ديرکرد زماني را محاسبه ميکند.تعداد کارهاي با تاخير کلمجموع زمانهاي زودکرد و ديرکرد کارها را محاسبه ميکند.زمانهاي زودکرد و ديرکرد کلمجموع زمانهاي تکميل وزني کارها را اندازهگيري ميکند.زمان تکميلوزني کلمجموع انحرافهاي زماني وزني کارها از موعدهاي تحويل را محاسبه ميکند.زمان ديرکرد وزني کلتعداد وزني کارهاي داراي ديرکرد زماني را نشان ميدهد.تعداد کارهاي با تاخير وزني کلمجموع زمانهاي زودکرد و ديرکرد وزني کارها را محاسبه ميکند.زمانهاي زودکرد و ديرکرد وزني کل 2-2-1. تک ماشینه[4]سادهترین حالت ممکن است که معمولا حالت خاص سایر مسائل در نظر گرفته میشود. در این حالت فقط یک ماشین در دسترس بوده و این ماشین قادر به پردازش تنها یک کار در هر لحظه میباشد. این مدل مبنا اساس کار برای ایجاد قوانین و قواعد زمانبندی برای استفاده در سایر مدلها میباشد به عبارت دیگر عموما روشها و راهکارها ابتدا برای یک مدل تک ماشینه تبدیل میگردد و سپس برای سایر مدلها بسط داده میشوند.2-2-2. ماشینهای موازی[5]در این سیستم تعدادی ماشین مشابه ( از لحاظ فرایند مربوطه ) در دسترس هستند و هر کار میتواند روی هر یک از ماشینها پردازش شود. این سیستم، از لحاظ ویژگیهای ماشین از قبیل سرعت پردازش، کیفیت محصولات تولیدی و هزینه تولید به دسته ماشینهای موازی یکسان[6] و ماشینهای موازی متفاوت[7] تقسیم میشوند.2-3. اثر یادگیری در زمانبندی:اثریادگیری اولین بار توسط رایت[5] مطرح شد و در آن مطالعه روی صنعت هواپیما، نشان داد که هزینههای کارگری هر واحد با افزایش نرخ تولید کاهش پیدا می کند. مطالعاتی که بر روی یادگیری و اثر آن بر رفتار موجودات زنده انجام شده نشان داد که زمان مورد نیاز برای انجام یک کار با افزایش تجربه آن کاهش می یابد. این مطالعه روانشناسی منجر به ایجاد پدیده جدید به نام اثریادگیری شد. اثر یادگیری در دورههای برنامه ریزی تولید کوتاهمدت از اهمیت به سزایی برخوردار است. کیچیه و فونتانا[6] اولین کسانی بودند که درهنگام محاسبه مقدار بهینه اندازه انباشته، اثر یادگیری را لحاظ کردند. در این حالت موجودی زودتر از زمانی که یادگیری لحاظ نشده به پایان میرسد. با درنظرگرفتن یک نرخ ثابت تقاضا این امر منجر به هزینههای نگهداری بالاتر و همچنین کاهش میزان اندازه انباشته بهینه میشود. اگرچه برنامه ریزی تولید یکی از وظایف اصلی در برنامهریزی تولید کوتاهمدت است اما اثر یادگیری در ادبیات زمانبندی اولین بار توسط بیسکاپ[7] مطرح شد. وی در تحقیقش اثر یادگیری را در مسئله زمانبندی تکماشینه کمینهسازی زمان تکمیل و مجموع وزنی انحرافات زمان تکمیل از موعد تحویل مورد بررسی قرار داد.
زمان بندی ماشین های موازی غیر مرتبط با اثر همزمان استهلاک و یادگیری و فعالیت-های نگهداری word
چکیده:نگهداری ماشین در تولید اغلب برای ممانعت از شکست ماشین به منظور حفظ راندمان تولید انجام میشود. در این پایاننامه مسئله کمینه سازی بیشترین زمان تکمیل بر روی ماشینهای موازی غیرمرتبط باتوجه به تاثیرات استهلاک بر زمان کارها و فعالیتهای نگهداری و اثر یادگیری در افق زمانبندی مورد بررسی قرار گرفت. یک ماشین بعد از عملیات نگهداری به شرایط اولیه خود بازمیگردد و اثر استهلاک از نو، آغاز میگردد. هدف در این مسئله پیدا کردن دفعات بهینه، بهترین زمان انجام عملیات نگهداری و توالی بهینه کارها روی ماشینها به طوری که بیشترین زمان تکمیل کارها کمینه گردد. برای مسئله مطرح شده یک مدل ریاضی خطی ارائه شد و بعد از اشاره به NP-hard بودن مسئله به ارائه روش فرا ابتکاری ژنتیک و رقابت استعماری جهت حل مسئله در ابعاد موجود در واقعیت پرداخته شد و در نهایت نتایج بدست آمده مورد بررسی و تحلیل قرار گرفت.کلمات کلیدی: ماشینهای موازی غیرمرتبط، اثر یادگیری، اثر استهلاک،فعالیتهای نگهداری.فهرستعنوان شماره صفحهچکیده فصل اول: مقدمه و کلیات تحقیق1-1. مقدمه 21-2. تعریف مسئله 31-3. فرضیات مسئله ماشینهای موازی این مطالعه 3 1-4. اهداف تحقیق 4 1-5. جنبههای نوآوری تحقیق 41-6. محتویات تحقیق 4 1-7. جمعبندی 4فصل دوم: ادبیات نظری و پیشینه تحقیق2-1. مقدمه 72-2. تعربف اثر یادگیری در فن زمانبندی 72-3. تعریف نگهداری و تعمیرات در زمانبندی 92-4. ادبیات و پیشینه تحقیق 102-4-1. مسائل ماشینهای موازی 102-4-2. مروری بر مطالعات زمانبندی با اثر یادگیری 112-4-3. مروری بر مطالعات اثر همزمان یادگیری و زوال در زمانبندی 11 2-4-4. مروری بر مطالعات زمانبندی با اثر استهلاک 122-5. جمعبندی 13فصل سوم: ارائه مدل ریاضی3-1. مقدمه 143-2. تعریف مسئله 14 3-3. فرضیات مسئله 143-4. مدل ریاضی پیشنهادی 153-4-1. اندیسها 153-4-2. پارامترهای مسئله 153-4-3. متغیرهای تصمیم 153-4-4. مدل ریاضی 163-4-5. توضیحات مدل 173-5. تحلیل حساسیت 17 3-6. پیچیدگی مسئله 223-7. مقدمهای بر الگوریتم ژنتیک 243-7-1. شمای کلی الگوریتم ژنتیک 25 3-7-2. واژگان الگوریتم ژنتیک 263-7-3. جامعه اولیه 263-7-4. عملیات ژنتیک 27 3-7-4-1.عملگر انتخاب 273-7-4-2.عملگر تقاطع 283-7-4-3. عملگر جهش 293-7-4-4.تابع برازش 30 3-7-4-5. شرط توقف 30 3-8 .معرفی الگوریتم رقابت استعماری3-8-1. مقدمه 303-8-2. شکلدهی امپراطوری اولیه 303-8-3. سیاست جذب، حرکت کشور مستعمره به سمت استعمارگر 333-8-4. انقلاب 353-8-5. جابهجایی قدرت بین استعمارگر و مستعمره 353-8-6. رقابت استعماری 36 3-8-7. همگرایی 37 فصل چهارم: یافتههای تحقیق4-1. مقدمه 414-2. ساختار الگوریتم ژنتیک پیشنهادی 414-2-1. ساختار کروموزوم 414-2-2. جمعیت اولیه 424-2-3. تابع برازش 424-2-4. عملگر تقاطع 43 4-2-5. عملگر جهش 444-2-6. ارزیابی فرزندان 454-2-7. جست و جوی محلی 454-2-8. معیار توقف 45 4-3. ساختار الگوریتم رقابت استعماری پیشنهادی 464-4. نتایج محاسباتی 474-4-1. تنظیم پارامترها 47 4-4-2. روش تاگوچی 474-4-3. روش تاگوچی برای تنظیم الگوریتم ژنتیک 494-4-4. روش تاگوچی برای تنظیم الگوریتم رقابت استعماری 504-5. معیارهای عملکرد4-5-1. شاخص زمان محاسباتی 524-5-2. روشهای اندازهگیری عملکرد الگوریتمها 524-5-3. تحلیل نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری 55 4-6. جمعبندی 56فصل پنجم: نتیجهگیری و پیشنهادات آتی5-1. جمعبندی 595-2. پیشنهادات آتی 59ضمیمه یک 60ضمیمه دو 65 منابع و مراجع 71 لیست جدولهاعنوانشماره صفحهجدول 3-1. دادههای مسئله اول برای کار و زمان 18 جدول 3-2. دادههای مسئله اول برای نرخ یادگیری 18جدول 3-3. دادههای مسئله اول برای نرخ استهلاک 18جدول 3-4. دادههای مربوط به زمان نگهداری برای مسئله اول 18 جدول 3-5. دادههای مسئله دوم برای کار و زمان 19جدول 3-6. دادههای مسئله دوم برای نرخ یادگیری 19جدول 3-7. دادههای مسئله دوم برای نرخ استهلاک 20 جدول 3-8. دادههای مربوط به زمان نگهداری برای مسئله دوم 20 جدول 3-9. دادههای مسئله سوم برای کار و زمان 21جدول 3-10. دادههای مسئله سوم برای نرخ یادگیری 21 جدول 3-11. دادههای مربوط به زمان نگهداری برای مسئله سوم 21جدول 3-12. دادههای مسئله سوم برای نرخ استهلاک 22 جدول 4-1. پارامترهای الگوریتم ژنتیک در سه سطح 49جدول 4-2. مقادیر بهینه برای پارامترهای GA50جدول 4-3. پارامترهای الگوریتم ICAدر سه سطح 50جدول 4-4. مقادیر بهینه برای پارامترهای ICA51جدول 4-5. نتایج بدستآمده از روش دقیق، الگوریتم ژنتیک و رقابت استعماری 53 لیست شکلهاعنوان شماره صفحهشکل 2-1. رویکردهای مدلسازی اثر یادگیری 9شکل 3-1. سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی 24شکل 3-2. تقاطع تکنقطهای 29شکل 3-3. تقاطع دو نقطهای 29شکل 3-4. نحوه تخصیص کشورهای مستعمره به کشور استعمارگر 32شکل 3-5. حرکت خطی مستعمره در راستای استعمارگر 34شکل 3-6. زاویه انحراف رسیدن کشور مستعمره به امپریالیسم 34شکل 3-7. مسیر انقلاب در یک کشور مستعمره 35شکل 3-8 .جابهجایی قدرت مابین کشورهای استعمارگر و مستعمره 36شکل 3-9. سقوط امپراطوریهای ضعیفتر 37شکل 4-1. ساختار دو بخش و نحوه کدگشایی کروموزوم 42شکل 4-2. نحوه عملکرد عملگرهای تقاطع 44شکل 4-3. نمایش و نحوه عملگر جهش 45شکل 4-4. مقادیر سطوح مختلف پارامترهای الگوریتم GA در نسبت S/N 49شکل 4-5. مقادیر سطوح مختلف پارامترهای الگوریتم ICA در نسبت S/N 51شکل 4-6. نمودار RPD مربوط به الگوریتم ژنتیک و رقابت استعماری 55شکل 4-7. نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری 56 فصل اولکلیات تحقیق 1- نگاهی به مسئله ی زمان بندی1-1.مقدمه:زمانبندی[1] فرآیند تخصیص منابع به فعالیتها با درنظرگرفتن دورههای زمانی مربوط به آنها به منظور بهینهسازی یک یا چند هدف میباشد. این فرآیند به عنوان یک فرآیند تصمیمگیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. زمانبندی کارای فعالیتها زمینه ساز بهبود عملکرد سیستمهای تولیدی میباشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار میآید. تئوری زمانبندی در ارتباط با مدلهای ریاضی است که فرآیند زمانبندی را تشریح میکنند. چشم انداز تئوریک یک نگرش کمی برای بدستآوردن ساختار مسائل در چهارچوب مدلهای ریاضی بدست میدهد که این امر با تشریح منابع و فعالیتها و تبدیل اهداف تصمیمگیری به یک تابع هدف، صورت میپذیرد. درنتیجه، منابع، فعالیتها و توابع هدف عناصر کلیدی مدلهای زمانبندی محسوب میشوند. منابع برحسب قابلیتهای کمی و کیفی خود مشخص میشوند. به طوری که هر مدل نشاندهنده نوع و میزان منابع به کاررفته در آن میباشد. از سوی دیگر، فعالیتها برحسب اطلاعاتی از قبیل منابع موردنیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف میشوند. توابع هدف نیز دربرگیرنده هزینههای سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیتها میباشند. تصمیمات عمده در فرآیند زمانبندی شامل بهره برداری کار از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمان های تحویل با موعدهای تحویلی تعیین شده می شوند.انگیزه بسیاری از توسعهها و پیشرفتهای علمی در حوزه زمانبندی برخاسته از محیطهای صنعتی است و به طورطبیعی در بیان مفاهیم زمانبندی از واژههای به کار رفته درصنعت استفاده میشود. به همین خاطر منابع با عنوان ماشین به کار میروند و به هرکدام از فعالیتها، کار اطلاق می شود بطوری که کارها اغلب به وسیله مجموعهای از ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند.به طورکلی، مسائل زمانبندی به صورت مسائل بهینهسازی محدودیتدار بیان میشوند که در آنها به بررسی تصمیمات مربوط به تخصیص ماشینها و توالی پردازش کارها پرداخته میشود. درحالتی که تنها یک ماشین موجود است، تعیین توالی پردازش کارها یک برنامه زمانی کامل را تشکیل میدهد. مسائل تک ماشینه با وجود سادگی ذاتی، سنگ بنای درک فراگیر مفاهیم زمان بندی را تشکیل میدهند. در مقابل، زمانبندی مسائل چند ماشینه شامل سیستمهای موازی، سیستمهای متوالی و سیستمهای ترکیبی میباشد. در سیستمهای موازی، هریک از کارها با انجام یک عملیات همانند مسائل تک ماشینه بر روی یکی از ماشینهای موازی موجود پردازش میشوند و مسائل مربوطه ساختار نسبتاً پیچیده تری را تجربه میکنند.1-2. تعریف مسئله:مسئله زمانبندی ماشینهای موازی نامرتبط ، به عنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است شناخته میشود. مسائل ماشینهای موازی نامرتبط[2] حالت عمومیت یافته مسائل تکماشینه و مسائل کلاسیک ماشینهای موازی محسوب میشوند.در مسائل کلاسیک ماشینهای موازی ، مجموعهای از کارهای مستقل وجود دارد که هرکدام از آنها بر روی یکی از ماشینهای موازی یکسان پردازش میشود و زمان پردازش کار j بر روی تمامی ماشینها یکسان است ولی در حالت نامرتبط بودن ماشینها، زمان پردازش کارها بر روی ماشینها نه تنها به نوع کار بلکه به نوع ماشین نیز وابسته است و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای مختلف وجود ندارد.در بسیاری از محیطهای کاری انسان به عنوان عنصر اصلی به شمار میرود. در فعالیتهایی که در آن انسان سهم بسزایی دارد مسئله یادگیری مهم است و تاکنون در اکثر مقالات فرض رایج بر این بوده که زمان پردازش کارها ثابت و مستقل از توالی است، در حالی که در بسیاری از موارد عملی با تکرار کارهای مشابه توانایی و مهارت اپراتور افزایش و در نتیجه آن ، زمان پردازش کارها کاهش مییابد. این امر باعث بهبود مستمر عملکرد تسهیلات تولیدی مخصوصا نیروی انسانی میشودکه به آن تاثیر یادگیری میگویند، که از جمله این فعالیتها میتوان به تمام کارهایی که سیستم دستی را شامل میشود اشاره کرد.یکی از پرکاربرد ترین توابع هدف در مسائل بهینهسازی ماشینهای موازی ، کمینه کردن بیشترین زمان تکمیل کارها [3]میباشد. چرا که رسیدن به این هدف سبب میشود کارها تا حد ممکن با یکنواختی بیشتری بین ماشینها توزیع شوند و به نحوی از ظرفیت کاری تمامی ماشینها تا حد مطلوب استفاده شود و در نتیجه از تجمع کارها بر روی یک یا تعدادی از ماشینها جلوگیری به عمل آید . از اینرو معیار بیشترین زمان تکمیل کارها به عنوان معیار بهینه سازی در مدل پیشنهادی مورد استفاده قرار گرفته است.در این تحقیق ، مسئله زمانبندی ماشینهای موازی نامرتبط با در نظر گرفتن اثر یادگیری و استهلاک به طور همزمان و در نظر گرفتن فعالیت نگهداری با هدف کمینه سازی بیشترین زمان تکمیل کارها معرفی و مورد بررسی قرار میگیرد. در ادامه برای مسئله بیان شده یک مدل ریاضی ارائه میشود. همچنین از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم رقابت استعماری برای حل آن استفاده میشود.از جمله کاربردهای مدل پیشنهادی در تحقیق پیش رو را میتوان در یک سیسنم خدماتی همانند بانک مشاهده نمود. در یک بانک، چند اپراتور به صورت موازی وجود دارند که هر کدام مسئول رسیدگی به بخشی از امور بانکی هستند. بر فرض مثال اپراتور اول وظیفه بازگشایی حساب ، صدور انواع حوالههای بانکی و انجام امور مرتبط با انتقال وجه را بر عهده دارد و اپراتور دوم به سایر امور بانکی نظیر رسیدگی به درخواستهای وام مشتریان، صدور گواهی سپرده ، خرید و فروش اوراق مشارکت و .. میپردازد. در این سیستم بانکی به دنبال این هستیم که بهترین توالی از انجام امور بانکی مشتریان را به نحوی بدست آوریم که بیشترین زمان تکمیل امور بانکی کمینه شود.1-3. اهداف این تحقیق:اهداف این تحقیق عبارتند از:- بررسی اثر استهلاک و یادگیری به طور همزمان در ماشینهای موازی غیر مرتبط- مروری بر مطالعات صورت گرفته ئر محیط ماشینهای موازی غیر مرتبط، نگهداری و تعمیرات، اثر یادگیری و اثر استهلاک- توسعه مدل ریاضی برای مسئله مطرحشده- توسعه روش فراابتکاری برای حل مدل مطرحشده1-4. فرضیات مسئله ماشین های موازی این مطالعه:فرضیاتی که در این مطالعه زمانبندی لحاظ شده است در زیر لیست شدهاند:1-5. جنبه های نوآوری تحقیق:تحقیق موجود از دوجنبه صورت مسئله و روش حل نسبت به تحقیقات پیشین دارای نوآوری میباشد. در این تحقیق یک مدل ریاضی جدید برای مسئله زمانبندی ماشینهای نامرتبط هدف حداقل کردن بیشترین زمان تکمیل و درنظرگرفتن اثر یادگیری و استهلاک بطور همزمان و فعالیتهای نگهداری توسعه داده شده است. همچنین یک رویکرد ابتکاری با استفاده از الگوریتم ژنتیک و الگوریتم رقابت استعماری برای حل مسئله ارائه شده است.مطالب ارائه شده در اين تحقيق در پنج فصل سازماندهي ميشوند: کليات تحقيق در فصل اول ارائه شده است. در فصل دوم به مرور ادبيات تحقيق زمانبندي پرداخته ميشود. درفصل سوم مدل رياضي پيشنهادي تشريح و اعتبارسنجي ميشود و سپس به معرفی الگوریتم ژنتیک و الگوریتم رقابت استعماری برای مسئله مذکور پرداخته میشود. نتايج محاسباتي الگوريتمهای پيشنهادي در فصل چهارم ارائه ميشود و نهايتا، فصل پاياني تحقيق شامل نتيجهگيري و پيشنهادات تحقيقات آتي ميباشد. فصل دومادبیات نظری و پیشینه تحقیق فصل دوم: مرور ادبیات و پیشینه تحقیق2-1. مقدمهدر این بخش به بررسی کارهای گذشته و طبقهبندی مسائل زمانبندی پروژه که در مقالات مختلف ارائه شده است میپردازیم. در این فصل سعی شده است تا یک دید کلی و جامع نسبت به طبقهبندی مسائل و کارهای انجامشده در زمینه زمانبندی پروژه با نرخهای یادگیری و استهلاک و فعالیتهای تعمیرات و نگهداری ارائه شود. از آنجا که هر یک از کارهای انجامگرفته در مرجعی که به آن اشاره شده است ، به طور کامل توضیح داده شده است، در اینجا فقط در مورد هرکدام توضیحاتی کلی ارائه میگردد.2-2.مروری بر مسائل زمانبندیالگوهای زیادی در تعریف مسائل زمانبندی و طبقهبندی آنها مطرح هستند: مسائل زمانبندی از نظر فرایند تولید محصولات و بسته به تعداد عملیاتهای مورد نیاز برای پردازش یک کار و نیز تعداد ماشینهای موجود برای پردازش هر عملیات دارای الگوهای زیادی میباشند. در کل یک مسئله زمانبندی عمومی را میتوان با استفاده از سه نماد که توسط گراهام و همکارانش ]36[ ارائه شد توصیف نمود که بیانگر وضعیت و شرایط ماشین یا منبع است و معمولا دارای یک نماد است، خصوصیات و جزئیات نحوه پردازش و محدودیتهای موجود را بیان میکند و ممکن است شامل هیچ نمادی نباشد و یا چندین نماد باشد، بیانگر تابع هدف مسئله است و معمولا شامل تنها یک نماد است.جدول 2-1. محيطهاي کارگاهي (نماد α)سادهترين شکل و حالت خاص تمامي محيطهاي کارگاهي ممکن.تکماشينهm ماشين کاملا يکسان به موازات هم قرار ميگيرند؛ هرکدام از کارها نياز به يک عمليات دارد و بر روي يکي از ماشينهاي موجود پردازش ميشود.ماشينهاي موازي يکسانحالت کليتر ماشينهاي موازي يکسان؛ ماشينها داراي سرعت پردازش متفاوت هستند.ماشينهاي موازي يکنواختحالت کليتر ماشينهاي موازي يکنواخت؛ سرعت پردازش ماشينها هم به نوع ماشين و هم به نوع کار بستگي دارد.ماشينهاي موازي نامرتبطm ماشين به صورت متوالي وجود دارد؛ هر کدام از کارها بر روي تمامي ماشينها پردازش ميشوند، تمامي کارها مسير پردازش يکساني دارند.کارگاه جريانيحالت کليتر کارگاه جرياني؛ m ايستگاه پردازش به صورت متوالي وجود دارد؛ در هر ايستگاه يکي از حالات سهگانه ماشينهاي موازي براي پردازش يک کار رخ ميدهد.کارگاه جرياني منعطفهر کدام از کارها داراي مسير پردازش متمايز بر رويm ماشين موجود ميباشند.توليد کارگاهيحالت کليتر توليد کارگاهي؛ m مرکز پردازش وجود دارد؛در هر ايستگاه يکي از حالات سهگانه ماشينهاي موازي براي پردازش يک کار رخ ميدهد.توليد کارگاهي منعطفm ماشين وجود دارد؛ هر کدام از کارها بر روي هر کدام از ماشينها يک يا چند بار پردازش ميشود؛ محدوديتي براي مسير پردازش کارها وجود ندارد.کارگاه باز جدول 2-2. جزئيات و محدوديتهاي پردازش کارها (نماد β)کار نوع j نميتواند قبل از زمان آمادهسازي خود () پردازش خود را آغاز کند.زمان آمادهسازي غير صفر کارهاپردازش يک کار بر روي يک ماشين ميتواند قبل از زمان تکميل کار قطع شود و کار ديگري بر روي آن ماشين پردازش شود.شکست کارهاقبل از اينکه يک کار پردازش خود را آغاز کند يک يا چند کار ديگر بايد پردازش شود.اولويت پردازش کارهازمان نصب وابسته به توالي بين پردازش کار i و j بر روي ماشين k منظور ميشود.زمان نصب وابسته به توالي کارها , n کار موجود به f گروه کاري تعلق دارند. اعضاي هر گروه زمانهاي پردازش متفاوتي دارند ولي آنها ميتوانند به صورت متوالي بر روييک ماشين بدون زمان نصب پردازش شوند.گروههاي کارييک ماشين مي تواند دستهاي از کارها را به طور همزمان پردازش کند و زمانهاي پردازش يک دسته لزوما برابر نيست.پردازش دستهاييک ماشين ممکن است به طور مستمر در دسترس نباشد.خرابي ماشينمجموعه شامل ماشينهاي ميباشد که قادر به پردازش کار نوع j هستند.دسترسي محدود به ماشينهادر مسائل کارگاه جرياني، ترتيبي که کارها بر روي ماشين اول پردازش ميشوند، در کل سيستم حفظ ميشود.جايگشتدر مسائل کارگاه جرياني با بافر محدود، هنگاميکه ظرفيت بافر کامل ميشود، کار تکميل شده بر روي ماشين بالادست باقي ميماند و از پردازش کار بعدي بر روي آن ممانعت ميشود.بلوکه شدندر مسائل کارگاه جرياني، کارها نميتوانند بين دو ماشين متوالي در حالت انتظار قرار گيرند.بدون انتظاردر مسائل توليد کارگاهي يک کار ميتواند در يک مرکز کاري بيشتر از يک بار پردازش شود.گردش مجدد جدول 2-3. تابع هدف مسئله (نمادγ)زمان تکميل آخرين کاري که سيستم را ترک ميکند.زمان تکميل بيشينهبيشترين انحراف زماني از موعدهاي تحويل کارها را نشان ميدهد.زمان تاخير بيشينهمجموع زمانهاي تکميل کارها را اندازهگيري ميکند.زمان تکميل کلمجموع انحرافهاي زماني کارها از موعدهاي تحويل را محاسبه ميکند.زمان ديرکرد کلتعداد کارهاي داراي ديرکرد زماني را محاسبه ميکند.تعداد کارهاي با تاخير کلمجموع زمانهاي زودکرد و ديرکرد کارها را محاسبه ميکند.زمانهاي زودکرد و ديرکرد کلمجموع زمانهاي تکميل وزني کارها را اندازهگيري ميکند.زمان تکميلوزني کلمجموع انحرافهاي زماني وزني کارها از موعدهاي تحويل را محاسبه ميکند.زمان ديرکرد وزني کلتعداد وزني کارهاي داراي ديرکرد زماني را نشان ميدهد.تعداد کارهاي با تاخير وزني کلمجموع زمانهاي زودکرد و ديرکرد وزني کارها را محاسبه ميکند.زمانهاي زودکرد و ديرکرد وزني کل 2-2-1. تک ماشینه[4]سادهترین حالت ممکن است که معمولا حالت خاص سایر مسائل در نظر گرفته میشود. در این حالت فقط یک ماشین در دسترس بوده و این ماشین قادر به پردازش تنها یک کار در هر لحظه میباشد. این مدل مبنا اساس کار برای ایجاد قوانین و قواعد زمانبندی برای استفاده در سایر مدلها میباشد به عبارت دیگر عموما روشها و راهکارها ابتدا برای یک مدل تک ماشینه تبدیل میگردد و سپس برای سایر مدلها بسط داده میشوند.2-2-2. ماشینهای موازی[5]در این سیستم تعدادی ماشین مشابه ( از لحاظ فرایند مربوطه ) در دسترس هستند و هر کار میتواند روی هر یک از ماشینها پردازش شود. این سیستم، از لحاظ ویژگیهای ماشین از قبیل سرعت پردازش، کیفیت محصولات تولیدی و هزینه تولید به دسته ماشینهای موازی یکسان[6] و ماشینهای موازی متفاوت[7] تقسیم میشوند.2-3. اثر یادگیری در زمانبندی:اثریادگیری اولین بار توسط رایت[5] مطرح شد و در آن مطالعه روی صنعت هواپیما، نشان داد که هزینههای کارگری هر واحد با افزایش نرخ تولید کاهش پیدا می کند. مطالعاتی که بر روی یادگیری و اثر آن بر رفتار موجودات زنده انجام شده نشان داد که زمان مورد نیاز برای انجام یک کار با افزایش تجربه آن کاهش می یابد. این مطالعه روانشناسی منجر به ایجاد پدیده جدید به نام اثریادگیری شد. اثر یادگیری در دورههای برنامه ریزی تولید کوتاهمدت از اهمیت به سزایی برخوردار است. کیچیه و فونتانا[6] اولین کسانی بودند که درهنگام محاسبه مقدار بهینه اندازه انباشته، اثر یادگیری را لحاظ کردند. در این حالت موجودی زودتر از زمانی که یادگیری لحاظ نشده به پایان میرسد. با درنظرگرفتن یک نرخ ثابت تقاضا این امر منجر به هزینههای نگهداری بالاتر و همچنین کاهش میزان اندازه انباشته بهینه میشود. اگرچه برنامه ریزی تولید یکی از وظایف اصلی در برنامهریزی تولید کوتاهمدت است اما اثر یادگیری در ادبیات زمانبندی اولین بار توسط بیسکاپ[7] مطرح شد. وی در تحقیقش اثر یادگیری را در مسئله زمانبندی تکماشینه کمینهسازی زمان تکمیل و مجموع وزنی انحرافات زمان تکمیل از موعد تحویل مورد بررسی قرار داد.