ارائه زمان‏بندی واکنشی برای مسأله کارگاه باز با تمرکز بر موعد تحویل کارها

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه مازندران، بابلسر، ایران

2 استادیار دانشکده علوم ریاضی، دانشگاه مازندران، بابلسر، ایران

3 کارشناس ارشد ریاضی کاربردی، دانشگاه مازندران، بابلسر، ایران

چکیده

زمانبندی، تخصیص منابع در افق برنامه‌ریزی برای اجرای مجموعه‌ای از وظایف است که استفاده از منابع در دسترس را بهینه می‌کند. بیشتر پژوهش‏های انجام شده در زمینه زمان‏بندی کارگاه باز (Open Shop)، حالت ایستا و قطعی دارند، یعنی همه داده‌ها مشخص هستند و در افق زمانی تغییر نمی‌کنند، در حالی که مسائل زمان‏بندی واقعی به بندرت ایستا و قطعی هستند. برنامه‌ریزی واکنشی، زمینه­ پژوهش‏هایی است که بروز تغییرات و فرضیه‏ها غیرقطعی در مسائل زمان‏بندی جهان واقعی را بررسی می‏کند. از طرف دیگر، مسأله کارگاه باز در دسته NP-hard قرار دارد، بنابر این، در صورت بروز رویدادهای غیرمنتظره، حل مجدد مدل اولیه از نظر هزینه محاسباتی و زمان اجرا مقرون به صرفه نیست. بنابراین، در این پژوهش‏ها ابتدا مدل برنامه‌ریزی عدد صحیح آمیخته برای تولید زمان‏بندی اولیه مسأله کارگاه باز را ارائه می­شود، در ادامه، به منظور اصلاح زمان‏بندی اولیه، مدل ارائه شده به برنامه‌ریزی واکنشی متناسب با تغییر موعد تحویل تعمیم داده می شود. در پایان، بنا به ضرورت مسأله، الگوریتمی کارا به منظور اصلاح زمان‏بندی اولیه ارائه می شود که در کنار مدل واکنشی، در صورت بروز هر رویدادی قابلیت کنترل بالایی را برای ناظر و مدیر کارگاه فراهم کند. این الگوریتم و تمامی مدل‌ها در محیط نرم افزاری Aimms پیاده‌سازی و اجرا شده‌ و نتیجه‏های به دست آمده؛ کارایی به کارگیری رویکرد زمان‏بندی واکنشی، در شرایط بروز اختلال در موعد تحویل کارها را تایید می‏کند.

کلیدواژه‌ها


عنوان مقاله [English]

Reactive Scheduling Presentation for an Open Shop problem Focused on jobs’ due Dates

نویسندگان [English]

  • Nemat allah taghi-nezhad 1
  • Hadi Naseri 2
  • Farzaneh Khalili Goodarzi 3
  • Fatemeh Taleshian Jelodar 3
1 Ph.D Student mathematical Sciences, university of mazandaran, Babolsar, Iran
2 Assistant professor of Research Center of Algebric Hyper structures and Fuzzy mathematics, university of mazandaran, Babolsar, Iran
3 M.sc Student mathematics Science , university of mazandaran, Babolsar, Iran
چکیده [English]

Scheduling consists of assigning resources to a set of tasks in a given time horizon, so that optimizes the usage of available resources. Most of researches in open shop area have static and deterministic status which means the situation is like that all data are certain and won't change in atime horizon. However, the real world scheduling problems are rarely static and deterministic. Reactive programming is a research field that considers and peruses each change and uncertain assumptions in real world scheduling problemsSo, in this paper, first we express a mixed integer programming model to produce­ initial scheduling to open shop problem and after that we will generalize the presented model to its equivalent reactive programming with due date’s hange. Finally we will express an algorithm due to necessity to revise the primal scheduling. This algorithm and all the models have been implemented in AIMMS software environment and the computational results have been reported.

کلیدواژه‌ها [English]

  • Reactive programming
  • Open shop
  • Scheduling
  • Due date
  • Uncertainty

1- مقدمه

زمان‏بندی، تخصیص منابع در افق برنامه‌ریزی برای اجرای مجموعه‌ای از وظایف است که استفاده از منابع در دسترس را بهینه می‌کند. در واقع، یک برنامه زمان‏بندی کارا می‌تواند به بهره‌برداری موثر از ظرفیت‌های تولید و افزایش سوددهی واحدهای تولیدی منجر گردد. زمان همیشه یکی از با ارزش‌ترین منابع موجود است، لذا زمان‏بندی منابع علاوه بر این ­که به افزایش کارایی و بهره‌برداری مناسب از ظرفیت تولید و نهایتا افزایش سود­دهی یک سازمان منجر می‌شود، سبب کاهش زمان مورد نیاز برای تکمیل کارها و صرفه‌جویی در زمان به عنوان با ارزش‌ترین منبع نیز خواهد شد.

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

