است)
فصل اول
مقدمه و کلیات تحقیق
1-1. مقدمه
زمانبندی[1]، فرآیند تخصیص منابع به فعالیتها با در نظر گرفتن دورههای زمانی مربوط به آنها به منظور بهینهسازی یک یا چند تابع هدف میباشد. این فرآیند به عنوان یک فرآیند تصمیم گیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. زمانبندی کارای فعالیتها زمینهساز بهبود عملکرد سیستمهای تولیدی میباشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار میآید. امروزه، مدیریت منابع موضوع به طور فزاینده مهمی برای سازمانها میباشد و تعیین توالی[2] و زمانبندی یک شکل از تصمیم گیری است که نقش حیاتی در صنایع تولیدی و خدماتی بازی می کند. زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه می کند.
بهطور کلی، منابع، فعالیتها و توابع هدف عناصر کلیدی زمانبندی محسوب میشوند. منابع برحسب قابلیتهای کمی و کیفی خود مشخص میشوند. از سوی دیگر، فعالیتها بر حسب اطلاعاتی از قبیل منابع مورد نیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف میشوند. توابع هدف نیز در برگیرنده هزینه های سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیتها میباشند. تصمیمات عمده در فرآیند زمانبندی شامل بهره برداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمانهای تحویل با موعدهای تحویل[3] تعیین شده میشوند.
در مسائل زمانبندی هدف از یافتن توالی انجام فعالیتها ممکن است متفاوت باشد. تعدادی از اهداف متداول عبارتند از: کمینهسازی زمان تکمیل کل کارها و یا کمینهسازی تعداد کارهایی که دیرکرد دارند. یکی از مهمترین اهداف در بسیاری از صنایع تولیدی تحویل به موقع[4] کالا و خدمات میباشد که در بهدست آوردن سود و یا هزینه های پایینتر نقش دارد. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیطهای تولید متنوع است. تکمیل یک کار زودتر از موعد تحویل ممکن است هزینههایی از قبیل هزینه نگهداری موجودی به تولید کنندگان تحمیل کند، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به پرداخت جریمههای قراردادی به مشتری و کاهش اعتبار تولید کننده میشود. حداقلسازی زودتر و دیرتر یکی از سیاستهای مسائل زمانبندی بهنگام میباشد.
انگیزه بسیاری از توسعهها و پیشرفتهای عملی در حوزه زمانبندی برخاسته از محیطهای صنعتی است و به طور طبیعی در بیان مفاهیم زمانبندی از واژههای بکار رفته در صنعت استفاده میشود. به همین خاطر منابع با عنوان ماشین به کار میروند و به هر کدام از فعالیتها، کار اطلاق میشود بطوریکه کارها اغلب به وسیلهی مجموعه ای از ماشینها در ایستگاههای مختلف کاری با توان مشخص پردازش میشوند.
بطور کلی، مسائل زمانبندی به صورت مسائل بهینهسازی دارای محدودیت بیان میشوند که در آنها به بررسی تصمیمات مربوط به تضمین ماشینها و توالی پردازش کارها پرداخته میشود. در حالتی که تنها یک ماشین موجود است، تعیین توالی پردازش کارها یک برنامه زمانی کامل را تشکیل میدهد. مسائل تکماشینه با وجود سادگی ذاتی، سنگ بنای درک فراگیر مفاهیم زمانبندی را تشکیل می دهند. در مقابل، زمانبندی مسائل چند ماشین شامل سیستمهای موازی، سیستمهای متوالی و سیستمهای ترکیبی میباشد. در سیستمهای موازی، هر یک از کارها با انجام یک عملیات همانند مسائل تکماشینه بر روی یکی از ماشینهای موازی موجود پردازش میشوند و به دنبال آن تخصیص ماشینها به کارها موضوعیت پیدا می کنند. این در حالی است که در سیستمهای متوالی و ترکیبی، کارها با انجام چند عملیات بر روی ماشینها پردازش میشوند و مسائل مربوطه ساختار نسبتاً پیچیدهتری را تجربه می کنند.
در این تحقیق، به بررسی مسأله جریان کارگاهی انعطافپذیر[5] به عنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است، پرداخته میشود. چنانچه ساختار سیستم تولیدی به شکل سری بوده و حداقل در یک مرحله چندین ماشین موازی وجود داشته باشد،در واقع با یک سیستم جریان کارگاهی انعطافپذیر مواجه هستیم که زمانبندی این نوع سیستمهای خطی به دلیل کاربردی بودن آنها در سالهای اخیر در صنعت مورد توجه قرار گرفته است.
1-2. تعریف مسأله
دربرخی از صنایع تولیدی و خدماتی سفارشها تحت عنوان کارها به وسیله مجموعه ای از ماشینها که به صورت سری در ایستگاههای کاری مختلف قرار گرفتهاند با توالی مشخص پردازش میشوند. یعنی کارها مسیر یکسانی را دنبال می کنند و ماشینها به صورت سری، پشت سر هم قرار دارند. وضعیت تعمیم یافتهای از این مسائل یعنی مسأله جریان کارگاهی منعطف میباشد که در هر مرحله (حداقل یکی از مراحل) حداقل دو ماشین بصورت موازی موجود است. در این حالت هر یک از کارها بایستی به ترتیب در هر مرحله توسط یکی از ماشینهای موجود پردازش شده و به مرحله بعد برود.
بیشتر ادبیات نظریه زمانبندی، و به همین دلیل بیشتر درک ما از مسائل زمانبندی، مربوط به محاسبه زمان جریان کل، تعداد کارهایی که تأخیر دارند و تأخیر کل میباشد. معیار مجموع تأخیرها، به طور خاص، به یک روش استاندارد برای اندازه گیری انطباق با تاریخ تحویل کارها تبدیل شده است، با این وجود عواقب کارهایی که زودتر از موعد تحویل، تکمیل میشوند نادیده گرفته شده و تنها آن دسته از کارهایی که دیرکرد دارند، با جریمه مواجه شده اند. اما این معیار با رشد سهم تولید بهنگام شروع به تغییر کرد، با تأکید بر این نکته که زودکرد همانند دیرکرد باید نامناسب در نظر گرفته شود. در یک محیط زمانبندی بههنگام، کاری که زود تکمیل می شود تا تاریخ تحویل آن کار باید در موجودی انبار نگهداری شود، در حالی که اگر یک کار پس از موعد تحویلش اتمام یابد ممکن است در برآوردن نیازهای مشتری اختلال ایجاد کند. بنابراین، یک زمانبندی ایدهآل، زمانبندی است که در آن همه کارها دقیقاً در تاریخهایی که به آنها اختصاص داده شده اتمام یابند. البته، زمانبندی بهنگام شامل مجموعه ای بسیار گستردهتر از اصولی است که مرتبط با موعدهای تحویل میباشد، اما مدلهای زمانبندی با هزینه زودکرد و دیر کرد (E / T) به یک بعد اساسی زمانبندی رویکردهای JIT آدرس دهی میشوند.
مسأله زمانبندی جریان کارگاهی اخیراً در صنعت بطور وسیعی در محیطهای صنعتی مورد استفاده قرار گرفته است، به همین دلیل در 50 سال اخیر به دقت بررسی شده است. مسأله مورد بررسی در این تحقیق، مسأله زمانبندی جریان کارگاهی انعطافپذیر در محیطهای تولید بهنگام میباشد.در برخی از کاربردهای زمانبندی مسأله جریان کارگاهی انعطافپذیر ماشینها دارای سطوح تکنولوژیکی متفاوتی هستند و لزوماً قادر به پردازش هریک از کارهای موجود در مجموعه کارها نمیباشند. در نتیجه، هر کدام از کارها تنها بر روی زیر مجموعهای از مجموعه ماشینها میتوانند پردازش شوند و اصطلاحاً پردازش کارها با دسترسی محدود به ماشینها[6] صورت میپذیرد.
مسائل زمانبندی غالباً به محیطهای کارگاهی میپردازند که در آنها زمان نصب[7] ماشین نادیده گرفته میشود و یا به عنوان بخشی از زمان پردازش کارها تلقی میشود. این نوع محیطهای کارگاهی با این فرض مدلسازی میشوند که زمانهای نصب در مقایسه با زمانهای پردازش کوچک هستند، بنابراین میتوان آنها را نادیده گرفت و یا اینکه زمانهای نصب مستقل از توالی پردازش کارها بر روی ماشینها هستند، در نتیجه میتوان آنها را به زمانهای پردازش اضافه نمود. با این وجود، در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی[8] هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد[6]. در این شرایط، زمان نصب به عنوان بخشی مجزا از زمان پردازش در نظر گرفته میشود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد به نوع کار قبلی که بر روی آن ماشین پردازش شده نیز بستگی دارد.تلقی زمان نصب به صورت مجزا از زمان پردازش در بیشتر تکنیکهای مدیریت تولید نوظهور نظیر تولید بموقع[9]، تکنولوژی گروهی[10] و تولید سلولی[11] مورد استفاده قرار میگیرد. همچنین در بعضی از مسائل ماشینها نیاز به زمان نصب برای پردازش کارها دارند، یعنی اگر یک کار به عنوان اولین کاری باشد که بر روی ماشین پردازش میشود یک زمان نصب وابسته به ماشین[12] مجزا از زمان پردازش برای آن در نظر گرفته میشود. تحقیقات زیادی در مورد مسأله جریان کارگاهی انعطافپذیر با فرض خرابی ماشین[13] خصوصاً هنگامیکه خرابی ماشین به کار انجام شده قبلی روی ماشین بستگی داشته باشد،انجام نشده است[46]. در بعضی از مسائل تمام کارها در ابتدای افق زمانی (لحظه صفر) در دسترس نیستند و زمان دسترسی[14] به هرکار مستقل از کارهای دیگر میباشد.
در این تحقیق، مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن محدودیتهای دسترسی به ماشین، زمان نصب وابسته به توالی و ماشین، خرابی ماشین و زمان دسترسی به کار با هدف کمینهسازی زمانهای زودکرد و دیرکرد وزنی بررسی میشود. یک مدل برنامه ریزی عدد صحیح برای این مسأله پیشنهاد میشود. همچنین چندین روش فرابتکاری[15] برای حل آن ارائه میگردد.
1-3. اهداف تحقیق
هدف ازاجرای این تحقیق طراحی یک مدل ریاضی وحل آن با الگوریتمهای ابتکاری و فرا ابتکاری برای مسأله جریان کارگاهی منعطف با محدودیت و توابع هدف کمینهسازی دیرکردها و زودکردهای وزنی و کمینهسازی هزینه بیکاری ماشینها میباشد، به علاوه چندین الگوریتم فراابتکاری به منظور حل این مدل در مقیاس کاربردی طراحی میگردد.
1-4. مفروضات مسأله
مفروضات زیر در ارائه مدل مسأله در نظر گرفته میشود:
کارها با توجه به زمان دسترسی خود در دسترس قرار می گیرند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
کارها با توجه زمان آماده سازی خود آماده می شوند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
زمان نصب هر کدام از کارها وابسته به توالی آنها بر روی ماشین هاست.
هر ماشین در هر لحظه حداکثر می تواند یک کار را پردازش کند.
هر کار در هر لحظه حداکثر می تواند بر روی یک ماشین پردازش شود.
ماشین ها به طور پیوسته در دسترس نیستند.
برش کار به این مفهوم که پردازش یک کار قبل از پایان زمان پردازش آن قطع شود ودر زمانهای بعدی بر روی ماشینهای دیگر پردازش آن ادامه یابد، مجاز نمی باشد.
1-5. جنبه های نوآوری تحقیق
تحقیق موجود از دو جنبه صورت مسأله و روش حل نسبت به تحقیقات پیش دارای نوآوری میباشد. در این تحقیق یک مدل ریاضی جدید برای مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن محدودیتهای دسترسی به ماشین، زمان نصب وابسته به توالی وماشین، خرابی ماشین و زمان دسترسی به کارها ارائه شده است. همچنین دو رویکرد با استفاده الگوریتمهای ژنتیک[16]و رقابت استعماری[17] برای حل مسأله ارائه شدهاست.
1-6. محتویات تحقیق
مطالب ارائه شده دراین تحقیق در پنج فصل سازماندهی میشود: مقدمه و کلیات تحقیق در فصل اول ارائه شدهاست. در فصل دوم به مرور ادبیات تحقیق زمانبندی جریان کارگاهی منعطف پرداخته میشود. در فصل سوم مدل ریاضی پیشنهادی تشریح و اعتبار سنجی میگردد. فصل چهارم شامل معرفی الگوریتمها و رویکردهای پیشنهادی این تحقیق به همراه نتایج محاسباتی مربوط به آن میباشد و نهایتاً، فصل پایانی تحقیق شامل نتیجهگیری و پیشنهادات تحقیقات آتی میباشد.
[1] Scheduling
[2] Sequence
[3] Due date
[سه شنبه 1398-12-06] [ 04:33:00 ب.ظ ]
|