1-1- مقدمه

 

2 1-2- تعاریف زمان­بندی

 

3 1-2-1- نمادها

 

3 1-2-2- محیط ماشین­ها و نوع كارگاه

 

4 1-2-3- مشخصه­های كاری و محدودیت­های زمان­بندی

 

5 1-2-4- معیارهای بهینه­سازی

 

7 1-3- نظریهء زمان­بندی

 

9 1-4- برنامه ­ریزی ریاضی

 

9 1-5- زمان­بندی چند هدفه

 

9 1-6- الگوریتم­های فرا ابتكاری در بهینه­سازی

 

11 1-6-1- الگوریتم ژنتیك

 

11 1-6-2- الگوریتم شبیه­سازی تبرید

 

12 1-7- طراحی آزمایشات

 

12 1-8- مسألهء زمان­بندی كارگاه باز

 

13 2- فصل دوم: ادبیات

 

15 2-1- مقدمه

 

16 2-2- معیارهای اندازه ­گیری و تابع هدف

 

16 2-3- مجاز نبودن بریدگی كارها

 

18 2-4- نگهداری و تعمیرات دوره­ای و محدودیت عدم دسترسی ماشین­ها

 

18 2-5- زمان­های حمل و نقل

 

19 2-6- زمان­های آماده ­سازی و جداسازی

 

20 2-7- روش­های حل

 

20 2-8- طراحی آزمایشات

 

22 3- فصل سوم: طرح مسأله و ارائه روش­های حل

 

24 3-1- مقدمه

 

25 3-2- فرمول­بندی مسأله

 

25 3-2-1- فرض­های مسأله

 

25 3-2-2- نماد گذاری

 

26 3-2-2-1- اندیس­ها

 

26 3-2-2-2- پارامترها

 

26 3-2-2-3- متغیرهای تصمیم

 

26 3-2-3- مدل برنامه ­ریزی خطی مختلط

 

26 3-2-4- یک مثال

 

28 3-2-5- تحلیل مدل

 

29 3-3- الگوریتم­های فرا ابتكاری

 

30 3-3-1- الگوریتم ژنتیك

 

30 3-3-1-1- نمایش كروموزوم

 

30 3-3-1-2- جمعیت اولیه

 

30 3-3-1-3- تابع هدف

 

31 3-3-1-4- تابع برازندگی

 

31 3-3-1-5- انتخاب

 

31 3-3-1-6- تقاطع

 

31 3-3-1-7- جهش

 

33 3-3-1-8- معیار توقف

 

33 3-3-1-9- الگوریتم ژنتیک اولیه

 

33 3-3-1-10- الگوریتم ژنتیک موازی چند هدفه

 

34 3-3-2- الگوریتم شبیه­سازی تبرید

 

35 3-3-2-1- الگوریتم شبیه­سازی تبرید اولیه

 

35 3-3-2-2- الگوریتم شبیه­سازی تبرید موازی چند هدفه

 

 

37 4- فصل چهارم: طراحی آزمایشات و ارزیابی محاسباتی

 

38 4-1- مقدمه

 

39 4-2- طراحی آزمایشات تاگوچی

 

39 4-2-1- تولید داده ­ها

 

40 4-2-2- تنظیم پارامترهای الگوریتم MOPGA

 

40 4-2-3- تنظیم پارامترهای الگوریتم MOPSA

 

42 4-3- ارزیابی محاسباتی

 

43 5- فصل پنجم: جمع­بندی و مطالعات آتی

 

 

 

45 5-1- جمع­بندی

46 5-2- مطالعات آتی

 

46 مراجع

 

48

فهرست جداول

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

