Journal of Industrial and Management Optimization (JIMO)

Single-machine scheduling with stepwise tardiness costs and release times

Pages: 825 - 848, Volume 7, Issue 4, November 2011      doi:10.3934/jimo.2011.7.825

       Abstract        References        Full Text (413.0K)       Related Articles       

Güvenç Şahin - Sabanci University, Manufacturing Systems and Industrial Engineering Program, Orhanli-Tuzla 34956 Istanbul, Turkey (email)
Ravindra K. Ahuja - University of Florida, Department of Industrial and Systems Engineering, Gainesville, FL 32611, United States (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.
Mathematics Subject Classification:  Primary: 90B35, 90C60; Secondary: 90B06.

Received: August 2010;      Revised: May 2011;      Available Online: August 2011.