Single-machine scheduling with stepwise tardiness costs and release times

Güvenç Şahin; Ravindra K. Ahuja

doi:10.3934/jimo.2011.7.825

Article Contents

2011, Volume 7, Issue 4: 825-848. Doi: 10.3934/jimo.2011.7.825

This issue Previous Article Transient and steady state analysis of an M/M/1 queue with balking, catastrophes, server failures and repairs Next Article Uniform estimates for ruin probabilities in the renewal risk model with upper-tail independent claims and premiums

Single-machine scheduling with stepwise tardiness costs and release times

Güvenç Şahin^1, and
Ravindra K. Ahuja^2,

1.
Sabanci University, Manufacturing Systems and Industrial Engineering Program, Orhanli-Tuzla 34956 Istanbul
2.
University of Florida, Department of Industrial and Systems Engineering, Gainesville, FL 32611

Received: July 31, 2010

Revised: April 30, 2011

Published: September 2011

Abstract Related Papers Cited by

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:

Mathematics Subject Classification: Primary: 90B35, 90C60; Secondary: 90B06.

Citation:

Related Papers

Cited by

References

[1]	M. van den Akker, "LP-based Solution Methods for Single-Machine Scheduling Problems," Ph.D Thesis, Eindhoven University of Technology, Eindhoven, The Netherlands, 1994.
[2]	M. van den Akker, C. A. J. Hurkens and M. W. P. Savelsbergh, Time-indexed formulations for machine scheduling problems: Column generation, INFORMS Journal on Computing, 12 (2000), 111-124.doi: 10.1287/ijoc.12.2.111.11896.
[3]	J. R. Birge and M. J. Maddox, Bounds on expected project tardiness, Operations Research, 43 (1995), 838-850.doi: 10.1287/opre.43.5.838.
[4]	P. Brucker and S. Knust, Complexity results for scheduling problems, Available from: http://www.informatik.uni-osnabrueck.de/knust/class/ (accessed 1 March 2011).
[5]	J. Curry and B. Peters, "Solving Parallel Machine Scheduling Problems with Stepwise Increasing Tardiness Cost Objectives," Working Paper, Department of Industrial Engineering, Texas A&M University, 2004.
[6]	J. Curry and B. Peters, Rescheduling parallel machines with stepwise increasing tardiness, International Journal of Production Research, 43 (2005), 3231-3246.doi: 10.1080/00207540500103953.
[7]	C. F. Daganzo, R. G. Dowling and R. W. Hall, Railroad classification yard throughput: The case of multistage triangular sorting, Transportation Research Part A, 17 (1983), 95-106.doi: 10.1016/0191-2607(83)90063-8.
[8]	C. F. Daganzo, Static blocking at railyards: Sorting implications and tracks requirements, Transportation Science, 20 (1986), 186-199.doi: 10.1287/trsc.20.3.189.
[9]	C. F. Daganzo, Dynamic blocking for railyards: Part I. Homogeneous traffic, Transportation Research Part B, 21 (1987a), 1-27.doi: 10.1016/0191-2615(87)90018-X.
[10]	C. F. Daganzo, Dynamic blocking for railyards: Part II. Heterogeneous traffic, Transportation Research Part B, 21 (1987b), 29-40.doi: 10.1016/0191-2615(87)90019-1.
[11]	J. Du and J. Y.-T. Leung, Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15 (1990), 483-495.doi: 10.1287/moor.15.3.483.
[12]	R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Discrete Optimization (Proc. Adv. Res. Inst. Discrete Optimization and Systems Appl., Banff, Alta., 1977), II, Annals of Discrete Mathematics, 5 (1979), 287-326.doi: 10.1016/S0167-5060(08)70356-X.
[13]	L. A. Hall, A. S. Schulz, D. B. Shmoys and J. Wein, Scheduling to minimize average completion time: Off-line and on-line approximation algorithms, Mathematics of Operations Research, 22 (1997), 513-544.doi: 10.1287/moor.22.3.513.
[14]	E. R. Kraft, A Hump sequencing algorithm for real time management of train connection reliability, Journal of the Transportation Research Forum, 30 (2000), 95-115.
[15]	E. R. Kraft, Priority-based classification for improving connection reliability in railroad yards-part I: Integration with car scheduling, Journal of the Transportation Research Forum, 56 (2002a), 93-105.
[16]	E. R. Kraft, Priority-based classification for improving connection reliability in railroad yards-part II: Dynamic block to track assignment, Journal of the Transportation Research Forum, 56 (2002b), 107-119.
[17]	E. L. Lawler, "A 'Pseudopolynomial' Algorithm for Sequencing Jobs to Minimize Total Tardiness," Studies in Integer Programming (Proc. Workshop, Bonn, 1975), Annals of Discrete Mathematics, 1, North-Holland, Amsterdam, (1977), 331-342.doi: 10.1016/S0167-5060(08)70742-8.
[18]	C. D. Martland, PMAKE analysis: Predicting rail yard time distributions using probabilistic train connection standards, Transportation Science, 16 (1982), 476-506.doi: 10.1287/trsc.16.4.476.
[19]	E. R. Petersen, Railyard modeling: Part I. Prediction of put-through time, Transportation Science, 11 (1977a), 37-49.doi: 10.1287/trsc.11.1.37.
[20]	E. R. Petersen, Railyard modeling: Part II. The effect of yard facilities on congestion, Transportation Science, 11 (1977), 50-59.doi: 10.1287/trsc.11.1.50.
[21]	C. Phillips, C. Stein and J. Wein, Minimizing average completion time in the presence of release dates, Mathematical Programming B, 82 (1998), 199-223.doi: 10.1007/BF01585872.
[22]	M. W. P. Savelsbergh, R. N. Uma and J. Wein, An experimental study of LP-based approximation algorithms for scheduling problems, INFORMS Journal on Computing, 17 (2005), 123-136.doi: 10.1287/ijoc.1030.0055.
[23]	J. P. De Sousa and L. A. Wolsey, A time-indexed formulation of non-preemptive single-machine scheduling problems, Mathematical Programming, 54 (1992), 353-367.doi: 10.1007/BF01586059.
[24]	M. A. Turnquist and M. S. Daskin, Queuing models of classification and delay in railyards, Transportation Science, 16 (1982), 207-230.doi: 10.1287/trsc.16.2.207.