۱| batch-processing, rj, sj |C max

۲۰۰۵

Qiming Liud

heurestic algorithms

۱۶

۱|BPM, incompatible job family, r j| ∑C j

۲۰۱۲

Shiqing Yao,

Branch & bound

۲-۹٫مروری اجمالی بر کارهای قبلی وبررسی خلا موجود
دراین پایان‌نامه، مسأله‌ی زمان‌بندی تک‌ماشینه با قابلیت پردازش دسته‌ای روی مجموعه‌ای از کارها که متعلق به خانواده‌های متفاوت‌اند و با اندازه‌ی سفارش و زمان دسترسی دلخواه وارد سیستم می‌شوند مورد مطالعه واقع می‌شود که اهداف مدنظر برای بررسی مسئله حداقل‌سازی Cmax و Tmax بطور همزمان می‌باشد:
از آنجایی که عملکرد بسیاری از سیستم‌های تولیدی به وسیله‌ی کیفیت زمان‌بندی گلوگاه‌هایی که شامل یک ماشین است تعیین خواهد شد، مطالعه در زمینه‌ی زمان‌بندی تک‌ماشینه از گذشته تا به حال مورد توجه فراوان بوده است و از طرفی دیگر وجود یک ماشین با قابلیت پردازش دسته‌ای از کارها در ایستگاه گلوگاهی خط تولید، بسیاری از مشکلات خط تولید که از ایستگاه گلوگاه ناشی می‌شود را می‌تواند بهبود دهد. از طرفی دیگر بررسی مسائل زمان‌بندی تک‌ماشینه در هر حالتی که باشد به‌عنوان اساس و شروع مسیر برای بسط به مدل‌های پیچیده‌تر خواهد بود.
با توجه به توضیحات بالا و بیان اهمیت موضوع مورد بحث، در ادامه مروری بر کارهای قبلی که در این زمینه انجام شده است را خواهیم داشت:
در حیطه‌ی مدل‌های زمان‌بندی تک‌ماشینه با قابلیت پردازش دسته‌ای از کارها در دهه‌ های اخیر مقالات زیادی منتشر شده است که گوپتا و همکارانش در سال۱۹۹۷ [۱۵] اولین کسانی بودند این مسئله را با هدف حداقل سازی‌سازی مجموع وزنی دیرکرد و زودکرد (JIT) مورد بررسی قرار دارند که در این مطالعه کارها متعلق به خانواده‌های متفاوت می‌باشند و زمان آماده‌سازی بین پردازش دسته‌ های متعلق به خانواده‌های مختلف لحاظ شده است و روش‌حل پیشنهادی دراین مطالعه برنامه‌ریزی پویا میباشد.
در سال ۱۹۹۸ لی و همکارانش در این زمینه با هدف حداقل‌سازی حداکثر دیرکرد از موعد تحویل مطالعه کرده‌اند، آنان در مطالعاتشان کارها را با زمان دسترسی و موعد تحویل سازگار در نظر گرفتند والگوریتم پیشنهادی آنان الگوریتم برنامه‌ریزی پویا بوده است.
در سال ۲۰۰۱ عزیزاقلو و همکارانش[۴۷] به زمان‌بندی کارهایی متعلق به خانواده‌های مختلف با هدف حداقل‌سازی مجموع وزنی زمان تکمیل کارها پرداختند که زمان دسترسی کارها متفاوت از هم بودند و روش حل پیشنهادی آنان شاخه و کران بوده است.
در سال ۲۰۰۲ سونگ وهمکارانش [۲۱] یک روش حل دقیق مبنی بر برنامه‌ریزی پویا رابر‌ای حداقل‌سازی زمان تکمیل آخرین کار در زمان‌بندی کارهایی متعلق به خانواده‌های متفاوت و با زمان دسترسی متفاوت ارائه کردند.
داپنت و همکارانش در سال ۲۰۰۲ [۱۰] به حداقل‌سازی زمان تکمیل آخرین کار با یک روش دقیق برای کارهایی که دارای اندازه‌ی سفارش دلخواه هستند پرداخته اند.
یوزی و همکارانش در سال ۲۰۰۲ [۱۴] یک الگوریتم ترکیبی ژنتیک با برنامه‌ریزی پویا برای حداقل‌سازی حداکثر تأخیر برای کارهایی که دارای زمان دسترسی متفاوت‌اند، ارائه کرده‌اند.
شریف ملوک و همکارانش در سال ۲۰۰۴ [۸] به حداقل‌سازی زمان تکمیل آخرین کار با روش فراابتکاری شبیه‌سازی ذوب روی کارهایی با اندازه‌ی سفارش متفاوت پرداختند.
پیرز و همکارانش در سال ۲۰۰۵ [۱۹] با تعدادی از روش‌های ابتکاری به حداقل‌سازی مجموع وزنی دیرکرد کارهایی متعلق به خانواده‌های متفاوتند پرداخته‌اند.
داموداران و همکارانش [۹] به حداقل‌سازی زمان تکمیل آخرین‌کار پرداختند. آنان با یک الگوریتم ژنتیک به بررسی کارهایی که دارای اندازه‌ی سفارش متفاوت بوده‌اند توجه کرده‌اند.
و در سال ۲۰۰۷ [۱۱] آنان به بررسی همین مسئله با روش حل شبیه‌سازی ذوب [۲۲]پرداختند.
یانگ در سال ۲۰۰۷ [۱۳] اثبات کرد که مسئله‌ زمان‌بندی کارهایی که متعلق به خانواده‌های مختلف‌اند و دارای زمان آماده‌سازی یکسان بین خانواده‌ها می‌باشند با هدف حداقل‌سازی حداکثر دیرکرد از موعد تحویل قویاً جزء مسائل Np-Hard بوده‌اند که از این تحقیق می‌توان برای اثبات Np-Hard بودن مسئله ما، که دارای پیچیدگی‌های بیشتری نسبت به آن است، استفاده کرد.
ایردال و همکارانش در سال ۲۰۰۷[۱۶] یک روش برنامه‌ریزی پویا برای حداقل‌سازی مجموع وزنی تعداد کارهای دچار دیرکرد ارائه دادند.
در سال ۲۰۰۹ چِن و همکارانش [۱۷] به بررسی زمان‌بندی پردازش دسته‌ای کارها با زمان پردازش یکسان برای تمامی کارها و بدون در نظرگیری سایر محدودیت‌ها نظیر : زمان دسترسی- زمان آماده‌سازی- خانواده‌‌ی کارها و … پرداختند که آنان در این مطالعه روش های ابتکاری متنوعی را برای بهینه سازی اهداف و معیارهای مختلف ارائه دادند.
از جمله کسانی که در زمینه‌ی زمان‌بندی پردازش دسته‌ای کارها تحقیقات زیادی انجام دادند و جزء پیشگامان پردازش دسته‌ای هستند جولای و کریمی و همکارانش می‌باشند که از تحقیقات آنان می‌توان اشاره‌ کرد به:
حداقل‌سازی تعداد کارهای دچار دیرکرد برای کارهای متعلق به خانواده‌های متفاوت با یک روش برنامه‌ریزی پویا در سال ۲۰۰۵ [۱۸].
روش‌ بهینه‌سازی برنامه‌ریزی پویا برای پردازش دسته‌ای با کارهایی که متعلق به مشتری‌های متفاوتند با حداقل‌سازی همزمان اهداف حداکثر تأخیر و زمان تکمیل آخرین‌کار را در سال ۲۰۱۰ [۲۰] ارائه دادند و همچنین آنان در سال ۲۰۱۰ [۷] به بهینه‌سازی همزمان اهداف حداکثر دیرکرد کارها و زمان تکمیل آخرین کار با روش‌های مبتنی بر ژنتیک چندهدفه برای کارهایی که دارای اندازه‌ی سفارش متفاوتی بودند پرداختند.
با توجه به پیشینه‌مطالعات گذشته و بررسی خلاء موجود در میان این کارها به این نتیجه رسیدیم که برای نزدیک‌تر کردن موضوع پردازش دسته‌ای به دنیای واقعی, این تحقیق را با اهداف و محدودیت‌های معرفی شده در زیر انجام می‌دهیم:
بطور کلی مسئله‌ی مدنظر ما را می‌توان به این‌صورت تعریف کرد که می‌خواهیم مجموعه‌ای از nکار مستقل از هم که متعلق به m خانواده از قطعات می‌باشند را بگونه‌ای دسته‌بندی و پردازش کنیم که دو هدف حداکثر دیرکرد از موعد تحویل کارها و زمان تکمیل آخرین کار را بطور همزمان حداقل کنیم. در حالی‌که همه‌ی کار در زمان صفر در دسترس نمی‌باشند و هر کار دارای اندازه‌ی سفارش مختص به خود است و قابلیت تفکیک شدن یک کار روی اندازه‌ی سفارش در دسته‌ های مختلف را نیز خواهد داشت و هر کار دارای یک موعد تحویل از پیش‌تعیین‌شده و زمان پردازش مختص به خود است و کارهایی که در آن زمان پردازش یکسان‌اند در یک خانواده جای می‌گیرند و ماشین قابلیت پردازش همزمان کارهای هم‌خانواده را فقط دارد( به‌عنوان مثال کوره‌های پخت شیرینی که قادر به پخت انواع مختلف شیرینی با زمان پخت یکسان‌اند) و ظرفیت محدود برای ماشین تعریف می‌شود که اندازه‌ی سفارش هیچ‌کاری پیش از ظرفیت ماشین نباید باشد.
در ضمن بین پردازش دسته‌ هایی از خانواده‌های مختلف, زمان آماده‌سازی وجود خواهد داشت. که در هیچ کدام از تحقیقات گذشته تمامی این محدودیت‌ها و فرضیات با هم در پردازش دسته‌ای در نظر گرفته نشده‌اند. و ما سعی کرده‌ایم تا با اعمال تمامی محدودیت‌هایی که ممکن است امروزه در صنایع تولید دسته‌ای به آن برخورد بکنیم این مدل را تا جای ممکن به واقعیت‌ها نزدیکتر بکنیم.
با توجه به اینکه در تحقیقات قبلی کارهایی با پیچیدگی کمتر از تحقیق ما Np-Hard بودن شان ثابت شده است، می‌توان به Np-Hard بودن این مدل پی ببریم و از طرفی دیگر قصد در بهینه‌سازی چندهدفه‌ی مدل مذکور داریم که این امر خود باعث پیچیدگی بالای کارمان می‌شود.
۲-۱۰٫مروری بر زمان‌بندی چندهدفه در محیط تک ماشینه
همان‌طور که در فصل قبلی اشاره کردیم زمان‌بندی در محیط‌های تک‌ماشینه برای ارائه مدل‌های پیچیده زمان‌بندی و ارائه مفهوم جدید، به‌عنوان پایه و اساس برای محققان محسوب می‌شود یعنی در عین ساده بودن این مدل از مهم‌ترین مدل‌ها می‌باشد.
براساس نوع نگرش نسبت به زمان‌بندی در سیستم‌های تولید تک‌ماشینه می‌توان معیارهای مختلفی را به عنوان هدف در نظر گرفت که در سال‌های اخیر تحقیقات محققان بیشتر روی بررسی‌های چندهدفه در محیط‌های تک‌ماشینه صورت گرفته است که این امر موجب نزدیک‌تر شدن اینگونه مسائل به دنیای واقعی شده است.
اکنون می‌خواهیم چند مورد از مطالعات چندهدفه که در زمان‌بندی تک‌ماشینه انجام شده‌اند را اشاره کنیم:

جهت