English

运筹学学报 ›› 2020, Vol. 24 ›› Issue (1): 147-154.doi: 10.15960/j.cnki.issn.1007-6093.2020.01.012

• • 上一篇    下一篇

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

王翼展1, 张安1,*, 陈永1, 陈光亭2   

  1. 1. 杭州电子科技大学理学院, 杭州 310018;
    2. 台州学院, 浙江台州 318000
  • 收稿日期:2018-06-25 发布日期:2020-03-09
  • 通讯作者: 张安 E-mail:anzhang@hdu.edu.cn
  • 基金资助:
    国家自然科学基金（Nos.11771114，11971139，11571252）

An approximation algorithm for reclaimer scheduling

WANG Yizhan1, ZHANG An1,*, CHEN Yong1, CHEN Guangting2   

  1. 1. School of Science, Hangzhou Dianzi University, Hangzhou 310018, China;
    2. Taizhou University, Taizhou 318000, Zhejiang, China
  • Received:2018-06-25 Published:2020-03-09

PDF

293

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

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

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

中图分类号: