• Previous Article
    Resilience analysis for project scheduling with renewable resource constraint and uncertain activity durations
  • JIMO Home
  • This Issue
  • Next Article
    Analysis and optimization of a gated polling based spectrum allocation mechanism in cognitive radio networks
April  2016, 12(2): 703-717. doi: 10.3934/jimo.2016.12.703

A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem

1. 

Department of Industrial Engineering and Systems Management, Feng Chia University, P.O. Box 25-097,Taichung, 40724, Taiwan, ROC, Taiwan

2. 

Planning and Operations Management Group, Singapore Institute of Manufacturing Technology, A-star, 7 Nanyang Avenue, 638075, Singapore

Received  October 2014 Revised  April 2015 Published  June 2015

This research presents a tabu search algorithm with a restart (TSA-R) approach to minimize total weighted tardiness (TWT) for the job shop scheduling problem. Jobs have non-identical due dates. The problem belongs to the class of NP-hard problems. The TSA-R approach uses dispatching rules to obtain an initial solution and searches for new solutions in a neighborhood based on the critical paths of jobs and blocks of operations. The TSA-R applies a new diversification scheme to exploit the initial solutions and its neighborhood structures so as to overcome entrapment issues and to enhance solutions. A computational result based on standard benchmark instances from the literature is presented to show the effectiveness of the proposed tabu search algorithm.
Citation: 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
References:
[1]

E. J. Anderson and J. C. Nyirenda, Two new rules to minimize tardiness in a job shop,, International Journal of Production Research, 28 (1990), 2277. doi: 10.1080/00207549008942866. Google Scholar

[2]

V. A. Armentano and C. R. Scrich, Tabu search for minimizing total tardiness in a job shop,, International Journal of Production Research, 63 (2000), 131. doi: 10.1016/S0925-5273(99)00014-6. Google Scholar

[3]

M. Asano and H. Ohta, A heuristic for job shop scheduling to minimize total weighted tardiness,, Computers and Industrial Engineering, 42 (2002), 137. doi: 10.1016/S0360-8352(02)00019-0. Google Scholar

[4]

K. R. Baker, Sequencing rules and due date assignments in a job shop,, Management Science, 30 (1984), 1093. doi: 10.1287/mnsc.30.9.1093. Google Scholar

[5]

K. R. Baker and J. J. Kanet, Job shop scheduling with modified due dates,, Journal of Operations Management, 4 (1983), 11. doi: 10.1016/0272-6963(83)90022-0. Google Scholar

[6]

E. Balas, Machine sequencing via disjunctive graph: an implicit enumeration algorithm,, Operations Research, 17 (1969), 941. doi: 10.1287/opre.17.6.941. Google Scholar

[7]

K. M. J. Bontridder, Minimizing total weighted tardiness in a generalized job shop,, Journal of Scheduling, 8 (2005), 479. doi: 10.1007/s10951-005-4779-7. Google Scholar

[8]

K. Bulbul, A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem,, Computers and Operations Research, 38 (2011), 967. doi: 10.1016/j.cor.2010.09.015. Google Scholar

[9]

G. Calleja and R. Pastor, A dispatching algorithm for flexible job-shop scheduling with transfer batches: an industrial application,, Production Planning and Control, 25 (2014), 93. doi: 10.1080/09537287.2013.782846. Google Scholar

[10]

I. Essafi, Y. Mati and S. Dauzere-Peres, A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem,, Computers and Operations Research, 35 (2008), 2599. doi: 10.1016/j.cor.2006.12.019. Google Scholar

[11]

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

[12]

Z. He, T. Yang and D. E. Deal, A multiple-pass heuristic rule for job shop scheduling with due dates,, International Journal of Production Research, 31 (1993), 2677. doi: 10.1080/00207549308956890. Google Scholar

[13]

A. S. Jain, B. Rangaswamy and S. Meeran, New and "stronger" job-shop neighborhoods: a focus on the method of Nowicki and Smutnicki (1996),, Journal of Heuristics, 6 (2000), 457. Google Scholar

[14]

J. J. Kanet and J. C. Hayya, Priority dispatching with operation due dates in a job shop,, Journal of Operations Management, 2 (1982), 167. Google Scholar

[15]

S. Kreipl, A large step random walk for minimizing total weighted tardiness in a job shop,, Journal of Scheduling, 3 (2000), 125. doi: 10.1002/(SICI)1099-1425(200005/06)3:3<125::AID-JOS40>3.0.CO;2-C. Google Scholar

