October  2014, 10(4): 1071-1090. doi: 10.3934/jimo.2014.10.1071

A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs

1. 

School of Mechanical Engineering, Southwest Jiaotong University, Chengdu, China, China

2. 

Department of Mathematics, Auburn University at Montgomery, AL, United States

Received  January 2013 Revised  August 2013 Published  February 2014

This paper studies a single-machine scheduling problem with the objective of minimizing the total tardiness for a set of independent jobs. The processing time of a job is modeled as a step function of its starting time and a specific deteriorating date. The total tardiness as one important objective in practice has not been concerned in the studies of single-machine scheduling problems with step-deteriorating jobs. To overcome the intractability of the problem, we propose a heuristic named simple weighted search procedure (SWSP) and a general variable neighborhood search algorithm (GVNS) to obtain near optimal solutions. Extensive numerical experiments are carried out on randomly generated test instances in order to evaluate the performance of the proposed algorithms. By comparing to the CPLEX optimization solver, the heuristic SWSP and the standard variable neighborhood search, it is shown that the proposed GVNS algorithm can provide better solutions within a reasonable running time.
Citation: 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 and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071
References:
[1]

A. Bachman and A. Janiak, Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126 (2000), 557-566. doi: 10.1016/S0377-2217(99)00310-0.

[2]

S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498. doi: 10.1287/opre.38.3.495.

[3]

Y. J. Chang and M. J. Yao, New heuristics for solving the economic lot scheduling problem with reworks, Journal of Industrial and Management Optimization, 7 (2011), 229-251. doi: 10.3934/jimo.2011.7.229.

[4]

T. C. E. Cheng and Q. Ding, Single machine scheduling with step-deteriorating processing times, European Journal of Operational Research, 134 (2001), 623-630. doi: 10.1016/S0377-2217(00)00284-8.

[5]

T. C. E. Cheng, Q. Ding, M. Y. Kovalyov, A. Bachman and A. Janiak, Scheduling jobs with piecewise linear decreasing processing times, Naval Research Logistics, 50 (2003), 531-554 . doi: 10.1002/nav.10073.

[6]

T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152 (2004), 1-13 . doi: 10.1016/S0377-2217(02)00909-8.

[7]

W. Cheng, P. Guo, Z. Zhang, M. Zeng and J. Liang, Variable neighborhood search for parallel machines scheduling problem with step deteriorating jobs, Mathematical Problems in Engineering, (2012), 1-20. doi: 10.1155/2012/928312.

[8]

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.

[9]

J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14 (1988), 387-393 . doi: 10.1016/0360-8352(88)90041-1.

[10]

P. Hansen, N. Mladenović and D. Perez-Britos, Variable neighborhood decomposition search, Journal of Heuristics, 7 (2001), 335-350. doi: 10.1023/A:1011336210885.

[11]

P. Hansen, N. Mladenović and J. A. Moreno Pérez, Variable neighbourhood search: Methods and applications, Annals of Operations Research, 175 (2010), 367-407. doi: 10.1007/s10479-009-0657-6.

[12]

C. C. He, C. C. Wu and W. C. Lee, Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs, Journal of the Operational Research Society, 60 (2009), 1759-1766. doi: 10.1057/jors.2008.123.

[13]

A. Ilić, D. Urošević, J. Brimberg and N. Mladenović, A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem, European Journal of Operational Research, 206 (2010), 289-300. doi: 10.1016/j.ejor.2010.02.022.

[14]

A. Jafari and G. Moslehi, Scheduling linear deteriorating jobs to minimize the number of tardy jobs, Journal of Global Optimization, 54 (2012), 389-404. doi: 10.1007/s10898-011-9767-1.

[15]

A. A. K. Jeng and B. M. T. Lin, Makespan minimization in single-machine scheduling with step-deterioration of processing times, Journal of the Operational Research Society, 55 (2004), 247-256. doi: 10.1057/palgrave.jors.2601693.

[16]

A. A. K. Jeng and B. M. T. Lin, Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs, Computers and Operations Research, 32 (2005), 521-536. doi: 10.1016/j.cor.2003.08.001.

[17]

M. Ji and T. C. E. Cheng, An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan, Information Processing Letters, 102 (2007), 41-47. doi: 10.1016/j.ipl.2006.11.014.