بیشتر پژوهش‏های انجام شده در مسائل زمان‏بندی بدون آن ­که توجه کافی به اتفاقات پیش‌بینی نشده داشته باشند؛ به طور عمده‌ بر تولید یک زمان‏بندی خوب تمرکز دارند. در واقع، انتقاد اصلی­ مچ اکتورک و جورجولو (1999) و کامانگ و جانسون (2002) که بر مدل‌های زمان‏بندی ایستا و قطعی وارد است؛ به علت بی­توجهی به این نکته است که رخدادهای واقعی‌ که در کارگاه اتفاق می‌افتند، از نظر تعداد بیشتر و بسیار متفاوت‌تر در مقایسه با عملیات و رخدادهای پیش‌بینی شده از قبیل زمان جداسازی کارها از ماشین، زمان آماده‌سازی کارها بر روی ماشین و غیره هستند. در اقع ممکن است عوامل گوناگونی رخ دهند که زمان‏بندی اولیه را مختل کند، بنابر این، یک عمل اصلاحی مناسب (یا واکنشی) باید رخ دهد تا وضعیت زمان‏بندی اولیه را بهبود بخشد یا آن را از نشدنی بودن رها سازد. از سوی دیگر، مسأله را در افق زمانی پیوسته مد نظر می‌گیرد. ابتدا زمان‏بندیی با اطلاعات کامل و مشخص اولیه تولید می‌کند و پردازش کارها منطبق با این زمان‏بندی انجام می‌شود و به محض این که اطلاعات جدیدی از موعد تحویل کارها به دست آمد، یک زمان‏بندی جدید منطبق با شرایط جدید تولید می‌شود که به آن زمان‏بندی اصلاح شده می‌گوییم. بنا به گفته سبابونجولکو و بایز (2000) در عملیات صنعتی، اکثر سیستم‌های زمان‏بندی، برای پاسخ‌گویی به رویدادهای غیرمنتظره و اصلاح درست زمان‏بندی اولیه و یا به علت پیچیدگی ترکیبی مسأله زمان‏بندی، که بار اضافی برای فرد برنامه‌ریز ممکن است باشد و باعث تولید زمان‏بندی‌های ضعیف و یا حتی نشدنی توسط او شود، خواهان استفاده از برنامه‌ریزی واکنشی هستند. از نظر دیگر نیز (جیارو، کوبل، پواکوسکی، 2002) با بررسی­های دقیق، مسأله کارگاه باز را NP-hard دسته‏بندی کرده، لذا در صورت بروز رویدادهای غیرمنتظره حل مجدد مدل اولیه از نظر هزینه محاسباتی و زمان اجرای مدل اولیه، مقرون به صرفه نیست. با توجه به آنچه گفته شد، زمان‏بندی واکنشی در هر سیستم زمان‏بندی با اهمیت است.

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

این مقاله، به این شکل مرتب شده که در بخش 2 مروری بر پیشینه و ادبیات مسأله­ زمان‏بندی کارگاه باز دارد، در بخش 3 مسأله زمان‏بندی کارگاه باز (Open Shop Scheduling Problem) را تشریح می‏شود، در بخش 4 فرمول‌بندی برای مسأله کارگاه باز ارائه می‏شود که زمان‏بندی اولیه را تولید میکند، بخش 5 به توسعه مدل و ارائه برنامه‌ریزی واکنشی در شرایط بروز تغییر در موعد تحویل می­پردازد، به همین منظور، ابتدا الگوریتمی برای تشخیص عملیات‌های بدون تغییر معرفی می شود و در ادامه؛ پارامترها، متغیرها و قیود جدیدی را تعریف و به مدل اضافه می‏شود. در بخش 6 برای آشنایی هر چه بهتر با روند ارائه شده در بخش‌های پیش، مثال عددی بررسی می شود  و در بخش 7 جمع‌بندی و نتیجه‌گیری مقاله ارائه می‏شود.

 

2- پیشینه و ادبیات مسأله

هر چند در گذشته توجه کمتری نسبت به مسائل کارگاه باز شده اما، به نظر می‌رسد در سال‌های اخیر مسائل زمان‏بندی کارگاه باز مد نظر پژوهشگران بسیاری قرار گرفته است. با این حال، مسائل کارگاه باز در مقایسه با سایر مسائل زمان‏بندی سهم بسیار اندکی از ادبیات موضوع را به خود اختصاص داده‌ است.

سدنو، الکاید لوپز دی پابلو، گونزالز مارتین (2009) روشی را بر مبنای جریان شبکه با فرض وجود پنجره زمانی، قابلیت بریدگی کارها ارائه نمودند. محدودیت پنجره زمانی آنها نیز باید به طور اکید برقرار شود. آنها به طور هم زمان دو معیار را برای کمینه‌سازی انتخاب نمودند. چن و هانگ و تانگ (2008) به بررسی توالی‌های انبوه برای مسأله زمان‏بندی کارگاه باز پرداختند. آنها در پژوهش‏ خود مسأله مورد نظر را با فرض وجود محدودیت‌های زمان‏های ترخیص بررسی نمودند. همچنین، در سناریوی مورد نظر خود مسأله کارگاه باز را با محدودیت عدم وجود زمان‌ بیکاری ماشین‌ها مطالعه کرده‏اند. موشیف و یاول (2008) به بررسی زمان‏بندی کارگاه باز دسته‌ای پرداختند. آنها در مسأله خود فرض نمودند که زمان­ پردازش کارها مشابه بوده و زمآنهای آماده‌سازی را وابسته به توالی در نظر گرفتند. همچنین، در سناریوی مورد بررسی وی، دسته‌ها در هر لحظه آماده پردازش هستند. هدف از این مسأله محاسبه مقدار بهینه هر دسته بوده است. نودا و آلکاید و مارتین (2006) رویکردهای جریان شبکه را برای مسائل زمان‏بندی با مجاز بودن بریدگی کارها و با فرض وجود پنجره زمانی ارائه دادند. لیاو (2005) مسأله زمان‏بندی کارگاه باز را برای کمینه‌سازی کل دیرکردها و با فرض مجاز بودن بریدگی کارها بررسی شد. لیونگ و لی و پیندو و سریسکاندراجه (2005) مسأله کارگاه باز را با فرض کارهای متداخل مطالعه نمودند. آنها مسأله را در حالت دو ماشینه بررسی نمودند و فرض کردند که هر کار باید روی هر دو ماشین پردازش شوند. البته در پژوهش‏ آنان برخلاف مسأله کارگاه باز کلاسیک، هر دو عملیات مربوط به یک کار می‌توانند در یک زمان با یکدیگر تداخل داشته باشند. تابع هدفی که برای کمینه‌سازی انتخاب شده کل زمان اتمام کارها است.

