فهرست مطالب

عنوان
صفحه
1- فصل اول: معرفی و کلیات تحقیق
1
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].