[16]

E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, Sequencing and scheduling: Algorithms and complexity,, in Handbooks in Operations Research and Management Science (eds. S. C. Graves, 4 (1993), 445. Google Scholar

[17]

H. L. Lu, G. Q. Huang and H. D. Yang, Integrating order review/release and dispatching rules for assembly job shop scheduling using a simulation approach,, International Journal of Production Research, 49 (2011), 647. Google Scholar

[18]

Y. Mati, S. Dauzere-Peres and C. Lahlou, A general approach for optimizing regular criteria in the job-shop scheduling problem,, European Journal of Operational Research, 212 (2011), 33. doi: 10.1016/j.ejor.2011.01.046. Google Scholar

[19]

D. C. Mattfeld and C. Bierwirth, An efficient genetic algorithm for job shop scheduling with tardiness objectives,, European Journal of Operational Research, 155 (2004), 616. doi: 10.1016/S0377-2217(03)00016-X. Google Scholar

[20]

E. Nowicki and C. Smutnicki, A fast taboo search algorithm for the job shop problem,, Management Science, 42 (1996), 797. Google Scholar

[21]

E. Nowicki and C. Smutnicki, An advanced tabu search algorithm for the job shop problem,, Journal of Scheduling, 8 (2005), 145. doi: 10.1007/s10951-005-6364-5. Google Scholar

[22]

S. Nguyen, M. Zhang, J. Mark and KC. Tan, A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem,, IEEE Transactions on Evolutionary Computation, 17 (2013), 621. Google Scholar

[23]

M. Pinedo and M. Singer, A shifting bottleneck heuristic for minimizing the total weighted tardiness in job shop,, Naval Research Logistics, 46 (1999), 1. doi: 10.1002/(SICI)1520-6750(199902)46:1<1::AID-NAV1>3.3.CO;2-R. Google Scholar

[24]

N. Raman and F. B. Talbot, The job shop tardiness problem: A decomposition approach,, European Journal of Operational Research, 69 (1993), 187. Google Scholar

[25]

M. Singer and M. Pinedo, A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops,, IIE Transactions, 30 (1998), 109. Google Scholar

[26]

P. J. M. Van Laarhoven, E. H. L. Aarts and J. K. Lenstra, Job shop scheduling by simulated annealing,, Operations Research, 40 (1992), 113. doi: 10.1287/opre.40.1.113. Google Scholar

[27]

A. P. J. Vepsalainen and T. E. Morton, Priority rules for job shops with weighted tardiness costs,, Management Science, 33 (1987), 1035. Google Scholar

[28]

T. Yang, Z. He and K. K. Cho, An effective heuristic method for generalized job shop scheduling with due dates,, Computers and Industrial Engineering, 26 (1994), 647. Google Scholar

[29]

C. Zhang, X. Shao, Y. Rao and H. Qiu, Some new results on tabu search algorithm applied to the job-shop scheduling problem, Tabu Search, Wassim Jaziri (Ed.), InTech, Available from: http://www.intechopen.com/articles/show/title/some_new_results_on_tabu_search_algorithm_applied_to_the_job-shop_scheduling_problem, (2008)., (2008). Google Scholar

[30]

R. Zhang, A genetic local search algorithm based on insertion neighborhood for the job shop scheduling problem,, Advances in Information Sciences and Services, 3 (2011), 117. Google Scholar

[31]

R. Zhang and C. Wu, A divide-and-conquer strategy with particle swarm optimization for the job shop scheduling problem,, Engineering Optimization, 42 (): 641. doi: 10.1080/03052150903369845. Google Scholar

[32]

R. Zhang and C. Wu, A hybrid immune simulated annealing algorithm for the job shop scheduling problem,, Applied Soft Computing, 10 (): 79. Google Scholar

[33]

R. Zhang and C. Wu, A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective,, Computers and Operations Research, 38 (2011), 854. doi: 10.1016/j.cor.2010.09.014. Google Scholar

[34]

R. Zhang, S. Song and C. Wu, A hybrid artificial bee colony algorithm for the job shop scheduling problem,, International Journal of Production Economics, 141 (2013), 167. Google Scholar

[35]

H. Zhou, W. Cheung and L. C. Leung, Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm,, European Journal of Operational Research, 194 (2009), 637. Google Scholar

show all references

References:
[1]

E. J. Anderson and J. C. Nyirenda, Two new rules to minimize tardiness in a job shop,, International Journal of Production Research, 28 (1990), 2277. doi: 10.1080/00207549008942866. Google Scholar

[2]

V. A. Armentano and C. R. Scrich, Tabu search for minimizing total tardiness in a job shop,, International Journal of Production Research, 63 (2000), 131. doi: 10.1016/S0925-5273(99)00014-6. Google Scholar

[3]

M. Asano and H. Ohta, A heuristic for job shop scheduling to minimize total weighted tardiness,, Computers and Industrial Engineering, 42 (2002), 137. doi: 10.1016/S0360-8352(02)00019-0. Google Scholar

[4]

K. R. Baker, Sequencing rules and due date assignments in a job shop,, Management Science, 30 (1984), 1093. doi: 10.1287/mnsc.30.9.1093. Google Scholar

[5]

K. R. Baker and J. J. Kanet, Job shop scheduling with modified due dates,, Journal of Operations Management, 4 (1983), 11. doi: 10.1016/0272-6963(83)90022-0. Google Scholar

[6]

E. Balas, Machine sequencing via disjunctive graph: an implicit enumeration algorithm,, Operations Research, 17 (1969), 941. doi: 10.1287/opre.17.6.941. Google Scholar

[7]

K. M. J. Bontridder, Minimizing total weighted tardiness in a generalized job shop,, Journal of Scheduling, 8 (2005), 479. doi: 10.1007/s10951-005-4779-7. Google Scholar

[8]

K. Bulbul, A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem,, Computers and Operations Research, 38 (2011), 967. doi: 10.1016/j.cor.2010.09.015. Google Scholar

[9]

G. Calleja and R. Pastor, A dispatching algorithm for flexible job-shop scheduling with transfer batches: an industrial application,, Production Planning and Control, 25 (2014), 93. doi: 10.1080/09537287.2013.782846. Google Scholar

[10]

I. Essafi, Y. Mati and S. Dauzere-Peres, A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem,, Computers and Operations Research, 35 (2008), 2599. doi: 10.1016/j.cor.2006.12.019. Google Scholar

[11]

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

[12]

Z. He, T. Yang and D. E. Deal, A multiple-pass heuristic rule for job shop scheduling with due dates,, International Journal of Production Research, 31 (1993), 2677. doi: 10.1080/00207549308956890. Google Scholar

[13]

A. S. Jain, B. Rangaswamy and S. Meeran, New and "stronger" job-shop neighborhoods: a focus on the method of Nowicki and Smutnicki (1996),, Journal of Heuristics, 6 (2000), 457. Google Scholar

[14]

J. J. Kanet and J. C. Hayya, Priority dispatching with operation due dates in a job shop,, Journal of Operations Management, 2 (1982), 167. Google Scholar

[15]

S. Kreipl, A large step random walk for minimizing total weighted tardiness in a job shop,, Journal of Scheduling, 3 (2000), 125. doi: 10.1002/(SICI)1099-1425(200005/06)3:3<125::AID-JOS40>3.0.CO;2-C. Google Scholar

[16]

E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, Sequencing and scheduling: Algorithms and complexity,, in Handbooks in Operations Research and Management Science (eds. S. C. Graves, 4 (1993), 445. Google Scholar

[17]

H. L. Lu, G. Q. Huang and H. D. Yang, Integrating order review/release and dispatching rules for assembly job shop scheduling using a simulation approach,, International Journal of Production Research, 49 (2011), 647. Google Scholar

[18]

Y. Mati, S. Dauzere-Peres and C. Lahlou, A general approach for optimizing regular criteria in the job-shop scheduling problem,, European Journal of Operational Research, 212 (2011), 33. doi: 10.1016/j.ejor.2011.01.046. Google Scholar

[19]

D. C. Mattfeld and C. Bierwirth, An efficient genetic algorithm for job shop scheduling with tardiness objectives,, European Journal of Operational Research, 155 (2004), 616. doi: 10.1016/S0377-2217(03)00016-X. Google Scholar

[20]

E. Nowicki and C. Smutnicki, A fast taboo search algorithm for the job shop problem,, Management Science, 42 (1996), 797. Google Scholar

[21]

E. Nowicki and C. Smutnicki, An advanced tabu search algorithm for the job shop problem,, Journal of Scheduling, 8 (2005), 145. doi: 10.1007/s10951-005-6364-5. Google Scholar

[22]

S. Nguyen, M. Zhang, J. Mark and KC. Tan, A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem,, IEEE Transactions on Evolutionary Computation, 17 (2013), 621. Google Scholar

[23]

M. Pinedo and M. Singer, A shifting bottleneck heuristic for minimizing the total weighted tardiness in job shop,, Naval Research Logistics, 46 (1999), 1. doi: 10.1002/(SICI)1520-6750(199902)46:1<1::AID-NAV1>3.3.CO;2-R. Google Scholar

[24]

N. Raman and F. B. Talbot, The job shop tardiness problem: A decomposition approach,, European Journal of Operational Research, 69 (1993), 187. Google Scholar

[25]

M. Singer and M. Pinedo, A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops,, IIE Transactions, 30 (1998), 109. Google Scholar

[26]

P. J. M. Van Laarhoven, E. H. L. Aarts and J. K. Lenstra, Job shop scheduling by simulated annealing,, Operations Research, 40 (1992), 113. doi: 10.1287/opre.40.1.113. Google Scholar

[27]

A. P. J. Vepsalainen and T. E. Morton, Priority rules for job shops with weighted tardiness costs,, Management Science, 33 (1987), 1035. Google Scholar

[28]

T. Yang, Z. He and K. K. Cho, An effective heuristic method for generalized job shop scheduling with due dates,, Computers and Industrial Engineering, 26 (1994), 647. Google Scholar

[29]

C. Zhang, X. Shao, Y. Rao and H. Qiu, Some new results on tabu search algorithm applied to the job-shop scheduling problem, Tabu Search, Wassim Jaziri (Ed.), InTech, Available from: http://www.intechopen.com/articles/show/title/some_new_results_on_tabu_search_algorithm_applied_to_the_job-shop_scheduling_problem, (2008)., (2008). Google Scholar

[30]

R. Zhang, A genetic local search algorithm based on insertion neighborhood for the job shop scheduling problem,, Advances in Information Sciences and Services, 3 (2011), 117. Google Scholar

[31]

R. Zhang and C. Wu, A divide-and-conquer strategy with particle swarm optimization for the job shop scheduling problem,, Engineering Optimization, 42 (): 641. doi: 10.1080/03052150903369845. Google Scholar

[32]

R. Zhang and C. Wu, A hybrid immune simulated annealing algorithm for the job shop scheduling problem,, Applied Soft Computing, 10 (): 79. Google Scholar

[33]

R. Zhang and C. Wu, A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective,, Computers and Operations Research, 38 (2011), 854. doi: 10.1016/j.cor.2010.09.014. Google Scholar

[34]

R. Zhang, S. Song and C. Wu, A hybrid artificial bee colony algorithm for the job shop scheduling problem,, International Journal of Production Economics, 141 (2013), 167. Google Scholar

[35]

H. Zhou, W. Cheung and L. C. Leung, Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm,, European Journal of Operational Research, 194 (2009), 637. Google Scholar

[1]

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 & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[2]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030

[3]

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

[4]

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

[5]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[6]

Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2019088

[7]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[8]

Jinjiang Yuan, Weiping Shang. A PTAS for the p-batch scheduling with pj = p to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2005, 1 (3) : 353-358. doi: 10.3934/jimo.2005.1.353

[9]

Chi Zhou, Wansheng Tang, Ruiqing Zhao. Optimal consumption with reference-dependent preferences in on-the-job search and savings. Journal of Industrial & Management Optimization, 2017, 13 (1) : 505-529. doi: 10.3934/jimo.2016029

[10]

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

[11]

Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial & Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253

[12]

M. Ramasubramaniam, M. Mathirajan. A solution framework for scheduling a BPM with non-identical job dimensions. Journal of Industrial & Management Optimization, 2007, 3 (3) : 445-456. doi: 10.3934/jimo.2007.3.445

[13]

Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191

[14]

Cheng-Ta Yeh, Yi-Kuei Lin. Component allocation cost minimization for a multistate computer network subject to a reliability threshold using tabu search. Journal of Industrial & Management Optimization, 2016, 12 (1) : 141-167. doi: 10.3934/jimo.2016.12.141

[15]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469

[16]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193

[17]

Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060

[18]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95

[19]

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

[20]

Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]