A Two-stage Scheduling Problem Arising from Locomotive Dispatching in Mine Railway

摘要

A locomotive dispatching problem arose from a coal mining area in 1950's: 2n jobs are executed by a locomotive, where n preceding jobs J_i with deadlines d_i (1 ≤ i ≤n) represent sending empty cars to n pits from the central station, while n successive jobs J'_i with release dates r'_i (1≤ i ≤ n) represent drawing back the loaded cars from n pits to the station; in order to reduce the detaining and increase the turnover rate of freight cars, we are asked to find a schedule of the locomotive so that the maximum flow-time is minimized. Here, the flow-time of a job is the difference between the deadline and the starting time (for a preceding job) or between the completion time and the release date (for a successive job). The present paper studies this two-stage single machine scheduling problem. The main result is a polynomial algorithm for solving it. Meanwhile, two variant models are discussed, one is easier and one is harder. The algorithms here can be regarded as generalizations of the EDD-ERD rule.