Optimising reclaimer schedules

The Hunter Valley Coal Chain (HVCC), with 40 coal mines, 30 load points, 3 coal loading terminals (9 ship berths and 7 loaders), and loading about 1,500 ships annually, is one of the largest coal export operations in the world. All planning and scheduling of coal exports in the Hunter Valley is managed by the Hunter Valley Coal Chain Coordinator Limited (HVCCC) with a main goal of maximizing the throughput. Effective management of the stockyards at the coal terminals is critical to achieving this goal. Coal arrives at a coal terminal by train. The coal is dumped and stacked to form stockpiles. Coal brands are a blended product, with coal from different mines having different characteristics “mixed” in a stockpile to meet the specifications of the customer. Once the ship for which the coal is destined arrives at a berth at the terminal, the coal is reclaimed and loaded onto the ship. The ship then transports the coal to its destination. The efficiency of a stockyard depends heavily on the reclaimers’ productivity. Thus, effective scheduling of the reclaimers is of crucial importance. To better understand the fundamental difficulties of reclaimer scheduling, we are investigating a number of variants of an abstract reclaimer scheduling problem. In this paper, we consider a variant in which two reclaimers serve two parallel identical stock pads, i.e., the reclaimers move back and forth along the length of the pads and reclaim stockpiles from both pads. However, since the two reclaimers move on the same rails they cannot pass each other. The goal is to reclaim a set of stockpiles with given positions on the pads as quickly as possible. More specifically, one reclaimer starts at one end of the stock pads and the other reclaimer starts at the other end of the stock pads. After reclaiming the stockpiles, the reclaimers need to return to their original position. The reclaimers are identical and thus have the same reclaim speed and the same travel speed. The reclaimers cannot pass each other. A set of stockpiles positioned on the two stock pads has to be reclaimed. Each stockpile has a start and end position and thus a length. When a stockpile is reclaimed, it has to be traversed along its entire length by one of the reclaimers, either from left to right or from right to left. The reclaim time of a stockpile is determined by its length and the reclaim speed of the reclaimers. The goal is to reclaim the stockpiles and minimise the maximum of the return time of two reclaimers to their original positions. In Angelelli et al. (2013), we have shown that this variant of the reclaimer scheduling problem is NP-complete and have introduced three approximation algorithms for its solution. The three approximation algorithms use different rules for deciding which stockpiles are to be served by each of the reclaimers, but in all three algorithms the reclaimers employ a simple out-and-back routing strategy to reclaim their assigned stockpiles. To decide on the assignment of stockpiles to reclaimers, the three algorithms divide each of the pads into two parts and assign the stockpiles on left of the dividing point to the left reclaimer and the remaining stockpiles to right reclaimer. The algorithms differ in how the dividing points are chosen. In this paper, we discuss the results of a computational study in which the performance of implementations of the different approximation algorithms are compared on randomly generated instances. The results demonstrate that high-quality solutions can be obtained efficiently for instances with widely varying characteristics