American Institute of Mathematical Sciences

Advanced
  • 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

Y. K. Lin 1, and  C. S. Chong 2,

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.
Keywords: Scheduling, total weighted tardiness., job shop, tabu search.
Mathematics Subject Classification: Primary: 90B35; Secondary: 68M2.
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-2292. 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-140. 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-147. 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-1104. 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-22. 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-957. 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-496. 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-983. 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-109. 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-2616. 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-326. 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-2692. 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-480. 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-175. 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-138. 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, A. H. G. Rinnooy Kan and P. H. Zipkin), 4 (1993), 445-522. 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-669. 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-42. 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-630. 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-813. Google Scholar

[21]

E. Nowicki and C. Smutnicki, An advanced tabu search algorithm for the job shop problem, Journal of Scheduling, 8 (2005), 145-159. 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-639. 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-17. 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-199. 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-118. 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-125. 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-1047. 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-660. 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). 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-125. 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-867. 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-178. 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-649. 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-2292. 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-140. 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-147. 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-1104. 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-22. 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-957. 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-496. 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-983. 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-109. 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-2616. 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-326. 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-2692. 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-480. 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-175. 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-138. 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, A. H. G. Rinnooy Kan and P. H. Zipkin), 4 (1993), 445-522. 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-669. 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-42. 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-630. 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-813. Google Scholar

[21]

E. Nowicki and C. Smutnicki, An advanced tabu search algorithm for the job shop problem, Journal of Scheduling, 8 (2005), 145-159. 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-639. 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-17. 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-199. 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-118. 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-125. 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-1047. 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-660. 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). 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-125. 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-867. 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-178. 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-649. 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, 2020, 16 (4) : 1801-1834. 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]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[7]

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, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088
[8]

Yukang He, Zhengwen He, Nengmin Wang. Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2451-2474. doi: 10.3934/jimo.2020077
[9]

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
[10]

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
[11]

Shuen Guo, Zhichao Geng, Jinjiang Yuan. Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021192
[12]

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
[13]

Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3223-3246. doi: 10.3934/jimo.2020115
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy