به نام یزدان پاک
تقدیم به
مادر و پدر عزیزم
به پاس محبتهای بی دریغشان
سپاسگذاری
با سپاس و تشکر فراوان از اساتید ارجمندم
آقایان دکتر توکلیمقدم و دکتر مهدوی امیری
بهخاطر زحمتها و راهنماییهای گرانقدرشان
و با سپاس از تمامی دوستانم
که در تمام مراحل این پژوهش با همفکری و
کمکهای دلسوزانه خود، مرا یاری نمودند.
چکیده
در دنیای رقابتی امروز برای بقا باید با زمان حرکت کرد. برای این منظور باید کلیه فعالیتها برای رسیدن بهموقع به هدف نهایی زمانبندی و ترتیبدهی شوند. توالی عملیات، نقش بسیار مهمی در مسائل امروزی شرکتها دارد. بنابراین بررسی توالی عملیات در محیطهای مختلف و با معیارهای مختلف یک گام مثبت جهت حفظ بقا میباشد. در این پایاننامه، یک مدل ریاضی جدید برای حل مسأله زمانبندی پویا ماشینهای موازی یکنواخت با اهداف میانگین وزنی زمان تکمیل کارها و مجموع جریمههای زودکرد و دیرکرد معرفی گردیده است. کارها به مرور زمان وارد میشوند و به دلیل اهمیت زمانهای آمادهسازی وابسته به توالی در بحث ماشینهای موازی، این محدودیت نیز در مدل مذکور در نظر گرفته شده است.
با توجه به وجود تضاد بین دو تابع هدف مذکور، استفاده از روشهای کلاسیک بهینهسازی جهت دستیابی به جوابهای بهینه، سراسری یا موضعی امری غیرممکن بوده و بنابراین برای حل مسأله، از روشی موسوم به بهینهسازی چندمعیاره استفاده میگردد. با توجه به پیچیدگی محاسباتی مسأله فوق، الگوریتم فراابتکاری تکاملی دیفرانسیلی (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-II26
2-6-2- مروری بر الگوریتم فراابتکاری تکاملی DE28
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- ساختار کلی الگوريتم تکاملی DE45
3-10-2- ساختار پيشنهادی الگوريتم DE48
3-10-2-1- ساختار كلي روش پيشنهادي DE48
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-II55
3-10-3-1- روش سریع مرتبسازی جوابهای مغلوب NSGA-II56
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- مدل ریاضی ارائه شده در نرمافزار GAMS84
پ 2- کد نوشته شده در محیط Matlab برای دو روش حل DE و NSGA-II و روشهای مقایسه آنها88
چکیده لاتین106
فهرست جداول:
عنوانشماره صفحهشماره صفحه
جدول 4-1- مفروضات اصلی کد نوشته شده در محیط GAMS62
جدول 4-2- اعداد توابع هدف64
جدول 4-3- پارامترهای تعیین شده برای روشهای حل67
جدول 4-4- نتایج مقایسهای دو الگوریتم DE و NSGA-II70
جدول 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- ساختار کلی VNS55
شکل 3-5- میزان مغلوبیت جوابها56
شکل 3-6- برتری جوابها در سطح اول57
شکل 3-7- برتری جواب با فاصله ازدحام بیشتر57
شکل 3-8- محاسبه فاصله ازدحام برای جواب i58
شکل 3-9- NSGA-II و عملگر مسابقهای دودویی58
شکل 3-10- ساختار کلی الگوریتم NSGA-II59
شکل 4-1- جواب حل مدل مورد نظر در محیط GAMS63
شکل 4-2- جبهه پارتو برای 50 جواب مختلف65
شکل 4-3- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل DE66
شکل 4-4- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل NSGA-II67
شکل 4-5- نمودار مقایسهای شاخص کیفیت برای دو الگوریتم DE و NSGA-II71
شکل 4-6- نمودار مقایسهای شاخص فاصلهگذاری برای دو الگوریتم DE و NSGA-II71
شکل 4-7- نمودار مقایسهای شاخص پراکندگی برای دو الگوریتم DE و NSGA-II72
شکل 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-3- نظریه زمانبندی
نظريه زمانبندي اصولاً با مدلهاي رياضي سر و كار دارد و بين كار زمانبندي و مدلهاي زمانبندي رابطه برقرار ميكند و بهطور پيوسته مدلها را با مسائل نظري و عملي زمانبندي محك ميزند. ديدگاه نظري به طور غالب رويكردي كمي است و سعي آن دست يافتن به ساختار مسأله در قالب شكل فشرده رياضي است. اين رويكرد كمي با تفسير اهداف تصميمگيري در قالب يك تابع هدف صريح و بيان موانع تصميمگيري به صورت محدوديتهاي صريح شروع ميشود [4]. حل هر مسأله زمانبندي برابر با پاسخگويي به اين دو سوال است:
1- كدام منبع براي انجام هر وظيفه تخصيص داده خواهد شد؟
2- هر وظيفه در چه وقت انجام خواهد شد؟
به عبارت ديگر، وظيفهي اصلي مسائل زمانبندي به تصميمگيري در مورد تخصيص منابع و توالي عمليات منحصر ميشود [4].
نظريه زمانبندي شامل شيوههاي متنوع و مختلفي است كه در حل مسائل زمانبندي مفيد واقع ميشود. در واقع حوزه زمانبندي به صورت نقطه كانوني ايجاد، به كارگيري و ارزيابي روشهاي تركيبي، شيوههاي شبيهسازي، روشهاي شبكهاي و رويكردهاي ابتكاري حل مسائل در آمده است .
انتخاب شيوه مناسب به پيچيدگي مسأله، طبيعت مدل، انتخاب معيار كارايي و عوامل ديگر بستگي دارد [4]. در عمل، زمانبنديها با استفاده از الگوريتم زمانبندي مبتني بر دانش ايجاد ميشوند. الگوريتمهاي زمانبندي، زمانبنديهايي را توسعه ميدهد كه يك معيار اندازهگيري را بهينه ميكند.
1-4- زمانبندي در كسب و كار
واحد زمانبندي در سازماني خدماتي يا سازماني توليدي بايد با بسياري از واحدهاي ديگر تعامل داشته باشد. اين تعاملات وابسته به سيستم هستند و به طور قابل ملاحظهاي از موقعيتي به موقعيت ديگر متفاوت ميباشند. اين تعاملات اغلب از طريق شبكه كامپيوتري در نظر گرفته ميشوند. با اين وجود، تعاملات ميان زمانبندي و ديگر واحدهاي تصميمگيري ميتواند از طريق جلسات و از طريق يادداشتها در نظر گرفته شود.
1-4-1- زمانبندي در توليد
سفارشاتي كه به جايگاه توليد رسيدهاند بايد به كارهايي با موعد تحويل مربوطه تبديل شوند. اين كارها اغلب بايد بر روي ماشينها در يك مركز كاري در توالي و ترتيبي از پيش فرض شده پردازش شوند. پردازش كارها با تأخير مواجه خواهد شد هنگاميكه ماشينهاي خاصي مشغول به كار باشند. اگر كارهايي با اولويت بالا آماده پردازش در سيستم باشند و ماشين خاصي مشغول به كار باشد، با توجه به اين نكته كه كارها با اولويت بالا بايد بلافاصله پردازش شوند، بريدگي در سيستم رخ خواهد داد. رويدادهاي غير قابل پيشبيني در كارگاه مانند خرابي ماشين و زمانهاي بيش از انتظار طولاني شده نيز بايد مورد توجه قرار گيرند به اين سبب كه ميتوانند تأثير بسزايي بر روي زمانبندي داشته باشند. ايجاد زمانبندي دقيق كارهايي كه قرار است پردازش شوند منجر به حفظ كارايي و كنترل عمليات ميشود.
كارگاه تنها قسمت تأثيرگذار بر روي فرآيند زمانبندي نميباشد. در واقع، فرآيند زمانبندی تحت تأثير فرآيند برنامهريزي توليد قرار دارد كه برنامهريزي ميان مدت تا بلند مدت را براي كل سازمان بر عهده دارد. هدف فرآيند برنامهريزي توليد، بهينه كردن تركيب محصول كلي شركت، تخصيص بلند مدت منابع بر اساس سطوح موجودي و پيشبيني تقاضا و نيازمنديهاي منابع است. تصميمات گرفته شده در سطوح بالاي برنامهريزي به طور مستقيم بر فرآيند زمانبندي مؤثر ميباشد.
در توليد، واحد زمانبندي بايد با ديگر واحدهاي تصميمگيري در سازمان تعامل داشته باشد .يكي از سيستمهاي شناخته شده كه بسيار مورد استفاده است، سيستم برنامهريزي نيازمنديهاي مواد8 (MRP) ميباشد. بعد از مشخص شدن زمانبندي، تمام مواد خام و منابع بايد در زمانهاي مشخصي قابل دسترس باشند. زمان در دسترس بودن كارها بايد به طور پيوسته توسط برنامهريزي توليد، سيستم زمانبندي و سيستم برنامهريزي نيازمنديهاي مواد مشخص شود.
سيستم برنامهريزي نيازمنديهاي مواد به طور طبيعي نسبتاً پيچيده ميباشد. براي انجام هر كار ليستي از قطعات مورد نياز9 (BOM) مشخص ميشود. سيستم برنامهريزي نيازمنديهاي مواد موجودي هر قطعه را كنترل ميكند. علاوه بر اين سيستم، زمان خريد هر قطعه را مشخص ميسازد. بدين منظور سيستم برنامهريزي نيازمنديهاي مواد از روشهايي همچون اندازه انباشته و زمانبندي انباشته استفاده ميكند كه مشابه روشهاي مورد استفاده در زمانبندي ميباشند.
بستههاي تجاري MRP بسيار در دسترس هستند. بنابراين بسياري از سازمانهاي توليدي از اين سيستم استفاده ميكنند. اگر سيستم زمانبندي در سازمان توليدي وجود نداشته باشد، سيستم برنامهريزي نيازمنديهاي مواد ممكن است براي اهداف برنامهريزي توليد مورد استفاده قرار گيرد. با اين وجود در سطوح پيشرفته MRP براي انجام زمانبندي دقيق با مشكلاتي مواجه ميشود.
سازمانهاي پيشرفته معمولاً از سيستمهاي اطلاعاتي پيشرفته كه شامل يك كامپيوتر مركزي و پايگاه داده ميباشد، استفاده ميكنند. شبكههاي محلي كامپيوترهاي شخصي، ايستگاههاي كاري و ترمينالهاي ورودي داده به كامپيوتر مركزي متصل شدهاند كه ميتوانند براي بازيابي اطلاعات يا براي ورود دادههاي جديد مورد استفاده قرار گيرند. ترمينالها در مكانهاي مهم به كامپيوتر زمانبندي متصل ميشوند و بدين وسيله امكان دسترسي دپارتمانها را به اطلاعات زمانبندي جاري فراهم ميكند. در نتيجه، اين دپارتمانها سيستم زمانبندي را با اطلاعات مناسب مانند تغييرات در وضعيت ماشين و كار تجهيز ميكنند.
1-4-2- زمانبندي در خدمات
تعريف سيستم زمانبندي خدماتي به معناي عام كار مشكلي است. واحد زمانبندي در يك سازمان خدماتي با مشكلات متنوعي مانند تخصيص منابع (كاميونها، اتاقهاي جلسه يا ديگر تجهيزات) يا زمانبندي نيروي كار (تخصيص نوبت كاري) مواجه ميشود. الگوريتمهاي مورد استفاده در محيطهاي خدماتي كاملاً متفاوت با الگوريتمهاي مورد استفاده در محيطهاي توليدي ميباشند. در حاليكه زمانبندي در هر دو محيط بايد با ديگر واحدهاي تصميمگيري هماهنگ باشد. اين هماهنگي معمولاً در داخل سيستمهاي اطلاعاتي پيچيده و مفصل حاصل ميشود. سيستم اطلاعاتي در محيط خدماتي معمولاً متكي بر پايگاه داده وسيعي است كه شامل اطلاعات مرتبط با در دسترس بودن منابع و مشتريان بالقوه ميباشد. در چنين محيطي، سيستم زمانبندي با ماژولهاي پيشبيني و مديريت تعامل دارد.
1-5- مروری بر مدلها
سيستمهاي توليدي و خدماتي با معيارهاي بسياري مانند تعداد ماشينها، سطح اتوماسيون، ويژگيهاي مربوط به ساختار مورد نظر، نوع سيستم حمل و نقل و غيره مشخص شدهاند. تفاوت در همه اين معيارها تعداد بسيار زيادي از مدلهاي زمانبندي را سبب ميشود.
منابع براي مثال اتاق هتل، ماشين، اسكله، خط هوايي و غيره بهطور كلي به ماشين اشاره دارند. موجوديتي كه بايد بر روي ماشين پردازش شود به عنوان كار در نظر گرفته ميشود. كار به عمليات خاص يا مجموعهاي از عمليات در فرآيند توليدي اشاره دارد. پارامترهايي كه در زير بيان ميشوند در طول اين فصل مورد استفاده قرار خواهند گرفت.
مدلهاي زمانبندي معمولا از طريق تركيب ماشينها، محدوديتها و توابع هدف مشخص ميشوند.
دو راه برای مشخص نمودن یک برنامه زمانبندی وجود دارد. راه ابتدایی توسط کنوی ارائه شد و روش دوم که بیشتر مورد استفاده است، توسط گراهام و همکارانش در سال 1979 توسعه داده شده است که با سه تایی مرتب α|β|γ توصیف میگردد.
محیط ماشین (α)
محیط ماشین و تعریفی که از نظم و سازماندهی ماشینها در نظر داریم را نشان میدهد. پنج محیط متعارف ماشین، به شرح زیر است.
تک ماشین: در این محیط فقط یک ماشین برای زمانبندی کارهای داده شده تحت محدودیتهای مشخص شده، وجود دارد که در واقع سادهترین محیط ممکن است. سيستمهاي توليدي بسياري به سيستمهاي توليدي تك ماشين منجر ميشوند. براي مثال، اگر در محيطي كه شامل چندين ماشين ميباشد گلوگاهي رخ دهد، آنگاه توالي كارها در گلوگاه به طور كلي بيان كننده عملكرد كل سيستم خواهد بود. در اين حالت تمامي عمليات پس از زمانبندي گلوگاه زمانبندي خواهند شد. چنين رويكردي دلالت بر در نظر گرفتن مسأله اصلي به صورت مسأله تك ماشين دارد. مدلهاي تك ماشين همچنين در رويكردهاي تجزيه كاربرد دارند. در چنين سيستمي، مسائل زمانبندي در محيطهاي پيچيده به چندين مسأله زمانبندي تك ماشين تبديل ميشوند. مدلهاي تك ماشين با محدوديتها و توابع هدف مختلفي در نظر گرفته شدهاند. نتايج به دست آمده منجر به ايجاد مجموعهاي از قواعد گرديده است كه نتيجه آنها ايجاد جواب بهينه در محيطهاي تك ماشين ميباشد. براي مثال، قانون زودترين موعد تحويل10 (EDD) كه كارها را به ترتيب صعودي موعد تحويل زمانبندي ميكند، منجر به حداقل شدن حداكثر ديركرد در ميان تمام كارها ميشود. قانون كمترين زمان پردازش11 (SPT) كه كارها را به ترتيب صعودي زمان پردازش زمانبندي ميكند منجر به حداقل شدن تعداد كارهاي منتظر براي پردازش ميشود.
مدلهاي ماشينهاي موازي: ماشينهاي موازي تعميمي از مدل تك ماشين ميباشد. بسياري از محيطهاي توليدي از چندين مرحله يا مركز كاري تشكيل شدهاند در حاليكه هر يك از آنها داراي چندين ماشين به صورت موازي ميباشند. ماشينهاي موجود در يك مركز كاري ميتوانند يكسان باشند. در اين حالت هر زماني كه كار وارد سيستم شود امكان پردازش آن بر روي هر يك از ماشينهاي در دسترس فراهم خواهد بود. همچنين، مدلهاي ماشينهاي موازي مانند مدلهاي تك ماشين از اين جهت داراي اهميت ميباشند كه اگر در سيستمهاي توليد چند مرحلهاي يك مركز كاري خاص به صورت گلوگاه عمل كند، آنگاه زمانبندي در مركز كاري مورد نظر تعيين كننده عملكرد كل سيستم خواهد بود. در اين صورت گلوگاه ميتواند به صورت مجموعهاي از ماشينهاي موازي مدل شود و به تنهايي مورد تحليل قرار گيرد. در بعضي از موارد ماشينهاي موازي ممكن است يكسان نباشند. در واقع در اين حالت برخي از ماشينها قديميتر از بقيه هستند و با سرعت پايينتري عمل ميكنند يا ممكن است ماشيني بهتر نگهداري شده باشد و بتواند كار را با كيفيت بالاتري انجام دهد. در اين صورت برخي از كارها ممكن است بر روي هر يك از m ماشين موازي پردازش شوند در حاليكه بقيه ممكن است تنها بر روي مجموعه خاصي از m ماشین پردازش شوند. زماني كه ماشينها انسان باشند، آنگاه زمان پردازش يك عمليات به نوع كار و به اپراتور نيز بستگي خواهد داشت. اپراتوري ممكن است در كار خاصي مهارت داشته باشد در حاليكه اپراتور ديگري ممكن است كار ديگري را به خوبي انجام دهد.
جریان کارگاهی12 (Fm): در بسياري از محيطهاي توليدي يا مونتاژ، كارها داراي چندين عمليات ميباشند كه معمولاً بايد بر روي چندين ماشين مختلف پردازش شود. اگر مسير همه كارها يكسان باشد، يعني همه كارها ماشينهاي يكساني را در ترتيب يكساني بازديد كنند چنين محيطي به عنوان محيط جريان كارگاهي در نظر گرفته ميشود. در واقع ماشینها در چنین محیطی به صورت سری چیده میشوند و هنگاميكه كاري زمان پردازشش بر روي ماشين خاصي تكميل ميشود، وارد صف ماشين بعدي ميشود. ترتيب كارها از ماشيني به ماشين ديگر ممكن است متفاوت باشد به ا ين سبب كه كارها ما بين ماشينها ممكن است دوباره مرتب شوند. با اين وجود، اگر سيستم حمل و نقل مواد، كارها را از يك ماشين به ماشين بعدي منتقل كند، در اين صورت توالي يكساني از كارها در كل سيستم برقرار خواهد بود. در برخي از سيستمهاي جريان كارگاهي، هنگاميكه كاري به پردازش بر روي ماشين خاصي نياز نداشته باشد، كار از ماشين مورد نظر ميگذرد و جلوتر از كارهايي كه پردازش شدهاند يا منتظر پردازش در آن مرحله هستند، قرار ميگيرد. تعميمي از مدل جريان كارگاهي، مدل جريان كارگاهي انعطاف پذير ميباشد كه از چندين مرحله به صورت سري تشكيل شده است كه در هر مرحله داراي تعدادي ماشين به صورت موازي وجود دارند. كارها در هر مرحله بر روي يكي از ماشينهاي موازي پردازش ميشوند. ظرفیت انبار بین ماشینهای متوالی ممکن است برای اهداف عملی نامحدود باشد، که این موضوع اغلب برای محصولاتی که از نظر فیزیکی کوچک هستند صادق است، بنابراین انبار نمودن مقادیر زیادی از این محصولات بین دو ماشین امری ممکن میباشد.
کار کارگاهی13 (Jm): این حالت، مانند حالت قبل است با این تفاوت که نیازی به وجود مسیر یکسانی برای همه کارها نیست. به عبارت دیگر هر کار دارای مسیر مخصوصی بین ماشینها است. به این محیط در نظریه زمانبندی بیشترین توجه شده است و بیشترین پیشرفتها در این محیط صورت گرفته است. در كارگاههاي چند عملياتي، كارها اغلب داراي مسيرهاي مختلفي هستند. در حقيقت مدل جريان كارگاهي مدل كار كارگاهي است كه در آن هر كار مسير يكساني دارد. سادهترين مدل كار كارگاهي فرض ميكند كه هر كار حداكثر يكبار بر روي ماشين خاص پردازش ميشود. در حاليكه در مدلهايي ممكن است كه يك كار چند بار در مسيرش در طول سيستم بر روي ماشيني خاص پردازش شود. چنين محيطهايي مقدس به گردش كاري مجدد هستند كه به طور قابل ملاحظهاي پيچيدگي مدل را افزايش ميدهد. تعميمي از مدل كار كارگاهي، مدل كار كارگاهي انعطاف پذير14 است كه داراي چندين ماشين به صورت موازي ميباشد. اگر در این مسائل یک کار روی ماشین خاصی بیش از یکبار برود، آن کار را دارای جریان مجدد میگویند و این حالت یک پدیده کاملا عمومی در دنیای واقعی است. به عنوان مثال، در تولید نیمه رسانا، کارها در اکثر اوقات دارای جریان مجدد است.
کارگاه باز15 (Om): در این محیط هیچگونه محدودیتی از نظر مسیر کارها در بین ماشینها وجود ندارد، به این معنی که کارهای یکسان ممکن است دارای مسیرهای متفاوتی باشند. در این محیط m ماشین وجود دارد و هریک از کارها میتواند روی هریک از m ماشین مجدداً فرایند شود، علاوه بر این ممکن است بعضی از زمان فرایندها صفر باشد. در مدل زمانبندی فوق، انعطاف زیادی جهت زمانبندی و تعیین توالی عملیات بهینه وجود دارد، ولی بدست آوردن توالی بهینه در این مدل دشوار است. هدف در مدل مذکور معمولاً حداقل کردن کل زمان تمکیل میباشد.
کارگاه مرکب16 (X): در این محیط، یک زیر مجموعهای از کارها وجود دارد که برای آن مسیر فرآیند ثابتی مشخص شده است و همزمان، بقیه کارها برای کمینه کردن تابع هدف برنامهریزی میشوند.
1-6 – فرضیات عمومی و ارائه یک مدل کلی
مسأله مورد بررسی در این تحقیق، مسأله زمانبندی ماشینهای موازی چندهدفه میباشد. یک مسأله زمانبندی شامل تعدادی کار میباشد که هر کدام زمان پردازش خاصی دارند.
فرضیات عمومی برای مسائل زمانبندی ماشینهای موازی یکنواخت به شرح زیر است:
در هر زمان فقط یک کار بر روی یک ماشین پردازش میشود.
همه کارها باید بهطور کامل پردازش شوند.
m ماشین موازی یکنواخت با سرعتهای مختلف در زمان صفر در دسترس میباشند.
هیچ ماشینی نمیتواند در یک زمان بیش از یک کار را پردازش کند.
پارامترهای مسأله از جمله زمان پردازش و موعد تحویل کارها در ابتدای کار معین بوده و ثابت میباشند.
ماشینها ممکن است زمان بیکاری داشته باشند.
زمان آمادهسازی ماشینها به صورت وابسته به توالی17 در نظر گرفته شده است.
کارها در طول افق برنامهریزی به مرور زمان (بهصورت پویا18) وارد میشوند.
اندیسها و پارامترها ی مدل به شرح زیر است:
j: اندیس کار (j=1,2,…,n)
m: اندیس ماشین (m=1,2,…,m)
Cj: زمان تکمیل کار j
Wj: وزن مربوط به کار jام
Tj: مقدار دیرکرد کار jام
βj: جریمه دیرکرد کار jام
Ej: مقدار زودکرد کار jام
αj: جریمه زودکرد کار jام
dj: موعد تحویل کار jام
بهطور کلی میتوان مدل زیر را برای مسأله ماشینهای موازی با اهداف کمینهکردن میانگین وزنی زمان تکمیل کارها و مجموع جریمههای دیرکرد و زودکرد استفاده کرد:
〖Min 1/w〗⁡∑_(j=1)^n▒〖w_j c_j 〗 ,
〖Min 〗⁡∑_(j∈J)▒〖α_j E_j+β_j T_j 〗 ,
s.t.
constraints

محدودیتهای مسأله در فصل سوم به تفصیل شرح داده خواهد شد.
1-7- ضرورت انجام تحقیق
با توجه به اهمیت روز افزون مسائل ماشینهای موازی، در نظر گرفتن معیارهای مختلف مورد توجه محققان این علم میباشد. امروزه در اغلب کارخانجات تولیدی و تولیدی، تامین به موقع سفارش مشتری یا خدمترسانی بهموقع، حائز اهمیت است. هزینههای زودکرد و دیرکرد در این مورد نه تنها مشتری را متضرر میگرداند، بلکه به شرکت نیز هزینه وارد شده و علاوه بر آن اعتبار خود را نیز از دست میدهد. حداقل کردن زمان تکمیل19 و جریمههای حاصل از دیرکرد سبب حداکثر شدن بهرهوری و کارایی سیستم تولیدی یا خدماتی میشود. همچنین حداقل کردن جریمههای زودکرد، باعث حداقل شدن هزینههایی از قبیل هزینه موجودی خواهد شد. لذا در این پایاننامه، مسأله زمانبندی ماشینهای موازی با استفاده از روش بهینهسازی چندمعیاره حل گردیده است.
در بسياري از مسائل زمانبندي فرض ميشود كه همه كارها به طور همزمان براي اجرا در دسترس باشند. اما در موارد متعددي ممكن است ورود كارها غيرهمزمان باشد. در حالتيكه با زمانهاي دسترسي مختلف سر و كار داريم، مجموعه كارهايي كه بايد زمانبندي شود با گذشت زمان تغيير ميكند که باعث تبدیل شدن محیط زمانبندی به یک محیط پویا میشود. در این پایاننامه، زمانهای دسترسی20 کارها بهصورت پویا در نظر گرفته شده است و کارها به مرور زمان وارد سیستم میشوند. همچنین در مسأله فوق، به دلیل اهمیت زمانهای آمادهسازی وابسته به توالی در بسیاری از صنایع، فرض وابسته بودن زمان آمادهسازی به توالی لحاظ شده است و سپس یک مدل ترکیبی بهینهسازی برای حل این مسأله ایجاد شده است.
1-8- هدف از تحقیق
با توجه به اهمیت سیستمهای تولید به موقع و نقش آن در شرکتهای تولید و خدماتی، توجه به دو معیار زودکرد و دیرکرد با در نظر گرفتن هزینههایی که به دنبال آن منجر میشود، ضروری به نظر میرسد. از طرفی در سیستمهای تولیدی امروزی، همواره بالا بردن بهرهوری و کارایی سیستم، بسیار مورد توجه مدیران سیستمها و محققان بوده است. به همین دلیل در مسائل زمانبندی، معیار زمان تکیمل کارها، از اهمیت بالایی برخوردار است چون حداقل شدن این معیار سبب بالا رفتن بهرهوری سیستم خواهد شد. در سیستمهای تولیدی واقعی، کارها دارای مشخصه اولویت برای تکمیل و آماده شدن میباشند. بنابراین بررسی معیار میانگین وزنی زمان تکمیل کارها بسیار موثر میباشد.
در این تحقیق، مسأله زمانبندی ماشینهای موازی با هدف تعیین توالی تولید بهینه با توجه به معیارهای میانگین وزنی زمان تکمیل و مجموع هزینههای زودکرد و دیرکرد مطرح شده است. به دلیل اهمیت زمان آمادهسازی در بسیاری از سیستمهای تولیدی امروزی، محدودیت زمان آمادهسازی وابسته به توالی نیز برای کارها در نظر گرفته شده است. همچنین برای نزدیکتر شدن به محیط تولید در دنیای واقعی، زمانهای دسترسی کارها بهصورت پویا در نظر گرفته شده است.
از آنجا كه مسألهي مورد بررسي جز مسائل پيچيدهي تركيباتي و از كلاس NP-Hardمیباشد، كارايي روش حل دقيق براي اندازههاي بزرگ مسأله كاهش مييابد. بنابراين با استفاده از الگوريتم تکامل دیفرانسیلی21 (DE) به ارايه جواب براي مسائل با اندازههاي بزرگ ميپردازيم.
با توجه به مرور ادبیات انجام شده در حیطه مسائل زمانبندی ماشینهای موازی یکنواخت با درنظر گرفتن زمانهای آمادهسازی وابسته به توالی و زمانهای دسترسی پویا بهطور همزمان، میتوان به این نتیجه رسید که در این محیط، هیچ تحقیقی وجود ندارد که توابع مسأله را بهصورت چندهدفه درنظر گرفته باشد و روش حل آن الگوریتم فراابتکاری باشد. در نتیجه نوآوری این تحقیق، مدل درنظر گرفته شده و روش حل آن، الگوریتم فراابتکاری تکامل دیفرانسیلی میباشد.
1-9- جمعبندی
در اين فصل، به معرفي كار و نظريه زمانبندي و نحوه تعامل آن با برنامهريزي پرداختيم. با توجه به اين كه مدلهاي زمانبندي معمولاً براساس تركيب ماشينها، نوع محدوديتها و معيارهاي در نظر گرفته شده مشخص ميشوند، انواع متداولي از موارد بالا مورد بررسي قرار گرفت. ضرورت انجام این پژوهش و هدف از انجام آن نیز بیان گردید. ساختار ادامهي اين پژوهش بدين شكل ميباشد. در فصل دو، ادبيات موضوع و پیشینهی تحقیق، مورد مطالعه قرار گرفته است. در بخش سه، مدل رياضي ارائه شده براي مسأله معرفي و پارمترهای مسأله شرح داده شده است. در فصل چهار الگوريتم تکامل دیفرانسیلی توسعه داده شده براي اين مسأله و الگوریتم NSGA-II معرفي میشود. نتايج عددي حل مسايل و مقايسه عملكرد دو روش DEو NSGA-II نيز در انتهاي اين بخش آورده شده است. در بخش پاياني، جمعبندي و پيشنهادها براي كار آيندگان آورده شده است. همچنين در پيوست پژوهش، کد مدل رياضي ارايه شده در محيط نرمافزار GAMS و کد الگوریتمهای فررابتکاری در محیط Matlab آورده شده است.
فصل دوم
ادبیات و پیشینه تحقیق
2-1- مقدمه
با توجه به اینكه در اين پاياننامه برآنيم تا مسأله ماشينهاي موازي را با در نظر گرفتن شرایط محیط پویا و زمانهای آمادهسازی وابسته به توالی، مورد بررسي قرار دهيم، در ادامه مروري بر ادبيات موضوع مطرح در زمينههايي كه در اين پايان نامه بهطور مستقيم يا غير مستقيم مورد توجه قرار گرفتهاند، خواهيم پرداخت. در ابتدا مسأله ماشينهاي موازي را در سه بخش محدوديتها، توابع هدف و روش حل مورد بررسي قرار ميدهيم. سپس، مسائل چندهدفه با تمركز بر روي الگوريتم تکاملی DE و NSGA-II مورد بررسي قرار ميگيرد.
2-2- مروری بر محدودیتها در محیط ماشینهای موازی
در صنایع، یک عملیات گلوگاهی معمولاً بر روی ماشینهای موازی پردازش میشود [5]. با در نظر گرفتن این موضوع که با افزایش تعداد مناسب ماشینها، انعطافپذیری یک سیستم تولیدی میتواند افزایش پیدا کند [6]، ماشینهای موازی در بسیاری از سیستمهای تولیدی قابل استفاده و کاربردی میشود. هرچند مسائل زمانبندی ماشینهای موازی22 (PMSP)، از جمله دسته مسائل سخت و مشکل زمانبندی است، به دلیل اینکه اکثر مسائل PMSP، NP-Hard هستند [7].
مسائل PMSP را در حال حاضر میتوان به سه دسته ماشینهای موازی یکسان، ماشینهای موازی یکنواخت و ماشینهای موازی نامرتبط تقسیمبندی کرد مرور ادبیات کامل و دقیقتر را میتوانید در مقاله گراهام و همکاران [8] پیدا کنید. از آنجایی که مشکل اصلی به دست آوردن جواب بهینه (و نزدیک بهینه) ریشه در وجود زمانهای آمادهسازی وابسته به توالی بین کارها دارد [9]، در اکثر الگوریتمهایی که برای مسأله PMSP وجود دارد، محدودیت SDST و زمانهای دسترسی کارها به صورت پویا در نظر گرفته نشده است [10].
در زیر به بررسی و مروری بر ادبیات دو محدودیت زمانهای آمادهسازی وابسته به توالی و محیط پویا در محیط ماشینهای موازی که در این پایاننامه در نظر گرفته شده است، پرداخته میشود.
2-2-1- زمانهای آمادهسازی وابسته به توالی
در برنامهريزي سيستمهاي توليدي، به طور كلي زمان آمادهسازي شامل كار جهت آماده كردن ماشين و يا تعيين موقعيت كارها در مرحله پردازش مواد اوليه ميباشد. مسائل توليدي كه بهطور صريح ملاحظات زمانبندي را در نظر ميگيرند به دو گروه عمده تقسيمبندي ميشوند: در گروه اول زمانها و يا هزينههاي آمادهسازي تنها وابسته به كاري هستند كه قرار است بر روي ماشين پردازش شود. چنين مسائلي با عنوان زمانهاي آمادهسازي مستقل از توالي در ادبيات موضوع شناخته ميشوند. در گروه دوم زمانها يا هزينههاي آمادهسازي نه تنها وابسته به كاري هستند كه قرار است پردازش شود، بلكه وابسته به كاري كه پردازش آن اخيراً تمام شده است نيز هستند. چنين مسائلي با عنوان زمانهاي آمادهسازي وابسته به توالي شناخته ميشوند.
مسائل زمانبندي كه نيازمند در نظر گرفتن زمانهاي آمادهسازي به طور واضح ميباشند در بسياري از محيطهاي كارگاهي يافت ميشوند. بررسي كاملي بر روي زمانبنديها شامل زمان آمادهسازي توسط اللهوردی و همکاران [11] انجام شده است. اواکیک و اوزسی [12] مسأله زمانبندي پوياي ماشينهاي موازي را با در نظر گرفتن زمانهاي آمادهسازي وابسته به توالي در نظر گرفتند. مجموعهاي از الگوريتمهاي افق غلتان23 براي انتخاب جواب بهينه توسط آنها پيشنهاد شده است. روچا و همکاران [13] مسأله زمانبندي ماشينهاي موازي نامرتبط را با در نظر گرفتن زمانهاي آمادهسازي وابسته به توالي و ماشين مورد بررسي قرار دادند. اين مسأله در ادبيات مسائل زمانبندي به صورت R | Sijm |Cmax +ΣwiTi نشان داده ميشود. آنها دو مدل مجزاي برنامهريزي آميخته عدد صحيح پيشنهاد كردند. مدل اول بر اساس مدل من24 در محيط كار كارگاهي و مدل دوم بر اساس مدل وگنر25 در محيط كار كارگاهي توسعه يافته است. متغير تصميم بر اساس زمان آغاز پردازش كار تعريف شده است. علاوه بر اين، الگوريتم شاخه و كران براي يافتن جواب بهينه ارائه شده است. الگوريتم شاخه و كران داراي سه جز اصلي ميباشد: يافتن جواب اوليه به عنوان حد بالا، توسعه دادن قواعدي بر مبناي خواص مسأله و طراحي رويكردي به منظور محاسبه حد پايين. الگوريتم شاخه و كران ارائه شده توسط روچا و همكاران داراي دو بخش طراحي رويكردهايي براي محاسبه حد پايين و بالا ميباشد. در الگوريتم ارائه شده جواب حاصله از روش ابتكاري GRASP 26 به عنوان حد بالا مورد استفاده قرار گرفته است. الگوريتم در دو فاز طراحي شده است. در فاز اول، كارها به ماشينها تخصيص يافتهاند، اما هيچ توالي مشخص نشده است. توالي كارها بر روي ماشينها در فاز دوم مشخص شده است. براي توابع هدف حداكثر زمان تكميل كارها و كل ديركرد وزني، حد پايينهاي جداگانه ارائه گرديده است. در پايان عملكرد الگوريتم شاخه و كران با دو رويكرد مدل برنامهريزي آميخته عدد صحيح مقايسه شده است.
توکلی مقدم و مهدیزاده [14] يك مدل برنامهريزي مختلط عدد صحيح خطي جديدي را براي مسأله زمانبندي ماشينهاي موازي يكسان با در نظر گرفتن زمانهاي آمادهسازي خانواده كارها بهمنظور حداقل نمودن كل زمان جريان ساخت پيشنهاد كردند. براي حل مسأله مورد نظر، یک الگوريتم فراابتكاري بر اساس الگوريتم ژنتيك براي دستيابي به جواب مناسب و نزديك بهينه، مخصوصاً براي مسائل با اندازه بزرگ، پيشنهاد شده است.
در بعضی از مقالات زمانهای آمادهسازی به صورت وابسته به توالی کارها و توالی ماشینها بررسی شده است. والادا و رویز [15] یک الگوریتم ژنتیک برای مسأله زمانبندی ماشینهای موازی نامرتبط که در آن زمان آمادهسازی وابسته به توالی کارها و ماشینها میباشد، ارائه شده است. الگوریتم ژنتیک ارائه شده شامل یک جستجوی محلی سریع میباشد. فلشزار و همکاران [16] مسأله NP-Hard زمانبندی کارها بر روی ماشینهای موازی نامرتبط با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی کارها و ماشینها بررسی شده است. در این مقاله، هدف کمینه کردن زمان تکمیل کارها میباشد. برای حل این مسأله از الگوریتم جستجوی همسایگی متغیر استفاده شده است.
2-2-2- محیط پویا
در محيط واقعي معمولاً شرايط پويا حاكم ميباشد؛ بدين معني كه تمام كارها به طور همزمان در زمان صفر در دسترس نميباشند. بیلج و همکاران [17]، مسأله زمانبندي ماشينهاي يكسان را كه در آن كارها در زمانهاي متفاوتي در طول افق برنامهريزي در دسترس هستند مورد بررسي قرار گرفته است. حداقل كردن كل ديركرد به عنوان تابع هدف در نظر گرفته شده است. سوبور و لاجندران [18] مسأله زمانبندي ماشينهاي موازي نامرتبط را مورد توجه قرار دادند. در مسأله در نظر گرفته شده، كارها داراي زمانهاي در دسترس بودن متفاوت و ماشينها داراي زمانهاي آماده به كار بودن متفاوت ميباشند. در مسأله مذكور، تمهيداتي براي مجموعهاي از كارها در



قیمت: تومان

دسته بندی : پایان نامه ارشد

دیدگاهتان را بنویسید