---
abstract: |
    We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor approximation algorithm.

    **Keywords:** reclaimer scheduling, stockyard management, approximation algorithm, complexity
author:
- |
    Enrico Angelelli\
    [*University of Brescia, Italy*]{}
- |
    Thomas Kalinowski , Reena Kapoor\
    [*University of Newcastle, Australia*]{}
- |
    Martin W.P. Savelsbergh\
    [*Georgia Institute of Technology, USA*]{}
title: 'A reclaimer scheduling problem arising in coal stockyard management[^1]'
---

Introduction
============

We investigate a scheduling problem that arises in the management of a stockyard at a coal export terminal. Coal is marketed and sold to customers by brand. The brand of coal dictates its characteristics, for example the range in which its calorific value, ash, moisture and/or sulphur content lies. In order to deliver a brand required by a customer, coal from different mines, producing coal with different characteristics, is “mixed” in a stockpile at the stockyard of a coal terminal to obtain a blended product meeting the required brand 