نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 دانشجوی دکتری ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه مازندران، بابلسر، ایران
2 استادیار دانشکده علوم ریاضی، دانشگاه مازندران، بابلسر، ایران
3 کارشناس ارشد ریاضی کاربردی، دانشگاه مازندران، بابلسر، ایران
چکیده
کلیدواژه‌ها
عنوان مقاله [English]
نویسندگان [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]
1- مقدمه
زمانبندی، تخصیص منابع در افق برنامه‌ریزی برای اجرای مجموعه‌ای از وظایف است که استفاده از منابع در دسترس را بهینه میکند. در واقع، یک برنامه زمانبندی کارا می‌تواند به بهره‌برداری موثر از ظرفیت‌های تولید و افزایش سوددهی واحدهای تولیدی منجر گردد. زمان همیشه یکی از با ارزش‌ترین منابع موجود است، لذا زمانبندی منابع علاوه بر این که به افزایش کارایی و بهره‌برداری مناسب از ظرفیت تولید و نهایتا افزایش سوددهی یک سازمان منجر میشود، سبب کاهش زمان مورد نیاز برای تکمیل کارها و صرفه‌جویی در زمان به عنوان با ارزش‌ترین منبع نیز خواهد شد.
زمانبندی کارگاه باز، مجموعه‌ای از عملیات است که در پردازش آنها لزومی به رعایت ترتیب خاصی وجود ندارد. بنابر این، فضای جواب در مسائل زمانبندی کارگاه باز به شکل قابل ملاحظهایی نسبت به فضای جواب مسائل دیگر بزرگتر است. از طرفی، با بررسی پیشینه مسأله به نظر می‌رسد، پژوهشگران توجه کمتری نسبت به مسائل کارگاه باز داشته‌اند. مسائل زمانبندی در محیط کارگاه باز شامل m ماشین و n کار هستند که هرکار حداکثر می‌تواند شامل m عملیات باشد. هر عملیات بایستی بر روی یک ماشین با زمان پردازش معین انجام شود.
بیشتر پژوهشهای انجام شده در مسائل زمانبندی بدون آن که توجه کافی به اتفاقات پیش‌بینی نشده داشته باشند؛ به طور عمده بر تولید یک زمانبندی خوب تمرکز دارند. در واقع، انتقاد اصلی مچ اکتورک و جورجولو (1999) و کامانگ و جانسون (2002) که بر مدل‌های زمانبندی ایستا و قطعی وارد است؛ به علت بیتوجهی به این نکته است که رخدادهای واقعی که در کارگاه اتفاق می‌افتند، از نظر تعداد بیشتر و بسیار متفاوت‌تر در مقایسه با عملیات و رخدادهای پیش‌بینی شده از قبیل زمان جداسازی کارها از ماشین، زمان آماده‌سازی کارها بر روی ماشین و غیره هستند. در اقع ممکن است عوامل گوناگونی رخ دهند که زمانبندی اولیه را مختل کند، بنابر این، یک عمل اصلاحی مناسب (یا واکنشی) باید رخ دهد تا وضعیت زمانبندی اولیه را بهبود بخشد یا آن را از نشدنی بودن رها سازد. از سوی دیگر، مسأله را در افق زمانی پیوسته مد نظر می‌گیرد. ابتدا زمانبندیی با اطلاعات کامل و مشخص اولیه تولید میکند و پردازش کارها منطبق با این زمانبندی انجام میشود و به محض این که اطلاعات جدیدی از موعد تحویل کارها به دست آمد، یک زمانبندی جدید منطبق با شرایط جدید تولید میشود که به آن زمانبندی اصلاح شده می‌گوییم. بنا به گفته سبابونجولکو و بایز (2000) در عملیات صنعتی، اکثر سیستم‌های زمانبندی، برای پاسخ‌گویی به رویدادهای غیرمنتظره و اصلاح درست زمانبندی اولیه و یا به علت پیچیدگی ترکیبی مسأله زمانبندی، که بار اضافی برای فرد برنامه‌ریز ممکن است باشد و باعث تولید زمانبندیهای ضعیف و یا حتی نشدنی توسط او شود، خواهان استفاده از برنامه‌ریزی واکنشی هستند. از نظر دیگر نیز (جیارو، کوبل، پواکوسکی، 2002) با بررسیهای دقیق، مسأله کارگاه باز را NP-hard دسته‌بندی کرده، لذا در صورت بروز رویدادهای غیرمنتظره حل مجدد مدل اولیه از نظر هزینه محاسباتی و زمان اجرای مدل اولیه، مقرون به صرفه نیست. با توجه به آنچه گفته شد، زمانبندی واکنشی در هر سیستم زمانبندی با اهمیت است.
در این مقاله، یک مدل برنامه‌ریزی عدد صحیح آمیخته، برای مسائل زمانبندی در محیط کارگاه باز ارائه شده است که زمانبندی اولیه برای مسأله از آن به دست خواهد آمد. اما با توجه به طبیعت غیر قطعی مسأله کارگاه باز، همیشه به علت توسعه ساختار یا اتفاقات ضروری پیش‌بینی نشده در کارگاه، تغییر کرده و در نتیجه زمانبندی اولیه نیز باید تغییر کند، از اینرو، نیاز به ارائه یک برنامه‌ریزی واکنشی برای مسأله وجود دارد. لفظ واکنشی در سبابونجولکو و بایز (2000) اصلاحی[1] و در سوه، لی و کو ( 1998) واکنشی[2] نامیده شده است و بخش واکنشی یک سیستم در واقع کار مانیتورینگ اجرا و انجام زمانبندی اولیه را بر عهده دارد و همچنین، باید از عهده اتفاقات غیر منتظره سیستم که زمانبندی را عوض میکند به خوبی برآید. در این مقاله، پارامتر حساس و کلیدی موعد تحویل که در اجرا و ارائه زمانبندی مناسب نقش عمده‌ای را بر عهده دارد، از نظر برنامه‌ریزی واکنشی بررسی میشود. به عبارت دیگر، این مقاله، برنامه‌ریزی واکنشی متمرکز بر موعد تحویل ارائه می دهد.
این مقاله، به این شکل مرتب شده که در بخش 2 مروری بر پیشینه و ادبیات مسأله زمانبندی کارگاه باز دارد، در بخش 3 مسأله زمانبندی کارگاه باز (Open Shop Scheduling Problem) را تشریح میشود، در بخش 4 فرمول‌بندی برای مسأله کارگاه باز ارائه میشود که زمانبندی اولیه را تولید میکند، بخش 5 به توسعه مدل و ارائه برنامه‌ریزی واکنشی در شرایط بروز تغییر در موعد تحویل میپردازد، به همین منظور، ابتدا الگوریتمی برای تشخیص عملیات‌های بدون تغییر معرفی می شود و در ادامه؛ پارامترها، متغیرها و قیود جدیدی را تعریف و به مدل اضافه میشود. در بخش 6 برای آشنایی هر چه بهتر با روند ارائه شده در بخش‌های پیش، مثال عددی بررسی می شود و در بخش 7 جمع‌بندی و نتیجه‌گیری مقاله ارائه میشود.
هر چند در گذشته توجه کمتری نسبت به مسائل کارگاه باز شده اما، به نظر می‌رسد در سال‌های اخیر مسائل زمانبندی کارگاه باز مد نظر پژوهشگران بسیاری قرار گرفته است. با این حال، مسائل کارگاه باز در مقایسه با سایر مسائل زمانبندی سهم بسیار اندکی از ادبیات موضوع را به خود اختصاص داده است.
سدنو، الکاید لوپز دی پابلو، گونزالز مارتین (2009) روشی را بر مبنای جریان شبکه با فرض وجود پنجره زمانی، قابلیت بریدگی کارها ارائه نمودند. محدودیت پنجره زمانی آنها نیز باید به طور اکید برقرار شود. آنها به طور هم زمان دو معیار را برای کمینه‌سازی انتخاب نمودند. چن و هانگ و تانگ (2008) به بررسی توالی‌های انبوه برای مسأله زمانبندی کارگاه باز پرداختند. آنها در پژوهش خود مسأله مورد نظر را با فرض وجود محدودیت‌های زمانهای ترخیص بررسی نمودند. همچنین، در سناریوی مورد نظر خود مسأله کارگاه باز را با محدودیت عدم وجود زمان بیکاری ماشین‌ها مطالعه کرده‌اند. موشیف و یاول (2008) به بررسی زمانبندی کارگاه باز دسته‌ای پرداختند. آنها در مسأله خود فرض نمودند که زمان پردازش کارها مشابه بوده و زمآنهای آماده‌سازی را وابسته به توالی در نظر گرفتند. همچنین، در سناریوی مورد بررسی وی، دسته‌ها در هر لحظه آماده پردازش هستند. هدف از این مسأله محاسبه مقدار بهینه هر دسته بوده است. نودا و آلکاید و مارتین (2006) رویکردهای جریان شبکه را برای مسائل زمانبندی با مجاز بودن بریدگی کارها و با فرض وجود پنجره زمانی ارائه دادند. لیاو (2005) مسأله زمانبندی کارگاه باز را برای کمینه‌سازی کل دیرکردها و با فرض مجاز بودن بریدگی کارها بررسی شد. لیونگ و لی و پیندو و سریسکاندراجه (2005) مسأله کارگاه باز را با فرض کارهای متداخل مطالعه نمودند. آنها مسأله را در حالت دو ماشینه بررسی نمودند و فرض کردند که هر کار باید روی هر دو ماشین پردازش شوند. البته در پژوهش آنان برخلاف مسأله کارگاه باز کلاسیک، هر دو عملیات مربوط به یک کار می‌توانند در یک زمان با یکدیگر تداخل داشته باشند. تابع هدفی که برای کمینه‌سازی انتخاب شده کل زمان اتمام کارها است.
لیاو و چنگ و چن (2005) زمانبندی دو ماشینه در محیط کارگاه باز در حالت بدون توقف را بررسی کردند. آنها حداکثر زمان تکمیل کارها را به عنوان یک معیار برای کمینه‌سازی انتخاب نمودند. چنگ و شاخلویچ (2005) بر روی کمینه‌سازی توابع هدف غیر نزاما جدا از هم، برای مسأله زمانبندی کارگاه باز با زمان واحد پرداختند. آنها در مطالعه خود هر دو حالت مجاز بودن و نبودن بریدگی را بررسی نمودند. این پژوهشگران برای مجموعه توالی‌های موجه، زمانهای اتمام کار را محاسبه کردند. براساس خواص چند وجهی زمانبندی حاصل، آنها نشان دادند که مسأله ایجاد یک توالی بهینه، برای کمینه‌سازی یک تابع هزینه مجزای غیر نزاما از زمان اتمام کار، به صورت چندجمله‌ای قابل حل است. شاخلویچ (2005) مسأله زمانبندی کارگاه باز را با فرض وجود عملیات‌های زمان واحد و تابع هدف غیر صعودی و متقارن وابسته به زمان اتمام کارها بررسی نمود. براسل و هنس (2004) به مطالعه مسأله کارگاه باز با فرض مجاز بودن بریدگی کارها پرداخته‌اند، آنها معیار متوسط زمان اتمام کارها را در مسأله خود در نظر گرفته و مدل‌های جدیدی از مسائل زمانبندی با فرض مجاز بودن بریدگی ارائه کرده‌اند. موشیف و یول (2004) مطالعه‌ای را در مورد زمانبندی جریان کارگاهی و کارگاه باز با فرض وجود ماشین بحرانی انجام دادند. آنها فرض کردند که هرکار حداکثر از دو عملیات تشکیل میشود. یکی از این دو عملیات برای همه کارها مشترک است. آکر و هوشاوین و وگینر (2003) به بررسی مسأله زمانبندی در محیط کارگاه باز دارای دو ماشین پرداختند. در این سناریو، هرکار شامل دو عملیات بوده و فرض میشود که عملیات تولید (دوم) باید توسط ماشین اول (دوم) انجام شود. در این پژوهش، ترتیبی که عملیات‌ها باید انجام شود ثابت نبوده و بازههای زمانی پردازش آنها نمی‌تواند تداخل داشته باشد. سراج و توکلی مقدم (2009)، یک الگوریتم جستجوی ممنوع چند هدفه جدید که بر مبنای رویکرد تصمیم‌گیری چند هدفه فازی است، برای مسأله کارگاه باز دوهدفه ارائه نمودند. آنها مسأله پیشنهادی خود را با پارامترهای قطعی در نظر گرفته و در آن به حداقل سازی میانگین زمانهای تکمیل و میانگین مقادیر دیرکرد کارها به طور همزمان پرداختند. در مدل ارائه شده، زمانهای آماده‌سازی به شکل مستقل از توالی در نظر گرفته شده است. نوری درویش و ایرج مهدوی و نظام مهدوی امیری (2012) زمانبندی کارگاه باز را با دنباله وابسته به زمان آماده سازی، زمان پردازش فازی و زمان تحویل فازی در نظر گرفتند. در سبابونجولکو و بایز (2000) بررسی کاملی مرتبط با کارهای صورت گرفته در برنامه‌ریزی واکنشی جریان کارگاهی (JSSP) انجام شده است.
زمانبندی واکنشی برای پیاده‌سازی موفقیت‌آمیز سیستم‌های زمانبندی با اهمیت است اما، تاکنون هیچ پژوهش قابل ملاحظه‌ای در ارتباط با زمانبندی واکنشی مسأله کارگاه باز انجام نشده است، این مقاله، به بررسی این موضوع میپردازد.
مسأله زمانبندی در محیط کارگاه باز متشکل از m ماشین و n کار است که هر کار تشکیل شده از دنباله . هر عملیات پردازشی از کار j روی ماشین i است و دارای زمان پردازش مشخص است، بنابر این، هر کار j حداکثر شامل m عملیات روی m ماشین است به عبارت دیگر هر کار حداکثر یک پردازش روی هر ماشین دارد و ترتیب پردازش کار j مشخص نیست، هر ماشین حداکثر یک کار را می‌تواند در یک زمان پردازش کند و بریدگی کارها مجاز نیست، به این معنی که پردازش یک عملیات از لحظهای که شروع میشود تا زمانی که کامل شود ادامه پیدا میکند و از ماشین جدا نمیشود. تابع هدف مسأله کمینه‌سازی مجموع دیرکرد کارها در نظر گرفته شده است. مجموع دیرکرد معیاری برای اندازه‌گیری تأخیر در تحویل به موقع محصولات محسوب میشود.
فرضیههای ذیل برای مدل‌سازی مسأله در نظر گرفته شد.
1) کارها می‌توانند با هر ترتیب دلخواهی بر روی ماشین‌ها پردازش شوند.
2) زمان پردازش کارها بر روی ماشین‌های متفاوت می‌تواند با هم تفاوت داشته باشد.
3) هر کار در هر لحظه حداکثر می‌تواند بر روی یک ماشین پردازش شود.
4) بریدگی کارها و خرابی ماشین‌ها مجاز نیست.
5) درجه اهمیت کارها الزاماً یکسان نیست.
6) هر کار دارای موعد تحویل معینی است.
7) از هر نوع ماشین تنها یکی در محیط کاری موجود دارد.
با در نظر گرفتن روابط و فرضیههای بالا، مسأله مد نظر به شکل یک برنامه‌ریزی خطی عدد صحیح آمیخته مدل‌سازی شده که در زیر مجموعه‌ها، پارامترها، متغیرها و سرانجام محدودیت‌های لازم ارائه می‌شوند.
تمام پارامترها با علامت ( ) بالای آنها قابل تشخیص هستند.
مدل برنامه‌ریزی عدد صحیح آمیخته به شکل زیر فرمول‌بندی میشود:
(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 است؛ استفاده از مدل و روشی که در صورت بروز رخدادهای مختل کننده نیاز به حل مجدد مدل اولیه نباشد؛ بسیار حایز اهمیت است، از اینرو در بخش بعد، مقاله به ارائه مدل واکنشی میپردازد.
بر اساس نظر ون ده واندر و دیملمستر و هرولن (2007) اصلاح زمانبندی اولیه می‌تواند به شکل، استواری پاسخ[3]، استواری کیفیت[4] یا ترکیبیباشد. هدف در گونه استواری پاسخ این است که تغییرات ایجاد شده بین زمانبندی اصلاح شده و برنامه زمانبندی اولیه حداقل باشد و در واقع، تابع هدف این مدل کمینه سازی تغییرات زمانبندی اولیه و اصلاح شده است به بیان دیگر، تابع هدف از نوع کمینه‌سازی انحراف مسأله اولیه از مسأله ثانویه است، در گونه استواری کیفیت به بالا بردن کیفیت جواب توجه میشود و تابع هدف آن نیز معمولا همان تابع هدف مدل اولیه است و به تغییرات ایجاد شده بین زمانبندی اصلاح شده و برنامه زمانبندی اولیه توجهی نمی‌کند.
در گونه ترکیبی تابع هدف نسبت به مدل اولیه تغییر نمی‌کند اما سقف و کران بالایی برای تغییرات بین زمانبندی اولیه و اصلاح شده در قیود در نظر گرفته میشود.
در این مقاله گونه ترکیبی برنامه‌ریزی واکنشی استفاده شده است، یعنی یک کران که توسط مدیر و ناظر سیستم برای کنترل تغییرات نسبت به زمانبندی اولیه در نظر می‌گیرد. به بیان دیگر، به دنبال کمینه کردن تأخیر ارائه کارها در زمانبندی اصلاح شده است، اما سعی دارد تغییرات بین زمانبندی اصلاح شده و اولیه را نیز کنترل کند.
ابتدا کلیت اصلاح زمانبندی اولیه در شکل 1 نشان داده شده است:
شکل 1- روند اصلاح زمانبندی اولیه
پیش از تشریح چگونگی اصلاح زمانبندی اولیه باید مفهوم زمان تشخیص تعریف شود.
زمان تشخیص: به زمان مطلع شدن از تغییرات صورت گرفته در موعد تحویل، زمان تشخص گفته میشود.
زمانبندی اولیه در کارگاه به کار گرفته می شود و پردازش کارها بر روی ماشین‌ها آغاز می شود. اگر تغییری در موعد تحویل کارها ایجاد نشود، زمانبندی اولیه تا پردازش تمامی عملیات‌های کارها اجرا میشود، اما اگر تغییری در موعد تحویل ایجاد شود، زمانی که از تغییرات آگاه شویم مجبور به اصلاح زمانبندی اولیه هستیم. بدیهی است که هرچه عملیات کمتری از کارها باقیمانده باشد و مدت بیشتری از زمانبندی اولیه استفاده شده باشد دیگر اصلاح زمانبندی اولیه اهمیت و کاربرد کمتری خواهد داشت.
شکل 1 به مرحله اول (زمانبندی اولیه) و مرحله دوم (زمان تشخیص یا زمان مطلع شدن از تغییرات) اشاره دارد. در مرحله سوم به این علت که در زمانبندی جدید (اصلاح شده)، عملیات کارهای پیش از زمان تشخیص را نمیشود تغییر داد، بایستی زمانبندی عملیات پردازش نشده تغییر یابد. برای اینکار الگوریتمی ارائه شده است.
تمام پارامترها، متغیرها و مولفه‌های زمانبندی اولیه با علامت که در بالای آن قرار می‌گیرد مشخص شده‌اند. برای مثال، زمان پایان تمام پردازش‌های مورد نیاز کار j در زمانبندی اولیه است.
برای اجرای دسته‌بندی پردازش عملیات از الگوریتم زیر استفاده شد.
در زمانبندی اصلاح شده، عملیاتی که پیش از زمان تشخیص انجام شده‌اند، قابل تغییر نیستند. الگوریتمی که درشکل نمایش داده شده است، در واقع عملیات را بر حسب زمان تشخیص دسته‌بندی میکند. مقاله در ادامه به تشریح این الگوریتم میپردازد.
در حلقه تکرار، این که زمان شروع پردازش کار j روی ماشین i پیش از زمان تشخیص
( ) بوده یا بعد از آن بررسی میشود. با توجه به این که تنها عمل این الگوریتم مقایسه بین زمان شروع و زمان تشخیص است و با وجود الگوریتمهای مقایسه با زمان اجرای بسیار مناسب، توانایی این الگوریتم برای حل مسائل با سایز بزرگ تضمین شده است.
اگر زمان شروع پردازش کار پیش از زمان تشخیص باشد و چون بریدگی کار از ماشین در این مسأله مجاز نیست، لذا زمان شروع پردازش کار j روی ماشین i در زمانبندی اصلاح شده نیز باید برابر با زمانبندی اولیه باشد. بدین منظور باید (که متغییری دودویی است برابر یک است؛ یعنی این امکان وجود دارد که زمان شروع پردازش کار j روی ماشین i در زمانبندی اصلاح شده نسبت به زمانبندی اولیه متفاوت باشد و اگر صفر شود یعنی باید زمان شروع پردازش کار j روی ماشین i با مقدار آن در زمانبندی اولیه یکسان باشد) برابر صفرشود تا زمانبندی اصلاح شده به رعایت برابری با زمانبندی اولیه تا پیش از زمان تشخیص ملزم شود.
حال‌که عملیات پیش و بعد زمان تشخیص معین شده‌اند، در مرحله چهارم بایستی اصلاحات لازم بر روی عملیاتی که بعد از زمان تشخیص انجام خواهند شد، اعمال شود. برای اینکار از مدل استفاده شده است.
هدف از بهکارگیری این مدل اصلاح زمانبندی اولیه با توجه به تغییر در موعد تحویل است و بدین صورت انجام می‌گیرد که وقتی در زمان تشخیص، تغییری در موعد تحویل کارها رخ دهد، بایستی زمانبندی جدیدی ارائه شود به طوری که مولفه تمام عملیاتش تا زمان تشخیص با زمانبندی اولیه برابر باشد و برای مدت زمان باقیمانده با توجه به موعد تحویل جدید کمترین تأخیر در موعد تحویل داشته باشد. لذا برای این منظور، مدل ارائه میشود.
شایان ذکر است، مجموعه‌ها و اندیس‌های این مدل مشابه با آنچه در بخش 4-1 تعریف شده است است.
علاوه بر پارامترهای بخش 4-2 چون بایستی تعداد تغییرات بین زمانبندی اولیه و اصلاح شده نیز کنترل شود، نیاز به تعریف پارامترهای جدیدی به شرح جدول (1) است.
جدول 1- تعریف پارامتر های جدید
منظور از برای پارامتر اعداد صحیح از 0 تا m (تعداد ماشین‌ها) به غیر از یک است چون اگر یک ترتیب یا نوبت یک کار در برنامه ترتیبی ماشین i تغییر کند، مطمئناً با کار دیگری جابجا شده است، پس نوبت آن کار نیز تغییر کرده و لذا تعداد تغییرات 2 است و این پارامتر نمی‌تواند عدد 1 باشد. به بیان دیگر عدد 1 برای این پارامتر، همان عمل عدد صفر را انجام میدهد. حداکثر مقدار این پارامتر نیز در شرایطی که ترتیب تمام کارها تغییر کند و جایگشتی کاملاً متفاوت از ترتیب کارها حاصل شود mاست. همین استدلال برای مقادیر پارامتر نیز قابل بیان است.
جدول 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) مدل برنامه‌ریزی واکنشی را تشکیل می‌دهند.
حال مثالی عددی جهت تشریح و پیاده‌سازی مدل ارائه میشود. کلیه مدلها با نرم افزار پیاده‌سازی و با ، حل شده‌اند. مثال مورد نظر توسط رایانهای با مشخصات زیر حل شده است:
مسأله کارگاه باز با 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 نیز بررسی شده اند و نتیجه از نظر کنترل تغییرات بین زمانبندی اولیه و اصلاح شده بسیار مطلوب است، زیرا هم تغییرات لازم در برنامه زمانبندی ایجاد میشود و هم می‌توان کران بالایی برای این تغییرات لحاظ کرد. زمان حل برنامه‌ریزی واکنشی بسیار مطلوب و کمتر از حل مجدد مدل اصلی است. به بیان دیگر با توجه به اینکه عملیات‌های پردازش شده تا زمان تشخیص، ثابت در نظر گرفته می‌شوند و قیود کنترلی نیز به مدل اضافه می‌شوند، می‌توان دریافت که فضای جواب شدنی مسأله به شدت کاهش می‌یابد و در نتیجه زمان حل کاهش قابل ملاحظه‌ای خواهد داشت.
در این مقاله، پس از مرور ضرورت بررسی و تمرکز بر مدل برنامه‌ریزی واکنشی و ارائه پیشینه و ادبیات مسأله کارگاه باز، یک مدل برنامه‌ریزی عدد صحیح آمیخته، برای آن ارائه شد تا زمانبندی اولیه برای مسأله توسط آن تولید شود اما با توجه به طبیعت غیرقطعی مسأله کارگاه باز ممکن است بخاطر توسعه ساختار یا اتفاقات ضرورتی پیش‌بینی نشده در کارگاه، نیاز به اصلاح زمانبندی اولیه احساس شود. در نتیجه نیاز به ارائه یک برنامه‌ریزی واکنشی برای مسأله وجود دارد. در این مقاله، پارامتر حساس و کلیدی موعد تحویل، که در اجرا و ارائه زمانبندی مناسب نقش عمده‌ای را بر عهده دارد، از نظر برنامه‌ریزی واکنشی بررسی شد. به بیان دیگر، به توسعه مدل ارائه شده و تبدیل آن در شرایط بروز تغییر در موعد تحویل به برنامه‌ریزی واکنشی پرداخته شد. به همین منظور، ابتدا الگوریتمی برای تشخیص عملیات بدون تغییر معرفی شد و در ادامه پارامترها، متغییرها و قیود جدیدی را تعریف و به مدل اضافه شد. پس از آن برای آشنایی هر چه بهتر با مطالب ارائه شده بخش‌های پیشی، مثالی عددی ارائه شدکه نتیجه آن از نظر کنترل تغییرات بین زمانبندی اولیه و اصلاح شده بسیار مطلوب است. زیرا هم تغییرات لازم در برنامه زمانبندی ایجاد میشود و هم می‌توان کران بالایی برای این تغییرات لحاظ کرد. از نظر زمان اجرا یعنی مقدار زمانی که برنامه برای اجرای کامل مدل مصرف میکند. زمان اجرا برنامه‌ریزی واکنشی بسیار مطلوب و کمتر از حل مجدد مدل اصلی است. از نظر پیچیدگی نیز باتوجه به اینکه مسأله کارگاه باز NP-hard است استفاده از مدل واکنشی که نیاز به حل مجدد مدل اولیه را از بین برده بسیار حایز اهمیت است.
به بیان دیگر، با توجه به این که عملیات تا زمان تشخیص ثابت در نظر گرفته می‌شوند و قیود کنترلی نیز به مدل اضافه می‌شوند، می‌توان دریافت که فضای جواب شدنی مسأله به شدت کاهش می‌یابد و در نتیجه زمان حل کاهش قابل ملاحظه‌ای خواهد داشت.
در همین راستا، برای یک کار پژوهشی آتی در راستای مطالعه انجام شده می‌توان به تمرکز بر پیچیدگی مدل پیشنهاد شده و همچنین، ارائه الگوریتمی برای حل مدل واکنشی پرداخت.
)