[18]

M. Ji and T. C. E. Cheng, Parallel-machine scheduling of simple linear deteriorating jobs, Theoretical Computer Science, 410 (2009), 3761-3768. doi: 10.1016/j.tcs.2009.04.018.

[19]

G. Kirlik and C. Oguz, A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine, Computers and Operations Research, 39 (2012), 1506-1520. doi: 10.1016/j.cor.2011.08.022.

[20]

C. Koulamas, The single-machine total tardiness scheduling problem: Review and extensions, European Journal of Operational Research, 202 (2010), 1-7. doi: 10.1016/j.ejor.2009.04.007.

[21]

W. Kubiak and S. Van de Velde, Scheduling deteriorating jobs to minimize makespan, Naval Research Logistics, 45 (1998), 511-523. doi: 10.1002/(SICI)1520-6750(199808)45:5<511::AID-NAV5>3.0.CO;2-6.

[22]

A. S. Kunnathur and S. K. Gupta, Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European Journal of Operational Research, 47 (1990), 56-64. doi: 10.1016/0377-2217(90)90089-T.

[23]

J. Layegh, F. Jolai and M. S. Amalnik, A memetic algorithm for minimizing the total weighted completion time on a single machine under step-deterioration, Advances in Engineering Software, 40 (2009), 1074-1077. doi: 10.1016/j.advengsoft.2009.03.018.

[24]

H. Lei, G. Laporte and B. Guo, A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times, Top, 20 (2012), 99-118. doi: 10.1007/s11750-011-0188-6.

[25]

J. Y. T. Leung, C. T. Ng and T. C. E. Cheng, Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times, European Journal of Operational Research, 187 (2008), 1090-1099. doi: 10.1016/j.ejor.2006.03.067.

[26]

N. Mladenović and P. Hansen, Variable neighborhood search, Computers and Operations Research, 24 (1997), 1097-1100. doi: 10.1016/S0305-0548(97)00031-2.

[27]

N. Mladenović, D. Urošević, S. Hanafi and A. Ilić, A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem, European Journal of Operational Research, 220 (2012), 270-285. doi: 10.1016/j.ejor.2012.01.036.

[28]

B. Mor and G. Mosheiov, Batch scheduling with step-deteriorating processing times to minimize flowtime, Naval Research Logistics, 59 (2012), 587-600. doi: 10.1002/nav.21508.

[29]

G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Operations Research, 39 (1991), 979-991. doi: 10.1287/opre.39.6.979.

[30]

G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single- and multi-machine, Computers and Industrial Engineering, 28 (1995), 869-879. doi: 10.1016/0360-8352(95)00006-M.

[31]

G. Moslehi and A. Jafari, Minimizing the number of tardy jobs under piecewise-linear deterioration, Computers and Industrial Engineering, 59 (2010), 573-584. doi: 10.1016/j.cie.2010.06.017.

[32]

D. Oron, Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times, Computers and Operations Research, 35 (2008), 2071-2078. doi: 10.1016/j.cor.2006.10.010.

[33]

M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Fourth Edition, Springer, New York, 2012. doi: 10.1007/978-1-4614-2361-4.

[34]

P. S. Sundararaghavan and A. S. Kunnathur, Single machine scheduling with start time dependent processing times: Some solvable cases, European Journal of Operational Research, 78 (1994), 394-403. doi: 10.1016/0377-2217(94)90048-5.

[35]

D. Wang and J. B. Wang, Single-machine scheduling with simple linear deterioration to minimize earliness penalties, International Journal of Advanced Manufacturing Technology, 46 (2010), 285-290. doi: 10.1007/s00170-009-2086-8.

[36]

C. C. Wu, W. C. Lee and Y. R. Shiau, Minimizing the total weighted completion time on a single machine under linear deterioration, International Journal of Advanced Manufacturing Technology, 33 (2007), 1237-1243. doi: 10.1007/s00170-006-0565-8.

[37]

C. C.Wu, Y. R. Shiau, L. H. Lee and W. C. Lee, Scheduling deteriorating jobs to minimize the makespan on a single machine, International Journal of Advanced Manufacturing Technology, 44 (2009), 1230-1236. doi: 10.1007/s00170-008-1924-4.

show all references

References:
[1]

