پایان نامه - مقاله و پروژه

مقاله علمی با منبع : طراحی یک مدل ریاضی وحل آن با الگوریتم های ابتکاری و …

فصل اول
مقدمه و کلیات تحقیق
۱-۱٫ مقدمه
زمانبندی[۱]، فرآیند تخصیص منابع به فعالیتها با در نظر گرفتن دورههای زمانی مربوط به آنها به منظور بهینهسازی یک یا چند تابع هدف میباشد. این فرآیند به عنوان یک فرآیند تصمیمگیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. زمانبندی کارای فعالیتها زمینهساز بهبود عملکرد سیستمهای تولیدی میباشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار میآید. امروزه، مدیریت منابع موضوع به طور فزاینده مهمی برای سازمانها میباشد و تعیین توالی[۲] و زمانبندی یک شکل از تصمیمگیری است که نقش حیاتی در صنایع تولیدی و خدماتی بازی میکند. زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه میکند.
بهطور کلی، منابع، فعالیتها و توابع هدف عناصر کلیدی زمانبندی محسوب میشوند. منابع برحسب قابلیتهای کمی و کیفی خود مشخص میشوند. از سوی دیگر، فعالیتها بر حسب اطلاعاتی از قبیل منابع مورد نیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف میشوند. توابع هدف نیز در برگیرنده هزینههای سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیتها میباشند. تصمیمات عمده در فرآیند زمانبندی شامل بهره برداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمانهای تحویل با موعدهای تحویل[۳] تعیین شده میشوند.
در مسائل زمانبندی هدف از یافتن توالی انجام فعالیتها ممکن است متفاوت باشد. تعدادی از اهداف متداول عبارتند از: کمینهسازی زمان تکمیل کل کارها و یا کمینهسازی تعداد کارهایی که دیرکرد دارند. یکی از مهمترین اهداف در بسیاری از صنایع تولیدی تحویل به موقع[۴] کالا و خدمات میباشد که در بهدست آوردن سود و یا هزینههای پایینتر نقش دارد. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیطهای تولید متنوع است. تکمیل یک کار زودتر از موعد تحویل ممکن است هزینههایی از قبیل هزینه نگهداری موجودی به تولید کنندگان تحمیل کند، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به پرداخت جریمههای قراردادی به مشتری و کاهش اعتبار تولید کننده میشود. حداقلسازی زودتر و دیرتر یکی از سیاستهای مسائل زمانبندی بهنگام میباشد.
انگیزه بسیاری از توسعهها و پیشرفتهای عملی در حوزه زمانبندی برخاسته از محیطهای صنعتی است و به طور طبیعی در بیان مفاهیم زمانبندی از واژههای بکار رفته در صنعت استفاده میشود. به همین خاطر منابع با عنوان ماشین به کار میروند و به هر کدام از فعالیتها، کار اطلاق میشود بطوریکه کارها اغلب به وسیلهی مجموعهای از ماشینها در ایستگاههای مختلف کاری با توان مشخص پردازش میشوند.
بطور کلی، مسائل زمانبندی به صورت مسائل بهینهسازی دارای محدودیت بیان میشوند که در آنها به بررسی تصمیمات مربوط به تضمین ماشینها و توالی پردازش کارها پرداخته میشود. در حالتی که تنها یک ماشین موجود است، تعیین توالی پردازش کارها یک برنامه زمانی کامل را تشکیل میدهد. مسائل تکماشینه با وجود سادگی ذاتی، سنگ بنای درک فراگیر مفاهیم زمانبندی را تشکیل میدهند. در مقابل، زمانبندی مسائل چند ماشین شامل سیستمهای موازی، سیستمهای متوالی و سیستمهای ترکیبی میباشد. در سیستمهای موازی، هر یک از کارها با انجام یک عملیات همانند مسائل تکماشینه بر روی یکی از ماشینهای موازی موجود پردازش میشوند و به دنبال آن تخصیص ماشینها به کارها موضوعیت پیدا میکنند. این در حالی است که در سیستمهای متوالی و ترکیبی، کارها با انجام چند عملیات بر روی ماشینها پردازش میشوند و مسائل مربوطه ساختار نسبتاً پیچیدهتری را تجربه میکنند.
در این تحقیق، به بررسی مسأله جریان کارگاهی انعطافپذیر[۵] به عنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است، پرداخته میشود. چنانچه ساختار سیستم تولیدی به شکل سری بوده و حداقل در یک مرحله چندین ماشین موازی وجود داشته باشد،در واقع با یک سیستم جریان کارگاهی انعطافپذیر مواجه هستیم که زمانبندی این نوع سیستمهای خطی به دلیل کاربردی بودن آنها در سالهای اخیر در صنعت مورد توجه قرار گرفته است.
۱-۲٫ تعریف مسأله
دربرخی از صنایع تولیدی و خدماتی سفارشها تحت عنوان کارها به وسیله مجموعهای از ماشینها که به صورت سری در ایستگاههای کاری مختلف قرار گرفتهاند با توالی مشخص پردازش میشوند. یعنی کارها مسیر یکسانی را دنبال میکنند و ماشینها به صورت سری، پشت سر هم قرار دارند. وضعیت تعمیم یافتهای از این مسائل یعنی مسأله جریان کارگاهی منعطف میباشد که در هر مرحله (حداقل یکی از مراحل) حداقل دو ماشین بصورت موازی موجود است. در این حالت هر یک از کارها بایستی به ترتیب در هر مرحله توسط یکی از ماشینهای موجود پردازش شده و به مرحله بعد برود.
بیشتر ادبیات نظریه زمانبندی، و به همین دلیل بیشتر درک ما از مسائل زمانبندی، مربوط به محاسبه زمان جریان کل، تعداد کارهایی که تأخیر دارند و تأخیر کل میباشد. معیار مجموع تأخیرها، به طور خاص، به یک روش استاندارد برای اندازهگیری انطباق با تاریخ تحویل کارها تبدیل شده است، با این وجود عواقب کارهایی که زودتر از موعد تحویل، تکمیل میشوند نادیده گرفته شده و تنها آن دسته از کارهایی که دیرکرد دارند، با جریمه مواجه شدهاند. اما این معیار با رشد سهم تولید بهنگام شروع به ت

