بخشی از مقاله
چکیده
در این مقاله مسأله زمانبندی محفظههای موازی غیریکسان در حملونقل دریایی در نظر گرفته شده است. به منظور کاهش زمان سفر و افزایش سهم حملونقل دریایی در انتقال محمولهها در بین سایر روشهای حملونقلی، استفاده از مدلهای ریاضی و بهینهسازی در اینگونه مسائل ضروری است. در این پژوهش دو مدل برنامهریزی خطی عدد صحیح با هدف کاهش کل زمان انتظار کشتیها ارائه میشود. به منظور ارزیابی عملکرد مدلهای ارائه شده، یک سری نمونه مسأله به صورت تصادفی ساخته شده است و توسط نرمافزار IBM ILOG CPLEX 12.6 حل شدهاند. در پایان عملکرد دو مدل به وسیله نتایج عددی مقایسه شدهاند.
1 مقدمه
حمل و نقل کالا توسط کشتی بر روی دریا و نیز در آبراهها، دربرخی موارد میتواند جایگزین مناسبی برای حمل و نقل جادهای باشد و علت آن، قابلیت اطمینان، کارایی - کشتی 3000تُنی میتواند به اندازهی 100 واگن قطار یا 150 کامیون بار حمل کند - ، هزینههای عملیاتینسبتاً کم و دوستدار طبیعت بودن این روش است. از این رو، اهمیت نسبی این حالت حمل و نقل در حال افزایش است. درگاهها1 که سطح آب در آبراهها و بنادر را ساماندهی میکنند، گاهاً گلوگاههایی را برای حملونقل بر روی آب پدید میآورند.
در بسیاری از آبراهههای درونمرزی نظیر کشورهای اروپایی، به درگاهها نیاز است تا اطمینان حاصل شود امکان جبران اختلاف سطح مناسب آب برای هدایت کشتیها وجود دارد. بطور معمول و به ویژه زمانیکه ازدحام ترافیکی آبراهه زیاد باشد، درگاهها به عنوان گلوگاه عمل نموده و یک زمان انتظار برای کشتیهای عبوری از این کانالها و آبراههها فراهم میآورند . امروزه مهمترین دغدغه این حوزه، کاهش زمان انتظار کشتیها میباشد که محقق کردن این مهم، منجر به بهبود سرعت و عملکرد این مدل حملونقل و درنتیجه افزایش سهم آن در بین سایرمدلهای حمل-ونقلی در انتقال محمولهها میشود.
در پژوهشهای گذشته برای زمانبندی کشتیها و کاهش کل زمان انتظار آنها، حالت های مختلفی مورد بررسی قرار گرفته است که از جمله آنها میتوان به درگاههایی با یک محفظه2، بررسی درگاههای سری[ 8]، یک درگاه با چند محفظه ثابت موازی و متفاوت به صورت تک جهته و دو جهته و یک درگاه با چند محفظه ثابت موازی و یکسان به صورت تک جهته و دو جهته اشاره نمود.[9]
مسألهای مورد بررسی در این پژوهش، مسأله زمانبندی کشتیها با درنظرگرفتن یک درگاه واحد است که از تعداد چند محفظه غیریکسان موازی تشکیل شده است و محفظهها مستقل از یکدیگر عمل میکنند.
یک حرکت محفظه، امکان ورود کشتی را فراهم نموده و سپس سطح آب در درگاه را از سطح آب پاییندست به سطح آب بالادست یا بالعکس تغییر میدهد و سپس به کشتی اجازهی خروج از درگاه را میدهد تا به مسیر خود ادامه دهد. هدف مسأله تعریف شده، تخصیص بهینه کشتیها به محفظهها و زمانبندی جابهجایی هرمحفظه میباشد به نحوی که کل زمان انتظار کشتیها به حداقل برسد. در ادامه مقاله، در بخش اول به بررسی سوابق پژوهشی موضوع مورد بحث میپردازیم، سپس شکاف تحقیقاتی بین پژوهشهای گذشته و تحقیق حاضر، بیان خواهد شد. در بخش دوم جزئیات مدل ریاضی و شرح آن ارائه میشود، در بخش سوم به بررسی نتایج حاصل از پیاده-سازی مدل بر روی نمونه مسائل ساخته شده، میپردازیم و در بخش پایانی نیز به جمعبندی و نتیجهگیری خواهیم پرداخت.
-2 پیشینه تحقیق
زمانبندی درگاه در متون و مقالات دانشگاهی چندان مورد بررسی قرار نگرفته است، هرچندکه به تازگی توجهاتی را به خود معطوف داشته است. در این بخش توضیح مختصری درباره پژوهشهایی که در گذشته در این زمینه صورت گرفته، ارائه میگردد. سابقه پژوهش در این زمینه به دو بخش تقسیم میشود. بخش اول مربوط به مسأله تخصیص کشتی ها به یک محفظه و زمانبندی جابهجایی از آن محفظه میباشد. در این بخش یک محفظه در نظر گرفته شده است اما در بخش دوم مسأله با بیش از یک محفظه مورد بررسی قرارگرفته است و مسأله تخصیص بهینه کشتیها به محفظهها و زمانبندی جابهجایی هرمحفظه در نظر گرفته شده است. درابتدا به مرور مقالاتی که مرتبط با بخش اول میباشد می پردازیم.
LEE و همکارانش [1] در سال 1992 مسأله زمانبندی روی ماشین های پردازش گروهی را مورد مطالعه قرار دادند. یک ماشین پردازش گروهی میتواند به طور همزمان کار را پردازش کند. زمان پردازش یک دسته با بزرگترین زمان پردازش کارهای متعلق به آن دسته برابر است. دراین مقاله یک الگوریتم پایهای برنامهریزی پویا برای حداقل کردن تعداد کارهای دارای تاخیر روی یک ماشین پردازش گروهی ارائه شده است. همچنین نویسندگان یک الگوریتم ابتکاری برای مسأله زمانبندی کارها روی ماشینهای پردازش گروهی مشابه موازی ارائه دادند.
Brucker و همکارانش [2] درسال 1998 به بررسی مسأله زمانبندی کار روی یک ماشین گروهی در دو حالت بدون محدودیت ظرفیت یعنی ≥ و با در نظرگرفتن محدودیت ظرفیت که در آن < میباشد، پرداختند. نویسندگان مدل بدون محدودیت ظرفیت را با توابع هدف مختلف با استفاده از الگوریتم برنامهریزی پویا حل کردند. از جمله این توابع هدف میتوان به حداقل کردن تعداد کارهای دارای دیرکرد اشاره کرد که با مرتبه زمانی - 3 - قابل حل میباشد. همچنین مسأله مذکور با هدف حداقل کردن بیشینه تاخیر با مرتبه زمانی - 2 - و با هدف حداقل کردن مجموع وزندار زمان تکمیل کارها با مرتبه زمانی - - حل میشود. آنها ثابت کردند که مسأله مطرح شده با تابع هدف حداقل کردن تعداد کارهای دارای دیرکرد در حالت وزندار NP-hard است.
برای مدل با محدودیت ظرفیت با تابع هدف حداقل کردن مجموع زمان تکمیل کارها یک الگوریتم برنامهریزی پویا با مرتبه زمانی - - - - −1 ارائه شده است. هنگامی که > 1 باشد، برای نمونهای که دارای زمان پردازش متفاوت است آنها یک الگوریتم برنامهریزی پویا با مرتبه زمانی - 2 22 - را ارائه دادند. در مرجع [3] به این مطلب اشاره شده است که درسال 2000، Potts و Kovalyor ادبیات مربوط به مسأله زمانبندی با دستهبندی کارها را مرور کردند.
نویسندگان، دو نوع از مدلهای زمانبندی که نیاز به دستهبندی دارند را مورد بررسی قرار دادند. دسته اول مدلهای زمانبندی خانوادگی هستند که کارها براساس زمان راهاندازی مشابهی که دارند در یک دسته قرار میگیرند. دسته دوم مدلهای ماشین دسته-ای هستند که کارهایی که همزمان پردازش میشوند تشکیل یک دسته را میدهند . برای حل مدل زمانبندی خانوادگی نشان داده شده است که استفاده از الگوریتم برنامهریزی پویا مفید میباشد.
بسیاری از مسائل مورد بحث در این مقاله یا به صورت چندجملهای قابل حل هستند و یا NP-hard میباشند . برای مسائل NP-hard تعداد محدودی از مطالعات به طراحی الگوریتم شاخهوکران و الگوریتمهای تقریبی پرداختهاند. در سال 2008، Finke و همکارانش [4] به تجزیه و تحلیل مسأله زمانبندی گروهی مرتبط با کاربردهای صنعتی خاص پرداختند. مدل ارائه شده در مقاله مرتبط است با مسأله زمانبندی کارهای گروهی با هدف حداقل کردن بیشینه زمان تکمیل کارها که با الگوریتم برنامهریزی پویا حل شده است.
Verstichel و Vanden Berghe در سال 2009 به بررسی الگوریتم پذیرش3 برای مسأله زمانبندی درگاه پرداختند. هدف مسأله زمانبندی درگاه، حداقل کردن زمان انتظار همه کشتیها و حداقل نمودن استفاده از آب درگاه به صورت همزمان میباشد. دراینجا برای کشتیها دو حالت عادی و اولویتدار درنظرگرفته شده است که باید زمان انتظار کشتیهای اولویتدار تا حد ممکن کمینه شود که حداقل کردن مصرف آب به عنوان حداقل کردن تعداد کل عبورهای محفظهها مدل شده است .[5]
Verstichel و همکارانش [6] درسال 2014 یک رویکرد یکپارچه برای حل مسأله زمانبندی یک درگاه عمومی ارائه دادند. دراین مقاله سه زیر مسأله مرتبط با هم یعنی مسأله قرار دادن کشتیها، مسأله تخصیص محفظه و زمانبندی عملیات عبور که به ترتیب با مسأله کوله پشتی4، مسأله تخصیص و مسأله زمانبندی ماشینهای موازی 5 معادل هستند، مطرح شد. زمانی که یک درگاه با محفظههای متفاوت داریم باید مسأله تخصیص نوع محفظه نیز حل شود. نویسندگان یک مدل برنامهریزی خطی عدد صحیح مختلط6 ارائه دادند و آن را توسط یک روش دقیق برای حل هر سه زیر مسأله به طور همزمان، بر روی دادههای مربوط به دو درگاه پیادهسازی کردند.
Passchyn و همکارانش در سال 2016 در مرجع [7] یک الگوریتم برنامهریزی پویا برای زمانبندی یک درگاه واحد با ظرفیت واحد را ارائه نمودند. آن ها ثابت کردند که یک الگوریتم با مرتبه زمانی - 2 - برای مسئلهی مذکور وجود دارد. این الگوریتم را میتوان برای حل نسخههای با ظرفیت متفاوت، زمان بارگیری وابسته به کشتی، زمان عبور غیریکنواخت و محدودیت در تعداد حرکت درگاه را توسعه و مورد استفاده قرار داد. به علاوه، عملکرد چندین روش اکتشافی را با اجرای آنها بر روی نمونههای ایجادشدهی تصادفی که مشخصههای شرایط واقعی را داشتند، مورد بررسی قراردادند.
در مرجع [8] آمده است که درسال 2016، Passchyn و همکارانش به ارائه زمانبندی درگاههای سری پرداختند. دراین مقاله دو مدل ریاضی متفاوت ارائه کردند و مشخص شد که هر دو فرمولبندی مدل در مقایسه با هم، مزایای خاص خود را دارند. آن ها همچنین به مقایسهی نتایج مدل یکپارچه با نتایج حاصل از زمانبندی اکتشافی درگاهها پرداختند. یافتههای آنها اثبات کرد که زمانبندی یکپارچهی درگاههای متوالی می-تواند تا حد زیادی زمان طی مسیر را کاهش دهد.
مقالههای مذکور همگی بر درگاههایی با محفظه واحد تمرکز دارند در حالی که در عمل بسیاری از درگاهها از بیش از یک محفظه تشکیل شدهاند . برای نمونه، در کانال پاناما هر درگاه از دو محفظه موازی یکسان تشکیل شده است. درگاه Wijnegem در بلژیک نیز یک مثال دیگر برای این موضوع است که این درگاه، کانال Albert را به بندرAntwerp متصل کرده و همچون تمامی دیگر درگاههای کانال Albert از سه محفظه ناهمسان تشکیل شده است. به علاوه، در حال حاضر ساخت محفظه چهارم در درگاه Wijnegem مد نظر است که در مرجع [9] به آن اشاره شده است. لذا در ادامه به مرور مقالات مرتبط با بخش دوم یعنی تحقیقات مربوط به مسأله تخصیص بهینه کشتیها به محفظهها و زمانبندی کردن عبورها از هرمحفظه که مرتبط با موضوع تحقیق حاضر میباشد و تحقیقات محدودتری دراین حوزه انجام شده است خواهیم پرداخت.
درمقاله [10] درسال Passchyn 2018 و همکارانش مسألهی زمانبندی یک درگاه دارای محفظههای موازی را مورد بررسی قرار دادند. آنها بر وجود زمانبندیهای بدون معطلی تمرکز نموده و پیچیدگی انواع مختلف اینگونه مسائل را در نظر گرفتند. بطور خاص برای یک درگاه متشکل از دو محفظه، عملی بودن راهحل را آزمودند و به یک الگوریتم زمان خطی دست یافتند. آنها یک الگوریتم کارآمد برای مواردی که در آن تمامی محفظههای یک درگاه، مشابه باشند نیز ارائه دادند. به علاوه، یک روش برنامهریزی پویا برای یک مورد کلی با محفظههای دلخواه تعریف نموده و اثبات کردند که این مسأله زمانیکه تعداد محفظهها جزء ورودیها باشد، یک مسألهی NP-Complete است.
-3 مدلهای برنامهریزی ریاضی
مسأله مورد بررسی در این پژوهش حالت تعمیمیافتهای از مسأله تخصیص کشتیها به درگاهها است.
