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