Single-machine scheduling with stepwise tardiness costs and release times
Güvenç Şahin - Sabanci University, Manufacturing Systems and Industrial Engineering Program, Orhanli-Tuzla 34956 Istanbul, Turkey (email)
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 data sets for the hump sequencing problem. Our experiments show promising results for both sets of problems.
Keywords: Single-machine scheduling, stepwise tardiness, hump sequencing, railyards, yard operations.
Received: August 2010; Revised: May 2011; Available Online: August 2011.
2015 Impact Factor.776