American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Transient and steady state analysis of an M/M/1 queue with balking, catastrophes, server failures and repairs
  • JIMO Home
  • This Issue
  • Next Article
    Uniform estimates for ruin probabilities in the renewal risk model with upper-tail independent claims and premiums
October  2011, 7(4): 825-848. doi: 10.3934/jimo.2011.7.825

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, Turkey
2. 

University of Florida, Department of Industrial and Systems Engineering, Gainesville, FL 32611, United States

Received  August 2010 Revised  May 2011 Published  August 2011

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: railyards, yard operations., stepwise tardiness, hump sequencing, Single-machine scheduling.
Mathematics Subject Classification: Primary: 90B35, 90C60; Secondary: 90B0.
Citation: Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825
References:
[1]

M. van den Akker, "LP-based Solution Methods for Single-Machine Scheduling Problems,", Ph.D Thesis, (1994). Google Scholar

[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. doi: 10.1287/ijoc.12.2.111.11896. Google Scholar

[3]

J. R. Birge and M. J. Maddox, Bounds on expected project tardiness,, Operations Research, 43 (1995), 838. doi: 10.1287/opre.43.5.838. Google Scholar

[4]

P. Brucker and S. Knust, Complexity results for scheduling problems,, Available from: \url{http://www.informatik.uni-osnabrueck.de/knust/class/} (accessed 1 March 2011)., (2011). Google Scholar

[5]

J. Curry and B. Peters, "Solving Parallel Machine Scheduling Problems with Stepwise Increasing Tardiness Cost Objectives,", Working Paper, (2004). Google Scholar

[6]

J. Curry and B. Peters, Rescheduling parallel machines with stepwise increasing tardiness,, International Journal of Production Research, 43 (2005), 3231. doi: 10.1080/00207540500103953. Google Scholar

[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. doi: 10.1016/0191-2607(83)90063-8. Google Scholar

[8]

C. F. Daganzo, Static blocking at railyards: Sorting implications and tracks requirements,, Transportation Science, 20 (1986), 186. doi: 10.1287/trsc.20.3.189. Google Scholar

[9]

C. F. Daganzo, Dynamic blocking for railyards: Part I. Homogeneous traffic,, Transportation Research Part B, 21 (1987), 1. doi: 10.1016/0191-2615(87)90018-X. Google Scholar

[10]

C. F. Daganzo, Dynamic blocking for railyards: Part II. Heterogeneous traffic,, Transportation Research Part B, 21 (1987), 29. doi: 10.1016/0191-2615(87)90019-1. Google Scholar

[11]

J. Du and J. Y.-T. Leung, Minimizing total tardiness on one machine is NP-hard,, Mathematics of Operations Research, 15 (1990), 483. doi: 10.1287/moor.15.3.483. Google Scholar

[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., 5 (1979), 287. doi: 10.1016/S0167-5060(08)70356-X. Google Scholar

[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. doi: 10.1287/moor.22.3.513. Google Scholar

[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. Google Scholar

[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 (2002), 93. Google Scholar

[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 (2002), 107. Google Scholar

[17]

E. L. Lawler, "A 'Pseudopolynomial' Algorithm for Sequencing Jobs to Minimize Total Tardiness,", Studies in Integer Programming (Proc. Workshop, 1 (1977), 331. doi: 10.1016/S0167-5060(08)70742-8. Google Scholar

[18]

C. D. Martland, PMAKE analysis: Predicting rail yard time distributions using probabilistic train connection standards,, Transportation Science, 16 (1982), 476. doi: 10.1287/trsc.16.4.476. Google Scholar

[19]

E. R. Petersen, Railyard modeling: Part I. Prediction of put-through time,, Transportation Science, 11 (1977), 37. doi: 10.1287/trsc.11.1.37. Google Scholar

[20]

E. R. Petersen, Railyard modeling: Part II. The effect of yard facilities on congestion,, Transportation Science, 11 (1977), 50. doi: 10.1287/trsc.11.1.50. Google Scholar

[21]

C. Phillips, C. Stein and J. Wein, Minimizing average completion time in the presence of release dates,, Mathematical Programming B, 82 (1998), 199. doi: 10.1007/BF01585872. Google Scholar

[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. doi: 10.1287/ijoc.1030.0055. Google Scholar

[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. doi: 10.1007/BF01586059. Google Scholar

[24]

M. A. Turnquist and M. S. Daskin, Queuing models of classification and delay in railyards,, Transportation Science, 16 (1982), 207. doi: 10.1287/trsc.16.2.207. Google Scholar

show all references

References:
[1]

M. van den Akker, "LP-based Solution Methods for Single-Machine Scheduling Problems,", Ph.D Thesis, (1994). Google Scholar

[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. doi: 10.1287/ijoc.12.2.111.11896. Google Scholar

[3]

J. R. Birge and M. J. Maddox, Bounds on expected project tardiness,, Operations Research, 43 (1995), 838. doi: 10.1287/opre.43.5.838. Google Scholar

[4]

P. Brucker and S. Knust, Complexity results for scheduling problems,, Available from: \url{http://www.informatik.uni-osnabrueck.de/knust/class/} (accessed 1 March 2011)., (2011). Google Scholar

[5]

J. Curry and B. Peters, "Solving Parallel Machine Scheduling Problems with Stepwise Increasing Tardiness Cost Objectives,", Working Paper, (2004). Google Scholar

[6]

J. Curry and B. Peters, Rescheduling parallel machines with stepwise increasing tardiness,, International Journal of Production Research, 43 (2005), 3231. doi: 10.1080/00207540500103953. Google Scholar

[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. doi: 10.1016/0191-2607(83)90063-8. Google Scholar

[8]

C. F. Daganzo, Static blocking at railyards: Sorting implications and tracks requirements,, Transportation Science, 20 (1986), 186. doi: 10.1287/trsc.20.3.189. Google Scholar

[9]

C. F. Daganzo, Dynamic blocking for railyards: Part I. Homogeneous traffic,, Transportation Research Part B, 21 (1987), 1. doi: 10.1016/0191-2615(87)90018-X. Google Scholar

[10]

C. F. Daganzo, Dynamic blocking for railyards: Part II. Heterogeneous traffic,, Transportation Research Part B, 21 (1987), 29. doi: 10.1016/0191-2615(87)90019-1. Google Scholar

[11]

J. Du and J. Y.-T. Leung, Minimizing total tardiness on one machine is NP-hard,, Mathematics of Operations Research, 15 (1990), 483. doi: 10.1287/moor.15.3.483. Google Scholar

[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., 5 (1979), 287. doi: 10.1016/S0167-5060(08)70356-X. Google Scholar

[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. doi: 10.1287/moor.22.3.513. Google Scholar

[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. Google Scholar

[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 (2002), 93. Google Scholar

[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 (2002), 107. Google Scholar

[17]

E. L. Lawler, "A 'Pseudopolynomial' Algorithm for Sequencing Jobs to Minimize Total Tardiness,", Studies in Integer Programming (Proc. Workshop, 1 (1977), 331. doi: 10.1016/S0167-5060(08)70742-8. Google Scholar

[18]

C. D. Martland, PMAKE analysis: Predicting rail yard time distributions using probabilistic train connection standards,, Transportation Science, 16 (1982), 476. doi: 10.1287/trsc.16.4.476. Google Scholar

[19]

E. R. Petersen, Railyard modeling: Part I. Prediction of put-through time,, Transportation Science, 11 (1977), 37. doi: 10.1287/trsc.11.1.37. Google Scholar

[20]

E. R. Petersen, Railyard modeling: Part II. The effect of yard facilities on congestion,, Transportation Science, 11 (1977), 50. doi: 10.1287/trsc.11.1.50. Google Scholar

[21]

C. Phillips, C. Stein and J. Wein, Minimizing average completion time in the presence of release dates,, Mathematical Programming B, 82 (1998), 199. doi: 10.1007/BF01585872. Google Scholar

[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. doi: 10.1287/ijoc.1030.0055. Google Scholar

[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. doi: 10.1007/BF01586059. Google Scholar

[24]

M. A. Turnquist and M. S. Daskin, Queuing models of classification and delay in railyards,, Transportation Science, 16 (1982), 207. doi: 10.1287/trsc.16.2.207. Google Scholar

[1]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071
[2]

Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040
[3]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial & Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757
[4]

Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691
[5]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323
[6]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019005
[7]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088
[8]

Mingbao Cheng, Shuxian Xiao, Guosheng Liu. Single-machine rescheduling problems with learning effect under disruptions. Journal of Industrial & Management Optimization, 2018, 14 (3) : 967-980. doi: 10.3934/jimo.2017085
[9]

Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219
[10]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058
[11]

Ata Allah Taleizadeh, Biswajit Sarkar, Mohammad Hasani. Delayed payment policy in multi-product single-machine economic production quantity model with repair failure and partial backordering. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-24. doi: 10.3934/jimo.2019002
[12]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[13]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71
[14]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2018148
[15]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259
[16]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771
[17]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703
[18]

Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591
[19]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009
[20]

Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences