فهرست مطالب

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

عنوان صفحه
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].

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

  • تعاریف زمان­بندی

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

[1] Efficiency

[2] Scheduling

[3] Allocation

[4] Performance measures

[5] Sequence

[6] Detailed scheduling

[7] Operations scheduling

[8] Order scheduling

[9] Shop scheduling

[10] Operations research

[11] Branch-and-bound

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...