A. Bachman and A. Janiak, Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126 (2000), 557-566. doi: 10.1016/S0377-2217(99)00310-0.

[2]

S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498. doi: 10.1287/opre.38.3.495.

[3]

Y. J. Chang and M. J. Yao, New heuristics for solving the economic lot scheduling problem with reworks, Journal of Industrial and Management Optimization, 7 (2011), 229-251. doi: 10.3934/jimo.2011.7.229.

[4]

T. C. E. Cheng and Q. Ding, Single machine scheduling with step-deteriorating processing times, European Journal of Operational Research, 134 (2001), 623-630. doi: 10.1016/S0377-2217(00)00284-8.

[5]

T. C. E. Cheng, Q. Ding, M. Y. Kovalyov, A. Bachman and A. Janiak, Scheduling jobs with piecewise linear decreasing processing times, Naval Research Logistics, 50 (2003), 531-554 . doi: 10.1002/nav.10073.

[6]

T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152 (2004), 1-13 . doi: 10.1016/S0377-2217(02)00909-8.

[7]

W. Cheng, P. Guo, Z. Zhang, M. Zeng and J. Liang, Variable neighborhood search for parallel machines scheduling problem with step deteriorating jobs, Mathematical Problems in Engineering, (2012), 1-20. doi: 10.1155/2012/928312.

[8]

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.

[9]

J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14 (1988), 387-393 . doi: 10.1016/0360-8352(88)90041-1.

[10]

P. Hansen, N. Mladenović and D. Perez-Britos, Variable neighborhood decomposition search, Journal of Heuristics, 7 (2001), 335-350. doi: 10.1023/A:1011336210885.

[11]

P. Hansen, N. Mladenović and J. A. Moreno Pérez, Variable neighbourhood search: Methods and applications, Annals of Operations Research, 175 (2010), 367-407. doi: 10.1007/s10479-009-0657-6.

[12]

C. C. He, C. C. Wu and W. C. Lee, Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs, Journal of the Operational Research Society, 60 (2009), 1759-1766. doi: 10.1057/jors.2008.123.

[13]

A. Ilić, D. Urošević, J. Brimberg and N. Mladenović, A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem, European Journal of Operational Research, 206 (2010), 289-300. doi: 10.1016/j.ejor.2010.02.022.

[14]

A. Jafari and G. Moslehi, Scheduling linear deteriorating jobs to minimize the number of tardy jobs, Journal of Global Optimization, 54 (2012), 389-404. doi: 10.1007/s10898-011-9767-1.

[15]

A. A. K. Jeng and B. M. T. Lin, Makespan minimization in single-machine scheduling with step-deterioration of processing times, Journal of the Operational Research Society, 55 (2004), 247-256. doi: 10.1057/palgrave.jors.2601693.

[16]

A. A. K. Jeng and B. M. T. Lin, Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs, Computers and Operations Research, 32 (2005), 521-536. doi: 10.1016/j.cor.2003.08.001.

[17]

M. Ji and T. C. E. Cheng, An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan, Information Processing Letters, 102 (2007), 41-47. doi: 10.1016/j.ipl.2006.11.014.

[18]

M. Ji and T. C. E. Cheng, Parallel-machine scheduling of simple linear deteriorating jobs, Theoretical Computer Science, 410 (2009), 3761-3768. doi: 10.1016/j.tcs.2009.04.018.

[19]

G. Kirlik and C. Oguz, A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine, Computers and Operations Research, 39 (2012), 1506-1520. doi: 10.1016/j.cor.2011.08.022.

[20]

C. Koulamas, The single-machine total tardiness scheduling problem: Review and extensions, European Journal of Operational Research, 202 (2010), 1-7. doi: 10.1016/j.ejor.2009.04.007.

[21]

W. Kubiak and S. Van de Velde, Scheduling deteriorating jobs to minimize makespan, Naval Research Logistics, 45 (1998), 511-523. doi: 10.1002/(SICI)1520-6750(199808)45:5<511::AID-NAV5>3.0.CO;2-6.

[22]

A. S. Kunnathur and S. K. Gupta, Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European Journal of Operational Research, 47 (1990), 56-64. doi: 10.1016/0377-2217(90)90089-T.

[23]

