Scheduling problems arising in coal export supply chains: algorithms and complexity

A coal supply chain is a highly complex logistics system, comprising of several parties and components, focused on transporting coal from suppliers to end buyers. An important goal in many supply chains is to maximize the throughput. Due to the complex structure of a coal supply chain, a number of challenges arises when trying to maximize the throughput of the chain. One of the key challenges in a coal supply chain and one that plays a vital role when maximizing the throughput of the chain is the scheduling of preventive maintenance of the components of the chain that degrade over time, such as the rail network and the coal stacking machinery. During the maintenance period, the components are unavailable for work, which may result in a reduction in the throughput of the supply chain. In order to understand the complexities associated with the problem of scheduling preventative maintenance, we have analysed the complexity of an abstract version of the problem. We studied the problem of scheduling maintenance on arcs of a capacitated network so as to maximize the total flow from a source node to a sink node over a set of given time periods. Maintenance of an arc shuts down the arc for the duration of the period in which its maintenance is scheduled, reducing its capacity to zero for that period. A set of arcs is designated to have maintenance during the planning period, which will require each of the arcs to be shut down for exactly one time period. In general, this problem is known to be NP-hard. We have identified a number of characteristics that are relevant for the complexity of instance classes. In particular, we investigated instances with restrictions on the set of arcs for which maintenance is scheduled; series parallel networks; capacities that are balanced, in the sense that the total capacity of arcs entering a (non-terminal) node equals the total capacity of arcs leaving the node; and identical capacities on all arcs. Another factor that has a great impact on the throughput of the coal supply chain is the management of the stockyard, which is the interface between the land portion of the coal supply chain and the ocean portion of the coal supply chain, and where the cargoes get assembled. Given a number of vessels arriving at the port, stockyard management decisions include: assigning a location to each cargo (stockpile) of a vessel in the stockyard, scheduling the assembly of the cargoes, scheduling the stacking and reclaiming of the cargoes, etc. The resulting decision problem is challenging, but plays a crucial role in the overall performance of the logistics chain. In this thesis, we have focused on the placement of the stockpiles on the stock pads and the scheduling of the reclaiming of the stockpiles. We study a number of variants of an abstract scheduling problem inspired by the scheduling of the reclaimers in the stockyard of a coal export terminal. We have analysed the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For some of the variants, we present mixed integer programming formulations, exact algorithms, such as branch and bound algorithms and dynamic programming algorithms, and constant factor approximation algorithms. Furthermore, we perform extensive computational studies to analyse the performance of the proposed solution methodologies.