چکیده

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

 

کلمات کلیدی: زمانبندی به­موقع، ماشین­های موازی یکنواخت، زمان آماده ­سازی وابسته به توالی، تاثیر یادگیری و محدودیت مجموعه پردازش

فهرست مطالب

.. 1

1-1. مقدمه. 2

1-2. تعریف مسئله. 3

1-3. اهداف تحقیق.. 5

1-4. مفروضات مسئله. 6

1-5. جنبه­ های نوآوری تحقیق.. 6

1-6. محتویات تحقیق.. 7

… 8

2-1. مقدمه. 9

2-2. زمان آماده ­سازی وابسته به کار قبلی.. 10

2-3. تاثیر یادگیری.. 13

2-4. محدودیت مجموعه پردازش… 17

2-5. زمان­های زودکرد و دیرکرد 19

2-6. نتیجه ­گیری.. 20

.. 21

3-1. مقدمه. 22

3-2. تعریف مسئله. 22

3-3. مفروضات مسئله. 23

3-4. مدل پیشنهادی.. 24

3-5. اعتبارسنجی مدل. 27

3-6. پیچیدگی مسئله. 31

3-7. نتیجه گیری.. 33

.. 34

4-1. مقدمه. 35

4-2. الگوریتم ژنتیک… 37

4-2-1. واژگان الگوریتم ژنتیک… 39

4-2-2. کدگذاری.. 40

4-2-3. جمعیت اولیه. 41

4-2-4. تابع شایستگی.. 41

4-2-5. عملگرهای ژنتیک… 41

4-2-5-1. عملگر انتخاب… 41

4-2-5-2. عملگر تقاطع. 43

4-2-5-3. عملگر جهش… 44

4-2-6. شرط توقف… 44

4-3. الگوریتم ازدحام ذرات… 45

4-3-1. ساختار کلی.. 45

4-3-2. مفاهیم پایه­ای الگوریتم ازدحام ذرات… 47

4-3-3. به­روز رسانی سرعت… 47

4-3-3-1. پارامتر شخصی c1 و پارامتر جمعی c2. 49

4-3-3-2. پارامتر وزن اینرسی.. 49

4-3-4. به­روز رسانی موقعیت… 49

4-4. تبرید شبیه­سازی­شده 50

4-4-1. مفاهیم الگوریتم تبرید شبیه­سازی­شده 52

4-5. الگوریتم­های پیشنهادی.. 54

4-5-1. تولید جامعه اولیه و نحوه­ نمایش کروموزوم­ها 55

4-5-2. اجرای الگوریتم ژنتیک… 56

4-5-2-1. عملگر تقاطع. 57

4-5-2-2. عملگر جهش… 58

4-5-3. اجرای الگوریتم بهینه­سازی ازدحام ذرات… 59

4-5-3-1. تعیین سرعت… 61

4-5-3-2. عمل جهش… 61

 

 

4-5-3-3. موقعیت جدید. 62

4-5-4. اجرای الگوریتم تبرید شبیه­سازی­شده 64

4-5-4-1. تعیین دمای اولیه. 65

4-5-4-2. تعیین دمای نهایی.. 66

4-5-4-3. روش کاهش دما 66

4-5-4-4. روش همسایگی.. 66

4-6. مجموعه داده ­ها 67

4-7. تنظیم پارامترها 68

4-7-1. اندازه جامعه اولیه. 69

4-7-2. تقاطع. 71

4-7-3. نرخ جهش… 71

4-7-4. حداکثر تعداد نسل­ها 71

4-8. تنظیم پارامتر چندعاملی.. 72

4-9.  ارزیابی الگوریتم­ها 79

4-10. جمع­بندی.. 90

… 91

.. 95

 

فهرست جداول

جدول 3-1. اطلاعات مسئله­ ساخته شده 28

جدول 3-2. زمان­های آماده ­سازی مسئله­ ساخته شده 29

جدول 3-3. زمان پردازش(ثانیه) 29

جدول 3-4. موعدهای تحویل (ثانیه) و هزینه زودکرد و دیرکرد. 30

جدول 3-5. زمان آماده ­سازی ماشین (ثانیه) 30

جدول 4-1. چیدمان کارها 56

جدول 4-2. خلاصه­ی داده ­ها 68

جدول 4-3. پارامترهای کنترل کننده الگوریتم ژنتیک و محدوده­ موثر آن. 71

جدول 4-4. فاکتورها و سطوح آن­ها 72

جدول 4-5. ترکیب فاکتورها و سطوح پاسخ مربوطه در آزمایشات چند­عاملی.. 73

جدول 4-6. ضرایب همبستگی تخمینی مدل برای نسبت­های SN… 74

جدول4-7. آنالیز واریانس برای نسبت­های SN… 74

جدول 4-8. ضرایب همبستگی تخمینی مدل برای میانگین پاسخ­ها 75

جدول4-9. آنالیز واریانس برای میانگین پاسخ­ها 75

