摘要
探讨了有限预知信息下的集装箱码头泊位与岸桥联合调度over-list在线模型,当分配每个船舶服务请求时预知后续k≥2个请求,要求完成所有请求的最大完工时间最小。着重考虑了由3个离散泊位组成的混合型泊位、6个岸桥以及只有两种请求的联合调度模型,证明了任意k≥2个请求预知能力下确定性在线策略的竞争比下界为9/7;同时,设计了k=2时的在线联合调度策略并证明其具有最优竞争比9/7,表明有限的预知能力即可实现在线策略最优调度效果,这也为集装箱码头资源调度实践中的策略设计提供理论依据。
Abstract： This paper studies an online over-list model of berth and quay crane integratedallocation in the scenario with k-lookahead ability such that the next k ≥ 2 requests are foreseen on the release of any requesi. The aim is to minimize the maximumcompletion time of request, i. e. , the makespan. We consider the model with two different sized requests, a hybrid berth consisting of three discrete berths, and six cranes. One main result is a lower bound 9/7 of competitive ratio for deterministic online strategies given any k = 2. We then propose an online strategy that has an ability of foreseeing only next requests, and prove it optimally 9/7-competitive. The above results reveal that any larger lookahead ability cannot further improve the competitive performanceof online strategies. It gives a hint in designing efficient scheduling strategies in container resource management practice.
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2016年第4期101-105,共5页
Operations Research and Management Science
基金
国家自然科学基金资助项目(71172189)
教育部新世纪优秀人才支持计划(NCET-12-0824)
东华大学"励志计划"(A201305)
中央高校基本科研业务费专项资金项目资助
关键词
排序
集装箱码头
在线策略
竞争比
scheduling
container port
online algorithm
competitive ratio
