sdf69

فصل اول

مقدمه و کلیات تحقیق

1-1. مقدمه
زمانبندی، فرآیند تخصیص منابع به فعالیتها با در نظر گرفتن دورههای زمانی مربوط به آنها به منظور بهینهسازی یک یا چند تابع هدف میباشد. این فرآیند به عنوان یک فرآیند تصمیمگیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. زمانبندی کارای فعالیتها زمینهساز بهبود عملکرد سیستمهای تولیدی میباشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار میآید. امروزه، مدیریت منابع موضوع به طور فزاینده مهمی برای سازمانها میباشد و تعیین توالی و زمانبندی یک شکل از تصمیمگیری است که نقش حیاتی در صنایع تولیدی و خدماتی بازی میکند. زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه میکند.
بهطور کلی، منابع، فعالیتها و توابع هدف عناصر کلیدی زمانبندی محسوب میشوند. منابع برحسب قابلیتهای کمی و کیفی خود مشخص میشوند. از سوی دیگر، فعالیتها بر حسب اطلاعاتی از قبیل منابع مورد نیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف میشوند. توابع هدف نیز در برگیرنده هزینههای سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیتها میباشند. تصمیمات عمده در فرآیند زمانبندی شامل بهره برداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمانهای تحویل با موعدهای تحویل تعیین شده میشوند.
در مسائل زمانبندی هدف از یافتن توالی انجام فعالیتها ممکن است متفاوت باشد. تعدادی از اهداف متداول عبارتند از: کمینهسازی زمان تکمیل کل کارها و یا کمینهسازی تعداد کارهایی که دیرکرد دارند. یکی از مهمترین اهداف در بسیاری از صنایع تولیدی تحویل به موقع کالا و خدمات میباشد که در بهدست آوردن سود و یا هزینههای پایینتر نقش دارد. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیطهای تولید متنوع است. تکمیل یک کار زودتر از موعد تحویل ممکن است هزینههایی از قبیل هزینه نگهداری موجودی به تولید کنندگان تحمیل کند، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به پرداخت جریمههای قراردادی به مشتری و کاهش اعتبار تولید کننده میشود. حداقلسازی زودتر و دیرتر یکی از سیاستهای مسائل زمانبندی بهنگام میباشد.
انگیزه بسیاری از توسعهها و پیشرفتهای عملی در حوزه زمانبندی برخاسته از محیطهای صنعتی است و به طور طبیعی در بیان مفاهیم زمانبندی از واژههای بکار رفته در صنعت استفاده میشود. به همین خاطر منابع با عنوان ماشین به کار میروند و به هر کدام از فعالیتها، کار اطلاق میشود بطوریکه کارها اغلب به وسیلهی مجموعهای از ماشینها در ایستگاههای مختلف کاری با توان مشخص پردازش میشوند.
بطور کلی، مسائل زمانبندی به صورت مسائل بهینهسازی دارای محدودیت بیان میشوند که در آنها به بررسی تصمیمات مربوط به تضمین ماشینها و توالی پردازش کارها پرداخته میشود. در حالتی که تنها یک ماشین موجود است، تعیین توالی پردازش کارها یک برنامه زمانی کامل را تشکیل میدهد. مسائل تکماشینه با وجود سادگی ذاتی، سنگ بنای درک فراگیر مفاهیم زمانبندی را تشکیل میدهند. در مقابل، زمانبندی مسائل چند ماشین شامل سیستمهای موازی، سیستمهای متوالی و سیستمهای ترکیبی میباشد. در سیستمهای موازی، هر یک از کارها با انجام یک عملیات همانند مسائل تکماشینه بر روی یکی از ماشینهای موازی موجود پردازش میشوند و به دنبال آن تخصیص ماشینها به کارها موضوعیت پیدا میکنند. این در حالی است که در سیستمهای متوالی و ترکیبی، کارها با انجام چند عملیات بر روی ماشینها پردازش میشوند و مسائل مربوطه ساختار نسبتاً پیچیدهتری را تجربه میکنند.
در این تحقیق، به بررسی مسأله جریان کارگاهی انعطافپذیر به عنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است، پرداخته میشود. چنانچه ساختار سیستم تولیدی به شکل سری بوده و حداقل در یک مرحله چندین ماشین موازی وجود داشته باشد،در واقع با یک سیستم جریان کارگاهی انعطافپذیر مواجه هستیم که زمانبندی این نوع سیستمهای خطی به دلیل کاربردی بودن آنها در سالهای اخیر در صنعت مورد توجه قرار گرفته است.
1-2. تعریف مسأله
دربرخی از صنایع تولیدی و خدماتی سفارشها تحت عنوان کارها به وسیله مجموعهای از ماشینها که به صورت سری در ایستگاههای کاری مختلف قرار گرفتهاند با توالی مشخص پردازش میشوند. یعنی کارها مسیر یکسانی را دنبال میکنند و ماشینها به صورت سری، پشت سر هم قرار دارند. وضعیت تعمیم یافتهای از این مسائل یعنی مسأله جریان کارگاهی منعطف میباشد که در هر مرحله (حداقل یکی از مراحل) حداقل دو ماشین بصورت موازی موجود است. در این حالت هر یک از کارها بایستی به ترتیب در هر مرحله توسط یکی از ماشینهای موجود پردازش شده و به مرحله بعد برود.
بیشتر ادبیات نظریه زمانبندی، و به همین دلیل بیشتر درک ما از مسائل زمانبندی، مربوط به محاسبه زمان جریان کل، تعداد کارهایی که تأخیر دارند و تأخیر کل میباشد. معیار مجموع تأخیرها، به طور خاص، به یک روش استاندارد برای اندازهگیری انطباق با تاریخ تحویل کارها تبدیل شده است، با این وجود عواقب کارهایی که زودتر از موعد تحویل، تکمیل میشوند نادیده گرفته شده و تنها آن دسته از کارهایی که دیرکرد دارند، با جریمه مواجه شدهاند. اما این معیار با رشد سهم تولید بهنگام شروع به تغییر کرد، با تأکید بر این نکته که زودکرد همانند دیرکرد باید نامناسب در نظر گرفته شود. در یک محیط زمانبندی بههنگام، کاری که زود تکمیل می شود تا تاریخ تحویل آن کار باید در موجودی انبار نگهداری شود، در حالی که اگر یک کار پس از موعد تحویلش اتمام یابد ممکن است در برآوردن نیازهای مشتری اختلال ایجاد کند. بنابراین، یک زمانبندی ایدهآل، زمانبندی است که در آن همه کارها دقیقاً در تاریخهایی که به آنها اختصاص داده شده اتمام یابند. البته، زمانبندی بهنگام شامل مجموعهای بسیار گستردهتر از اصولی است که مرتبط با موعدهای تحویل میباشد، اما مدلهای زمانبندی با هزینه زودکرد و دیر کرد (E / T) به یک بعد اساسی زمانبندی رویکردهای JIT آدرس دهی میشوند.
مسأله زمانبندی جریان کارگاهی اخیراً در صنعت بطور وسیعی در محیطهای صنعتی مورد استفاده قرار گرفته است، به همین دلیل در 50 سال اخیر به دقت بررسی شده است. مسأله مورد بررسی در این تحقیق، مسأله زمانبندی جریان کارگاهی انعطافپذیر در محیطهای تولید بهنگام میباشد.در برخی از کاربردهای زمانبندی مسأله جریان کارگاهی انعطافپذیر ماشینها دارای سطوح تکنولوژیکی متفاوتی هستند و لزوماً قادر به پردازش هریک از کارهای موجود در مجموعه کارها نمیباشند. در نتیجه، هر کدام از کارها تنها بر روی زیر مجموعهای از مجموعه ماشینها میتوانند پردازش شوند و اصطلاحاً پردازش کارها با دسترسی محدود به ماشینها صورت میپذیرد.
مسائل زمانبندی غالباً به محیطهای کارگاهی میپردازند که در آنها زمان نصب ماشین نادیده گرفته میشود و یا به عنوان بخشی از زمان پردازش کارها تلقی میشود. این نوع محیطهای کارگاهی با این فرض مدلسازی میشوند که زمانهای نصب در مقایسه با زمانهای پردازش کوچک هستند، بنابراین میتوان آنها را نادیده گرفت و یا اینکه زمانهای نصب مستقل از توالی پردازش کارها بر روی ماشینها هستند، در نتیجه میتوان آنها را به زمانهای پردازش اضافه نمود. با این وجود، در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد[6]. در این شرایط، زمان نصب به عنوان بخشی مجزا از زمان پردازش در نظر گرفته میشود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد به نوع کار قبلی که بر روی آن ماشین پردازش شده نیز بستگی دارد.تلقی زمان نصب به صورت مجزا از زمان پردازش در بیشتر تکنیکهای مدیریت تولید نوظهور نظیر تولید بموقع، تکنولوژی گروهی و تولید سلولی مورد استفاده قرار میگیرد. همچنین در بعضی از مسائل ماشینها نیاز به زمان نصب برای پردازش کارها دارند، یعنی اگر یک کار به عنوان اولین کاری باشد که بر روی ماشین پردازش میشود یک زمان نصب وابسته به ماشین مجزا از زمان پردازش برای آن در نظر گرفته میشود. تحقیقات زیادی در مورد مسأله جریان کارگاهی انعطافپذیر با فرض خرابی ماشین خصوصاً هنگامیکه خرابی ماشین به کار انجام شده قبلی روی ماشین بستگی داشته باشد،انجام نشده است[46]. در بعضی از مسائل تمام کارها در ابتدای افق زمانی (لحظه صفر) در دسترس نیستند و زمان دسترسی به هرکار مستقل از کارهای دیگر میباشد.
در این تحقیق، مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن محدودیتهای دسترسی به ماشین، زمان نصب وابسته به توالی و ماشین، خرابی ماشین و زمان دسترسی به کار با هدف کمینهسازی زمانهای زودکرد و دیرکرد وزنی بررسی میشود. یک مدل برنامهریزی عدد صحیح برای این مسأله پیشنهاد میشود. همچنین چندین روش فرابتکاری برای حل آن ارائه میگردد.
1-3. اهداف تحقیق
هدف ازاجرای این تحقیق طراحی یک مدل ریاضی وحل آن با الگوریتمهای ابتکاری و فرا ابتکاری برای مسأله جریان کارگاهی منعطف با محدودیت و توابع هدف کمینهسازی دیرکردها و زودکردهای وزنی و کمینهسازی هزینه بیکاری ماشینها میباشد، به علاوه چندین الگوریتم فراابتکاری به منظور حل این مدل در مقیاس کاربردی طراحی میگردد.
1-4. مفروضات مسأله
مفروضات زیر در ارائه مدل مسأله در نظر گرفته میشود:
• کارها با توجه به زمان دسترسی خود در دسترس قرار می گیرند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
• کارها با توجه زمان آماده سازی خود آماده می شوند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
• زمان نصب هر کدام از کارها وابسته به توالی آنها بر روی ماشین هاست.
• هر ماشین در هر لحظه حداکثر می تواند یک کار را پردازش کند.
• هر کار در هر لحظه حداکثر می تواند بر روی یک ماشین پردازش شود.
• ماشین ها به طور پیوسته در دسترس نیستند.
• برش کار به این مفهوم که پردازش یک کار قبل از پایان زمان پردازش آن قطع شود ودر زمانهای بعدی بر روی ماشینهای دیگر پردازش آن ادامه یابد، مجاز نمی باشد.
1-5. جنبه های نوآوری تحقیق
تحقیق موجود از دو جنبه صورت مسأله و روش حل نسبت به تحقیقات پیش دارای نوآوری میباشد. در این تحقیق یک مدل ریاضی جدید برای مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن محدودیتهای دسترسی به ماشین، زمان نصب وابسته به توالی وماشین، خرابی ماشین و زمان دسترسی به کارها ارائه شده است. همچنین دو رویکرد با استفاده الگوریتمهای ژنتیکو رقابت استعماری برای حل مسأله ارائه شدهاست.
1-6. محتویات تحقیق
مطالب ارائه شده دراین تحقیق در پنج فصل سازماندهی میشود: مقدمه و کلیات تحقیق در فصل اول ارائه شدهاست. در فصل دوم به مرور ادبیات تحقیق زمانبندی جریان کارگاهی منعطف پرداخته میشود. در فصل سوم مدل ریاضی پیشنهادی تشریح و اعتبار سنجی میگردد. فصل چهارم شامل معرفی الگوریتمها و رویکردهای پیشنهادی این تحقیق به همراه نتایج محاسباتی مربوط به آن میباشد و نهایتاً، فصل پایانی تحقیق شامل نتیجهگیری و پیشنهادات تحقیقات آتی میباشد.
فصل دوم
ادبیات تحقیق
2-1. مقدمه
در این فصل ابتدا مروری بر مسائل زمانبندی داشته و بعضی مفاهیم اولیه آن مورد بررسی قرار می گیرد. همچنین انواع محیطهای زمانبندی نیز تشریح خواهند شد. در ادامه به بررسی پیشینه تحقیقهای صورت گرفته در حوزههای مرتبط با این تحقیق خواهیم پرداخت.
2-2. مروری بر مسائل زمانبندی
الگوهای زیادی در تعریف مسائل زمانبندی و طبقه بندی آنها مطرح هستند. برای مسائل زمانبندی از نظر فرآیند تولید محصولات و بسته به تعداد عملیاتهای مورد نیاز برای پردازش یک کار و نیز تعداد ماشینهای موجود برای پردازش هر عملیات الگوهای زیادی را میتوان برشمرد. در کل یک مسأله زمانبندی عمومی میتواند با استفاده از سه نماد بصورتα/β/γ تعریف شود که α بیانگر وضعیت و شرایط ماشین یا منبع است و معمولاً دارای یک نماد است، β خصوصیات و جزئیات نحوه پردازش و محدودیتهای موجود را بیان میکند و ممکن است شامل هیچ نمادی نباشد و یا چندین نماد باشد، γ بیانگر تابع هدف مسأله است و معمولاً شامل تنها یک نماد است. از نظر تعداد عملیاتهای لازم برای تکمیل یک کار مسائل زمانبندی را میتوان به صورت زیر دسته بندی کرد.
2-2-1. مسائل تک ماشینی
سادهترین حالت ممکن است که معمولاً حالت خاص سایر مسائل در نظر گرفته میشود. در این حالت فقط یک ماشین در دسترس بوده و این ماشین قادر به پردازش تنها یک کار در هر لحظه میباشد و هر کار فقط به یک عملیات برای تکمیل شدن، نیاز دارد. این مدل مبنا و اساس کار برای ایجاد قوانین و قواعد زمانبندی برای استفاده در سایر مدلها میباشد به عبارت دیگر عموماً روشها و راه کارها ابتدا برای یک مدل تک ماشینه تبدیل میگردد و سپس برای سایر مدلها بسط داده میشوند.
2-2-2 . ماشینهای موازی
تعدادی ماشین معمولاً مشابه در دسترساند و هر کار تک عملیاتی میباشد و روی هر یک از این ماشینها میتواند پردازش شود. این سیستم، از لحاظ ویژگیهای ماشین از قبیل سرعت پردازش، کیفیت محصولات تولیدی و هزینه تولید به دو دسته ماشینهای موازی یکسان و ماشینهای موازی متفاوت تقسیم میشوند.
2-2-3 . جریان کارگاهی
در این سیستم تولیدی، هر کار به چند عملیات برای تکمیل شدن نیاز دارد. کارها روی چند ماشین در یک توالی یکسان پردازش میشوند، اما زمان پردازش هر کار روی هر ماشین ممکن است متفاوت با زمان پردازش سایر کارها روی همان ماشین باشد.
2-2-4 . کارگاه جریان کاری مختلط
این حالت تعمیم یافته حالت جریان کارگاهی و ماشینهای موازی میباشد. در این سیستم تعدادی کارگاه به صورت متوالی وجود دارد که در هر کارگاه، تعدادی ماشین به طور موازی کار میکنند و در هر کارگاه، یک کار حداکثر روی یک ماشین میتواند انجام شود. اغلب مسائل دنیای واقعی، سازگار با محیط جریان کارگاهی مختلط میباشند.
2-2-5 . کار کارگاهی
هر کار به چند عملیات نیاز دارد، تعدادی ماشین مختلف در کارگاه وجود دارند. هر کار ممکن است به برخی یا تمام ماشینها در یک توالی مشخص مربوط به خود، نیاز داشته باشد. یک کار میتواند برای پردازش به یکی از ماشینها یک و یا چند مرتبه مراجعه نماید.
2-2-6 . سیستم کارگاهی باز
این محیط تولیدی، مشابه کار کارگاهی است، با این تفاوت که یک کار میتواند روی ماشینها به هر توالی دلخواهی پردازش شود. به عبارت دیگر هیچ تقدم و تأخر عملیاتی در فرآیند تولید محصولات وجود ندارد. معمولاً هدف در این سیستم تولیدی، حداقلسازی زمان اتمام کلیه کارها است.
2-2-7. پردازش دستهای
در این فرآیند، کارها به صورت دستهای به صورت همزمان پردازش میشوند. پردازش هر دسته، نیازمند زمان مشخصی است و ممکن است برای تعداد کارهایی که می توانند در یک زمان پردازش شوند یک محدودیت ظرفیتی وجود داشته باشد.
2-2-8 . سیستم ساخت انعطاف پذیر
در این سیستم هر ماشین ممکن است قادر به انجام بیش از یک عملیات باشد. بنابراین هر دو ماشین در انجام یک سری از عملیات ممکن است حکم دو ماشین موازی را داشته باشند و در مورد برخی از عملیات با یکدیگر اشتراکی نداشته باشند.
2-2-9. سیستم کارگاهی وابسته
یک محیط سیستم کار کارگاهی است که در آن، زمان شروع و پایان برخی از کارها، به هم وابسته است. مثال بارز این سیستم، خطوط مونتاژ است. در مورد هر یک از سیستمهای تولیدی فوق، وابستگی زمان و هزینه راهاندازی وابسته به توالی، میتواند دو سیستم مختلف را پدید آورد. از طرفی، سیستمهای تولیدی در دنیای واقعی با پدیدههای تصادفی بسیاری روبرو هستند که موجب قطع یا شکست سیستم میگردد. این رویدادها به عنوان رویدادهای زمان واقعی شناخته میشوند.
2-3. پیشینه تحقیق
تحقیق در زمینه زمانبندی در طی 50 سال گذشته تکامل یافته است و به موضوعی با تاریخچه تحقیقاتی غنی از قواعد ساده تا الگوریتمهای پیچیده نظیر شاخه و حد، روشهای برنامهریزی پویا، روشهای ابتکاری و روشهای فراابتکاری تبدیل شدهاست. مسائل واقعی زمانبندی تولید عموماً دارای تعداد زیادی فعالیت و منبع بوده که یک مجموعه گوناگون از اهداف و محدودیت بهرهبرداری از منابع در مورد آنها مطرح میشود. لذا تعجبی ندارد که تلاشهای حل برنامهریزی ریاضی و یا حتی فرموله نمودن آنها نسبتاً سنگین و پر زحمت باشد. یکی از این مسائل، زمانبندی مدلهای جریان کارگاهی میباشد. مدلهای جریان کارگاهی ابزار کارآمدی برای مدیریت هستند. آنها برای مدل کردن بسیاری از فرآیندهای خدماتی و تولیدی بهکار میروند. سیستمهای تولید پیوسته نمونههایی از این فرآیندها میباشند. در مدلهای کارگاه با جریان در حالت نرمال بیش از یک مرکز تولید یا خدمت وجود دارد. هر کار با رفتن روی ماشین اول شروع میکند و سپس به سوی ماشین دوم میرود و به همین ترتیب تا آن که کار روی آن، با ترک آخرین ماشین روی خط به پایان برسد. در مدل کارگاه جریان کار، ماشینها به صورت سری قرار میگیرند و توالی قرارگیری ماشینها ثابت است. وضعیت تعمیم یافتهای از این مسائل یعنی مسأله جریان کارگاهی منعطف میباشد که در هر مرحله (حداقل یکی از مراحل) حداقل دو ماشین بصورت موازی موجود است. در این حالت هر یک از کارها بایستی به ترتیب در هر مرحله توسط یکی از ماشینهای موجود پردازش شده و به مرحله بعد برود. مسائل زمانبندی جریان کارگاهی منعطف تاکنون با تابع هدفهای گوناگون نظیر هدفهای مرتبط با معیار زمان تکمیل، معیار دیرکرد، معیار زمان تکمیل و دیرکرد و … مورد مطالعه قرار گرفته است.
در این تحقیق، مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن محدودیتهای دسترسی به ماشین، زمان نصب وابسته به توالی و ماشین، خرابی ماشین و زمان دسترسی به کارها با هدف کمینهسازی زمانهای زودکرد و دیرکرد وزنی بررسی میشود. در ادامه بهمنظور مرور ادبیات تحقیق زمانبندی جریان کارگاهی منعطف، تحقیقات مرتبط با مسأله مورد بررسی این تحقیق به تفکیک محدودیتها و تابع هدف مسأله در بخشهای جداگانهای آدرسدهی میشوند.
2-4. زمان نصب وابسته به توالی کارها
زمان نصب ماشین نمایانگر عملیاتی میباشد که به منظور آمادهسازی یک ماشین برای پردازش کارها بر روی آن صورت میپذیرد. عملیاتی نظیر تنظیم و اصلاح ابزارها، نصب جیگها و فیکسچرها، تمیزکاری و … از این قبیل محسوب میشوند. در ادبیات تحقیق مسائل زمانبندی، زمان نصب ماشین برای مدتها نادیده و یا جزئی از زمان پردازش کارها در نظر گرفته میشد. این وضعیت شاید در برخی از موارد قابل توجیه باشد اما بسیاری از مسائل زمانبندی نیازمند در نظرگرفتن زمان نصب به صورت مجزا از زمان پردازش میباشند. به طور معمول، مسائل زمانبندی با در نظر گرفتن نصب ماشین به دو دسته کلی تقسیم میشوند: در دسته اول زمان نصب تنها به نوع کاری که بر روی ماشین پردازش میشود بستگی دارد که اصطلاحاً زمان نصب مستقل از توالی نامیده میشود و در دسته دوم زمان نصب علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به کار قبلی که بر روی آن ماشین پردازش شده نیز بستگی دارد و به آن زمان نصب وابسته به توالی اطلاق میشود.
اهمیت تلقی زمان نصب به صورت مجزا از زمانهای پردازش کارها در تحقیقات مختلفی بررسی شده است. الین [18] تأثیر فرآیندهای نصب وابسته به توالی را در افزایش تولید و ورتمن[66] اهمیت آنها را در مدیریت ظرفیت تولید بررسی نمودند. کراجفسکی وهمکارانش[40] فاکتورهایی را که در سیستمهای تولیدی دارای بیشترین تأثیر بر روی عملکرد هستند، بررسی نمودند. نتایج بدستآمده حاکی از آن بود که بدون توجه به نوع سیستم تولیدی مورد استفاده، کاهش همزمان زمانهای نصب و اندازههای انباشته مؤثرترین راه برای کاهش ذخیره انبار و بهبود خدمات مشتری میباشد.
ملاحظه عملیات نصب در صنایع مختلف تولیدی یا خدماتی نظیر الکترونیک، شیمیایی، نساجی، داروسازی، سرامیکسازی، پرردازش اطلاعات و … به چشم میخورد. برونو و داونی[12] یک سیستم کامپیوتری را شرح میدهند که در آن فعالیت کامپیوتری بعدی نیازمند کامپایلری غیر از کامپایلر موجود در حافظه میباشد، یک زمان نصب برای بارگذاری کامپایلر جدید در حافظه به سیستم تحمیل میشود. آندرس و همکارانش[6] یک مسأله تولید گروهی را در صنعت سرامیکسازی بررسی و آن را در سیستم زمانبندی جریان کارگاهی منعطف با محدودیت زمان نصب وابسته به توالی مدلسازی نمودند. آنها خاطرنشان مینمایند که هدف این نوع مسائل کاهش زمانهای نصب به منظور کاهش زمان تولید میباشد. مطالعات مشابهی[10,57,65] در تولید نیمههادیها، صنایع شیمیایی و داروسازی وجود دارد.
در ادامه مهمترین مطالعات صورت گرفته در زمینه مسائل زمانبندی با محدودیتهای زمان نصب وابسته به توالی در هر کدام از محیطهای کارگاهی تک ماشینه،جریان کارگاهی و ماشینهای موازی به طور جداگانه بررسی میشوند.
2-4-1. مسائل تکماشینه
انواع مدلها در دنیای واقعی در حیطه کار زمانبندی وجود دارد، که یکی از این مدلها، مدل برنامهریزی تولید تکماشینه است. در این مدل تنها یک ماشین (منبع سرویس دهنده) در دسترس است و کارها (محصولات) باید روی آن ماشین پردازش شوند. به عبارت دیگر، ماشین در هر لحظه قادر است تنها یکی از کارها را پردازش کند.
مسائل تک ماشینه با محدودیت زمان نصب ماشین وابسته به توالی کارها و تابع هدف کمینهسازی زمان تکمیل کار بیشینه، معادل کمینهسازی زمان نصب کل میباشند و معمولاً از این نوع مسائل با عنوان مسأله فروشنده دورهگرد یاد میشود. در یکی از اولین تحقیقات گلیمور و گوموری[25] مسأله تکماشینه را با تابع هدف هزینه نصب کل و محدودیت زمان نصب ماشین وابسته به توالی کارها مدلسازی و حل نمودند. بورستل[13] برای یک تابع هزینه شامل زمان نصب کل یک روش حل ابتکاری را بکار گرفتهاست که در آن از الگوریتم شاخه و کران به عنوان رویه جستجو استفاده شده است. بیانکو و همکارانش[10] در مسألهای با تابع هدف زمان تکمیل کار بیشینه و محدودیت زمان آزادسازی کارها و زمان نصب با استفاده از برنامهریزی خطی آمیخته فرمولسازی نموده و یک روش ابتکاری برای حل آن ارائه نمودند. کیم و همکاران[39] و تان و ناراسیمهان[59] به ترتیب یک روش ترکیبی با استفاده از شبکههای عصبی و تبرید شبیهسازی شده برای بهینهسازی زمان تأخیر کل وزنی ارائه نمودند که در آنها زمان محاسباتی سایر الگوریتمهای موجود در ادبیات تحقیق به چالش کشیده شدهاست.
روبین و راگتز [51] یک روش جستجو با استفاده از الگوریتم ژنتیک برای مسألهای با محدودیت زمان نصب و تابع هدف زمان دیرکرد کل ارائه نمودند. ونگ و ونگ[64] مسأله مشابهی را با اختصاص هزینه به زمان دیرکرد و زودکرد و همچنین زمان نصب مجموع، با استفاده از یک الگوریتم ژنتیک ترکیبی حل نمودند و به جوابهای بهینه با کیفیت بهتر نسبت به الگوریتمهای ژنتیک کلاسیک دست یافتند. ارن و گونر[17] مسأله را با تابع هدف زمان تکمیل کار وزنی کل به علاوه زمان دیرکرد کل بررسی نمودند. آنها برای مسأله یک مدل برنامهریزی عددصحیح طراحی نموده و با استفاده از یک روش ابتکاری ساده یک جواب اولیه برای الگوریتم جستجوی ممنوع خود تولید کردند.
در جدیدترین تحقیقات صورت گرفته در مسائل تکماشینه با محدودیت زمان نصب، آرویو و همکارانش[7] سه الگوریتم چندهدفه بر مبنای روش جستجوی همسایگی متغیر را برای حل مسألهای با تابع هدف زمانهای زودکرد و دیرکرد وزنی مقایسه نمودند. آنها دو رویه شمارشی برای بهبود روش جستجوی همسایگی متغیر ارائه نمودند و جوابهای بدستآمده از این روش را بهبود بخشیدند.
سیود و همکارانش[56] ترکیبی از الگوریتم ژنتیک، الگوریتمهای تکاملی چند هدفه و الگوریتم کلونی مورچگان را برای حل مسألهای با تابع هدف زمان تأخیر کل بکار گرفتند. نتایج محاسباتی در این تحقیق کارایی الگوریتم ترکیبی ارائه شده نسبت به بسیاری از روشهای موجود در تحقیقات دیگر را نشان میدهد.
در جدول(2-1) خلاصهای از مطالب ارائه شده در این بخش نمایش داده شده است.
جدول2-1. مسائل تکماشینه با محدودیت زمان نصب ماشین
رویکردها توابع ومحدودیتها نویسندگان
برنامهریزی عددصحیح TST گیلمور و گوموری
روش ابتکاری بر مبنای الگوریتم شاخه و کران TST بروستل
برنامهریزی صفر و یک
TSC, TST تاها
برنامهریزی عددصحیح آمیخته Cmax (rj)بیانکو و همکاران
الگوریتم شاخه و کران Lmax(Prec)اوزوی و همکاران
روش ترکیبی بر مبنای شبکههای عصبی مصنوعی و قواعد توزیع WjTjکیم و همکاران
الگوریتم تبرید شبیه سازی شده WjTj, TSC تان و ناراسیمهان
الگوریتم ژنتیک
Tjروبین و راگتز
برنامهریزی عددصحیح آمیخته f(WjTj, WjEj, TSC)
کیت و همکاران
الگوریتم ژنتیک ترکیبی f(Tj, Ej, TST) ونگ و ونگ
الگوریتم جستجوی ممنوع
λCj+(1-λ)Tjارن و گونر
روش جستجوی همسایگی متغیر
WjEj+W’jTjآریو و همکاران
ترکیبی از الگوریتم ژنتیک، الگوریتمهای تکاملی چند هدفه و الگوریتم کلونی مورچگان
Tjسیو و همکاران
2-4-2. مسائل ماشینهای موازی
در ادبیات تحقیق زمانبندی ماشینهای موازی الگوریتمهای ابتکاری و فراابتکاری مختلفی به چشم میخورد که بخش زیادی از آن به ماشینهای موازی یکسان و یکنواخت مربوط میشود. گوینت و داساچوی[28] مسأله زمانبندی ماشینهای موازی یکسان با محدودیت زمان نصب وابسته به توالی با تابع هدف زمان پایان کار ماکسیمم با استفاده از یک روش ابتکاری بر مبنای روش مجارستانیرا بررسی نمودهاند.
کیم و شین[38] یک الگوریتم جستجوی ممنوع را برای مسأله مشابهی با تابع هدف زمان تأخیر ماکسیمم ارائه کردند. این الگوریتم تعداد جستجوها را بدون حذف جوابها به طور قابل ملاحظهای کاهش میدهد. همچین، فاولر و همکارانش[22] یک الگوریتم ژنتیک ترکیبی را در مسأله مشابهی برای توابع هدف مختلف شامل زمان پایان کار بیشینه، زمان تکمیل کار وزنی کل و زمان دیرکرد وزنی کل بکار گرفتند. این الگوریتم کارها را به ماشینها اختصاص میدهد و از قوانین توزیع برای زمانبندی ماشینها استفاده میکند. نتایج محاسباتی الگوریتم برای هر سه نوع معیار بهینهسازی ذکر شده، عملکرد بهتر آن را نسبت به الگوریتمهای قبلی نشان میدهد.
با وجود مطالعات فراوان صورت گرفته در زمینه ماشینهای موازی یکسان، مسائل زمانبندی ماشینهای موازی نامرتبط کمتر مورد توجه قرار گرفتهاند. این موضوع با در نظر گرفتن محدودیت زمان نصب ماشین بیش از پیش به چشم میآید. در ادامه تعدادی از مهمترین تحقیقات ارائه شده در این زمینه آدرسدهی میشوند:
ژو و هیدی[67] مسأله زمانبندی ماشینهای موازی نامرتبط را با محدودیت زمان نصب وابسته به توالی کارها و تابع هدف مجموع زمانهای دیرکرد و زودکرد وزنی ارائه کردند. آنها یک مدل برنامهریزی عددصحیح برای این مسأله پیشنهاد مینمایند که به اندازه نه کار و سه ماشین در زمان محسباتی معقول به جواب بهینه میرسد.
ونگ و همکاران[65] مسأله را با تابع هدف زمان پایان کار وزنی کل آدرسدهی نمودند. آنها هفت روش ابتکاری ساده را از طریق بررسی نتایج محاسباتی با یکدیگر مقایسه نموده و یکی از آنها را به عنوان بهترین روش انتخاب مینمایند. این روش هریک از کارها را بر اساس کوچکترین نرخ زمان پردازش به علاوه زمان نصب نسبت به وزن کار در تابع هدف به ماشینها اختصاص میدهد. آکیول و همکارانش[2] با استفاده از شبکههای عصبی مصنوعی و روش تابع جریمه به حل مسألهای با تابع هدف زمانهای زودکرد و دیرکرد وزنی پرداختند. نتایج بدستآمده نشان میدهد که این روش به یک جواب بهینه مناسب دست مییابد بطوریکه انگیزه کاربرد آن در مسائل با اندازه بزرگتر را ایجاد میکند.
در جدول(2-2) خلاصهای از مطالب ارائه شده در این بخش نمایش داده شده است.
جدول2-2. مسائل ماشینهای موازی با محدودیت زمان نصب ماشین
رویکردها توابع ومحدودیتها نویسندگان
یک روش ابتکاری بر مبنای روش مجارستانی P| STsd|Cmaxگوینت و داساچوی
الگوریتم جستجوی ممنوع P| STsd|Lmaxکیم و شین
الگوریتم ژنتیک P| STsd , rj|Cmax ,WjCj,WjTjفاولر و همکاران
برنامهریزی عددصحیح آمیخته R | STSD, rj|WjEj+WjTjژو و هیدی
برنامه ریزی خطی R| STsd|WjCjونگ و همکاران
شبکه عصبی مصنوعی R| STsd|ejEj+tjTjآکیول و همکاران
تبرید شبیهسازی شده R| STsd, dj |Tjچن
2-4-3. مسائل جریان کارگاهی:
در یک مسأله جریان کارگاهی m ماشینه، تعداد m مرحله عملیات به صورت متوالی بر روی کارها صورت میگیرد. هر کدام از کارها بر روی همه ماشینها با توالی یکسان پردازش میشوند. در مسائل جریان کارگاهی منعطف حداقل در یکی از مراحل بیش از یک ماشین برای پردازش کارها وجود دارد و در واقع در این مرحله خاص، یکی از انواع مختلف مسائل ماشینهای موازی به وقوع میپیوندد.
مسأله جریان کارگاهی برای اولین بار توسط جانسون[36] با دو ماشین و تابع هدف زمان تکمیل کار بیشینه بررسی شد. تمامی مدلهای موجود در تحقیقات بعدی توسعه این مدل بشمار میآیند. در مسائل کلاسیک یک بافر نامحدود که کارها روی ماشینها یا در بین دو ماشین متوالی در حال انتظار باشند، مفروض است. با این وجود در مسائل جریان کارگاهی بدون انتظار این فرض منظور نمیشود و کارها بدون وقفه از ابتدا تا انتهای زمان پردازش خود بر روی ماشینها پردازش میشوند [30]. زمانیکه بافر واسطه بین ماشینها وجود ندارد، مسائل بدون بافر به وجود میآیند. مسائل بدون انتظار و مسائل بدون بافر با ماشین در حالتی که زمانهای نصب ماشین جزئی از زمان پردازش کارها هستند، معادل هم میباشند. برای حالت زمان نصب مجزا دو حالت مختلف برای مسائل بدون بافر وجود دارد: در حالت اول تا زمانی که کار جاری ماشین اول را ترک نکند، به کار بعدی اجازه نصب داده نمیشود و در حالت دوم به محض این که پردازش کار جاری بر روی ماشین اول به اتمام برسد، نصب کار بعدی آغاز میشود[3] .
کروین اسوگبو [16] مسأله جریان کارگاهی دو ماشینه را با توجه به معیار زمان تکمیل کار بیشینه و محدودیت زمان نصب وابسته به توالی بر روی ماشین اول و زمان نصب مستقل از توالی بر روی ماشین دوم و بالعکس،آدرسدهی نمودند.آنها با استفاده از زمانبندی جایگشتی به جواب بهینه دست یافتند و همچنین برای این مسأله یک مدل برنامهریزی پویا طراحی نمودند.گوپتا و دارو [29] مسأله مشابهی را با محدودیت زمان وابسته به توالی برای هر دو ماشین بررسی نمودند و خاطرنشان نمودند که مسأله حتی برای حالت یک ماشین با زمان نصب وابسته به توالی در کلاس مسائلStrongly NP-hard قرار میگیرد.ریوس مرکادو و بارد [50] برای مسأله جریان کارگاهی با m ماشین و تابع هدف زمان تکمیل کار بیشینه یک الگوریتم شاخه و کران به همراه حد بالا و پائین و معیار حذف مغلوب ارائه نمودند.
در دهههای اخیر مسائل زمانبندی جریان کارگاهی منعطف توجه بسیاری از محققان را به خود جلب نمودهاست. دلیل این امر را میتوان ماهیت نسبتاً پیچیده این مسائل و کاربرد فراوان آنها در محیط صنعتی دانست [49]. این نوع مسائل با محدودیت زمان نصب ماشین وابسته به توالی در کلاس Np-hard قرار میگیرند [41]. کرز و آسکین [42] با توجه به دشواری حل مسأله با استفاده از برنامهریزی عددصحیح، یک الگوریتم ژنتیک با کلیدهای تصادفی را برای حل مسأله توسعه دادند. آنها حدهای پایین را برای مسأله تولید و از آن برای ارزیابی الگوریتم استفاده نمودند. جانگواتاکی و همکارانش [37] مسأله را در حالت ماشینهای نامرتبط و با تابع هدف مجموع وزنی تعداد کارهای با تأخیر و زمان تکمیل کار بیشینه مورد توجه قرار دادند.آنها الگوریتمهای ژنتیک و تبرید شبیهسازی شده بکار رفته در مسائل جریان کارگاهی را برای حالت منعطف تطابق دادند و با ارائه نتایج محاسباتی خاطرنشان نمودند که الگوریتم ژنتیک عملکرد مناسبتری نسبت به الگوریتم تبرید شبیهسازی شده از خود نشان میدهد.
در یکی از آخرین تحقیقات صورت گرفته در مسائل جریان کارگاهی منعطف، بهنامیان و همکارانش [9] ترکیبی از الگوریتم ژنتیک و روش جستجوی همسایگی متغیر را برای یک تابع دو هدفه با معیارهای زمان تکمیل کار بیشینه و هزینههای تخصیص منابع بکار گرفتند و کارایی الگوریتم پیشنهادی خود را برای اندازههای بزرگ مسأله نشان دادند.
زندیه و غلامی [47] در زمانبندی جریان کارگاهی منعطف با زمان آمادهسازی وابسته به توالی به منظور کمینهسازی زمان پایان کار ماکسیمم،از الگوریتم ایمنی استفاده نمودهاند.بدین ترتیب که آنها یک الگوریتم فرا ابتکاری مبتنی بر سیستم ایمنی توسعه دادند و برای ارزیابی این الگوریتم، دادههایی مطابق با تحقیق کرز و آسکین [42] را تولید و نتایج را با الگوریتم پیشنهادی خود مقایسه نمودند. جدول (2-3) خلاصهای از آنچه که در این بخش عنوان شد را نمایش میدهد.
جدول2-3. مسائل جریان کارگاهی با محدودیت زمان نصب ماشین
رویکردها توابع و محدودیتها نویسندگان
برنامهریزی پویا و زمانبندی جایگشتی F2| STsd|Cmaxکروین و اسوگبو
برنامهریزی عددصحیح F2| STsd|Cmaxگوپتا و دارو
الگوریتم شاخه و کران Fm| STsd|Cmaxمرکادو و برد
الگوریتم ژنتیک با کلیدهای تصادفی FFm| STsd|Cmaxکروز و آسکین
الگوریتم سیستم ایمنی FFm| STsd|Cmaxزندیه و همکاران
الگوریتم ژنتیک و الگوریتم تبرید شبیهسازی شده FFm| STsd|λCmax+(1-λ)Ujجانگواتانکیت و همکاران
الگوریتم تبرید شبیهسازی شده و روش جستجوی محلی FFm| STsd|(Cj,Tj)نادری وهمکاران
الگوریتم ژنتیک و روش جستجوی همسایگی متغیر FFm| STsd|Cmax,f(ST) بهنامیان و همکاران
2-5. دسترسی محدود به ماشینها
مسائل زمانبندی با محدودیت دسترسی محدود به ماشینها با عناوینی چون زمانبندی با محدودیت مجموعههای پردازشی، محدودیت دسترسی و همچنین دسترسی محدود به ماشینها ارائه میشوند[44] . در این مسائل به هریک از کارها یک زیر مجموعه از مجموعه ماشینها با عنوان مجموعه پردازشی نسبت داده میشود بطوریکه هر کار تنها بر روی ماشینهای موجود در مجموعه پردازشی خود میتواند پردازش شود. در یک نگرش کلی به محدودیت دسترسی محدود به ماشینها، هر کدام از مجموعههای پردازشی مربوط به وضعیتی میباشد که در آن کارها دارای ویژگیهایی هستند که تنها بخشی از ماشینها قادر به پردازش آنها میباشند. وایراکتاراکیس[62] یکی از این نوع مسائل را به منظور مدیریت بازدهی اتاقهای عمل بیمارستان مدلسازی نمودند. یک اتاق عمل معمولاً با تجهیزات مدرنی با ارزش میلیونها دلار تجهیز میشود. با توجه به میزان تجهیزات موجود، هر اتاق تنها برای بخشی از بیماران قابل دسترسی است و کمینهسازی زمان پایان کار بیشینه بهرهوری اتاقهای عمل را بهبود میبخشد. گلاس و کلرر [26] مسأله تخصیص پردازندههای یک رایانه به برنامههای کاربردی را به صورت یک مدل زمانبندی با مجموعههای پردازشی ارائه نمودند.پردازندهها دارای سرعت یکسان و ظرفیت حافظه متفاوت هستند.هر کدام از برنامهها برای اجرا به میزان مشخصی از حافظه پردازنده نیاز دارند و بدین ترتیب تنها توسط پردازندههای محدودی میتوانند پردازش شوند.
لی و لیونگ [43] زمانبندی ماشینهای موازی نامرتبط را با محدودیت دسترسی محدود به ماشینها با تمرکز بر روی تابع هدف پایان کار بیشینه بررسی نمودند. لوگندران و سوبر [45] یک الگوریتم ابتکاری بر مبنای الگوریتم جستجوی ممنوع را در مسأله مشابهی با تابع هدف زمان دیرکرد وزنی کل بکارگیری و عملکرد آن را به صورت تجربی ارائه نمودند.
رویز و ماروتو [52] شکاف بین مفهوم تئوری و عملی مسأله زمانبندی جریان کارگاهی را تحلیل نموده و برای این مسأله با فرض ماشینهای موازی نامرتبط در هر مرحله، محدودیتهای زمان نصب وابسته به توالی و دسترسی محدود به ماشین، متاهیورستیکی به شکل الگوریتم ژنتیک ارائه کردند. رویز و استاتزل [53] یک مدل ریاضی و الگوریتمی ابتکاری برای جریان کارگاهی منعطف با تابع هدف زمان پایان کار ماکسیمم و زمان دیرکرد وزنی با فرض ماشینهای موازی نامرتبط در هر مرحله، محدودیتهای زمان دسترسی به ماشین و دسترسی محدود به ماشین ارائه کردند. شین و همکاران [55] مسأله زمانبندی n کار مستقل بر روی m ماشین یکسان با محدودیتهای زمان دسترسی و دسترسی محدود به ماشین با تابع هدف کمینهسازی ماکسیمم تأخیرها مورد بررسی قرار دادند که در آن ماشین ممکن است به دلیل خرابی در دسترس نباشد.
2-6. خرابی ماشین
علی اللهوردی و جان میتنتال [4] مسأله زمانبندی جریان کارگاهی دو ماشینه با هدف کمینهسازی زمان پایان کار کل و محدودیت خرابی تصادفی ماشین را بررسی کردند.آنها ابتدا نشان دادند که کارها باید با توالی یکسانی روی هر ماشین پردازش شوند و پس از ارائه یک معیار کاهش برای برای بهینهسازی تابع هدف با احتمال 1,نشان دادند که تحت شرایط مناسب الگوریتم جانسون به طور احتمالی زمان تکمیل کار کل را کمینه میکند.
جیان زیونگ و لی نینگ زینگ [34] زمانبندی قوی مسأله کارکارگاهی منعطف چند هدفه با خرابی ماشین تصادفی را مورد بررسی قرار دادند.آنها دو هدف زمان پایان کار و قوت را همزمان در نظر گرفتند و یک الگوریتم تکاملی چند هدفه ارائه دادند.جان برگ و کوین گلازبروک [35] تأثیرات خرابی ماشین روی زمانبندی احتمالی را بررسی نمودند و یک استراتژی برای ارزیابی این تأثیرات ارائه دادند.
علی اللهوردی [5] به بررسی مسأله زمانبندی جریان کارگاهی دو ماشینه با تابع هدف کمینهسازی ماکسیمم تأخیر و محدودیت خرابی تصادفی ماشین پرداخت و نشان داد که تحت شرایط مناسب سیاست بزرگترین زمان پردازش(LPT)وقتیکه فقط اولین ماشین دارای محدودیت خرابی باشد با احتمال 1 تابع هدف را کمینه میکند.همچنین نشان داد هنگامیکه فقط دومین ماشین دارای چنین محدودیتی باشد سیاست کمترین زمان پردازش (SPT) تابع هدف را بهینه میکند.
نصر الحینای و المکاوی [48] زمانبندی مسأله کار کارگاهی منعطف پایدار و نیرومند با خرابی ماشین تصادفی را بررسی کردند.آنها یک الگوریتم ژنتیک مختلط دو مرحلهای(HGA) برای تولید زمانبندی پیشگویانه ارائه دادند.
چانگ یی لی و چن سین لین [15] زمانبندی مسأله تک ماشینه را با فرض زمان پردازش قطعی و خرابی ماشین مطالعه کردند.آنها این مسأله را با تابع هدفهای متفاوتی مانند زمان پایان کار پیش بینی شده,زمان تکمیل پیشبینی شده کل,ماکسیمم تأخیر پیشبینی شده و تأخیر ماکسیمم پیشبینی شده را به ترتیب بررسی نمودند.
علی اللهوردی و جان میتنتال [1] مسأله زمانبندی جریان کارگاهی با تابع هدف کمینهسازی زمان پایان کار کل و میانگین زمان جریان و محدودیت خرابی ماشین را بررسی کردند و نشان دادند توالی بهینه برای تابع هدف زمان پایان کار کل هنگامی حاصل میشود که فقط یکی از دو ماشین دارای محدودیت خرابی باشد و برای تابع هدف میانگین زمان جریان وقتیکه هر دو ماشین دارای محدودیت خرابی تصادفی باشند,توالی بهینه بدست میآید.
احرام سفری و سید جعفر سجادی [20] یک روش مختلط برای زمانبندی جریانهای کارگاهی با هدف کمینه سازی زمان تکمیل کل پیشبینی شده با فرض خرابی ماشین و محدودیت نگهداری بر مبنای وضعیت ارائه کردند.آنها یک استراژی نگهداری بر مبنای وضعیت را در نظر گرفتند که میتواند در بیشتر صنایع استفاده شود و الگوریتمی ارائه کردند که برای حالت جریان کارگاهی جمعناپذیر طراحی شده,بطوریکه پردازش کارها بعد از نگهداری پیشگیرانه از ابتدا شروع میشود.آنها یک الگوریتم مختلط بر اساس الگوریتم ژنتیک و شبیهسازی تبرید ارائه دادند و از روش تاگوچی برای تنظیم پارامتر استفاده نمودند.
لیائو و چن [14] یک کارخانه نساجی که خرابی ماشین در آن بهکثرت اتفاق میافتد را مطالعه نمودند و هیوریستیکی برای ایجاد زمان راهاندازی طولانیتر(یا برابر,زمان بیکاری طولانیتر) برای کاهش نرخ خرابی ماشین توسعه دادند.آنها دادههای حقیقی کارخانه را برای اثبات اثربخشی هیوریستیک استفاده کردند و عملکرد آن را با الگوریتم شاخه و کران مقایسه نمودند.
2-7. زمانهای زودکرد و دیرکرد
با بکارگیری موفقیتآمیز مفاهیم تولید بهموقع در سیستمهای تولیدی، زمانهای زودکرد کارها همانند زمانهای دیرکرد در کانون توجه قرار گرفتند. در یک محیط زمانبندی بر مبنای تولید به موقع کارهایی که پردازش آنها زودتر از موعد تحویل به اتمام رسیده باشد، تا رسیدن موعد تحویل در انبار محصولات نهایی نگهداری میشوند، در حالی که کارهایی که پس از موعد تحویل به اتمام رسیدهاند، موجب عدم رضایت مشتری از تأخیر در تحویل میشوند. زودکرد و دیرکرد هر کدام از کارها میتواند میزان اهمیت متفاوتی نسبت به سایر کارها داشته باشد و با اختصاص ضرایب وزنی به زورکرد و دیرکرد کارها در معیارهای بهینهسازی این میزان اهمیت ملاحظه میشود.
در ادامه مهمترین تحقیقات صورت گرفته در زمینه زمانبندی ماشینهای موازی با معیار بهینهسازی زمانهای زودکرد و دیرکرد بررسی میشود:
در یکی از اولین تحقیقات، هال [31] معیار زمانهای زودکرد و دیرکرد را در مسأله ماشینهای موازی یکسان با موعد تحویل مشترک برای تمام کارها بکار برد. الگوریتم پیشنهادی وی ماشینی که پردازش کار را به اتمام رسانده انتخاب و کاری که بیشترین زمان پردازش را در بین کارهای باقیمانده دارد به آن اختصاص میدهد. با این روند تمامی کارها به ماشینها اختصاص مییابند. امونز [21] این رویکرد را در مسألهای با وزنهای متفاوت زمانهای زودکرد و دیرکرد ارائه نمودهاست. در این تحقیق یک وزن مشترک برای زمانهای دیرکرد و یک وزن مشترک برای زمانهای زودکرد تمامی کارها منظور شدهاست. ژو و هیدی [67] مسأله زمانبندی ماشینهای موازی نامرتبط با وزنهای زودکرد و دیرکرد و موعدهای تحویل متمایز را با روش برنامهریزی عددصحیح مدلسازی نمودند. مدل ارائه شده توسط آنها جوابهای بهینه لازم برای اعتبارسنجی الگوریتمهای تقریبی در مسائل مشابه را ارائه میکند. بهنامیان و همکارانش [9] یک الگوریتم ترکیبی را به منظور بهینهسازی یک تابع چندهدفه شامل زمان تکمیل بیشینه و مجموع زمانهای زودکرد و دیرکرد ارائه نمودند. نتایج محاسباتی الگوریتمهای پیشنهادی آنها حاکی از آن است که این الگوریتم جوابهای بهینه پارتو مناسبی تولید میکند. توکلیمقدم و همکارانش [61] یک الگوریتم ژنتیک را در مسألهای با تابع هدف چندمعیاره شامل زمانهای زودکرد و دیرکرد وزنی به علاوه هزینه نصب ماشینها بکار گرفتند و نتایج محاسباتی را برای تعدادی مسأله آزمایشی ارائه نمودند. لیتاو و همکارانش [60] مسأله ماشینهای موازی نامرتبط با آثار خرابی و فعالیتهای نگهداری را برای کمینهسازی مجموع هزینههای زودکردها و دیرکردها بطور همزمان بررسی کردند. هدف آنها تعیین همزمان موقعیت بهینه فعالیتهای نگهداری، موعد تحویل مشترک بهینه برای همه کارها و زمانبندی بهینه برای کمینهسازی مجموع هزینههای زودکردها و دیرکردها میباشد. برای تعداد ثابت ماشینها، یک الگوریتم با زمان حل چند جملهای ارائه کردند.
2-8. جمعبندی
در این فصل ابتدا مسائل زمانبندی با استفاده سیستم استاندارد سهنمادی طبقهبندی شدند. پس از آن به معرفی ادبیات تحقیق زمانبندی ماشینهای موازی پرداخته شد. در ادامه به منظور مرور ادبیات مرتبط با مسأله مورد بررسی این تحقیق، مطالعات صورت گرفته به تفکیک محدودیتها و تابع هدف مسأله در بخشهای جداگانهای بررسی شدند. با توجه به بررسی انجام شده، تحقیق حاضر از دو جنبه صورت مسأله و روش حل نسبت به تحقیقات پیشین دارای نوآوری میباشد.