عنوان	صفحه
1-1- مقادیر پارامتر α	5
1-2- مقادیر پارامتر β	7
1-3- مقادیر پارامتر γ	8
3-1- تعداد متغیرها	29
3-2- تعداد محدودیت­ها	29
3-3- تعداد متغیرها و محدودیت­ها مطابق با مدل MOMILP	29
4-1 فاكتورهای الگوریتم MOPGA و سطوح آن­ها	41
4-2- آزمایشات مربوط به آرایهء L9 در الگوریتم MOPGA	41
4-3- جدول تحلیل واریانس كسر S/N مربوط به فاكتورهای الگوریتم MOPGA	42
4-4- فاكتورهای الگوریتم MOPSA و سطوح آن­ها	42
4-5- آزمایشات مربوط به آرایهء L4 در الگوریتم MOPSA	42
4-6- جدول تحلیل واریانس كسر S/N مربوط به فاكتورهای الگوریتم MOPSA	43
4-7- عملكرد مدل MOMILP و الگوریتم­های GA و SA اولیه در برخورد با مسأله­های با ابعاد كوچك	44
4-8- میانگین RPD برای الگوریتم­های MOPGA و MOPSA در حل مسأله­های با ابعاد بزرگ	44

 

فهرست شكل­ها

 

 

 

 

 

 

 

 

 

عنوان	صفحه
1-1- رابطهء جایگزینی بین دو هدف و	10
3-1- توالی كارها روی یک ماشین j	25
3-2- نمودار گانت مربوط به حل بهینهء مثال	28
3-3- نحوهء تقسیم ­بندی جمعیت و عملكرد موازی زیر-جمعیت­ها	34
3-4- جستجوی همسایگی الگوریتم شبیه­سازی تبرید	36
3-5- قدم­های الگوریتم شبیه­سازی تبرید اولیه	36
4-1- نمودار كسر S/N مربوط به RPD در فاكتورهای الگوریتم MOPGA	41
4-2- نمودار كسر S/N مربوط به RPD در فاكتورهای الگوریتم MOPSA	43

چكیده

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

مقدمه

از مهمترین شرط­های ارتقای وضعیت فعلی در هر سازمان می­توان به استفادهء مناسب از سرمایه­ها و جلوگیری از هدر رفت آن­ها اشاره كرد. منظور از ” استفادهء مناسب ” در اینجا مفهومِ واژهء كارایی[1] یعنی سرعت عمل در استفاده از ظرفیت است كه بدون داشتن برنامهء از پیش تعیین شده ممكن نیست. افزون بر آن، هرچه دقت در برنامه بیشتر و مطالعه مكفی­تر باشد سرعت عمل بیشتر شده و توان رقابتی بالاتر می­رود. وقتی صحبت از سرمایه ­های یک سازمان به میان می ­آید ممكن است ذهن­ها به سمت سرمایه ­های فیزیكی مثل ماشین­آلات و دستگاه­های گران­قیمت منحرف شود. حال آنكه، مفهوم مورد انتظار ما بطور خاص “زمان” است. استفادهء مناسب از زمان بعنوان یک سرمایه و جلوگیری از هدر رفت آن از جمله ابزارهای مهم مدیرانِ سازمان­ها در عرصه ­های رقابتی است. زمان را می­توان منبعی دانست كه باید بطور صحیح تقسیم ­بندی و مدیریت شده و با برنامهء خاص به فعالیت­ها تخصیص داده شود و این همان چیزیست كه به آن زمان­بندی[2] اطلاق می­ شود.

زمان­بندی شامل تخصیص[3] منابع محدود به فعالیت­هاست با هدف بهینه­سازی یک یا چند معیار اندازه ­گیری[4] [1]. از طرفی، ماهیت برخی منابع همچون ماشین­آلات و نیروی انسانی بگونه­ای است كه قادر به انجام همزمان بیش از یک فعالیت نیستند. بنابراین، تعریف دیگری برای زمان­بندی به این شرح ارائه می­ شود: زمان­بندی، یافتن توالی[5] مناسب انجام فعالیت­ها توسط ماشین­ها و یا نیروی انسانی است بنحوی كه یک یا چند معیار اندازه ­گیری بهینه شوند. برای تحلیل سیستم زمان­بندیِ تولیدِ جاری و یافتن راه­های بهبود آن، آگاهی از روش­های زمان­بندی تولید بسیار مهم است. دو مسألهء كلیدی در زمان­بندیِ تولید اولویت و ظرفیت هستند [2]. بعبارت دیگر، “چه كاری باید ابتدا انجام شود؟” و “چه كسی باید آن را انجام دهد؟” وایت [2] زمان­بندی را اینگونه تعریف می­كند: “تعیین زمان برای انجام یک فعالیت”. او همچنین، در یک شركت تولیدی زمان­بندیِ تفصیلی[6] در سطح یک كارگاه را درنظر می­گیرد. یعنی، زمان­بندی كه در آن زمان شروع و پایان هر عملیات معلوم است. كوكس و همكاران [3] زمان­بندی تفصیلی را اینگونه تعریف می­كنند: “تخصیص واقعی زمان شروع و یا پایان فعالیت­ها یا گروهی از فعالیت­ها بنحوی كه سفارش تولید در موعد مقرر تكمیل شود.” آن­ها همچنین از زمان­بندی عملیات[7]، زمان­بندی سفارش[8] و زمان­بندی كارگاه[9] بطور معادل یاد می­كنند.

