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

Peng Guo; Wenming Cheng; Yi Wang

doi:10.3934/jimo.2014.10.1071

Previous Article
A barrier function method for generalized Nash equilibrium problems
JIMO Home
This Issue
Next Article
Linear programming technique for solving interval-valued constraint matrix games

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

Peng Guo ^1, , Wenming Cheng ^1, and Yi Wang ^2,

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

Abstract
Related Papers

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.

Keywords: heuristic, general variable neighborhood search, Single-machine scheduling, total tardiness., step-deterioration.

Mathematics Subject Classification: Primary: 90B35, 90C59; Secondary: 90C1.

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 & 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. doi: 10.1016/S0377-2217(99)00310-0. Google Scholar
[2]	S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor,, Operations Research, 38 (1990), 495. doi: 10.1287/opre.38.3.495. Google Scholar
[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. doi: 10.3934/jimo.2011.7.229. Google Scholar
[4]	T. C. E. Cheng and Q. Ding, Single machine scheduling with step-deteriorating processing times,, European Journal of Operational Research, 134 (2001), 623. doi: 10.1016/S0377-2217(00)00284-8. Google Scholar
[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. doi: 10.1002/nav.10073. Google Scholar
[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. doi: 10.1016/S0377-2217(02)00909-8. Google Scholar
[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. doi: 10.1155/2012/928312. Google Scholar
[8]	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
[9]	J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times,, Computers and Industrial Engineering, 14 (1988), 387. doi: 10.1016/0360-8352(88)90041-1. Google Scholar
[10]	P. Hansen, N. Mladenović and D. Perez-Britos, Variable neighborhood decomposition search,, Journal of Heuristics, 7 (2001), 335. doi: 10.1023/A:1011336210885. Google Scholar
[11]	P. Hansen, N. Mladenović and J. A. Moreno Pérez, Variable neighbourhood search: Methods and applications,, Annals of Operations Research, 175 (2010), 367. doi: 10.1007/s10479-009-0657-6. Google Scholar
[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. doi: 10.1057/jors.2008.123. Google Scholar
[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. doi: 10.1016/j.ejor.2010.02.022. Google Scholar
[14]	A. Jafari and G. Moslehi, Scheduling linear deteriorating jobs to minimize the number of tardy jobs,, Journal of Global Optimization, 54 (2012), 389. doi: 10.1007/s10898-011-9767-1. Google Scholar
[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. doi: 10.1057/palgrave.jors.2601693. Google Scholar
[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. doi: 10.1016/j.cor.2003.08.001. Google Scholar
[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. doi: 10.1016/j.ipl.2006.11.014. Google Scholar
[18]	M. Ji and T. C. E. Cheng, Parallel-machine scheduling of simple linear deteriorating jobs,, Theoretical Computer Science, 410 (2009), 3761. doi: 10.1016/j.tcs.2009.04.018. Google Scholar
[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. doi: 10.1016/j.cor.2011.08.022. Google Scholar
[20]	C. Koulamas, The single-machine total tardiness scheduling problem: Review and extensions,, European Journal of Operational Research, 202 (2010), 1. doi: 10.1016/j.ejor.2009.04.007. Google Scholar
[21]	W. Kubiak and S. Van de Velde, Scheduling deteriorating jobs to minimize makespan,, Naval Research Logistics, 45 (1998), 511. doi: 10.1002/(SICI)1520-6750(199808)45:5<511::AID-NAV5>3.0.CO;2-6. Google Scholar
[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. doi: 10.1016/0377-2217(90)90089-T. Google Scholar
[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. doi: 10.1016/j.advengsoft.2009.03.018. Google Scholar
[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. doi: 10.1007/s11750-011-0188-6. Google Scholar
[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. doi: 10.1016/j.ejor.2006.03.067. Google Scholar
[26]	N. Mladenović and P. Hansen, Variable neighborhood search,, Computers and Operations Research, 24 (1997), 1097. doi: 10.1016/S0305-0548(97)00031-2. Google Scholar
[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. doi: 10.1016/j.ejor.2012.01.036. Google Scholar
[28]	B. Mor and G. Mosheiov, Batch scheduling with step-deteriorating processing times to minimize flowtime,, Naval Research Logistics, 59 (2012), 587. doi: 10.1002/nav.21508. Google Scholar
[29]	G. Mosheiov, V-shaped policies for scheduling deteriorating jobs,, Operations Research, 39 (1991), 979. doi: 10.1287/opre.39.6.979. Google Scholar
[30]	G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single- and multi-machine,, Computers and Industrial Engineering, 28 (1995), 869. doi: 10.1016/0360-8352(95)00006-M. Google Scholar
[31]	G. Moslehi and A. Jafari, Minimizing the number of tardy jobs under piecewise-linear deterioration,, Computers and Industrial Engineering, 59 (2010), 573. doi: 10.1016/j.cie.2010.06.017. Google Scholar
[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. doi: 10.1016/j.cor.2006.10.010. Google Scholar
[33]	M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems,, Fourth Edition, (2012). doi: 10.1007/978-1-4614-2361-4. Google Scholar
[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. doi: 10.1016/0377-2217(94)90048-5. Google Scholar
[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. doi: 10.1007/s00170-009-2086-8. Google Scholar
[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. doi: 10.1007/s00170-006-0565-8. Google Scholar
[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. doi: 10.1007/s00170-008-1924-4. Google Scholar

show all references

References:

[1]	A. Bachman and A. Janiak, Minimizing maximum lateness under linear deterioration,, European Journal of Operational Research, 126 (2000), 557. doi: 10.1016/S0377-2217(99)00310-0. Google Scholar
[2]	S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor,, Operations Research, 38 (1990), 495. doi: 10.1287/opre.38.3.495. Google Scholar
[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. doi: 10.3934/jimo.2011.7.229. Google Scholar
[4]	T. C. E. Cheng and Q. Ding, Single machine scheduling with step-deteriorating processing times,, European Journal of Operational Research, 134 (2001), 623. doi: 10.1016/S0377-2217(00)00284-8. Google Scholar
[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. doi: 10.1002/nav.10073. Google Scholar
[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. doi: 10.1016/S0377-2217(02)00909-8. Google Scholar
[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. doi: 10.1155/2012/928312. Google Scholar
[8]	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
[9]	J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times,, Computers and Industrial Engineering, 14 (1988), 387. doi: 10.1016/0360-8352(88)90041-1. Google Scholar
[10]	P. Hansen, N. Mladenović and D. Perez-Britos, Variable neighborhood decomposition search,, Journal of Heuristics, 7 (2001), 335. doi: 10.1023/A:1011336210885. Google Scholar
[11]	P. Hansen, N. Mladenović and J. A. Moreno Pérez, Variable neighbourhood search: Methods and applications,, Annals of Operations Research, 175 (2010), 367. doi: 10.1007/s10479-009-0657-6. Google Scholar
[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. doi: 10.1057/jors.2008.123. Google Scholar
[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. doi: 10.1016/j.ejor.2010.02.022. Google Scholar
[14]	A. Jafari and G. Moslehi, Scheduling linear deteriorating jobs to minimize the number of tardy jobs,, Journal of Global Optimization, 54 (2012), 389. doi: 10.1007/s10898-011-9767-1. Google Scholar
[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. doi: 10.1057/palgrave.jors.2601693. Google Scholar
[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. doi: 10.1016/j.cor.2003.08.001. Google Scholar
[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. doi: 10.1016/j.ipl.2006.11.014. Google Scholar
[18]	M. Ji and T. C. E. Cheng, Parallel-machine scheduling of simple linear deteriorating jobs,, Theoretical Computer Science, 410 (2009), 3761. doi: 10.1016/j.tcs.2009.04.018. Google Scholar
[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. doi: 10.1016/j.cor.2011.08.022. Google Scholar
[20]	C. Koulamas, The single-machine total tardiness scheduling problem: Review and extensions,, European Journal of Operational Research, 202 (2010), 1. doi: 10.1016/j.ejor.2009.04.007. Google Scholar
[21]	W. Kubiak and S. Van de Velde, Scheduling deteriorating jobs to minimize makespan,, Naval Research Logistics, 45 (1998), 511. doi: 10.1002/(SICI)1520-6750(199808)45:5<511::AID-NAV5>3.0.CO;2-6. Google Scholar
[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. doi: 10.1016/0377-2217(90)90089-T. Google Scholar
[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. doi: 10.1016/j.advengsoft.2009.03.018. Google Scholar
[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. doi: 10.1007/s11750-011-0188-6. Google Scholar
[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. doi: 10.1016/j.ejor.2006.03.067. Google Scholar
[26]	N. Mladenović and P. Hansen, Variable neighborhood search,, Computers and Operations Research, 24 (1997), 1097. doi: 10.1016/S0305-0548(97)00031-2. Google Scholar
[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. doi: 10.1016/j.ejor.2012.01.036. Google Scholar
[28]	B. Mor and G. Mosheiov, Batch scheduling with step-deteriorating processing times to minimize flowtime,, Naval Research Logistics, 59 (2012), 587. doi: 10.1002/nav.21508. Google Scholar
[29]	G. Mosheiov, V-shaped policies for scheduling deteriorating jobs,, Operations Research, 39 (1991), 979. doi: 10.1287/opre.39.6.979. Google Scholar
[30]	G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single- and multi-machine,, Computers and Industrial Engineering, 28 (1995), 869. doi: 10.1016/0360-8352(95)00006-M. Google Scholar
[31]	G. Moslehi and A. Jafari, Minimizing the number of tardy jobs under piecewise-linear deterioration,, Computers and Industrial Engineering, 59 (2010), 573. doi: 10.1016/j.cie.2010.06.017. Google Scholar
[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. doi: 10.1016/j.cor.2006.10.010. Google Scholar
[33]	M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems,, Fourth Edition, (2012). doi: 10.1007/978-1-4614-2361-4. Google Scholar
[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. doi: 10.1016/0377-2217(94)90048-5. Google Scholar
[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. doi: 10.1007/s00170-009-2086-8. Google Scholar
[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. doi: 10.1007/s00170-006-0565-8. Google Scholar
[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. doi: 10.1007/s00170-008-1924-4. Google Scholar

[1]	Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024
[2]	Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[3]	Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137
[4]	Marian Gidea, Rafael de la Llave, Tere M. Seara. A general mechanism of instability in Hamiltonian systems: Skipping along a normally hyperbolic invariant manifold. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6795-6813. doi: 10.3934/dcds.2020166
[5]	Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[6]	A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044

2019 Impact Factor: 1.366

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors