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