تعابیر متنوعی از تعریف­های ارائه شده برای زمان­بندی در محیط های مختلف قابل تصور است. بعنوان مثال، منابع می­توانند ماشین­ها در یک كارگاه، پردازنده و حافظه در یک سیستم كامپیوتری، باندهای فرود در یک فرودگاه، تعمیركاران در یک تعمیرگاه خودرو و غیره باشند. همچنین، فعالیت­ها می­توانند شامل عملیات مختلف در یک فرایند ساخت، اجرای یک برنامهء كامپیوتری، نشستن و برخاستن هواپیماها در فرودگاه، تعمیر خودروهای تعمیرگاه و مواردی از این دست باشند.

مطالعه بر روی زمان­بندی به دههء 1950 برمی­گردد كه محققان در پژوهش عملیاتی[10]، مهندسی صنایع و مدیریت با مسألهء اداره كردن فعالیت­های مختلفی كه در یک كارگاه رخ می­دادند مواجه بودند. در آن زمان، الگوریتم­های زمان­بندی خوب می­توانستند هزینهء تولید را در فرایند ساخت كاهش داده و توان رغابتی شركت­ها را بالا ببرند. در اواخر دههء 1960، دانشمندان كامپیوتر نیز با مسألهء زمان­بندی در توسعه سیستم­های عملیاتی روبرو شدند. چراكه، در آن روزها منابع محاسباتی همچون پردازشگرها و حافظه­ها محدود بودند و بهره ­برداری مؤثر از این منابع محدود می­توانست هزینهء‌ اجرای برنامه ­های كامپیوتری را كاهش دهد. بنابراین، مطالعه بر روی زمان­بندی توجیه اقتصادی پیدا كرد [4].

مسأله­های زمان­بندی در دههء 1950 بسیار ساده بودند و تعدادی الگوریتم­های كارا برای رسیدن به جواب بهینه توسعه یافتند كه كارهای جكسون [5،6]، جانسون [7] و اسمیت [8] از مهمترین آن­ها هستند. با گذشت زمان، مسأله­ها پیچیده­تر شده و دیگر محققان قادر به توسعه الگوریتم­های كارا برای آن­ها نبودند. بیشتر محققان تلاش كردند روش­های شاخه و كران[11] را كه عمدتاً الگوریتم­هایی با زمان نمایی[12] بودند را گسترش دهند. با ظهور تئوری پیچیدگی[13] [11-9]، محققان دریافتند كه بسیاری از این مسأله­ها ذاتاً برای حل سخت هستند. در دههء 1970 نشان داده شد كه بیشتر مسأله­های زمان­بندی NP-hard هستند [15-12] یعنی زمان حل آن­ها شدیداً غیر چندجمله­ای[14] است. در دههء 1980، چندین زمینهء مختلف در دانشگاه و صنعت مورد بررسی قرار گرفت. یكی از این زمینه­ها توسعه و تحلیل الگوریتم­های تقریبی[15] و دیگری افزایش توجه به مسأله­های زمان­بندی اتفاقی[16] بود. از آن پس، تحقیق در زمینهء تئوری زمان­بندی با فراز و نشیب­هایی همراه بوده ­است. بعد از گذشت بیش از 60 سال، هنوز ابهاماتی در این شاخه از علم وجود دارد.
ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود است

متن کامل را می توانید دانلود نمائید