لیاو و چنگ و چن (2005) زمان‏بندی دو ماشینه در محیط کارگاه باز در حالت بدون توقف را بررسی کردند. آنها حداکثر زمان تکمیل کارها را به عنوان یک معیار برای کمینه‌سازی انتخاب نمودند. چنگ و شاخلویچ (2005) بر روی کمینه‌سازی توابع هدف غیر نزاما جدا از هم، برای مسأله زمان‏بندی کارگاه باز با زمان واحد پرداختند. آنها در مطالعه خود هر دو حالت مجاز بودن و نبودن بریدگی را بررسی نمودند. این پژوهشگران برای مجموعه توالی‌های موجه، زمان­های اتمام کار را محاسبه کردند. براساس خواص چند وجهی زمان‏بندی حاصل، آنها نشان دادند که مسأله ایجاد یک توالی بهینه، برای کمینه‌سازی یک تابع هزینه مجزای غیر نزاما از زمان اتمام کار، به صورت چندجمله‌ای قابل حل است. شاخلویچ (2005) مسأله زمان‏بندی کارگاه باز را با فرض وجود عملیات‌های زمان واحد و تابع هدف غیر صعودی و متقارن وابسته به زمان اتمام کارها بررسی نمود. براسل و هنس (2004) به مطالعه مسأله کارگاه باز با فرض مجاز بودن بریدگی کارها پرداخته‌اند، آنها معیار متوسط زمان اتمام کارها را در مسأله خود در نظر گرفته و مدل‌های جدیدی از مسائل زمان‏بندی با فرض مجاز بودن بریدگی ارائه کرده‌اند. موشیف و یول (2004) مطالعه‌ای را در مورد زمان‏بندی جریان کارگاهی و کارگاه باز با فرض وجود ماشین بحرانی انجام دادند. آنها فرض کردند که هرکار حداکثر از دو عملیات تشکیل می‌شود. یکی از این دو عملیات برای همه کارها مشترک است. آکر و هوشاوین و وگینر (2003) به بررسی مسأله زمان‏بندی در محیط کارگاه باز دارای دو ماشین پرداختند. در این سناریو، هرکار شامل دو عملیات بوده و فرض می‌شود که عملیات تولید (دوم) باید توسط ماشین اول (دوم) انجام شود. در این پژوهش، ترتیبی که عملیات‌ها باید انجام شود ثابت نبوده و بازه­های زمانی پردازش آنها نمی‌تواند تداخل داشته باشد. سراج و توکلی مقدم (2009)، یک الگوریتم جستجوی ممنوع چند هدفه جدید که بر مبنای رویکرد تصمیم‌گیری چند هدفه فازی است، برای مسأله کارگاه باز دوهدفه ارائه نمودند. آنها مسأله پیشنهادی خود را با پارامترهای قطعی در نظر گرفته و در آن به حداقل سازی میانگین زمان‏های تکمیل و میانگین مقادیر دیرکرد کارها به طور همزمان پرداختند. در مدل ارائه شده، زمان‏های آماده‌سازی به شکل مستقل از توالی در نظر گرفته شده است. نوری درویش و ایرج مهدوی و نظام مهدوی امیری (2012) زمان‏بندی کارگاه باز را با دنباله وابسته به زمان آماده سازی، زمان پردازش فازی و زمان تحویل فازی در نظر گرفتند. در سبابونجولکو و بایز (2000) بررسی کاملی مرتبط با کارهای صورت گرفته در برنامه‌ریزی واکنشی جریان کارگاهی (JSSP) انجام شده است.

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

 

3- تعریف و فرضیه‏ها مسأله

مسأله زمان‏بندی در محیط کارگاه باز  متشکل از m ماشین و n کار است که هر کار تشکیل شده از دنباله‌ . هر عملیات  پردازشی از کار j روی ماشین i است و دارای زمان پردازش مشخص  است، بنابر این، هر کار j حداکثر شامل m عملیات روی m ماشین است به ‌عبارت ‌دیگر هر کار حداکثر یک پردازش روی هر ماشین دارد و ترتیب پردازش‌ کار j مشخص نیست، هر ماشین حداکثر یک کار را می‌تواند در یک زمان پردازش کند و بریدگی کارها مجاز نیست، به این معنی که  پردازش یک عملیات از لحظه­ای که شروع می‌شود تا زمانی که کامل شود ادامه پیدا می‌کند و از ماشین جدا نمی­شود. تابع هدف مسأله کمینه‌سازی مجموع دیرکرد کارها در نظر گرفته شده‌ است. مجموع دیرکرد معیاری برای اندازه‌گیری تأخیر‏ در تحویل به موقع محصولات محسوب می‌شود.

 

3-1- فرضیه‏ها مسأله

فرضیه‏های ذیل برای مدل‌سازی مسأله در نظر گرفته شد.

1)  کارها می‌توانند با هر ترتیب دلخواهی بر روی ماشین‌ها پردازش شوند.

2)    زمان پردازش کارها بر روی ماشین‌های متفاوت می‌تواند با هم تفاوت داشته باشد.

3)    هر کار در هر لحظه حداکثر می‌تواند بر روی یک ماشین پردازش شود.

4)    بریدگی کارها و خرابی ماشین‌ها مجاز نیست.

5)    درجه اهمیت کارها الزاماً یکسان نیست.

6)    هر کار دارای موعد تحویل معینی است.

7)  از هر نوع ماشین تنها یکی در محیط کاری موجود دارد.

 

3-2- نمادهای ریاضی

