English

运筹学学报

• 运筹学 • 上一篇    下一篇

具有预知信息的集装箱码头泊位与岸桥联合调度在线模型

李英1 乔龙亮1,* 郑斐峰1   

  1. 1. 东华大学旭日工商管理学院, 上海 200051
  • 收稿日期:2016-03-18 出版日期:2018-09-15 发布日期:2018-09-15
  • 通讯作者: 乔龙亮 E-mail: qiaolongliang@163.com
  • 基金资助:

    国家自然科学基金(Nos. 71771048, 71832001), 中央高校基本科研业务费专项资金项目资助

A study of online berth and quay crane integrated allocation problem with lookahead ability

LI Ying1 QIAO Longliang1,*  ZHENG Feifeng1   

  1. 1. Glorious Sun School of Business & Management, Donghua University, Shanghai 200051, China
  • Received:2016-03-18 Online:2018-09-15 Published:2018-09-15

PDF

180

摘要：

探讨了预知服务需求信息能力下的集装箱码头泊位与岸桥联合调度 over-list 在线模型. 在每个船舶服务请求释放时, 决策者预知后续 k(k \geq 2)个请求的信息，目标为最小化所有请求的最大完工时间. 针对由3个离散泊位组成的混合型泊位与4个岸桥, 以及只有大小两种服务请求的情形, 给出了预知任意 k \geq 2个请求下的竞争比下界; 同时, 对于k=2的特定情形, 给出了具有最优竞争比7/6 的在线策略. 数值实验进一步表明了所设计策略的良好执行性能.

关键词: 调度决策, 在线策略, 竞争比, 集装箱码头, 预知信息

Abstract:

This paper studies an online over-list model of berth and quay crane integrated allocation problem, and it focuses on the case with lookahead ability such that on the release of any request, an online player can foresee the next k(k \geq 2) requests. The objective is to minimize the maximum completion time of a request, i.e., the makespan. It is assumed that there are two different sized requests, a hybrid berth consisting of three discrete berths and four quay cranes. We first prove several lower bounds of competitive ratio for k \geq 2, and then present an optimal 7/6-competitive algorithm for the case with k=2. Numerical results further demonstrate that the proposed algorithm behaves well in average performance.

Key words: scheduling, online algorithm, competitive ratio, container port, lookahead