فصل سوم
مدل ریاضی
و
الگوریتمهای پیشنهادی
3-1. مقدمه
فرموله کردن مسأله زمانبندی، با روشهای ریاضی جهت کنترل و بهینه کردن کارایی مسائل دنیای واقعی، درک موقعیت مسأله و مشخص کردن پیچیدگی مسأله مورد نظر، همواره مورد توجه محققان این علم بوده است. لذا ما باید به دنبال مدلی باشیم که کارایی سیستم تولیدی را بالا ببریم. ارائه مدلی که بتواند اهداف مورد نظر را برآورده سازد میتواند سبب کاهش قیمت، تنوع محصولات تولید شده، دقت و کیفیت بالا در سیستمهای تولیدی شود. رویکرد برنامهریزی عددصحیح به عنوان یک روش دقیق ظرفیت عملکرد محدودی در بهینهسازی مسائل زمانبندی در زمان محاسباتی معقول دارد. از سوی دیگر، بیشتر مسائل موجود در محیطهای صنعتی اندازه بزرگتری نسبت به ظرفیت محاسباتی مدلهای برنامهریزی عدد صحیح دارند. با این وجود، این مدلها جوابهای بهینه لازم برای توسعه و اعتبارسنجی عملکرد رویکردهای ابتکاری و فرا ابتکاری گوناگون را فراهم مینمایند.
در این فصل مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن محدودیتهای دسترسی به ماشین، زمان نصب وابسته به توالی وماشین، خرابی ماشین و زمان دسترسی به کار با هدف کمینهسازی زمانهای زودکرد و دیرکرد وزنی کارها معرفی میشود سپس یک مدل برنامهریزی عدد صحیح جدید برای مسأله ارائه و اعتبار آن با استفاده از مسائل آزمایشی موجود در ادبیات تحقیق سنجیده میشود. بعد از معرفی مدل ریاضی پیشنهادی، جهت آشنایی کلی با الگوریتمهای ژنتیک، رقابت استعماری و کاربردهای آنها در توالی عملیات تولید، به تشریح اصول زیربنایی این الگوریتمها پرداخته میشود.
3-2. تعریف مسأله
مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن محدودیتهای دسترسی به ماشین، زمان نصب وابسته به توالی وماشین، خرابی ماشین و زمان دسترسی به کار با هدف کمینه سازی زمانهای زودکرد و دیرکرد وزنی کارها به شرح زیر ارائه میگردد:
یک مجموعه از n کار متمایز N={1,2,…,n} در M مرحله متوالی M={1,2,…,m} پردازش میشوند. در هر مرحله t ,tϵM یک یا چند ماشین موازی یکسان Mt={1, 2,…,mt} داریم به طوریکه در هر لحظه، هر کار تنها بر روی یک ماشین پردازش میشود و هر ماشین در هر لحظه قادر به پردازش تنها یک کار میباشد. هر یک از کارها در هر مرحله بر روی زیرمجموعهای از ماشینها بصورت Mj ⪿ Mi میتواند پردازش شود. این زیرمجموعهها اصطلاحاً مجموعههای پردازشی نامیده میشوند و تعداد n مجموعه پردازشی در مسأله وجود دارد. قبل از آغاز پردازش یک کار بر روی یک ماشین به منظور آمادهسازی آن ماشین برای پردازش آن کار عملیاتی انجام میشود که از آن با عنوان عملیات نصب ماشین یاد میشود و به دوره زمانی که در آن عملیات نصب ماشین انجام میشود زمان نصب ماشین اطلاق میشود. این زمان به نوع کاری که بر روی ماشین پردازش میشود، به نوع کار قبلی پردازش شده و همچنین به نوع ماشین بستگی دارد و اصطلاحاً به آن زمان نصب وابسته به توالی کارها اطلاق میشود، و اگر کار به عنوان اولین کار بر روی ماشین پردازش شود زمان نصب وابسته به ماشین اطلاق میشود. هر یک از ماشینها بعد از پردازش یک کار ممکن است خراب شود و زمانی برای تعمیر آن لازم است. اصطلاحاً خرابی ماشین نامیده میشود. هر کار زمان دسترسی مستقلی دارد، امکان پردازش هر کار قبل از زمان دسترسی آن کار امکان پذیر نمیباشد. هر کار با در نظر گرفتن موقعیت آن در توالی پردازش کارها بر روی ماشین مربوطه پس از سپری شدن زمان نصب، زمان تعمیر احتمالی، زمان دسترسی به کار و زمان پردازش تکمیل میشود.
ممکن است کارها دارای موعد تحویل متمایز باشند و میزان انحراف زمان تکمیل کارها از موعدهای تحویل به صورت زودکرد یا دیرکرد زمانی محاسبه میشوند. به زمانهای زودکرد یا دیرکرد هر کدام از کارها وزنهای به صورت ضرایب متمایز نسبت داده میشود که بیانگر زمانهای زودکرد و دیرکرد میباشند. مجموع این زمانها به عنوان معیار بهینهسازی محسوب شده و در نتیجه تابع هدف مسأله کمینهسازی هزینههای زودکرد و دیرکرد کارها میباشد.
3-3. مفروضات مسأله
در مسأله ارائه شده در این تحقیق فرض های زیر در نظر گرفته می شوند:
• کارها با توجه به زمان دسترسی خود در دسترس قرار می گیرند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
• کارها با توجه زمان آمادهسازی خود آماده می شوند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
• زمان نصب هر کدام از کارها وابسته به توالی آنها بر روی ماشین هاست.
• هر ماشین در هر لحظه حداکثر می تواند یک کار را پردازش کند.
• هر کار در هر لحظه حداکثر می تواند بر روی یک ماشین پردازش شود.
• ماشین ها به طور پیوسته در دسترس نیستند.
• برش کار به این مفهوم که پردازش یک کار قبل از پایان زمان پردازش آن قطع شود ودر زمانهای بعدی بر روی ماشینهای دیگر پردازش آن ادامه یابد، مجاز نمی باشد.
3-4. مدل پیشنهادی
در این بخش مدل ریاضی پیشنهادی با رویکرد برنامهریزی عددصحیح برای مسأله مورد بررسی ارائه میگردد. پیش از ارائه مدل به شرح اندیسها و پارامترهای ورودی، متغیرهای تصمیمگیری، محدودیتها و تابع هدف آن پرداخته میشود.
3-4-1. اندیسها (نمادها)
i: اندیس برای ماشینها
j: اندیس برای کارها
l: اندیس برای کارها
: t اندیس برای مرحلهها
3-4-2. پارامترهای ورودی
: n تعداد کارها
mt: تعداد ماشینها در هر مرحله t
dj: موعد تحویل کار نوع j
:Pil زمان پردازش کار نوع l بر روی ماشین نوع i
: rj زمان دسترسی به کار نوع j
αj: هزینه زودکرد کار نوع j
βj: هزینه دیرکرد کار نوع j
:Mijtاگر امکان پردازش کار نوع j بر روی ماشین نوع i در مرحله t وجود داشته باشد 1، در غیر این صورت 0
:Sjlt زمان نصب کار نوع l هنگامیکه بعد از کار نوع j در مرحله t بر روی یکی از ماشینها پردازش میشود.
:chilt زمان نصب کار نوع l هنگامیکه به عنوان اولین کار بر روی ماشین نوع i در مرحله t پردازش میشود.
avit : زمان دسترسی ماشین نوع i در مرحله t
: pdj t احتمال خرابی ماشین بعد از پردازش کار نوع j در مرحله t
Rt: مدت زمان لازم برای تعمیر ماشینها در هر مرحله t
M’ : یک عدد صحیح مثبت بزرگ
3-4-3. متغیرهای تصمیم گیری
Xijt: اگر کار نوع j در مرحله t بر روی ماشین نوع i قرار گیرد برابر 1، و در غیر این صورت 0 می باشد.
Yijlt: اگر کار نوع j در مرحله t قبل از کار نوع l بر روی ماشین نوع i قرار گیرد برابر 1، و در غیر این صورت 0 می باشد.
Cjt: زمان تکمیل کار نوع j در مرحله t
Clt: زمان تکمیل کار نوع l در مرحله t
Ej: زمان زودکرد کار نوع j
Tj: زمان دیرکرد کار نوع j
متغیرهای مدل E , C و T دارای مقادیر صحیح نامنفی و متغیر X و Yاز نوع صفر و یک میباشند.
3-4-4. تابع هدف
j=1nαjEj+βjTj تابع هدف مدل برابر مجموع زمانهای زودکرد و دیرکرد وزنی کارها میباشد. در این فرمول مقادیر متغیرهای تصمیم گیری Ej و Tj برای کار نوع j به ترتیب از روابط (3-1) و (3-2) بدست می آیند.
(3-1) Ej=max0,dj-Cjt
Tj=max 0, Cjt-dj (3-2)
3-4-5. محدویتها
i=1mtXijt=1 ∀ t,j ●
این محدودیت بیانگر آن است که هر کار در هر مرحله t بر روی یک و تنها یک ماشین میتواند پردازش شود.
● l=1nYijlt ≤ Xijt ∀ i,j,t j≠lj=0nYijlt = Xilt ∀ t,i,l l≠j ●
این دو محدودیت به همراه هم تضمین میکنند که در هر مرحله t هر کار بلافاصله قبل و بلافاصله بعد از تنها یک کار دیگر بر روی ماشین پردازش شود.
● l=1nYi0lt=1 ∀ t,i این محدودیت اولین کاری را که در هر مرحله t بر روی ماشین نوع i پردازش میشود مشخص میکند.
Xijt≤ Mijt ∀ t,i,j●
این محدودیت دسترسی محدود به ماشینها را معرفی میکند. همانطورکه در بخش پارامترهای ورودی مدل بیان شد، اگر امکان پردازش کار نوع j بر روی ماشین نوع i در مرحله t وجود داشته باشد مقدار پارامتر Mijtیک در غیر این صورت صفر را میگیرد. امکان پردازش کار نوع j بر روی ماشین نوع i در مرحله t با توجه به مجموعه پردازشی کار نوع j یعنی Mjtمشخص میشود. Mjtزیر مجموعهای از مجموعه ماشینها Mt و شامل ماشینهای میباشد که میتوانند کار نوع j را پردازش کنند. به این ترتیب این محدودیت مدل را مقید میسازد که برای تخصیص ماشین نوع i به کار نوع j و به تبع آن تخصیص مقدار یک به متغیر تصمیمگیری Xijt، Mijtرا که جز پارامترهای ورودی مدل میباشد را نیز بررسی نماید و در صورتی این تخصیص صورت میپذیرد که مقدار Mijtنیز همانند Xijtیک باشد.
● ∀ t,i,j,l Clt- Cjt≥ Sjlt+ Pil t* Yijlt+ pdj t*Rt+ Yijl t- 1*M Cjt≥0 ∀ t,j ●
Clt- Clt-1≥i=1mtj=1n Yijlt*Sjl t+i=1mtchil* Yi0lt+i=1mtj=1nPil*Yijlt+i=1mtPil*Yi0lt+ j=1npdj* Rt*Yijlt ∀ t,l j≠l●
Clt≥i=1mtavit* Yi0lt+ i=1mtchilt* Yi0lt+i=1mtPil*Yi0lt ∀ t,l●
Cj0≥rj ∀ j●
این محدودیتها زمان تکمیل هر کار را مشخص میکنند.
Tj≥ Cjk-dj ∀ j ●
Tj≥0 ∀ j ●
این دو محدودیت زمانهای دیرکرد برای کار نوع j را مشخص میکنند.
Ej≥ dj-Cjk ∀ j●
● Ej≥0 ∀ j این دو محدودیت زمانهای زودکرد برای کار نوع j را مشخص میکنند.
با توجه به مطالب ذکر شده مدل پیشنهادی به صورت زیر ارائه میشود:
Min Z=j=1n(αjEj+βjTj)Subject to:
i=1mtXijt=1 j=1…n, t =1…k (1)
l=1nYijlt≤Xijt i=1…m, j=1…n, t=1…k j≠l (2)
j=0nYijlt = Xilt i=1…m, l=1…n, t=1…k j≠l (3)
l=1nYi0lt=1 i=1…m, t=1…k (4)
Xijt≤ Mijt i=1…m, j=1…n, t =1…k (5)
Clt- Cjt≥ Sjlt+ Pil t* Yijlt+ pdj t*Rt+ Yijl t- 1*M j=1… n, i=1…m, t=1…k (6)
Cjt≥0 j=1… n, t=1…k (7)
Clt- Clt-1≥i=1mtj=1n Yijlt*Sjl t+i=1mtchil* Yi0lt+i=1mtj=1nPil*Yijlt+i=1mtPil*Yi0lt+ j=1npdj* Rt*Yijlt l=1… n, t=1…k, j≠l (8)
Clt≥i=1mtavit* Yi0lt+ i=1mtchilt* Yi0lt+i=1mtPil*Yi0lt l=1…n,t=1…k (9)
Cj0≥rj j=1…n (10)
Tj≥ Cjk-dj j=1…n (11)
Tj≥0 j=1…n (12)
Ej≥ dj-Cjk j=1…n (13)
Ej≥0 j=1…n (14)