با در نظر گرفتن روابط و فرضیه‏های بالا، مسأله مد نظر به شکل یک برنامه‌ریزی خطی عدد صحیح آمیخته مدل‌سازی شده که در زیر مجموعه‌ها، پارامترها، متغیرها و سرانجام محدودیت‌های لازم ارائه می‌شوند.

 

مجموعه‌ها و اندیس‌ها

 

پارامترها

تمام پارامترها با علامت ( ) بالای آن­ها قابل تشخیص هستند.

 

متغیرهای تصمیم پیوسته و دودویی

 

 

3-3-مدل ریاضی

مدل برنامه‌ریزی عدد صحیح آمیخته به­ شکل زیر فرمول‌بندی می‌شود:

 

 

 

 

 (1) تابع هدف مدلی است که شامل مجموع تأخیر‏ در تحویل کل کارهاست، محدودیت (2) و (3) ترتیب کارها بر روی تک تک ماشین‌ها را مشخص می‌کنند به بیان دیگر، کار j روی ماشین i پیش از کار k باشد یا بعد از آن، محدودیت (4) و (5) ترتیب ماشین‌ها برای هر کار را مشخص می‌کنند به بیان دیگر، کار j روی ماشین i پیش از ماشین  باشد یا بعد از آن. در (6) زمان پایان کار j روی تمام ماشین‌ها:  را بزرگتر مساوی زمان پایان تمام عملیات‌های کار j یعنی  قرار می‌دهیم. در (7) میزان تأخیر‏ از موعد تحویل کارها محاسبه می‌شود یعنی زمان تکمیل کار j اگر پیش یا برابر زمان تحویل  باشد که  برابر صفر می‌شود اما، اگر کار بعد از موعد تحویل آماده شود  مقداری بزرگتر از صفر خواهد گرفت. در (8) نوبت تمام کارها را در برنامه ترتیبی ماشین i مشخص می‌کنیم برای مثالی با 3 کار و یک ماشین داریم: و  و  یعنی روی ماشین 1 اول کار 2 بعد کار 3 و بعد کار 1 انجام می‌شود. در واقع، در این قید مجموع کل کارهای بعد از کار j  را می‌شماریم، چون مجموع کارهای بعد از کار  pام، عدد n-p است مجموع را از n که تعداد کل کارهاست کم کرده‌ایم. در (9) مانند قید 8 است با این تفاوت که نوبت تمام ماشین‌ها را در برنامه ترتیبی کار j مشخص می‌کند. یعنی در قید 8 برنامه ترتیبی ماشین به دست می‌آید و در قید 9 برنامه ترتیبی کارها مشخص می‌شوند. برای مثالی با 1 کار و 3 ماشین داریم: و  و  یعنی کار 1 اول روی ماشین 3 بعد روی ماشین 1 و در انتها روی ماشین 2 انجام می‌شود. در واقع، در این قید مجموع کل ماشین‌های بعد از بعد i را می‌شماریم، چون مجموع ماشین‌های بعد از ماشین‌  pام، عدد m-p است مجموع را از m که تعداد کل ماشین‌هاست کم کرده‌ایم. با توجه به این که مسأله کارگاه باز NP-hard است؛ استفاده از مدل و روشی که در صورت بروز رخدادهای مختل کننده نیاز به حل مجدد مدل اولیه نباشد؛ بسیار حایز اهمیت است، از این‏رو در بخش بعد، مقاله به ارائه مدل واکنشی می­پردازد.

 

4- توسعه مدل به برنامه‌ریزی واکنشی

بر اساس نظر ون ده واندر و دیملمستر و هرولن (2007)  اصلاح زمان‏بندی اولیه می‌تواند به شکل، استواری پاسخ[3]، استواری کیفیت[4] یا ترکیبیباشد. هدف در گونه‌ استواری پاسخ این است که تغییرات ایجاد شده بین زمان‏بندی اصلاح شده و برنامه زمان‏بندی اولیه حداقل باشد و در واقع، تابع هدف این مدل کمینه سازی تغییرات زمان‏بندی اولیه و اصلاح شده است به بیان دیگر، تابع هدف از نوع کمینه‏سازی انحراف مسأله اولیه از مسأله ثانویه است، در گونه استواری کیفیت به بالا بردن کیفیت جواب توجه می‌شود و تابع هدف آن نیز معمولا همان تابع هدف مدل اولیه است و به تغییرات ایجاد شده بین زمان‏بندی اصلاح شده و برنامه زمان‏بندی اولیه توجهی نمی‌کند.

   در گونه ترکیبی تابع هدف نسبت به مدل اولیه تغییر نمی‌کند اما سقف و کران بالایی برای تغییرات بین زمان‏بندی اولیه و اصلاح شده در قیود در نظر گرفته می‌شود.

در این مقاله گونه ترکیبی برنامه‌ریزی واکنشی استفاده شده است، یعنی یک کران که توسط مدیر و ناظر سیستم برای کنترل تغییرات نسبت به زمان‏بندی اولیه در نظر می‌گیرد. به ‌بیان ‌دیگر، به دنبال کمینه کردن تأخیر‏ ارائه کارها در زمان‏بندی اصلاح شده است، اما سعی دارد تغییرات بین زمان‏بندی اصلاح شده و اولیه را نیز کنترل کند.

   ابتدا کلیت اصلاح زمان‏بندی اولیه در شکل 1 نشان داده شده است:

 

 

شکل 1- روند اصلاح زمان‏بندی اولیه

 

 

   پیش از تشریح چگونگی اصلاح زمان‏بندی اولیه باید مفهوم زمان تشخیص تعریف شود.

زمان تشخیص: به زمان مطلع شدن از تغییرات صورت گرفته در موعد تحویل، زمان تشخص گفته می‌شود.

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

