بخشی از مقاله
چکیده
پایانههای انتقال، انبارهایی برای تخلیه و بارگیری سریع کالاها1 میباشند که دارای یک یا چند ایستگاه تخلیه و بارگیری هستند. در این تحقیق یک پایانهی انتقال با چند ایستگاه تخلیه و بارگیری یکسان و با در نظر گرفتن محدودیت موجودی مطالعه شده است. هر یک از عملیاتهای تخلیه یا بارگیری به عنوان یک کار و هر یک از ایستگاهها به عنوان یک ماشین در نظر گرفته میشوند. به بیان دیگر، مسأله این تحقیق زمانبندی ماشینهای موازی با وجود محدودیت موجودی و زمان ورود برای کارها و با هدف کمینه کردن زمان اتمام پردازش کل کارها است. برای این مسأله یک مدل برنامهریزی عددصحیح خطی ارائه میشود اما از آنجا که این مسئله حتی با تعداد یک ماشین و بدون در نظر گرفتن زمان آمادگی برای کارها، یک مسئلهی بسیار پیچیده است، حل بهینهی مدل مربوطه زمانبر میباشد. بنابراین، دو الگوریتم حل ابتکاری با اسامی موازی و سریال طراحی شده است. سپس با استفاده از نمونه مسائل تصادفی تولید شده، کارایی این دو الگوریتم مورد تحلیل قرار گرفته است. نتایج محاسباتی نشان میدهد که الگوریتم موازی کارایی بهتری نسبت به الگوریتم سریال دارد.
کلمات کلیدی:پایانههای انتقال- زمانبندی ماشینهای موازی- محدودیت موجودی
-1 مقدمه
در مدیریت زنجیره تأمین به منظور صرفهجویی در هزینههای توزیع و حمل و نقل کالا، از پایانهها یا انبارهای موقتی جهت تخلیه و بارگیری سریع کالا استفاده میشود که در ادبیات زنجیره تأمین با عنوان پایانههای انتقال شناخته میشوند. در این انبارها کالاها به مدت زیادی انبارش نمیشوند و معمولاً مدت نگهداری آنها کمتر از 24 ساعت است. شکل - 1 - ، عملیات صورت گرفته در یک پایانهی انتقال را نشان میدهد.مسئلهای که در این تحقیق به آن پرداخته میشود، در واقع توسعهای است بر مسئلهای که در سال 2010 توسط Briskorn و همکارانش مطرح شد.[1] آنها مسئلهی زمانبندی تک ماشین در صورت وجود محدودیتهای موجودی را مطالعه کردند به طوریکه در مسئلهی مطرح شده، کارها باعث افزایش یا کاهش سطح موجودی مرکزی میشود و میزان این تغییر، به نوع کار بستگی دارد.
سطح موجودی باید در تمام طول برنامهریزی نامنفی باشد. بنابراین کارهایی که باعث کاهش موجودی میشوند تا زمانیکه به اندازهی مورد نیاز موجودی در دسترس نباشد، نباید پردازش شوند. آنها همچنین ظرفیت انبار پایانه را نامحدود در نظر گرفتند و فرض کردند که تمام کارها در ابتدای افق زمانی در دسترس هستند. سپس پیچیدگی مسئله را با توجه به توابع هدف مختلف بررسی کردند. آنها ثابت کردند که این مسئله، بسیار پیچیده - - NP-hard است.در [2] رویکردهای دقیق برای حل مسئلهی زمانبندی تک ماشین با هدف کمینه کردن مجموع زمان اتمام وزن دهی شدهی کارها و در صورت وجود محدودیتهای موجودی، ارائه شد. در [3]، مسئلهی مشابهی مطرح شد و هدف در آن، یافتن زمانبندی مناسب برای کارها به گونهای بود که بیشترین تأخیر در بین کارها کمینه گردد. در این مقاله چهار الگوریتم شاخه و کران، توسعه داده شد.
در [ 4]، یک پایانه تخلیه و بارگیری سریع با چند ایستگاه دریافت و ارسال مطالعه شد. آنها یک راه حل بهینه بر اساس برنامهریزی پویا و به منظور یافتن بهترین زمانبندی برای عملیات حمل و نقل پیشنهاد دادند.هدف در این تحقیق، یافتن زمانبندی مناسب بصورتی است که زمان اتمام کل کارها کمینه شود. فرض میکنیم که پایانه دارای چندین ایستگاه تخلیه و بارگیری است به طوریکه در هر یک از ایستگاهها امکان تخلیه و یا بارگیری با ظرفیت و سرعت یکسان وجود دارد.همچنین یک مکان با ظرفیت مشخص و محدود جهت انبارش کالا، در این پایانه وجود دارد که فرض میشود در ابتدای افق زمانی دارای موجودی اولیهی مشخصی است.
به دلیل اینکه در شرایط واقعی ممکن است تمام کارها در ابتدای افق زمانی در دسترس نباشند، برای هر کار زمان آغاز مخصوص به آن کار در نظر گرفته شده است. تمامی این فرضیات بصورت یکجا در هیچ مقالهای در نظر گرفته نشده است. این مسئلهی جدید بصورت یک مسئلهی برنامهریزی عدد صحیح فرموله و توسط نرمافزار ILOG CPLEX-12.3 حل شده است. همچنین به دلیل پیچیدگی بالای مسئله، دو الگوریتم ابتکاری طراحی و پیاده سازی شده است.در ادامه، تعریف دقیق مسئله و مدلسازی آن، الگوریتمهای پیشنهادی، نتایج محاسباتی و مقایسهی نتایج حاصل از الگوریتمهای پیشنهادی با مقدار بهینه مورد بررسی قرار گرفته است.
-2 مسئله
-1-2 تعریف مسئله
در این تحقیق یک پایانه تخلیه و بارگیری در نظر گرفته شده است که دارای یک مجموعه با اندازه | | از ایستگاههای تخلیه و بارگیری است. همچنین فرض شده است که در این پایانه فقط یک نوع کالا تخلیه و بارگیری میشود. مجموعه عملیاتهای تخلیه و بارگیری را با نشان میدهیم که مجموعههای + و − به ترتیب بیانگر عملیات-های تخلیه و بارگیری میباشند. هر عملیات تخلیه و یا بارگیری که توسط یک وسیله حمل و نقل در لحظه وارد این پایانه میشود و جهت تخلیه و یا بارگیری نیازمند زمان مشخصی برابر با است. همچنین یک مکان مشترک برای تخلیه و یا بارگیری این نوع کالا با ظرفیت در این پایانه وجود دارد که فرض میشود در ابتدای افق زمانی دارای موجودی اولیهای برابر با است. اثر هر عملیات تخلیه یا بارگیری روی موجودی کالا برابر با است که این مقدار برای عملیاتهای تخلیه کالا مقداری مثبت و برای عملیات-های بارگیری آن مقداری منفی است.
اثر هر عملیات بارگیری روی موجودی کل پایانه در لحظه شروع عملیات است ولی در عملیات تخلیه این اثر موجودی در لحظه اتمام بارگیری بصورت یکجا اعمال میگردد.واضح است که در این مسأله در هر لحظه که| | - {1, … , | |} یک حد بالا برای اتمام کلیهی عملیاتهای مجموعه است - نباید سطح موجوی کالا در پایانه منفی شود. بعلاوه، در این تحقیق فرض شده است که کلیهی پارامترهای مذکور مقادیر صحیح میباشند.این مسأله مشابه مسأله زمانبندی ماشینهای موازی در نظریه زمانبندی است که در آن هر یک از ایستگاههای تخلیه و بارگیری یک ماشین و هر عملیات تخلیه یا بارگیری یک کار فرض شده و فقط محدودیت موجودی کالا به آن اضافه شده است. هدف مسأله کمینهسازی زمان انجام کل کارها - - بوده که میتوان آن را بصورت 1| , | نشان داد. برای سهولت در ادامه، به منظور تجزیه و تحلیل مسأله از اصطلاحات نظریه زمانبندی ماشین آلات استفاده شده است.
-2-2 مدلسازی مسئله
به منظور مدلسازی مسئله، پارامترها و متغیرهای مورد استفاده به ترتیب به شرح جدول - 1 - و جدول - 2 - تعریف شده است.
