پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شماره‌ها | 1,706 |
| تعداد مقالات | 13,972 |
| تعداد مشاهده مقاله | 33,570,162 |
| تعداد دریافت فایل اصل مقاله | 13,310,793 |
توسعه یک کران بالا و الگوریتم حـل ابتـکاری برای مسأله زمانبنـدی سفارشـات با هدف کمینه سازی زمان بیکاری ماشین ها | ||
| پژوهش در مدیریت تولید و عملیات | ||
| مقاله 3، دوره 3، شماره 2، مهر 1391، صفحه 41-58 اصل مقاله (883.82 K) | ||
| نوع مقاله: مقاله پژوهشی- فارسی | ||
| نویسندگان | ||
| هادی مختاری1؛ عیسی نخعی کمال آبادی* 2؛ سید حسام الدین ذگردی2 | ||
| 1دانشجوی دکتری مهندسی صنایع دانشکده فنی و مهندسی دانشگاه تربیت مدرس | ||
| 2دانشیار مهندسی صنایع دانشکده فنی و مهندسی دانشگاه تربیت مدرس | ||
| چکیده | ||
| در این تحقیق، مسأله زمانبندی تولید سفارش‌های یک سازنده، با معیار کمینه‌سازی زمان بیکاری ماشینها، مدلسازی شده و سپس یک رویکردی تحلیلی به منظور حل آن طراحی شد. در مسأله پیشنهادی، تولیدکننده تعدادی سفارش را در ابتدای افق برنامه‌ریزی از مشتریان دریافت می‌نماید، که هر کدام از آنها به دو مرحله عملیات مجزا برای تکمیل نیاز دارند. در راستای کاهش هزینه موجودی هنگام ساخت، محدودیت عدم انتظار بین عملیات بین دو مرحله تولیدی لحاظ شده است. پس از اثبات معادل بودن زمانبندی ناشی از کمینه‌سازی زمان کل بیکاری ماشینها، با زمانبندی حاصل از معیار حداکثر زمان تکمیل کارها، مفهومی با عنوان «زوج سفارش» تعریف، و الگوریتمی به منظور تعیین زوج سفارش‌های بهینه بر مبنای مدل مسأله تخصیص متقارن ارائه شد. بر اساس زوج سفارش‌های تشکیل شده، کران بالایی بر مبنای سهم کل زوج سفارش‌های از زمان کل بیکاری ماشینها استخراج شد. همچنین حالات مختلف بهبود کران بالای توسعه داده شده، در 12 وضعیت بالقوه که در تعیین توالی دو زوج سفارش ممکن است، بررسی و میزان بهبود کران بالا، در هر حالت اثبات شد. در نهایت، یک الگوریتم حل ابتکاری، بر اساس نتایج حاصل از بهبودهای زوجی توسعه داده شد و همچنین، یک مثال عددی در راستای اثبات کابرد رویکرد پیشنهادی بررسی و تحلیل شد. | ||
| کلیدواژه‌ها | ||
| زمانبندی سفارشات؛ رویکرد حل تحلیلی؛ کران بالا؛ مسأله تخصیص متقارن | ||
| اصل مقاله | ||
|
1-مقدمه زمانبندی فرآیندی است که در آن تخصیص منابع به منظور انجام مجموعهای از کارها در یک دوره زمانی انجام می‌گیرد (بیکر[1]، 1974). در سالیان اخیر توسعه‌ی مدل‌های ریاضی که به ارائه تکنیک‌های حل و کاربردهای عملیاتی زمانبندی در صنایع مختلف منجر میشوند، به عنوان پل و ارتباطی بین تئوری و اجرا مطرح شده‌اند. رویکردهای تئوری مدلسازی و حل مسائل زمانبندی با ساختارهای پیچیده، حجم زیادی از مسائل کمی را شامل می‌شود. این رویکردهای ریاضی با یک توصیف اولیه از منابع در دسترس و کارهایی که باید انجام شوند، شروع شده و در نهایت به مدلسازی این شرایط در محموعه‌ای از محدودیت‌ها و توابع هدف منجر میشوند. در بهترین حالت، تابع هدف مسأله زمانبندی باید کلیه هزینه‌های تصمیمات زمانبندی را در برگیرد، اما در عمل، اندازه‌گیری و مدلسازی چنین هزینه‌ای بسیار دشوار است. نوعاً سه دسته کلی از توابع هدف در مسائل زمانبندی قابل به کارگیری هستند: دسته اول شامل توابع هدف مبتنی بر زمان تکمیل[2] هستند که در آنها زمان مورد نیاز برای تکمیل کارها ارزیابی میشوند، در حالی که دسته دوم توابع هدف مبتنی بر موعد تحویل[3] هستند که در این دسته معیار ارزیابی یک زمانبندی، عملکرد آن زمانبندی در برآورده سازی موعد مقرر تحویل کار به مشتری است. علاوه بر نوع توابع هدف، عوامل مختلف دیگری نیز همچون پیکربندی منابع تولیدی (ماشن‌آلات، وسائل حمل و نقل، نیروی انسانی و غیره) و ماهیت کارها (سفارش‌ها) در دستهبندی مسائل زمانبندی دخیل هستند. برای نمونه، یک مدل زمانبندی ممکن است شامل یک یا چندین ماشین باشد. در حالت تک ماشینه، نوعاً کارها نیز تنها به یک عملیات تولیدی برای پردازش نهایی نیاز دارند، در حالی که مدل‌های با چند ماشین، شامل کارهایی با چندین مرحله عملیات هستند. همچنین، در حالت اول، ماشین‌های مشابه قابلیت چینش به صورت موازی را دارا هستند. علاوه بر این دستهبندی، اگر مجموعه کارهای دریافت شده توسط سازنده برای پردازش، در طول زمان تغییری نداشته باشند، مدل زمانبندی، استاتیک نامیده می‌شود و در حالی که اگر در طول زمان کارهای جدیدی نیز وارد شوند، به چنین مدلی، مدل زمانبندی پویا اطلاق می‌گردد. مدل‌های استاتیک نسبت به مدل‌های پویا، حجم بیشتری از ادبیات زمانبندی را به خود تخصیص داده‌اند. علاوه بر این، اگر همه پارامترهای مؤثر بر مدل زمانبندی از قبل مشخص و قطعی باشند، مدل‌های قطعی زمانبندی مطرح میشوند و در نقطه مقابل این مدل‌ها، مسائل تصادفی زمانبندی با عدم قطعیت در پارامترها دستهبندی میشوند. معمولاً دو دسته از محدودیت‌ها در مسائل زمانبندی مطرح هستند: دسته اول مربوط به محدودیت در ظرفیت منابع تولیدی شامل ماشین‌آلات هستند و دسته دوم محدودیت‌های توالی تکنولوژیکی انجام کارها را نمایش می‌دهند. به طور کلی، مسائل زمانبندی شامل دو نوع تصمیم: «تخصیص منابع تولیدی به کارها» و «تعیین توالی انجام کارها» هستند. یکی از مدل‌های خاص زمانبندی، مدل‌های زمانبندی در شرایط عدم انتظار[4] است که مربوط به نحوه انجام کارهاست. مسأله زمانبندی در حالت عدم انتظار یک مسأله زمانبندی را معرفی می‌نماید که در آن یک محدودیت جدید به مسأله عمومی زمانبندی اضافه شده است. این محدودیت جدید که در صنایعی همانند صنعت چاپ و نشر مشاهده می‌شود، بیان می‌نماید که هیچ کدام از کارها نمی‌توانند هیچ زمان انتظاری را تحمل کنند، مگر روی ماشین اول. یک مجموعه از کار و ماشین داده شده است، به گونه‌ای که هر کار باید مسیر خاص و از پیش تعیین شده‌ای را از میان ماشینها طی نماید. علاوه بر این، یک ماتریس که بیانگر زمان فرآیندهای کارهاست، به عنوان ورودی به مسأله داده شده است. به منظور برقراری محدودیت عدم انتظار در این مسأله، به محض اینکه اولین فرآیند هر کار شروع شد، باید کلیه فرآیندهای آن بدون هیچ انتظاری بین ماشینها و هیچ انقطاعی حین فرآیندها، به اتمام برسد. در واقع، مسأله زمانبندی در حالت عدم انتظار، حالت خاصی از مسأله عمومی زمانبندی است که در آن هیچ زمان انتظار و انقطاعی برای کارها مجاز نیست. به عبارت دیگر، تفاوت بین زمان تکمیل همه کارها و زمان شروع آنها باید دقیقاً برابر با مجموع زمان کلیه فرآیندهای آن باشد. در ادبیاتِ مسائل زمانبندی، عموماً مسائلی زمانبندی در حالت عدم انتظار با تابع هدف حداکثر زمان تکمیل کارها در نظر گرفته شده است و همچنین، نشان داده شده است که این مسأله حتی با دو ماشین، یک مسأله قویاً NP-Hard است. هال[5] وسیریسکانداراجاه[6] (1996) ادبیات مسائل در حالت عدم انتظار را مرور کرده و همچنین نشان دادند که مسأله فوق مخصوصاً برای ابعاد بزرگ مسأله، جزو مسائل سخت بهینه‌سازی محسوب می‌شود. ادبیات مربوط به این مسأله قابل تقسیم به دو حیطه است: (1) پیچیدگی محاسباتی مسأله؛ (2) رویکردهای حل مسأله. بر اساس اطلاعات نویسنده این تحقیق، فقط تعداد محدودی تحقیق، مرتبط با روش‌های حل برای این مسأله ارائه شده است. در مورد روش‌های دقیق حل، تنها یک الگوریتم شاخه و کران در ادبیات توسعه داده شده است (ماسکیس[7] و پاسیارلی[8]، 2002). علاوه بر این، چندین روش فراابتکاری مانند شبیه‌سازی تبرید (رایامارکار[9] و هوگون[10]، 2000)، جستجوی ممنوعه (ماسچیارولی[11] و همکاران، 1996 و اسکوستر[12]، 2006)، جستجوی همسایگی متغیر (اسکوستر و فرامینان[13]، 2003)، الگوریتم ژنتیک (بریزولا[14] و همکاران، 2001)، جستجوی محلی (ژو و همکاران، 2009)، ترکیب الگوریتم ژنتیک و گدازش شبیه‌سازی شده (ونگ[15] و ژنگ[16]، 2001)، جستجوی همسایگی (فرامینان و اسکوستر، 2006) و الگوریتم ژنتیک ترکیبی (پن[17] و هوانگ[18]، 2009 و مختاری[19] و همکاران، 2011) برای مسأله موضوع این تحقیق ارائه شده است. همچنین، ردی[20] و رامومورسی[21] (1973) با ارائه یک رویکرد تحلیلی مبتنی بر حد پایین، الگوریتم شاخه و کرانی را برای مسأله زمانبندی تولید در حالت دو مرحله‌ای توسعه دادند.
2- مدلسازی ریاضیمدل ریاضی‌ای که از این مسأله قابل ارائه است، بسته به نوع تعریف متغیرها قابل فرمولبندی است. در این قسمت، ابتدا پارامترها را تعریف نموده و سپس مدل‌بندی آن را ارائه می‌دهیم.
پارامترهای مسأله: تعداد سفارش‌های دریافتی تعداد ماشینها سفارش شماره iام ماشین شماره kام تعداد فرآیندهای (در مسأله مورد بحث در این تحقیق داریم ) j-امین فرآیند سفارش زمان فرآیند مجموعه زوج عملیات سفارش‌های و که روی ماشین‌های یکسان انجام میشوند زمان تجمعی فرآیندهای سفارش شامل فرآیند jام () یک عدد مثبت بزرگ
متغیرهای تصمیم: زمان شروع حداکثر زمان تکمیل سفارش‌های متغیر صفر و یک که روابط پیش‌نیازی عملیات و را نشان می‌دهند. ( پیش‌نیاز خواهد بود، اگر برابر صفر باشد و برعکس)
مدل ریاضی مسأله با توجه به پارامترهای تعریف شده و به منظور کمینه کردن به صورت زیر فرمولبندی می‌شود: به طوری که در آن تابع هدف، کمینه کردن زمان تکمیل کل کارهاست. مجموعه محدودیت‌های (2) تضمین می‌نماید که کلیه کارها بدون هیچ زمان انتظاری از شروع تا تکمیل پیش بروند. محدودیت‌های (3) از ایجاد تداخل[22] بین فرآیندهای جفت کارهایی که باید روی یک ماشین صورت گیرند، جلوگیری می‌نماید. همچنین، مجموعه محدودیت‌های (4) کارها را محدود می‌نمایند به طوری که زمان تکمیل آنها از حداکثر زمان تکمیل سفارش‌های تجاوز ننماید. در ادامه، نشان خواهیم داد که مسأله فوق، با مسأله زمانبندی سفارش‌های با هدف کمینه‌سازی زمان بیکاری ماشینها معادل است.
3- استخراج ویژگی‌های ساختاری مسألهدر این قسمت تعدادی از ویژگی‌های ساختاری مسأله و همچنین، حالات مختلفی از آن را در قالب روابط ریاضی استخراج می‌نماییم. در ابتدا تعدادی از نمادهای مسأله دو ماشینه را تعریف می‌کنیم. مسأله پیشنهادی، کمینه‌سازی زمان تکمیل کل کارها در حالتی است که تولیدکننده در ابتدای افق برنامه‌ریزی، تعدادی سفارش از مشتریان دریافت می‌نماید. هر کدام از سفارش‌ها دارای یک زمان تحویل مطلوب بوده و برای تکمیل شدن به دو عملیات متفاوت نیاز دارند. به دلیل ساختار برخی از سفارش‌ها در صنعت چاپ، انتظار بین دو عمل از هر سفارش مجاز نیست. برای ساده‌سازی، زمان پردازش اولین عمل از هر سفارش را با و دومین عمل را با نمایش می‌دهیم. در ادامه، در راستای در نظر گرفتن محدودیت عدم انتظار سفارش‌ها، مفهومی با عنوان «زوج سفارش» را تعریف می کنیم. و سپس بر اساس برنامه‌ریزی ریاضی زوج سفارش‌های بهینه را تعیین نموده، مقداری اولیه برای کران بالای تابع هدف تعیین می‌کنیم. سپس حالات مختلف توالی زوج سفارش‌ها را به صورت ریاضی استخراج می‌نماییم.
3-1- تعریف زوج سفارشدر این قسمت مفهومی با عنوان زوج سفارش و همچنین، نقش آن در الگوریتم پیشنهادی توصیف می‌شود. تعریف1: مجموعه که از دو سفارش و تشکیل شده‌اند، یک زوج سفارش تعریف میشوند، اگر و تنها اگر: (1) توالی تکنولوژیکی انجام کار برای دو سفارش عکس هم باشند (). (2) بلافاصله پس از و همچنین بلافاصله بعد از آغاز شوند. شکل (1) زیر نمونه‌ای از زوج سفارش تشکیل شده را نمایش می‌دهد. شکل 1. نمایش زوج سفارش چنانچه در شکل مشاهده می‌شود، توالی انجام سفارش به صورت و سفارش به صورت بوده و همچنین بلافاصله پس از و بلافاصله بعد از آغاز میشوند. همان طوری که قابل استنباط است، تشکیل زوج سفارش‌ها منجر می‌شود که محدودیت عدم انتظار تضمین شود. در ادامه، رویکردی را برای تشکیل مناسبترین زوج سفارش‌ها توسعه می‌دهیم. برای اختصار زوج سفارش ام را با نمایش می‌دهیم. ایده به کارگیری زوج سفارش‌ها در تحقیقات مشابهی در ادبیات نیز مطرح شده است (لیا[23]، 2008).
3-2- تعیین زوج سفارش‌های بهینهبهترین ترکیب برای تشکیل زوج سفارش‌ها، ترکیبی است که در آن تابع هدف مسأله که همان زمان تکمیل کارهاست، بهینه شود. قضیه1: اگر زمانبندی زمان تکمیل کل کارها را حداقل نماید، زمان بیکاری ماشین‌آلات نیز توسط حداقل خواهد شد. اثبات:اگر زمان بیکاری متناظر با ماشین را با نمایش دهیم، زمان کل بیکاری ماشینها برابر خواهد بود با: که در آن:
و همچنین زمان پردازش سفارش را روی ماشین نشان می‌دهد. بنابراین رابطه (5) را می‌توان مجدداً به صورت زیر بازنویسی نمود: بر اساس رابطه (7)، از آنجایی که و مقادیر ثابتی هستند، بنابر این اثبات می‌شود که معیار معادل با معیار است. به عنوان نتیجه حاصل از قضیه 1، تعیین ترکیب بهینه زوج سفارش‌ها برای کمینه‌سازی معیار ، مسلماً معیار را نیز بهینه خواهد نمود. در همین راستا، مفهوم «سهم زوج سفارش از زمان بیکاری ماشینها» رادر ادامه تعریف می‌نماییم. همان طوری که از شکل (2) مشخص است، زمان بیکاری ماشینها متناظر با زوج سفارش نمایش داده شده، برابر خواهد بود با مجموع و . شکل 2: سهم زوج سفارش از زمان بیکاری ماشینها در این صورت سهم زوج سفارش از زمان بیکاری ماشینها به صورت زیر محاسبه می‌شود:
زوج سفارش‌های بهینه، ترکیبی از سفارش‌ها خواهند بود که به کمترین مقدار منجر شوند. در راستای تعیین این ترکیب، الگوریتم زیر بر اساس مدل مسأله تخصیص متقارن[24] ارائه می‌شود: گام نخست: مقدار سهم هر زوج سفارش بالقوه از زمان بیکاری ماشینها را محاسبه کنید. گام دوم: مجموعه را مجموعه سفارش هایی که از ماشین شروع میشوند و مجموعه رامجموعه سفارش‌هایی که از ماشین آغاز میشوند،قرار دهید. بدیهی است که. گام سوم: اگر، به تعداد سفارش مجازی باتولید نموده و به مجموعهبا کمترین عضو اضافه نمایید.پساز افزودن سفارش‌های مجاری، تعداد اعضای دو مجموعه و برابر خواهد شد. گام چهارم: برای تعیین بهترین زوج سفارش هایی که دارای کمترین سهم از زمان بیکاری ماشینها هستند، مسأله تعیین زوج سفارشات را به صورت یک مسأله تخصیص فرمولبندی می‌کنیم.
تابع هدف (9) مقدار کل سهم زوج سفارش‌های تشکیل شده را از زمان بیکاری ماشینها تعیین می‌کند و در آن متغیر تصمیم صفر و یک است و تعیین می‌نماید که آیا زوج سفارش تشکیل شود یا خیر. محدودیت سری (10) الزام می‌نماید که هر سفارش عضو مجموعه تنها با یک سفارش از مجموعه زوج شود. همچنین، محدودیت سری (11) تضمین می‌نماید که هر سفارش عضو نیز تنها با یک سفارش از مجموعه زوج شود. 3-3 کران بالا برای زمان بیکاری ماشینهاهمان طوری که در بخش قبل مطرح شد، مدل (9-11) مربوط به یک مسأله تخصیص متقارن است که در آن باید در راستای تشکیل بهینه زوج سفارش‌ها، هر عضو از مجموعه تنها به یک عضو از مجموعه تخصیص یابد و بالعکس. زمانی که دو سفارش یک زوج سفارش را تشکیل می‌دهند، سهم زوج سفارش تشکیل شده از زمان بیکاری ماشینها را می‌توان زمان بیکاری بالقوه ماشینها لحاظ نمود. لذا مقدار بهینه تابع هدف مدل تخصیص (9-11)، کران بالایی برای تابع هدف مسأله، زمان بیکاری ماشینها، محسوب می‌شود. (12)
مسلماً زمان بیکاری ماشینها از UB محاسبه شده بیشتر نخواهد شد، ولیکن این حد، حاصل از جمع کران بالای متناظر با زوج سفارش‌هاست، زمانی که هر کدام از زوج سفارش‌ها به طور مستقل و به صورت زمانبندی جزئی[25] لحاظ شده‌اند. بدیهی است قرارگرفتن این زوج سفارش‌ها به ترتیبی در کنار هم، به پوشش زمان بیکاری یک زوج سفارش توسط زوج سفارش دیگر منجر شود. بنابراین، می‌توان نتیجه گرفت که UB محاسبه شده نیز در شرایطی قابل بهبود است. شکل (3) نمونه‌ای از بهبود حاصل از قرار گرفتن دو زوج سفارش و در کنار هم را نشان می‌دهد.
شکل 3. زمانبندی ناشی از توالی دو زوج سفارش و در حالت استقلال زوج سفارش‌ها، مقدار بیکاری متناظر با ماشینها که برابر با مجموع زمان بیکاری زوج سفارش‌های و است، به صورت زیر محاسبه می‌شود.
اما همان طوری که بیان شد و در شکل نیز مشخص است، با توالی دو زوج سفارش و ، زمان بیکاری ماشینها به عدد به اضافه نوار هاشور زده شده، کاهش پیدا کرد. به طوری که:
که در آن و به ترتیب زمان بیکاری متناظر با ماشین و است. بر این اساس، در ادامه به بررسی حالات مختلفی که در توالی زوج سفارش‌ها رخ می‌دهد و همچنین، اثبات مقدار کاهش در کران بالا در هر یک از این حالات می‌پردازیم. پس از تعیین زوج سفارش‌های بهینه در بخش قبل (مدل تخصیص)، در این قسمت به بررسی حالات مختلفی که در تعیین ترتیب قرار گرفتن زوج سفارش‌ها در کنار هم رخ می‌دهد، اثبات مقدار کاهش در زمان بیکاری ماشینها در هر حالت و میزان بهبود در UB می‌پردازیم. در این راستا مجموعه زوج سفارش‌های برنامه‌ریزی شده را در لحظه‌ای که قرار است زوج سفارش برنامه‌ریزی شود، می‌نامیم. فرض می‌کنیم نخستین زوج سفارش برنامه‌ریزی شده در مجموعه ، زوج سفارش و آخرین زوج سفارش باشند. شکل (4) مجموعه سفارش های برنامه‌ریزی شده را نمایش می‌دهد.
شکل 4. مجموعه زوج سفارش‌های برنامه‌ریزی شده در لحظه ورود زوج سفارش کاندید دو حالت برای زوج سفارش کاندید ورود امکان‌پذیر است: (1) زوج سفارش به ابتدای مجموعه زوج سفارش‌های برنامه‌ریزی شده اضافه شود. (2) زوج سفارش به انتهای مجموعه زوج سفارش‌های برنامه‌ریزی شده اضافه شود. ابتدا به بررسی حالت اول می‌پردازیم. در این حالت بر اساس ویژگی‌های زوج سفارش کاندید ورود و زوج سفارش ، شش وضعیت مختلف امکان‌پذیر است که هر یک از این وضعیت‌ها در ادامه بررسی میشوند.
شکل (5)، نمایی از این وضعیت را نمایش می‌دهد.
شکل 5: ورود زوج سفارش کاندید به ابتدای مجموعه در وضعیت (1) از حالت اول که در آن، داریم: همان طوری که در شکل مشخص است، از آنجایی که در این وضعیت بیکاری ماشینها کاهشی نیافته، لذا میزان بهبود در UB برابر با صفر است.
شکل (6)، نمایی از این وضعیت را نمایش می‌دهد.
شکل 6. ورود زوج سفارش کاندید به ابتدای مجموعه در وضعیت (2) از حالت اول
که در آن داریم:
همان طوری که در شکل مشخص است، در این وضعیت نیز بیکاری ماشینها کاهشی نیافته، لذا میزان بهبود در UB برابر با صفر است.
شکل 7.ورود زوج سفارش کاندید بهابتدای مجموعه در وضعیت (3) از حالت اول که در آن داریم:
میزان بهبود در کران بالای بیکاری ماشینها ناشی از ورود زوج سفارش به صورت زیر خواهد بود:
شکل (8)، نمایی از این وضعیت را نمایش می‌دهد.
شکل 8. ورود زوج سفارش کاندید به ابتدای مجموعه در وضعیت (4) از حالت اول ج که در آن داریم: میزان بهبود در کران بالای بیکاری ماشینها ناشی از ورود زوج سفارش به صورت زیر خواهد بود:
شکل (9)، نمایی از این وضعیت را نمایش می‌دهد.
شکل 9. ورود زوج سفارش کاندید به ابتدای مجموعه در وضعیت (5) از حالت اول که در آن داریم:
میزان بهبود در کران بالای بیکاری ماشینها ناشی از ورود زوج سفارش به صورت زیر خواهد بود:
شکل (10)، نمایی از این وضعیت را نمایش می‌دهد.
شکل 10. ورود زوج سفارش کاندید به ابتدای مجموعه در وضعیت (6) از حالت اول
که در آن داریم:
میزان بهبود در کران بالای بیکاری ماشینها ناشی از ورود زوج سفارش به صورت زیر خواهد بود:
به طریقی مشابه، می‌توان به بررسی وضعیت‌های مختلفی که در حالت دوم رخ می‌دهد، پرداخت. در این حالت نیز بر اساس ویژگی‌های زوج سفارش کاندید ورود و زوج سفارش انتهایی مجموعه ؛ یعنی ، شش وضعیت مختلف امکان‌پذیر است که به طریق مشابه قابل اثبات است.
4- الگوریتم ابتکاری برای بهبود کران بالابا توجه به نتایج حاصل از تعیین توالی زوج سفارش‌ها در بخش قبل، در این قسمت الگوریتمی ابتکاری برای بهبود کران بالای استخراج شده و براساس ویژگی‌های اثبات شده در بخش قبل ارائه می‌شود. در فاز آغازین این الگوریتم، مجموعه زوج سفارش‌های برنامه‌ریزی شده تنها شامل یک زوج سفارش است. در راستای رسیدن به کمترین مقدار از حداکثر زمان تکمیل کارها، زوج سفارشی برای ورود اتنخاب می‌شود که به بیشترین مقدار بهبود در کران بالای زمان بیکاری ماشینها منجر شود. در هر تکرار الگوریتم، بر اساس (12) وضعیت اثبات شده در بخش قبل، زوج سفارشی که دارای چنین ویژگی‌ای بوده، انتخاب شده و برنامه‌ریزی می‌شود. از آنجایی که خرورجی الگوریتم پیشنهادی به نخستین زوج سفارش انتخاب شده حساس است، لذا سه سیاست مختلف در فاز شروع برای انتخاب اولین زوج سفارش پیشنهاد می‌شود. این رویه تا زمانی که تمامی زوج سفارش‌ها برنامه‌ریزی شوند، ادامه می‌یابد. در ادامه، مراحل الگوریتم ابتکاری پیشنهادی ارائه می‌شود.
(1) زوج سفارش‌های تشکیل شده بر اساس مدل مسأله تخصیص متقارن (9-11) را به عنوان ورودی دریافت کنید. (2) قرار دهید ، و ؛ (3) زوج سفارش اول را انتخاب و مجموعه را تشکیل دهید. (4) مجموعه زوج سفارش های برنامه‌ریزی نشده را بروز کنید و قرار دهید . (5) تا زمانی که مراحل زیر را تکرار کنید: (5-1) قرار دهید . (5-2) تا زمانی که مراحل زیر را تکرار کنید: (5-2-1) مقدار بهبود در UB را بر اساس (6) وضعیت اثبات شده در بخش (3-4) و برای برنامه‌ریزی عضو -ام از در ابتدای محاسبه و آن را نامگذاری کنید. (5-2-2) مقدار بهبود در UB را بر اساس (6) وضعیت اثبات شده در بخش(3-4) و برای برنامه‌ریزی عضو -ام از در انتهای محاسبه و آن را نامگذاری کنید. (5-3) قراردهید (5-4) قراردهید (5-5) حداکثر بهبود در کران بالا را از طریق محاسبه کنید. (5-6) زوج سفارش متناظر با حداکثر بهبود در کران بالا و همچنین موقعیت بهینه برنامه‌ریزی آن را (ابتدای یا انتهای آن) تعیین نمایید. (5-7) زوج سفارش را برنامه‌ریزی نموده، مجموعه‌های و را از بروز رسانی دو مجموعه و تشکیل دهید. (5-8) قرار دهید . (6) مقدار کران بالای بهبود یافته متناظر با مجموعه را محاسبه نموده و بنامید.
5- ارزیابی عملکردیکی از صنایعی که مقوله برنامه‌ریزی و زمانبندی تولید و تحویل بموقع سفارش‌ها به مشتریان در آن اهمیت خاصی پیدا کرده است، صنعت چاپ و نشر است. به طور کلی، چاپ عبارت است از انتقال یک متن یا تصویر اولیه به روی کاغذ و یا هر جسم فیزیکی دیگر برای تولید انبوه و یا سفارشی. یکی از صنایعی که امروزه درصد بالایی از حجم تولیدات را به خود اختصاص داده است، صنعت چاپ است. تنوع تولید محصولات چاپی به اندازهای است که این صنعت به عنوان یک صنعت جانبی، در کنار اکثر صنایع دیگر مشاهده می‌شود. همانند بسیاری از صنایع دیگر، صنعت چاپ نیز تحت تأثیر تغییرات شدید تکنولوژیک قرار دارد. رایانه و تکنولوژی‌های جدید، فرآیندهایی را که محصول چاپی از طریق آنها تولید می‌شود، دگرگون کرده‌اند. بسیاری از فرآیندهای چاپی که قبلاً به صورت دستی انجام می‌شدند، امروزه به سمت غیردستی شدن پیش رفته‌اند و تأثیر تکنولوژی بر تمامی مراحل چاپ مشاهده می‌شود. در این میان، با افزایش پیچیدگی‌های صنعت چاپ و افزایش رقابت در بازار، زمانبندی و برنامه‌ریزی در زنجیره تأمین صنعت چاپ اهمیت خاصی پیدا کرده است. بطور کلی، فرایند تولید چاپ، جریانی از مواد اولیه و اطلاعات است که شامل سه زیر فرآیند اصلی؛ یعنی پیش از چاپ[26]، چاپ[27] و پس از چاپ[28] است. عامل اتصال پیش از چاپ و چاپ پلیت بوده و چاپ و پس از چاپ نیز با فرم‌های چاپی به یکدیگر مربوط میشوند. پیش از چاپ، به آن دسته از فرآیندهایی از تولید محصول چاپی اطلاق می‌گردد که برای تبدیل یک تصویر و یا طرح اعم از فایل الکترونیکی و یا غیر الکترونیکی به یک پلیت و یا فیلم فیزیکی، انجام می‌گیرند. منظور از پلیت فیزیکی یک نمونه ساخته شده از تصویر بر روی یک جسم صلب فیزیکی به عنوان مهر است که بعداً در فرآیند چاپ به عنوان قالب برای تکثیر محصول چاپی استفاده می‌شود. مراحلی را که در یک چاپخانه به صورت پیش از چاپ انجام می‌گیرد، به صورت زیر می‌توان دستهبندی نمود.
همچنین، چاپ عبارت است از باز آفرینی عینی مجموعه ای از اطلاعات (شامل متن، تصویر و یا گرافیک) بر روی یک محمل تصویر، مانند کاغذ و در نسخه‌های متعدد. همان طوری که قبلاً مطرح شد، عنوان چاپ به فرآیند پس از تهیه پلیت و یا فیلم اطلاق می‌شود. در مرحله چاپ، پلیت یا فیلم تهیه شده باید روی دستگاه چاپ نصب شده و به تعداد مورد نیاز از آن روی کاغذ چاپ می‌شود. این فرآیند بسته به نوع محصول چاپی، با استفاده از یک و یا چندین دستگاه چاپ انجام می‌گیرد که هر کدام می‌توانند از تکنولوژی‌های تولید گوناگونی استفاده نمایند که بنا بر هدف این تحقیق فرصت بحث آنها نیست. خروجی این مرحله، فرم‌های چاپی هستند که نیاز به عملیات خاصی دارند که در بخش پس از چاپ توضیح داده میشوند. پس از چاپ فرآیند آخر در صنعت چاپ محسوب می‌شود که ورودی آن، فرم‌های چاپ شده به صورت ورقی یا رول، متناسب با کاربرد نهایی‌شان هستند. عملیات پس از چاپ به دو گروه عمده تکمیلی[29] و تبدیلی[30] تقسیم میشوند که هر کدام از محصولات چاپی بنابر نوعشان، به تعدادی از این مراحل نیاز دارند. در این قسمت، در راستای بررسی کاربرد و اعتبارسنجی رویکرد پیشنهادی برای زمانبندی سفارش‌ها، تعدادی از سفارش‌های رسیده به یک واحد تجاری که به تولید محصولات چاپی اشتغال دارد بررسی شده اند. همان طوری که قبلاً مطرح شد، مراحل تولید محصولات چاپی به سه دسته پیش از چاپ، چاپ و پس از چاپ دستهبندی می‌شود. معمولاً فرآیندهای تکمیلی و تبدیلی که شامل عملیات پوشش‌کاری، طلاکاری، برجسته‌سازی، صحافی، برش، پانچ کردن، بریدن، سوراخ گردن، تا زدن و غیره هستند، در آماده‌سازی پیش از چاپ و عملیات نهایی پس از چاپ به کار می‌روند. لذا به طور کلی می‌توان فرض نمود که فرآیند زمانبندی سفارش ها در چاپخانه‌ها به دو مرحله تکمیلی/آماده‌سازی و چاپ نیاز دارد. جدول (1) فهرستی از سفارش‌های رسیده به یک واحد چاپی و همچنین زمان‌های برآورد شده برای پردازش آنها را نمایش می‌دهد. بر اساس توالی پردازش عملیاتِ سفارش‌ها، دو مجموعه و به صورت زیر محاسبه میشوند.
از آنجایی که تعداد اعضای دو مجموعه برابر نیستند، لذا به تعداد اختلاف بین تعداد اعضای آنها، زوج سفارش مجازی با تولید می‌کنیم. تعداد زوج سفارش‌های مجازی برابر با خواهد بود. مقدار سهم زوج سفارش‌ها بالقوه از زمان بیکاری ماشینها با استفاده از محاسبه شده و نتایج آن در جدول (2) ارائه شده است. بر اساس اطلاعات جدول (2)، مدل مسأله تخصیص متقارن (9-11) برای تعیین زوج سفارش‌های بهینه را تشکیل داده و با حل بهینه مدل با استفاده از بسته بهینه‌سازی نرم‌افزار MATLAB، زوج‌سفارش‌های: , و به عنوان زوج سفارش‌های بهینه تشکیل شدند.
این عدد به عنوان مقدار اولیه‌ای برای کران بالای مسأله بوده که در فاز تعیین توالی زوج سفارش‌ها با استفاده از حل ابتکاری پیشنهادی بخش قبلی قابل بهبود است. ترتیب نهایی به دست آمده از زوج سفارش‌ها به صورت: } { است که مقدار بیکاری ماشینها در آن به عدد 4 کاهش یافته است. بر اساس قضیه (1) متناظر با این مقدار از زمان بیکاری ماشینها، حداکثر زمان تکمیل کارها نیز به حداقل خود کاهش یافته که برابر با 125 ساعت است. شکل (11) توالی نهایی به دست آمده برای زوج سفارش‌ها را نمایش می‌دهد.
جدول 1: مشخصات سفارش‌های دریافتی توسط واحد تولید محصولات چاپی
جدول 2: سهم زوج سفارش‌های بالقوه در زمان بیکاری ماشینها
6- نتیجه‌گیری در این تحقیق مدلی برای زمانبندی بهینه سفارش‌های تولید و با هدف کمینه‌سازی حداکثر زمان تکمیل سفارش‌ها، ارائه شد. در راستای حل بهینه مدل ارائه شده، رویکردی تحلیلی مبتنی بر ویژگی‌های ریاضی و ساختاری مسأله پیشنهاد شد. در این رویکرد، مفهوم زوج سفارش‌های بهینه، برای کمینه‌سازی زمان بیکاری کل ماشین‌آلات و در نتیجه کمینه‌سازی حداکثر زمان تکمیل سفارش‌های، توسعه داده شد. همچنین مدلی ریاضی منطبق بر مسأله تخصیص متقارن، برای تعیین زوج سفارش‌های بهینه استخراج و بر اساس ویژگی‌های استخراج شده از ساختار زوج سفارش‌های، یک کران بالا برای تابع هدف و الگوریتمی ابتکاری برای بهبود این کران ارائه گردید. بررسی و تحلیل ریاضی وضعیت‌های مختلف که در تعیین توالیِ زوج سفارش‌های ممکن است، و اثبات میزان بهبود در کران بالا در هر حالت منجر شد که الگوریتم ابتکاری پیشنهادی به بهترین ترکیب از توالی زوج سفارش‌ها منجر شود. همان طوری که اشاره شد، مسأله ارائه شده به کلاس مسائل NP-hard تعلق داشته که طراحی رویکرد حل (بهینه) که در زمان چندجمله‌ای قادر به حل آن باشد، بعید است. لذا رویکردهای حلی که تا کنون در ادبیات برای مسائلی از این خانواده ارائه شده مبتنی بر روش‌های هوشمند و محاسباتی همانند رویکردهای فرا ابتکاری است که اساساً به ویژگی‌ها و ساختار ریاضی خاص مسأله ورود پیدا نمی‌کنند. لذا ویژگی اصلی رویکرد حل پیشنهادی ما در این تحقیق، ارائه یک الگوریتم ابتکاری بر اساس ویژگی‌های ریاضی خاص مسأله است که در 12 حالت برای بهبود کران بالا (جواب موجه اولیه) توسعه داده شد. همچنین، کاربرد مدل و رویکرد حل پیشنهادی در صنعت چاپ محصولات تجاری مورد تحقیق قرار گرفت. امروزه صنعت چاپ به عنوان یکی از صنایعی که برنامه‌ریزی و زمانبندی تولید در آن اهمیت خاصی پیدا کرده، مطرح است. در این مطالعه زمانبندی تعدادی سفارش چاپی که در یک دوره برنامه‌ریزی یک ماهه توسط یکی از چاپخانه‌های تجاری دریافت شده بود، مورد توجه قرار گرفت. فرآیند چاپی شامل یک مرحله، آماده‌سازی، یک مرحله چاپ طرح بر روی بستر چاپ و یک مرحله عملیات تکمیلی و تبدیلی بوده است که برای هر سفارش دو مرحله از این مراحل بسته به ماهیت آن مورد تیاز است. نتایج حاصل از این مطالعه، کاربرد رویکرد پیشنهادی را جهت زمانبندی محصولات چاپی نشان می‌دهد.
شکل 11. زمانبندی نهایی زوج سفارش‌ها [1] Baker [2] Completion Time [3] Delivery Time [4] No-wait Jobs Shop [5] Hall [6] Sriskandarajah [7] Mascis [8] Pacciarelli [9] Raaymakers [10] Hoogeven [11] Macchiaroli [12] Schuster [13] Framinan [14] Brizuela [15] Wang [16] Zhang [17] Pan [18] Huang [19] Mokhtari [20] Reddi [21] Ramamoorthy [22] Overlap [23] Liaw [24] Symmetric Assignment Problem [25] Partial Schedule [26] Prepress [27] Printing/ Press [28] Postpress/ Finishing [29] Finishing [30] Converting | ||
| مراجع | ||
|
Baker, K.R. 1974. Introduction to sequencing and scheduling. NY: Wiley. Brizuela, C. A., Zhao, Y., and Sannomiya, N., “No-wait and blocking job-shops: Challenging problems for GA’s”. In IEEE international conference on systems, man, and cybernetics, Tucson, Arizona, USA, 2001. Framinan, J.M., & Schuster, C. (2006). "An enhanced timetabling procedure for the no-wait job shop problem:", A complete local search approach. Computers & Operations Research, 331, 1200–1213. Hall, N. G., & Sriskandarajah, C. (1996)." A survey of machine scheduling problems with blocking and no-wait in process", Operations Research, 44, 510–525. Liaw, C.-F. (2008). "An efficient simple metaheuristic for minimizing the makespan in two-machine no-wait job shops", Computers & Operations Research, 35, 3276–3283. Macchiaroli, R., Molè, S., Riemma, S., & Trifiletti, L. (1996)." Design and implementation of a tabu search algorithm to solve the no-wait job-shop scheduling problem", In Proceeding of the CESA’96 Lille (467–472). Mascis, A., & Pacciarelli, D. (2002). "Job-shop scheduling with blocking and no-wait constraints", European Journal of Operational Research, 143, 498–517. Mokhtari, H., Nakhai Kamal Abadi, I., & Zegordi, S.H. (2011)." Production capacity planning and scheduling in a no-wait environment with controllable processing times:", An integrated modeling approach, Expert Systems with Applications, 38, 12630-12642. Pan, J. C.-H., & Huang H.-C. (2009). "A hybrid genetic algorithm for no-wait job shop scheduling problems.", Expert Systems with Applications, 36, 5800-5806. Raaymakers, W. H. M., & Hoogeven, J. A. (2000). "Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing", European Journal of Operational Research, 126, 131–151. Reddi, S., & Ramamoorthy, C. (1973). "A scheduling problem.", Operational Research Quarterly, 24, 441–446. Schuster, C. (2006). "No-wait job shop scheduling: Tabu search and complexity of subproblems", Mathematical Methods of Operations Research, 63, 473–491. Schuster, C., & Framinan, J.M. (2003). "Approximative procedures for no-wait job shop scheduling",. Operations Research Letters, 31, 308–18. Wang, L., & Zheng, D. (2001). "An effective hybrid optimization strategy for job-shop scheduling problems.", Computers & Operations Research, 28, 585–96. Yang,Y .,Wu,W.W., Liang,D.P. and Yu,B.,(2010), ”Strategic planning for management of technology of China’s high technology enterprises”,Journal of Technology Management in China, 5, 6-25. Zhu, J., Li, X., & Wang, Q. (2009). "Complete local search with limited memory algorithm for no-wait job shops to minimize makespan.", European Journal of Operational Research, 198, 378-386. | ||
|
آمار تعداد مشاهده مقاله: 1,311 تعداد دریافت فایل اصل مقاله: 1,029 |
||