3-5. اعتبار سنجی مدل
در این بخش به منظور اعتبار سنجی مدل ارائه شده از مدل ریاضی ارائه شده در مقاله بهنامیان و همکارانش [33] استفاده کردهایم. برای بررسی اعتبار، مدل پیشنهادی و مدل ریاضی ارائه شده توسط بهنامیان و همکارانش در نرم افزار Lingo9 پیاده سازی شدند. مدل ارائه شده توسط آنها برای مسأله زمانبندی جریان کارگاهی منعطف با تابع هدف کمینهسازی مجموع زمانهای زودکرد و دیرکرد کارها میباشد.
به منظور انطباق مدل پیشنهادی با مدل بهنامیان و همکارانش، مقدار وزن زودکرد و دیرکرد کارها در تابع هدف مدل پیشنهادی برابر یک در نظرگرفته میشود. همچنین، مدل بهنامیان و همکارانش محدودیتهای دسترسی محدود به ماشین، زمان نصب وابسته به ماشین، خرابی ماشین و زمان دسترسی به کارها را ندارد،بنابراین در مدل پیشنهادی این محدودیتها برابر صفر در نظر گرفته میشوند.
مسائل زیادی با ابعاد یکسان برای هر دو مدل با استفاده از نرم افزار Lingo9 طراحی گردید و نتایج محاسباتی مقایسه شد که نتیجه این بررسی معتبر بودن مدل پیشنهادی را نشان میدهد. در ادامه یکی از این مسائل طراحی شده با شش کار و سه ماشین در مرحله اول، دو ماشین در مرحله دوم، سه ماشین در مرحله سوم آورده شده است. مقادیر زمانهای پردازش، موعدهای تحویل و زمانهای نصب وابسته به توالی و زمانهای نصب وابسته به ماشین و همچنین محدودیتهای دسترسی به ماشینها برای کارها به ترتیب در جدولهای (3-1)، (3-2)، (3-3)، (3-4) ارائه شدهاند.
جدول3-1. زمان پردازش و موعد تحویل
Jobs J1J2J3J4J5J6زمان پردازش 4 3 3 3 2 2
موعد تحویل 25 34 28 16 16 21
جدول3-2. زمان نصب وابسته به توالی
Jobs J1J2J3J4J5J6J10 3 2 3 0 1
J23 0 1 2 2 1
J3J42
1 2
3 0
2 1
0 3
1 2
3
J50 2 1 0 0 2
J61 0 2 2 2 0
جدول3-3. زمان نصب وابسته به ماشین
Jobs m1m2m3J10 0 1 J21 0 0 J3J41
2 0
1 1
0 J52 1 0 J60 2 1 جدول3-4. دسترسی محدود به ماشین
Jobs m1m2m3m1m2m1m2m3J11 1 1 0 1 1 1 1
J21 1 0 1 1 0 1 1
J31 1 1 0 1 1 1 0
J40 1 1 0 1 0 0 1
J51 1 0 1 0 1 1 1

این نوشته در مقالات ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *