APP下载

集成岸桥分派的在线泊位分配问题

2017-08-16陈光亭

关键词:分配

杨 帆,张 安,陈 永,陈光亭

(杭州电子科技大学理学院,浙江 杭州 310018)

集成岸桥分派的在线泊位分配问题

杨 帆,张 安,陈 永,陈光亭

(杭州电子科技大学理学院,浙江 杭州 310018)

主要研究一类集成岸桥分派的在线泊位分配问题.考虑了3个连续泊位、4台岸桥的情形,以极小化集装箱货轮的总处理(装载、卸载任务)时间为目标函数,证明了最好可能的在线分派方案是2-2-0,并设计了竞争比为5/4的最优在线泊位分配算法.

岸桥分派;泊位分配;在线算法;竞争比

0 引 言

1 问题描述与基本符号

记3个连续的泊位分别为b1,b2,b3,考虑到泊位空间的限制以及岸桥的安全距离要求,一般假定每个泊位至多分派两台岸桥[4-5].因此,4台岸桥在3个连续泊位上的分派方案只可能有3种:2-2-0,2-1-1,1-2-1(依据下文货轮的类型,2-0-2分派方案相对于2-2-0分派方案属于劣势分派方案,因此不再考虑2-0-2方案).根据停靠泊位的情况,集装箱货轮也分为停靠1个泊位的小型货轮与停靠2个泊位的大型货轮两种类型.为简化模型,记小型货轮的装卸需求量为1,大型货轮的装卸需求量为Δ,且一般有Δ≥2[4-5].如果一艘大(小)型货轮停靠的泊位上共有m(m≥1)台岸桥,那么它的处理时间为Δ/m(1/m).在线问题是指货轮及其需求是实时产生的,决策者只有在需求产生后才能决定如何分配泊位.为方便起见,假设货轮的需求量按I=(r1,r2,…,rn)顺序到达,其中ri=1或Δ,目标是极小化这批需求的总处理时间.由于岸桥总数为4台,因此最少处理时间C*(I)必然满足:

(1)

2 算法设计与竞争比分析

首先给出在3种可能的岸桥分派方案下在线泊位分配问题的下界.

登录APP查看全文

猜你喜欢

分配
分配正义:以弱势群体为棱镜
基于可行方向法的水下机器人推力分配
应答器THR和TFFR分配及SIL等级探讨
Crying Foul
遗产的分配
一种分配十分不均的财富
绩效考核分配的实践与思考
收入分配视阈下的共享发展思考
浙江绩效分配改革观察
俄罗斯的分配状况