شکل 1 به مرحله اول (زمان‏بندی اولیه) و مرحله دوم (زمان تشخیص یا زمان مطلع شدن از تغییرات) اشاره دارد. در مرحله سوم به این علت‏ که در زمان‏بندی جدید (اصلاح شده)، عملیات کارهای پیش از زمان تشخیص را نمی‏شود تغییر داد، بایستی زمان‏بندی عملیات پردازش نشده تغییر یابد. برای این­کار الگوریتمی ارائه شده است.

   تمام پارامترها، متغیرها و مولفه‌های زمان‏بندی اولیه با علامت  که در بالای آن قرار می‌گیرد مشخص شده‏اند. برای مثال،  زمان پایان تمام پردازش‌های مورد نیاز کار j در زمان‏بندی اولیه است.

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

 

1-1- الگوریتم دسته‌بندی :

در زمان‏بندی اصلاح شده، عملیاتی که پیش از زمان تشخیص انجام شده‌اند، قابل تغییر نیستند. الگوریتمی که درشکل نمایش داده شده است، در واقع عملیات  را بر حسب زمان تشخیص دسته‌بندی می‌کند. مقاله در ادامه به تشریح این الگوریتم می‏پردازد.

 

 

 

 


در حلقه تکرار، این که زمان شروع پردازش کار j روی ماشین i پیش از زمان تشخیص
( ) بوده  یا بعد از آن بررسی می‏شود. با توجه به این که تنها عمل این الگوریتم مقایسه بین زمان شروع و زمان تشخیص است و با وجود الگوریتم­های مقایسه با زمان اجرای بسیار مناسب، توانایی این الگوریتم برای حل مسائل با سایز بزرگ تضمین شده است.

اگر زمان شروع پردازش کار پیش از زمان تشخیص باشد و چون بریدگی کار از ماشین در این مسأله مجاز نیست، لذا زمان شروع پردازش کار j روی ماشین i  در زمان‏بندی اصلاح شده نیز باید برابر با زمان‏بندی اولیه باشد. بدین منظور باید  (که متغییری دودویی است برابر یک است؛ یعنی این امکان وجود دارد که زمان شروع پردازش کار j روی ماشین i در زمان‏بندی اصلاح شده نسبت به زمان‏بندی اولیه متفاوت باشد و اگر صفر شود یعنی باید زمان شروع پردازش کار j روی ماشین i با مقدار آن در زمان‏بندی اولیه یکسان باشد)  برابر صفر‏شود تا زمان‏بندی اصلاح شده به رعایت برابری با زمان‏بندی اولیه تا پیش از زمان تشخیص ملزم شود.

حال‌که عملیات پیش و بعد زمان تشخیص معین شده‌اند، در مرحله چهارم بایستی اصلاحات لازم بر روی عملیاتی که بعد از زمان تشخیص انجام خواهند شد، اعمال شود. برای این­کار از مدل استفاده شده است.

 

1-2- مدل  

هدف از به­کارگیری این مدل اصلاح زمان‏بندی اولیه با توجه به تغییر در موعد تحویل است و بدین صورت انجام می‌گیرد که وقتی در زمان تشخیص، تغییری در موعد تحویل کارها رخ دهد، بایستی زمان‏بندی جدیدی ارائه شود  به طوری که مولفه‌ تمام عملیاتش تا زمان تشخیص با زمان‏بندی اولیه برابر باشد و برای مدت زمان باقی­مانده با توجه به موعد تحویل جدید کمترین تأخیر‏ در موعد تحویل داشته باشد. لذا برای این منظور، مدل  ارائه می­شود.

شایان ذکر است، مجموعه‌ها و اندیس‌های این مدل مشابه با آنچه در بخش 4-1 تعریف شده است است.

 

پارامترها

علاوه بر پارامترهای بخش 4-2 چون بایستی تعداد تغییرات بین زمان‏بندی اولیه و اصلاح شده نیز کنترل شود، نیاز به تعریف پارامترهای جدیدی به شرح جدول (1) است.

 

جدول 1- تعریف پارامتر های جدید

 

 

 

منظور از  برای پارامتر  اعداد صحیح از 0 تا m (تعداد ماشین‌ها) به غیر از یک است چون اگر یک ترتیب یا نوبت یک کار در برنامه ترتیبی ماشین i تغییر کند، مطمئناً با کار دیگری جابجا شده است، پس نوبت آن کار نیز تغییر کرده و لذا تعداد تغییرات 2 است و این پارامتر نمی‌تواند عدد 1 باشد. به بیان دیگر عدد 1 برای این پارامتر، همان عمل عدد صفر را انجام می‌دهد. حداکثر مقدار این پارامتر نیز در شرایطی که ترتیب تمام کارها تغییر کند و جایگشتی کاملاً متفاوت از ترتیب کارها حاصل شود  mاست. همین استدلال برای مقادیر پارامتر  نیز قابل بیان است.   

 

 

1-2-1- متغیرهای تصمیم پیوسته و دودویی

جدول 2- تعریف متغیرهای دودویی

 


1-2-2- محدودیت‌های مدل

قیود (10) و (11) باید به مدل  اضافه شوند تا برای عملیات انجام شده پیش زمان تشخیص، زمان‏بندی اصلاح شده مجبور به تبعیت از زمان‏بندی اولیه کند، در غیر این صورت کارهای گذشته اصلاح شده‌اند، اما در واقیعت هیچگاه نمی‏توان به گذشته برگشت و تصمیمات اجرا شده را اصلاح کرد.

 (10)             (11)         

 

