\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90B35; Secondary: 68M20.

    Citation:

    \begin{equation} \\ \end{equation}
  • [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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    [20]

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

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

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

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

    [24]

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

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

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

    [27]

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

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

    [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).

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

    [31]

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

    [32]

    R. Zhang and C. Wu, A hybrid immune simulated annealing algorithm for the job shop scheduling problem, Applied Soft Computing, 10 (2010b), 79-89.

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

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

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

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(385) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return