proposed for its solution.

For the single reclaimer case, the fact that the reclaimer has to travel along every stockpile gives it a traveling salesman flavor. The basic traveling salesman problem is trivial when all nodes are on a line, but it becomes difficult when additional constraints, such as time windows, are added ([@psaraftis1990routing], [@tsitsiklis1992special]). In our problem, the single reclaimer case becomes a traveling salesman problem on a line with prescribed edges: the nodes are the endpoints of the stockpiles, and for every stockpile the edge connecting its endpoints has to be traversed in the solution.

Problem Description {#sec:problem}
===================

The practical importance of reclaimer scheduling at a coal terminal prompted us to study a set of simplified and idealized reclaimer scheduling problems. These simplified and idealized reclaimer scheduling problems turn out to lead to intriguing and, in some cases, surprisingly challenging optimization problems.

We make the following basic assumptions:

-   There are two reclaimers $R_0$ and $R_1$ that serve two pads; one on either side of the reclaimers.

-   Reclaimer $R_0$ starts at one end of the stock pads and Reclaimer $R_1$ starts at the other end of the stock pads.

-   Stockpiles are reclaimed by one of 