با استفاده از الگوریتم دسته‌بندی  مقادیر پارامتر  برای عملیات انجام شده پیش از زمان تشخیص باید صفر باشد، لذا زمان شروع عملیات کار j روی ماشین i در زمان‏بندی اصلاح شده و اولیه باید یکسان باشد. اما برای بقیه عملیات‌ها می‌تواند به این پارامتر مقدار صفر یا یک داده شود و در نتیجه این امکان به مدیر و کنترل کننده سیستم داده می‌شود که زمان شروع عملیات‌های بعد از زمان تشخیص را مدیریت کند و در صورت لزوم برای زمان شروع آنها نیز زمان‏بندی اصلاح شده را یکسان با زمان‏بندی اولیه نماید.

در ادامه به محدودیت‌های کنترلی دیگری نیاز است تا اختلاف بین زمان‏بندی اولیه و اصلاح شده را مدیریت شود. همان‏طور که در مدل بخش 4-4 ارائه شد، دو متغیر  و  برنامه ترتیبی ماشین i و برنامه ترتیبی کار j  را مشخص می‌کردند. برای رعایت حداکثر تعداد تغییرات در این ترتیب‌ها بین زمان‏بندی اولیه و اصلاح شده باید قیود (12) تا (17) به مدل اضافه شود.

 

 

 

 

 

 

با توجه به تعریف،   متغیری دودویی است که اگر برابر یک باشد نشان می­دهد نوبت ماشین i در برنامه ترتیبی کار j در زمان‏بندی اولیه و زمان‏بندی اصلاح شده یکسان نیست. یعنی:. در قیود (12) و (13) برای هر i و j اگر این اختلاف وجود داشته باشد، متغیر  مقدار یک اختیار می­کند (در واقع ترکیب این 2 قید کار قدر مطلق را انجام می‌دهد) و با استفاده از قید (14) اجازه نمی­دهد مجموع تعداد این تغییرات از حداکثر تعداد تغییرات در نظر گرفته شده توسط کنترل کننده­ سیستم، یعنی  بیشتر شود. همینطور، قیود (15) تا (16) نیز در برنامه ترتیبی ماشین‌ها محدودیت لازم و مشابه را اعمال می­کنند، یعنی می­خواهد  اختلاف نوبت کارها در برنامه ترتیبی ماشین‌ها را در زمان‏بندی اولیه با زمان‏بندی اصلاح شده محاسبه کند و در اینجا نیز اجازه نمی‌دهد مجموع تعداد این تغییرات از حداکثر تعداد تغییرات در نظر گرفته شده توسط کنترل‌کننده سیستم یعنی  بیشتر شود.

در کل، قیود بالا برای کنترل اختلاف زمان‏بندی اولیه نسبت به زمان‏بندی جدید به کار گرفته‌ شده، میزان تغییرات را مدیر یا تصمیم‌گیرنده سیستم توزیع مشخص می­کند. در صورتی که این مقادیر صفر باشد، در واقع زمان‏بندی جدید مجبور است در کلیه مولفه‌ها با زمان‏بندی اولیه برابر باشد و هر چه این مقادیر بزرگتر باشد، فضای شدنی افزایش یافته و در نتیجه ممکن است به زمان‏بندی جدید بهتری دست یابد.

قیود (10) تا (17) به همراه قیود (2) تا (9) و تابع هدف (1) مدل برنامه‌ریزی واکنشی را تشکیل می‏دهند.

 

2- مثال عددی

حال مثالی عددی جهت تشریح و پیاده‌سازی مدل ارائه می‏شود. کلیه مدل­ها با نرم افزار  پیاده‌سازی و با ،  حل شده‏اند. مثال مورد نظر توسط رایانه­ای با مشخصات زیر حل شده است:

 

 

مسأله کارگاه باز با 3 ماشین و 5 کار در نظرگرفته می شود. داده‌های مربوط به زمان پردازش کارها بر روی ماشین‌ها و زمان تحویل کارها بر حسب ثانیه در ارائه شده است.

 


جدول 3- زمان پردازش و موعد تحویل کارها

زمان تحویل کارها

ماشین 3

ماشین 2

ماشین 1

کارها

40

12

10

5

کار 1

20

7

3

2

کار 2

60

18

21

20

کار 3

45

14

8

10

کار 4

50

7

22

9

کار 5

 

 

در شکل 2 نمودار گانت زمان‏بندی اولیه مشاهده میشود همچنین، این مثال نیز در 7 ثانیه به جواب بهین رسید.

 

.

شکل 2- نمودار گانت مربوط به زمان‏بندی اولیه

 

 

این مقاله، در ادامه برای بررسی مدل برنامه‌ریزی واکنشی ارائه شده، به ازای زمان تشخیص 5، 15 و 25 می‏پردازد، به این صورت که در به ازای هر یک از این زمان‏های موعد تحویل تغییر می‏یابد. البته برای اجرای مدل واکنشی نیاز به پارامترهای کنترلی نیزاست که مقادیر این پارامترها و موعد تحویل جدید در جدول (4) و جدول (5) آورده شده است

 

.

جدول 4- پارامترهای کنترلی کارها و موعد تحویل تغییر یافته

موعد تحویل جدید

موعد تحویل اولیه

 

کارها

35

40

2

کار 1

15

20

2

کار 2

50

60

2

کار 3

60

45

3

کار 4

50

50

3

کار 5

 


جدول 5- پارامترهای کنترلی ماشین‌ها

 

کارها

4

ماشین 1

4

ماشین 2

4

ماشین 3

 

مقدار پارامتر باینری بایستی یک باشد تا امکان تغییر زمان شروع عملیات کار j روی ماشین i در زمان‏بندی اصلاح شده نسبت به اولیه برای عملیات‌های بعد از زمان تشخیص وجود داشته باشد. در حالت کلی مقدار صفر برای این پارامتر بسیار سختگیرانه است و به زمان‏بندی اصلاح شده اجازه هیچ‏گونه تغییری نمی‌دهد، لذا به غیر شرایط خاص که کنترل کننده سیستم به عدم تغییر تاکید دارد مقدار صفر پیشنهاد نمی‌شود.