جدول4-10.  پاسخ SN… 76

جدول4-11.  پاسخ میانگین­ها 76

جدول 4-12. مقادیر تنظیم شده­ی پارامترهای ژنتیک… 78

جدول 4-13. مقادیر تنظیم شده­ی پارامترهای تبرید شبیه­سازی­شده 78

جدول 4-14. مقادیر تنظیم شده­ی پارامترهای الگوریتم ازدحام ذرات… 78

جدول 4-15. خلاصه مسائل.. 79

جدول 4-16. مسائل با اندازه­ کوچک… 80

جدول 4-17. مسائل با اندازه­ متوسط.. 81

جدول 4-18. مسائل با اندازه­ بزرگ… 82

جدول 4-19. مقدار PRE و زمان حل برای سطح کوچک… 84

جدول 4-20. مقدار RPD و زمان حل برای سطح متوسط.. 85

جدول 4-21. مقدار RPD و زمان حل برای سطح بزرگ… 86

جدول 4-22. میانگین زمان حل و RPD برای تعداد مختلف کارها 88

جدول 4-23. مجموع مقایسه شده­ی پارامتر الگوریتم­ها 89

جدول 4-24. درصد جواب­های بهتر الگوریتم­ها 89

 

فهرست اشکال

شکل 3-1. سلسله مراتب پیچیدگی محیط­های کاری ]57[ 32

شکل 3-2. سلسله مراتب پیچیدگی توابع هدف ]57[ 32

شکل4-1. نمای کلی الگوریتم ژنتیک کلاسیک… 39

شکل 4-2. نمایش کروموزوم. 56

شکل 4-3. عملیات تقاطع. 58

شکل 4-4. جهش نوع اول. 58

شکل 4-5. جهش اول نوع دوم. 59

شکل 4-6. جهش دوم نوع دوم. 59

 شکل4-7. تغییر موقعیت ذره 62

شکل4-8. تغییر موقعیت ذره همراه با اصلاحیات… 63

 شکل4-9. تغییر موقعیت ذره با توجه به محدودیت پردازشی.. 64

 شکل4-10. کیفیت جواب­ها و اندازه­ جامعه. 70

شکل4-11. زمان محاسباتی و اندازه­ جامعه. 70

شکل4-12. پاسخ میانگین­ها 77

شکل4-13. پاسخ ضرایب SN… 77

شکل 4-14. نمودار میانگین و فواصل LSD… 87

شکل 4-15. RPD برای تعداد مختلف کارها 88

 

فصل اول

کلیات تحقیق

1-1. مقدمه

برنامه ­ریزی و زمانبندی[1] یک فعالیت بسیار معمول در صنعت و عملیات غیر­صنعتی است. هر روز، جلسات برنامه ­ریزی می­شوند. ضرب­العجل­هایی برای انجام پروژه­ ها و کارها تعیین می­ شود. خدمات تعمیر و نگهداری و عملیات برنامه ­ریزی می­شوند. بازی­های ورزشی برنامه ­ریزی و زمانبندی می­شوند.

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

دلیل بسیاری از پیشرفت­های علم زمانبندی بواسطه­ محیط­های صنعتی و استفاده این علم در صنعت است. به طور طبیعی در بیان مفاهیم زمانبندی از واژه­ های بکار رفته در صنعت استفاده می­ شود. که در آن­ منابع با عنوان ماشین و فعالیت­ها به عنوان کار شناخته می­شوند. بطوریکه کار­ها اغلب به وسیله مجموعه ­ای از ماشین­ها در ایستگاه­های مختلف کاری با توالی مشخص پردازش می­شوند.

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

در این تحقیق، به بررسی مسئله زمانبندی ماشین­های موازی با سرعت­های مختلف[3] پرداخته می­ شود. مسائل ماشین­های موازی با سرعت­های مختلف حالت عمومی یافته مسائل تک­ماشینه و حالت خاصی از مسائل ماشین­های متوالی منعطف محسوب می­شوند. در بخش­های آتی این فصل، شرح تفصیلی مسئله مورد بررسی این تحقیق ارائه می­ شود.

1-2. تعریف مسئله

ماشین­های موازی به عنوان یکی از زیر­مجموعه­های اصلی و پایه در زمانبندی از جایگاه ویژه ومهمی برخوردارند و همواره زمانبندی این مدل بر مبنای معیار­های عملکرد مختلف مورد نظر بوده است. با این توجه که، عموم روش­های حل در مدل­های پیچیده تر مانند مدل ماشین­های متوالی منعطف بر مبنای راهکارهای مدل­های ساده­تر از جمله ماشین­های موازی استوار است ]1[.

در کارخانه­ها وقتی ماشین­­ها و دستگاه­­های جدید خریداری می­شوند و در کنار ماشین­های قدیمی قرار می­گیرند، تفاوت سرعت بین ماشین­های جدید و قدیمی بوجود می ­آید که این تفاوت سرعت، مسئله­ چندین ماشین با سرعت­های متفاوت را بوجود می­آورد.

در برخی از محیط­های کاری زمانبندی ماشین­های موازی با سرعت متفاوت، ممکن است که تمامی ماشین­ها نتوانند تمامی کارها را پردازش کنند که در این حالت هر کار توسط مجموعه ­ای از ماشین­ها می ­تواند انجام شود که به آن محدودیت مجموعه پردازش[4] می­گویند.

در بسیاری از محیط­های کاری انسان به عنوان عنصر اصلی به­شمار می­رود. در فعالیت­هایی که انسان در آن سهم بسزایی دارد مسئله­ یادگیری بسیار مهم است و تاکنون در اکثر مقالات فرض رایج بر این بوده که زمان پردازش کار­ها ثابت و مستقل از توالی است. در­حالیکه در بسیاری از موارد عملی با تکرار کار­های مشابه (و یا متفاوت)، توانایی ومهارت اپراتور افزایش و در نتیجه آن، زمان پردازش کار­ها کاهش می­یابد. این امر باعث بهبود مستمر عملکرد تسهیلات تولیدی مخصوصا نیروی انسانی می­ شود که به آن تأثیر یادگیری[5] می­گویند. که از جمله­ این فعالیت­ها می­توان به تمامی کار­هایی که سیستم دستی را شامل می­ شود مثلا راه­اندازی ماشین­آلات، تمیز­ کردن ماشین و زمان آماده ­سازی[6] اشاره کرد .

در مسائل زمانبندی کلاسیک عموما با درنظر گرفتن این فرض که زمان­های آماده ­سازی در مقایسه با زمان پردازش کوچک و یا اینکه مستقل از توالی پردازش کارها بر روی ماشین­ها هستند، زمان آماده ­سازی را نادیده گرفته و یا آن را به زمان پردازش اضافه می­کردند. اما با این­وجود، در بسیاری از محیط­های صنعتی یک زمان آماده ­سازی وابسته به توالی[7] هنگام تعویض کار­ها بر روی ماشین­ها به وقوع می­پیوندد ]17[. در این شرایط، زمان آماده ­سازی به عنوان بخشی مجزا از زمان پردازش در نظر گرفته می­ شود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به نوع کار قبلی که بر روی ماشین پردازش شده نیز بستگی دارد. تلقی زمان آماده ­سازی به صورت مجزا از زمان پردازش در بیشتر تکنیک­های مدیریت تولید نوظهور نظیر تولید به­موقع[8]، تکنولوژی گروهی[9] و تولید سلولی[10] مورد استفاده قرار می­گیرد.

در محیط­های کسب و کار حاضر، رقابت شرکت­های تولیدی از طریق قابلیت آن­ها برای پاسخگویی سریع به تغییرات سریع زمینه تجاری و تولید محصولات با کیفیت بالاتر و هزینه­ای کمتر تعیین می­ شود. یکی از راه­های رسیدن به این منظور استفاده از مفهوم تولید به­موقع است ]2[. در محیط تولید به­موقع، شرکت­ها تمایل دارند که تا حدامکان زمان تکمیل کار­ها­یشان به موعد تحویل نزدیک باشد تا از جریمه­های زودکرد و دیرکرد بکاهند. در صورتی که یک کار قبل از موعد تحویل تکمیل شود، باید تا موعد تحویل در انبار نگهداری شود لذا هزینه­ زودکرد به سیستم تحمیل می­ شود. جریمه­های زودکرد به آن دلیل مورد توجه هستند که تا زمانیکه موعد تحویل مشتری فرا برسد، هزینه نگهداری شامل هزینه فساد مواد اولیه (در حالیکه کالاها فاسد شدنی هستند) به سیستم تحمیل می­ شود. و اگر یک کار بعد از موعد تحویل تکمیل شود، جریمه دیرکرد ناشی از نارضایتی مشتری، جریمه قراردادی یا جریمه از دست دادن اعتبار ایجاد می­ شود.

در این تحقیق، مسئله­ ماشین­های موازی با سرعت­های مختلف با در نظر گرفتن محدودیت­های زمان آماده ­سازی وابسته به کار قبلی، محدودیت مجموعه پردازش و تأثیر یادگیری با هدف کمینه­سازی زمان­های زودکرد و دیرکرد کل بررسی می­ شود. یک مدل برنامه ­ریزی عدد صحیح برای این مسئله پیشنهاد می­ شود. همچنین الگوریتم­های ژنتیک[11] و بهینه­سازی ازدحام ذرات[12] و تبرید شبیه­­سازی­شده[13] برای حل آن ارائه می­گردد.

1-3. اهداف تحقیق

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

 

1-4. مفروضات مسئله

مفروضات زیر در ارائه مدل مسئله در نظر گرفته می­ شود:

• تأثیر یادگیری بر زمان پردازش کارها در نظر گرفته شده است.