برای دانلود متن کامل این فایل به سایت torsa.ir مراجعه نمایید.

غییر کرد، با تأکید بر این نکته که زودکرد همانند دیرکرد باید نامناسب در نظر گرفته شود. در یک محیط زمانبندی بههنگام، کاری که زود تکمیل می شود تا تاریخ تحویل آن کار باید در موجودی انبار نگهداری شود، در حالی که اگر یک کار پس از موعد تحویلش اتمام یابد ممکن است در برآوردن نیازهای مشتری اختلال ایجاد کند. بنابراین، یک زمانبندی ایدهآل، زمانبندی است که در آن همه کارها دقیقاً در تاریخهایی که به آنها اختصاص داده شده اتمام یابند. البته، زمانبندی بهنگام شامل مجموعهای بسیار گستردهتر از اصولی است که مرتبط با موعدهای تحویل میباشد، اما مدلهای زمانبندی با هزینه زودکرد و دیر کرد (E / T) به یک بعد اساسی زمانبندی رویکردهای JIT آدرس دهی میشوند.
مسأله زمانبندی جریان کارگاهی اخیراً در صنعت بطور وسیعی در محیطهای صنعتی مورد استفاده قرار گرفته است، به همین دلیل در ۵۰ سال اخیر به دقت بررسی شده است. مسأله مورد بررسی در این تحقیق، مسأله زمانبندی جریان کارگاهی انعطافپذیر در محیطهای تولید بهنگام میباشد.در برخی از کاربردهای زمانبندی مسأله جریان کارگاهی انعطافپذیر ماشینها دارای سطوح تکنولوژیکی متفاوتی هستند و لزوماً قادر به پردازش هریک از کارهای موجود در مجموعه کارها نمیباشند. در نتیجه، هر کدام از کارها تنها بر روی زیر مجموعهای از مجموعه ماشینها میتوانند پردازش شوند و اصطلاحاً پردازش کارها با دسترسی محدود به ماشینها[۶] صورت میپذیرد.
مسائل زمانبندی غالباً به محیطهای کارگاهی میپردازند که در آنها زمان نصب[۷] ماشین نادیده گرفته میشود و یا به عنوان بخشی از زمان پردازش کارها تلقی میشود. این نوع محیطهای کارگاهی با این فرض مدلسازی میشوند که زمانهای نصب در مقایسه با زمانهای پردازش کوچک هستند، بنابراین میتوان آنها را نادیده گرفت و یا اینکه زمانهای نصب مستقل از توالی پردازش کارها بر روی ماشینها هستند، در نتیجه میتوان آنها را به زمانهای پردازش اضافه نمود. با این وجود، در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی[۸] هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد[۶]. در این شرایط، زمان نصب به عنوان بخشی مجزا از زمان پردازش در نظر گرفته میشود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد به نوع کار قبلی که بر روی آن ماشین پردازش شده نیز بستگی دارد.تلقی زمان نصب به صورت مجزا از زمان پردازش در بیشتر تکنیکهای مدیریت تولید نوظهور نظیر تولید بموقع[۹]، تکنولوژی گروهی[۱۰] و تولید سلولی[۱۱] مورد استفاده قرار میگیرد. همچنین در بعضی از مسائل ماشینها نیاز به زمان نصب برای پردازش کارها دارند، یعنی اگر یک کار به عنوان اولین کاری باشد که بر روی ماشین پردازش میشود یک زمان نصب وابسته به ماشین[۱۲] مجزا از زمان پردازش برای آن در نظر گرفته میشود. تحقیقات زیادی در مورد مسأله جریان کارگاهی انعطافپذیر با فرض خرابی ماشین[۱۳] خصوصاً هنگامیکه خرابی ماشین به کار انجام شده قبلی روی ماشین بستگی داشته باشد،انجام نشده است[۴۶]. در بعضی از مسائل تمام کارها در ابتدای افق زمانی (لحظه صفر) در دسترس نیستند و زمان دسترسی[۱۴] به هرکار مستقل از کارهای دیگر میباشد.
در این تحقیق، مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن محدودیتهای دسترسی به ماشین، زمان نصب وابسته به توالی و ماشین، خرابی ماشین و زمان دسترسی به کار با هدف کمینهسازی زمانهای زودکرد و دیرکرد وزنی بررسی میشود. یک مدل برنامهریزی عدد صحیح برای این مسأله پیشنهاد میشود. همچنین چندین روش فرابتکاری[۱۵] برای حل آن ارائه میگردد.
۱-۳٫ اهداف تحقیق
هدف ازاجرای این تحقیق طراحی یک مدل ریاضی وحل آن با الگوریتمهای ابتکاری و فرا ابتکاری برای مسأله جریان کارگاهی منعطف با محدودیت و توابع هدف کمینهسازی دیرکردها و زودکردهای وزنی و کمینهسازی هزینه بیکاری ماشینها میباشد، به علاوه چندین الگوریتم فراابتکاری به منظور حل این مدل در مقیاس کاربردی طراحی میگردد.
۱-۴٫ مفروضات مسأله
مفروضات زیر در ارائه مدل مسأله در نظر گرفته میشود:

  • کارها با توجه به زمان دسترسی خود در دسترس قرار می گیرند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
  • کارها با توجه زمان آماده سازی خود آماده می شوند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
  • زمان نصب هر کدام از کارها وابسته به توالی آنها بر روی ماشین هاست.
  • هر ماشین در هر لحظه حداکثر می تواند یک کار را پردازش کند.
  • هر کار در هر لحظه حداکثر می تواند بر روی یک ماشین پردازش شود.
  • ماشین ها به طور پیوسته در دسترس نیستند.
  • برش کار به این مفهوم که پردازش یک کار قبل از پایان زمان پردازش آن قطع شود ودر زمانهای بعدی بر روی ماشینهای دیگر پردازش آن ادامه یابد، مجاز نمی باشد.