در جدول (4) امکان تغییر ترتیب ماشین‌ها برای کار j مقداردهی شده است. در جدول (5) امکان تغییر ترتیب کارها برای ماشین i مقدار 4 در نظر گرفته شده به این معنی که در برنامه ترتیبی ماشین i حداکثر 4 کار می‌تواند تغییر ترتیب دهند. هر چه این مقادیر بزرگتر انتخاب شود امکان تغییر زمان‏بندی اصلاح شده نسبت به زمان‏بندی اولیه بیشتر خواهد بود و با کوچک کردن این مقادیر برنامه زمان‏بندی اصلاح شده به زمان‏بندی اولیه نزدیک‌تر خواهد شد. شکل 4 تا 6 نمودارهای گانت مربوط به زمان‏بندی اصلاح شده در زمان‏های تشخیص 5، 15 و 25 را نشان می‌دهند. برنامه‌ریزی واکنشی مربوط به آنها نیز به ترتیب در 3.24 ، 2.8 و 1.6 ثانیه حل شدند.

 

 

شکل 3- نمودار گانت مربوط به زمان‏بندی اصلاح شده به ازای زمان تشخیص 5

 

شکل 4- نمودار گانت مربوط به زمان‏بندی اصلاح شده به ازای زمان تشخیص 15

 

شکل 5-نمودار گانت مربوط به زمان‏بندی اصلاح شده به ازای زمان تشخیص 25

 

 

   همان طور که در شکل 3 مشاهده می‌شود، چون زمان تشخیص تغییر موعد تحویل واحد 5 ام زمان بوده است، در نتیجه زمان‏بندی اولیه و اصلاح شده تا این ثانیه هیچگونه تفاوتی با هم ندارند اما بعد از این زمان:     در برنامه ترتیبی ماشین 1، ترتیب کارهای  4 و 5 جابه‏جا شده است. بنابر این، 2 تغییر وجود دارد.

در برنامه ترتیبی ماشین 2 نوبت کار 3 و 4 و 5 جابجا شده است. بنابر این3 تغییر وجود دارد.

در برنامه ترتیبی ماشین 3 نوبت کار 3 و 4 جابجا شده است. بنابر این 2 تغییر وجود دارد.

در برنامه ترتیبی کار 1 (رنگ سبز) هیچ تغییری وجود ندارد.

در برنامه ترتیبی کار 2 (رنگ قرمز) هیچ تغییری وجود ندارد.

در برنامه ترتیبی کار 3 (رنگ آبی) ماشین‌های 2 و 3 جابجا شده‌اند، در نتیجه 2 تغییر وجود دارد.

در برنامه ترتیبی کار 4 (رنگ نارنجی) ماشین‌های 1 و 2 و 3 جابجا شده‌اند، در نتیجه 3 تغییر وجود دارد.

در برنامه ترتیبی کار 5 ( رنگ قهوه‌ای تیره) ماشین‌های 1 و 2 و 3 جابجا شده‌اند، بنابراین 3 تغییر وجود دارد.

به همین ترتیب عملکرد زمان‏بندی اصلاح شده برای زمان‏های تشخیص 15 و 25 نیز بررسی شده اند و نتیجه‌ از نظر کنترل تغییرات بین زمان‏بندی اولیه و اصلاح شده بسیار مطلوب است، زیرا هم تغییرات لازم در برنامه زمان‏بندی ایجاد می‌شود و هم می‌توان کران بالایی برای این تغییرات لحاظ کرد. زمان حل برنامه‌ریزی واکنشی بسیار مطلوب و کمتر از حل مجدد مدل اصلی است. به بیان دیگر با توجه به اینکه عملیات‌های پردازش شده تا زمان تشخیص، ثابت در نظر گرفته می‌شوند و قیود کنترلی نیز به مدل اضافه می‌شوند، می‌توان دریافت که فضای جواب شدنی مسأله به شدت کاهش می‌یابد و در نتیجه زمان حل کاهش قابل ملاحظه‌ای خواهد داشت.

 

3- نتیجه‌گیری

در این مقاله، پس از مرور ضرورت بررسی و تمرکز بر مدل برنامه‌ریزی واکنشی و ارائه پیشینه و ادبیات مسأله­ کارگاه باز، یک مدل برنامه‌ریزی عدد صحیح آمیخته، برای آن ارائه شد تا زمان‏بندی اولیه برای مسأله توسط آن تولید ‌شود اما با توجه به طبیعت غیرقطعی مسأله کارگاه باز ممکن است بخاطر توسعه ساختار یا اتفاقات ضرورتی پیش‌بینی نشده در کارگاه، نیاز به اصلاح زمان‏بندی اولیه احساس شود. در نتیجه نیاز به ارائه یک برنامه‌ریزی واکنشی برای مسأله وجود دارد. در این مقاله، پارامتر حساس و کلیدی موعد تحویل، که در اجرا و ارائه زمان‏بندی مناسب نقش عمده‌ای را بر عهده دارد، از نظر برنامه‌ریزی واکنشی بررسی شد. به بیان ‌دیگر، به توسعه مدل ارائه شده و تبدیل آن در شرایط بروز تغییر در موعد تحویل به برنامه‌ریزی واکنشی پرداخته شد. به همین منظور، ابتدا الگوریتمی برای تشخیص عملیات‌ بدون تغییر معرفی شد و در ادامه پارامترها، متغییرها و قیود جدیدی را تعریف و به مدل اضافه شد. پس از آن برای آشنایی هر چه بهتر با مطالب ارائه شده بخش‌های پیشی، مثالی عددی ارائه شدکه نتیجه‌ آن از نظر کنترل تغییرات بین زمان‏بندی اولیه و اصلاح شده بسیار مطلوب است. زیرا هم تغییرات لازم در برنامه زمان‏بندی ایجاد می‌شود و هم می‌توان کران بالایی برای این تغییرات لحاظ کرد. از نظر زمان اجرا یعنی مقدار زمانی که برنامه برای اجرای کامل مدل مصرف می‏کند. زمان اجرا برنامه‌ریزی واکنشی بسیار مطلوب و کمتر از حل مجدد مدل اصلی است. از نظر پیچیدگی نیز باتوجه به اینکه مسأله کارگاه باز NP-hard است استفاده از مدل واکنشی که نیاز به حل مجدد مدل اولیه را از بین برده بسیار حایز اهمیت است.

 به بیان دیگر، با توجه به این که عملیات‌ تا زمان تشخیص ثابت در نظر گرفته می‌شوند و قیود کنترلی نیز به مدل اضافه می‌شوند، می‌توان دریافت که فضای جواب شدنی مسأله به شدت کاهش می‌یابد و در نتیجه زمان حل کاهش قابل ملاحظه‌ای خواهد داشت.

