Single-machine scheduling with stepwise tardiness costs and release times

This is the latest version of this item.

Abstract

We study a scheduling problem that belongs to the yard operations component of the railroad planning problems, namely the hump sequencing problem. The scheduling problem is characterized as a single-machine problem with stepwise tardiness cost objectives. This is a new scheduling criterion which is also relevant in the context of traditional machine scheduling problems. We produce complexity results that characterize some cases of the problem as pseudo-polynomially solvable. For the difficult-to-solve cases of the problem, we develop mathematical programming formulations, and propose heuristic algorithms. We test the formulations and heuristic algorithms on randomly generated single-machine scheduling problems and real-life datasets for the hump sequencing problem. Our experiments show promising results for both sets of problems.

Available Versions of this Item

• Single-Machine Scheduling with Stepwise Tardiness Costs and Release Times. (deposited 31 Oct 2007 08:18)
  • Single-machine scheduling with stepwise tardiness costs and release times. (deposited 06 Dec 2010 16:38)
    • Single-machine scheduling with stepwise tardiness costs and release times. (deposited 27 Oct 2011 14:04) [Currently Displayed]