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