J. Layegh, F. Jolai and M. S. Amalnik, A memetic algorithm for minimizing the total weighted completion time on a single machine under step-deterioration, Advances in Engineering Software, 40 (2009), 1074-1077. doi: 10.1016/j.advengsoft.2009.03.018.

[24]

H. Lei, G. Laporte and B. Guo, A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times, Top, 20 (2012), 99-118. doi: 10.1007/s11750-011-0188-6.

[25]

J. Y. T. Leung, C. T. Ng and T. C. E. Cheng, Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times, European Journal of Operational Research, 187 (2008), 1090-1099. doi: 10.1016/j.ejor.2006.03.067.

[26]

N. Mladenović and P. Hansen, Variable neighborhood search, Computers and Operations Research, 24 (1997), 1097-1100. doi: 10.1016/S0305-0548(97)00031-2.

[27]

N. Mladenović, D. Urošević, S. Hanafi and A. Ilić, A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem, European Journal of Operational Research, 220 (2012), 270-285. doi: 10.1016/j.ejor.2012.01.036.

[28]

B. Mor and G. Mosheiov, Batch scheduling with step-deteriorating processing times to minimize flowtime, Naval Research Logistics, 59 (2012), 587-600. doi: 10.1002/nav.21508.

[29]

G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Operations Research, 39 (1991), 979-991. doi: 10.1287/opre.39.6.979.

[30]

G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single- and multi-machine, Computers and Industrial Engineering, 28 (1995), 869-879. doi: 10.1016/0360-8352(95)00006-M.

[31]

G. Moslehi and A. Jafari, Minimizing the number of tardy jobs under piecewise-linear deterioration, Computers and Industrial Engineering, 59 (2010), 573-584. doi: 10.1016/j.cie.2010.06.017.

[32]

D. Oron, Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times, Computers and Operations Research, 35 (2008), 2071-2078. doi: 10.1016/j.cor.2006.10.010.

[33]

M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Fourth Edition, Springer, New York, 2012. doi: 10.1007/978-1-4614-2361-4.

[34]

P. S. Sundararaghavan and A. S. Kunnathur, Single machine scheduling with start time dependent processing times: Some solvable cases, European Journal of Operational Research, 78 (1994), 394-403. doi: 10.1016/0377-2217(94)90048-5.

[35]

D. Wang and J. B. Wang, Single-machine scheduling with simple linear deterioration to minimize earliness penalties, International Journal of Advanced Manufacturing Technology, 46 (2010), 285-290. doi: 10.1007/s00170-009-2086-8.

[36]

C. C. Wu, W. C. Lee and Y. R. Shiau, Minimizing the total weighted completion time on a single machine under linear deterioration, International Journal of Advanced Manufacturing Technology, 33 (2007), 1237-1243. doi: 10.1007/s00170-006-0565-8.

[37]

C. C.Wu, Y. R. Shiau, L. H. Lee and W. C. Lee, Scheduling deteriorating jobs to minimize the makespan on a single machine, International Journal of Advanced Manufacturing Technology, 44 (2009), 1230-1236. doi: 10.1007/s00170-008-1924-4.

[1]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial and Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[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 and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[3]

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 and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[4]

Shuen Guo, Zhichao Geng, Jinjiang Yuan. Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works. Journal of Industrial and Management Optimization, 2023, 19 (1) : 456-471. doi: 10.3934/jimo.2021192

[5]

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

[6]

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

[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 and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[8]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1329-1347. doi: 10.3934/jimo.2019005

[9]

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 and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[10]

Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial and Management Optimization, 2022, 18 (6) : 3953-3973. doi: 10.3934/jimo.2021142

[11]

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

[12]

Shengyang Jia, Lei Deng, Quanwu Zhao, Yunkai Chen. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021225

[13]

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 and Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591

[14]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial and Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613

[15]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[16]

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

[17]

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

[18]

Enjie Wu, Jin Zhu. Integrated proactive-reactive approach and a hybrid adaptive large neighborhood search algorithm for berth and quay crane scheduling under uncertain combination. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022188

[19]

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 and Management Optimization, 2020, 16 (3) : 1273-1296. doi: 10.3934/jimo.2019002

[20]

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 and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (167)
  • HTML views (0)
  • Cited by (12)

Other articles
by authors

[Back to Top]