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 سال، هنوز ابهاماتی در این شاخه از علم وجود دارد.

 

 

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

 

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