۱-۵٫ جنبه های نوآوری تحقیق
تحقیق موجود از دو جنبه صورت مسأله و روش حل نسبت به تحقیقات پیش دارای نوآوری میباشد. در این تحقیق یک مدل ریاضی جدید برای مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن محدودیتهای دسترسی به ماشین، زمان نصب وابسته به توالی وماشین، خرابی ماشین و زمان دسترسی به کارها ارائه شده است. همچنین دو رویکرد با استفاده الگوریتمهای ژنتیک[۱۶]و رقابت استعماری[۱۷]up> برای حل مسأله ارائه شدهاست.
۱-۶٫ محتویات تحقیق
مطالب ارائه شده دراین تحقیق در پنج فصل سازماندهی میشود: مقدمه و کلیات تحقیق در فصل اول ارائه شدهاست. در فصل دوم به مرور ادبیات تحقیق زمانبندی جریان کارگاهی منعطف پرداخته میشود. در فصل سوم مدل ریاضی پیشنهادی تشریح و اعتبار سنجی میگردد. فصل چهارم شامل معرفی الگوریتمها و رویکردهای پیشنهادی این تحقیق به همراه نتایج محاسباتی مربوط به آن میباشد و نهایتاً، فصل پایانی تحقیق شامل نتیجهگیری و پیشنهادات تحقیقات آتی میباشد.
فصل دوم
ادبیات تحقیق
۲-۱٫ مقدمه
در این فصل ابتدا مروری بر مسائل زمانبندی داشته و بعضی مفاهیم اولیه آن مورد بررسی قرار می گیرد. همچنین انواع محیطهای زمانبندی نیز تشریح خواهند شد. در ادامه به بررسی پیشینه تحقیقهای صورت گرفته در حوزههای مرتبط با این تحقیق خواهیم پرداخت.
۲-۲٫ مروری بر مسائل زمانبندی