در همین راستا، برای یک کار پژوهشی آتی در راستای مطالعه انجام شده می‏توان به تمرکز بر پیچیدگی مدل پیشنهاد شده و همچنین، ارائه الگوریتمی برای حل مدل واکنشی پرداخت.



[1]- Revisions

[2] - Reactive

[3]-  Qulity robustness

[4] - Solution robustness

  

Akker, V.D , Hoogeveen, J.A., & Woeginger .G.J. (2003). “The two machine open shop problem: To fit or not to fit, that is the question”. Operations Research Letters, 31, 219-224.

Brasel, H., & Hennes, H. ( 2004). “On the open shop problem with preemption and minimizing the average completion time”. European Journal of Operational Research,  157, 607-619.

Cheng, T.C.E., &  Shakhlevich, N.V.( 2005).  “Minimizing non decreasing separable objective function for the unit time open shop scheduling problem”. European Journal of Operational Research, 165, 444-456.

Chen, R., Huang, W., & Tang, G. (2008). “Dense open shop schedules with release time”. Theoretical Computer Science, 407(1–3), 389–399.

Cowling, P., & Johansson, M. )2002(. “Using real time information for effective dynamic scheduling”. European Journal of Operational Research, 139 (2) , 230-244.

Giaro, K. , Kubale, M. , Piwakowski, K. )2002(. “Complexity results on open shop scheduling to minimize total cost of operations”. International Journal of Complex Systems in Science, 3, 84-91.

Jensen, M. T. (2003(. “Generating Robust and Flexible Job Shop Schedules using Genetic Algorithms”.  IEEE Transactions on Evolutionary Computation, 7 (3), 275-288.

Leung, J.Y.T ,  Li,H. ,  Pinedo,M.  and Sriskandarajah,C. (2005). “Open shops with jobs overlap revisited”. European Journal of Operational Research, 163, 569-571.

Liaw, C.F. , Cheng, C.Y. and Chen, M. (2005). “Scheduling two machine no wait open shops to minimize makespan”. Computers & Operations Research, 32, 901-917.

Liaw, C.F. (2005). “Scheduling preemptive open shop to minimize total tardiness”. European Journal of Operational Research, 162, 173-183.

Match Akturk, M. S. and Gorgulu, E.) 1999) . “Match-up scheduling under a machine breakdown”. European Journal of Operational Research, 112(1), 81-97.

Mosheiov,G. and Yovel,U. (2004). “Comments on flow shop and open shop scheduling with a critical machine and two operations per job”. European Journal of Operational Research, 157, 257-261.

Mosheiov, G. , Oron, D.(2008). “Open shop batch scheduling with identical jobs”. European Journal of Operational Research, 187, 1282-1292.

Noda, A.S. , Alcaide, D. , Martin, C.G. (2006). “Network flow approaches to preemptive open shop scheduling problems with time windows”. European Journal of Operational Research, 174, 1501-1518.

Noori-Darvish, S. , Mahdavi, I. , Mahdavi-Amiri, N. (2012). “A  bi-objective  possibilistic  programming  model  for  open  shop  scheduling problems  with  sequence-dependent  setup  times,  fuzzy  processing  times,  and fuzzy  due  dates”. Applied  Soft  Computing, 12, 1399–1416.

Sabuncuoglu, I. and Bayiz,M. ( 2000). “Analysis of reactive scheduling problems in a job shop environment”. European Journal of Operational Research, 126 (3), 567-586.

Sedeno-Noda,A. ,  Alcaide Lopez de Pablo, D. and Gonzalez-Martin, C. (2009). “A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows”. European Journal of Operational Research, 196(1), 140–154.

Seraj,O.  and Tavakkoli-Moghaddam, R. (2009). “A tabu search method for a new bi-objective open shop scheduling problem by a fuzzy multi-objective decision making approach”. International Journal of Engineering, Transactions A: Basics, 22, 1-14.

Shakhlevich, N.V. ( 2005). “Open shop unit time scheduling problems with symmetric objective function”. 4OR, 3, 117-131.

Suh, M. S. , Lee, A. , Lee, Y. J. and Ko, Y.K. (1998). “Evaluation of  ordering strategies for  constraint satisfaction reactive scheduling”. Decision Support Systems, 22(2), 187-197.

Van de vonder ,S. , Demeulemeester, E. and Herroelen, W. (2007). “A Classification of preactive-reactive project scheduling procedures” . Journal of Scheduling ,10 , 167-207.