English

运筹学学报 >

2020 , Vol. 24 >Issue 1: 147 - 154

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2020.01.012

堆取料机调度问题的一个近似算法

展开
  • 1. 杭州电子科技大学理学院, 杭州 310018;
    2. 台州学院, 浙江台州 318000

收稿日期: 2018-06-25

  网络出版日期: 2020-03-09

基金资助

国家自然科学基金（Nos.11771114，11971139，11571252）

收起

An approximation algorithm for reclaimer scheduling

Expand
  • 1. School of Science, Hangzhou Dianzi University, Hangzhou 310018, China;
    2. Taizhou University, Taizhou 318000, Zhejiang, China

Received date: 2018-06-25

  Online published: 2020-03-09

Fold

摘要

研究源自煤炭港口料场管理的堆取料机调度问题.该问题中，堆取料机从长为L的料场作业区最左端开始空机或载料运行，两者的速度之比为s：1（s ≥ 1）.决策者需确定储料堆在作业区的分布以及堆取料机处理它们的先后次序，目的是极小化一批煤料运输船的在港服务时间.考虑堆取料机处理完毕需要回到料场终端的作业模型，证明了存在最坏情况界不超过1+1/4s的近似算法.

关键词： 堆取料机调度; 储料堆; 近似算法; 最坏情况分析

本文引用格式

王翼展, 张安, 陈永, 陈光亭 . 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020 , 24(1) : 147 -154 . DOI: 10.15960/j.cnki.issn.1007-6093.2020.01.012

Abstract

This paper studies the reclaimer scheduling problem that arises in the management of a stockyard at a coal terminal. In this problem, we are given a single reclaimer initially located at the left end of a stock pad of length L. The reclaimer can either travel across or reclaim stockpiles on the stock pad, with a speed ratio of s ≥ 1. The scheduler has to decide the placement positions of the stockpiles on the stock pad and sequence the reclaiming of the stockpiles so as to minimize the total time serving the arrived vessels. We show that there exists an approximation algorithm with a worst case ratio no larger than 1 + 1/4s, provided that the reclaimer has to return to the endpoints of the stock pad.

Key words： reclaimer scheduling; stockpile; approximation algorithm; worst case analysis

参考文献

[1] Kalinowski T, Kapoor R, Savelsbergh Martin W P. Scheduling reclaimers serving a stock pad at a coal terminal[J]. Journal of Scheduling, 2017, 20(1):85-101.
[2] Angelelli E, Kalinowski T, Kapoor R, et al. A reclaimer scheduling problem arising in coal stockyard management[J]. Journal of Scheduling, 2016, 19(5):563-582.
[3] Bierwirth C, Meisel F. A survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research, 2010, 202(3):615-627.
[4] Bierwirth C, Meisel F. A follow-up survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research, 2015, 244(3):675-689.
[5] Boysen B, Briskorn D, Meisel F. A generalized classification scheme for crane scheduling with interference[J]. European Journal of Operational Research, 2017, 258:343-357.
[6] Zhen L, Yu S C, Wang S A, et al. Scheduling quay cranes and yard trucks for unloading operations in container ports[J]. Annals of Operations Research, 2019, 273:455-478.
[7] Ma H L, Chung S H, Chan H K, et al. An integrated model for berth and yard planning in container terminals with multi-continuous berth layout[J]. Annals of Operations Research, 2019, 273:409-431.
[8] Graham R L. Bounds on multiprocessing timing anomalies[J]. SIAM Journal on Applied Mathematics, 1969, 17(2):416-429.
Options
文章导航

/

〈 〉