More Web Proxy on the site http://driver.im/

research-article

A hybrid evolutionary approach for the single-machine total weighted tardiness problem

Authors:

Liping XuAuthors Info & Claims

Computers and Industrial Engineering, Volume 108, Issue C

Pages 70 - 80

https://doi.org/10.1016/j.cie.2017.04.006

Published: 01 June 2017 Publication History

Abstract

HEA incorporates the dynasearch into the evolutionary framework.We improve the dynasearch with a fast neighbourhood search.We introduce a buffer technique in HEA to reduce computational time.The tradeoff between combination and perturbation is essential to HEA.HEA is the only metaheuristic to solve 1000-job instances in 3.97h in average. This paper presents a hybrid evolutionary algorithm (HEA) for solving the single-machine total weighted tardiness problem, which incorporates several distinctive features such as a fast neighbourhood search and a buffer technique. HEA solves all the standard benchmark problem instances with 40, 50, and 100 jobs from the literature within 0.04s. For larger instances with 150, 200, 250, and 300 jobs, HEA obtains the optimal solutions for all of them within four minutes. To the best of our knowledge, HEA is the only metaheuristic algorithm that can obtain the optimal solutions for all the 25 instances with 1000 jobs within an average time of 3.97h, demonstrating the efficacy of HEA in terms of both solution quality and computational efficiency. Furthermore, some key features of HEA are analyzed to identify its critical success factors.

References

[1]

T. Abdul-Razaq, C.N. Potts, L.N. Van Wassenhove, A survey of algorithms for the single machine total weighted tardiness scheduling problem, Discrete Applied Mathematics, 26 (1990) 235-253.

Digital Library

[2]

D. Anghinolfi, M. Paolucci, A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem, International Journal of Operations Research, 5 (2008) 1-17.

[3]

S. Avci, M.S. Akturk, R.H. Storer, A problem space algorithm for single machine weighted tardiness problems, IIE Transactions, 35 (2003) 479-486.

[4]

U. Benlic, J.K. Hao, Breakout local search for maximum clique problems, Computers & Operations Research, 40 (2013) 192-206.

Digital Library

[5]

U. Benlic, J.K. Hao, Breakout local search for the vertex separator problem, in: Proceedings of the twenty-third international joint conference on artificial intelligence, AAAI Press, 2013, pp. 461-467.

Digital Library

[6]

. Bilge, M. Kurtulan, F. Kra, A tabu search algorithm for the single machine total weighted tardiness problem, European Journal of Operational Research, 176 (2007) 1423-1435.

[7]

W. Boejko, J. Grabowski, M. Wodecki, Block approach tabu search algorithm for single machine total weighted tardiness problem, Computers & Industrial Engineering, 50 (2006) 1-14.

Digital Library

[8]

T.C.E. Cheng, C.J. Hsu, D.L. Yang, Unrelated parallel-machine scheduling with deteriorating maintenance activities, Computers & Industrial Engineering, 60 (2011) 602-605.

Digital Library

[9]

T.C.E. Cheng, C. Ng, J. Yuan, Z. Liu, Single machine scheduling to minimize total weighted tardiness, European Journal of Operational Research, 165 (2005) 423-443.

[10]

R.K. Congram, C.N. Potts, S.L. van De Velde, An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem, INFORMS Journal on Computing, 14 (2002) 52-67.

[11]

H. Crauwels, C.N. Potts, L.N. Van Wassenhove, Local search heuristics for the single machine total weighted tardiness scheduling problem, INFORMS Journal on Computing, 10 (1998) 341-350.

Digital Library

[12]

M. den Besten, T. Sttzle, M. Dorigo, Ant colony optimization for the total weighted tardiness problem, in: Parallel Problem Solving from Nature PPSN VI, Springer, 2000, pp. 611-620.

Digital Library

[13]

J. Ding, Z. L, T.C.E. Cheng, L. Xu, Breakout dynasearch for the single-machine total weighted tardiness problem, Computers & Industrial Engineering, 98 (2016) 1-10.

Digital Library

[14]

H. Emmons, One-machine sequencing to minimize certain functions of job tardiness, Operations Research, 17 (1969) 701-715.

Digital Library

[15]

. Ergun, J.B. Orlin, Fast neighborhood search for the single machine total weighted tardiness problem, Operations Research Letters, 34 (2006) 41-45.

Digital Library

[16]

Ferrolho, A.M. Crisstomo, Single machine total weighted tardiness problem with genetic algorithms, in: IEEE/ACS international conference on computer systems and applications, 2007. AICCSA07, IEEE, 2007, pp. 1-8.

[17]

D.B. Fogel, An evolutionary approach to the traveling salesman problem, Biological Cybernetics, 60 (1988) 139-144.

Digital Library

[18]

L. Gao, G. Zhang, L. Zhang, X. Li, An efficient memetic algorithm for solving the job shop scheduling problem, Computers & Industrial Engineering, 60 (2011) 699-705.

Digital Library

[19]

Geiger, M. (2010a). New instances for the single machine total weighted tardiness problem. Research Report.

[20]

M.J. Geiger, On heuristic search for the single machine total weighted tardiness problemsome theoretical insights and their empirical verification, European Journal of Operational Research, 207 (2010) 1235-1243.

[21]

M. Gen, R. Cheng, John Wiley & Sons, 2000.

[22]

A. Grosso, F. Della Croce, R. Tadei, An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem, Operations Research Letters, 32 (2004) 68-72.

Digital Library

[23]

O. Holthaus, C. Rajendran, A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs, Journal of the Operational Research Society, 56 (2004) 947-953.

[24]

W.H. Huang, P.C. Chang, M.H. Lim, Z. Zhang, Memes co-evolution strategies for fast convergence in solving single machine scheduling problems, International Journal of Production Research, 50 (2012) 7357-7377.

[25]

T. Ibaraki, Enumerative approaches to combinatorial optimization-part III, Annals of Operations Research, 11 (1988) 345-602.

Digital Library

[26]

T. Ibaraki, Y. Nakamura, A dynamic programming method for single machine scheduling, European Journal of Operational Research, 76 (1994) 72-82.

[27]

M. Ji, K. Chen, J. Ge, T.C.E. Cheng, Group scheduling and job-dependent due window assignment based on a common flow allowance, Computers & Industrial Engineering, 68 (2014) 35-41.

Digital Library

[28]

A.R. Kan, B. Lageweg, J. Lenstra, Minimizing total costs in one-machine scheduling, Operations Research, 23 (1975) 908-927.

Digital Library

[29]

A.B. Keha, K. Khowala, J.W. Fowler, Mixed integer programming formulations for single machine scheduling problems, Computers & Industrial Engineering, 56 (2009) 357-367.

Digital Library

[30]

T. Kellegz, B. Toklu, J. Wilson, Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem, Applied Mathematics and Computation, 199 (2008) 590-598.

[31]

K. Khowala, A. Keha, J. Fowler, A comparison of different formulations for the non-preemptive single machine total weighted tardiness scheduling problem, in: Proceedings of the second multidisciplinary international scheduling conference: Theory and applications (MISTA 2005), New York, 2005.

[32]

J.K. Lenstra, A.R. Kan, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1 (1977) 343-362.

[33]

E. Levner, V. Kats, D.A.L. de Pablo, T.C.E. Cheng, Complexity of cyclic scheduling problems: A state-of-the-art survey, Computers & Industrial Engineering, 59 (2010) 352-361.

Digital Library

[34]

Z. L, F. Glover, J.K. Hao, A hybrid metaheuristic approach to solving the UBQP problem, European Journal of Operational Research, 207 (2010) 1254-1262.

[35]

Z. L, J.K. Hao, A memetic algorithm for graph coloring, European Journal of Operational Research, 203 (2010) 241-250.

[36]

Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program, C3P Report 826.

[37]

P. Moscato, Memetic algorithms, in: A short introduction, new ideas in optimization, Mcgraw-Hill Ltd., Maidenhead, UK, 1999, pp. 219-234.

Digital Library

[38]

C. Ng, J.B. Wang, T.C.E. Cheng, S. Lam, Flowshop scheduling of deteriorating jobs on dominating machines, Computers & Industrial Engineering, 61 (2011) 647-654.

Digital Library

[39]

Y. Pan, L. Shi, On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems, Mathematical Programming, 110 (2007) 543-559.

Digital Library

[40]

C.N. Potts, L.N. Van Wassenhove, A branch and bound algorithm for the total weighted tardiness problem, Operations Research, 33 (1985) 363-377.

Digital Library

[41]

C.N. Potts, L.N. Van Wassenhove, Single machine tardiness sequencing heuristics, IIE Transactions, 23 (1991) 346-354.

[42]

T. Sen, J.M. Sulek, P. Dileepan, Static scheduling research to minimize weighted and unweighted tardiness: A state-of-the-art survey, International Journal of Production Economics, 83 (2003) 1-12.

[43]

S. Tanaka, S. Fujikuma, M. Araki, An exact algorithm for single-machine scheduling without machine idle time, Journal of Scheduling, 12 (2009) 575-593.

Digital Library

[44]

M.F. Tasgetiren, Y.C. Liang, M. Sevkli, G. Gencyilmaz, Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem, International Journal of Production Research, 44 (2006) 4737-4754.

[45]

J.M. Valente, J.E. Schaller, Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem, Computers & Operations Research, 39 (2012) 2223-2231.

Digital Library

[46]

A. Volgenant, E. Teerhuis, Improved heuristics for the n-job single-machine weighted tardiness problem, Computers & Operations Research, 26 (1999) 35-44.

Digital Library

[47]

B.J. Wagner, D.J. Davis, H.V. Kher, The production of several items in a single facility with linearly changing demand rates, Decision Sciences, 33 (2002) 317-346.

[48]

X. Wang, L. Tang, A hybrid VNS with TS for the single machine scheduling problem to minimize the sum of weighted tardiness of jobs, in: Advanced intelligent computing theories and applications. With aspects of artificial intelligence, Springer, 2008, pp. 727-733.

Digital Library

[49]

X. Wang, L. Tang, A population-based variable neighborhood search for the single machine total weighted tardiness problem, Computers & Operations Research, 36 (2009) 2105-2110.

Digital Library

[50]

H. Xu, Z. L, T.C.E. Cheng, Iterated Local Search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness, Journal of Scheduling, 17 (2014) 271-287.

Digital Library

[51]

H. Xu, Z. L, A. Yin, L. Shen, U. Buscher, A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times, Computers & Operations Research, 50 (2014) 47-60.

Cited By

Ding JDauzère-Pérès SShen LLü Z(2023)A Novel Evolutionary Algorithm for Energy-Efficient Scheduling in Flexible Job ShopsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322279127:5(1470-1484)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3222791
Zakharova Y(2023)Hybrid Evolutionary Algorithm with Optimized Operators for Total Weighted Tardiness ProblemMathematical Optimization Theory and Operations Research10.1007/978-3-031-35305-5_15(224-238)Online publication date: 2-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-35305-5_15
Luo XLi MFeng HFeng N(2017)Intertemporal mixed bundling strategy of information products with network externalityComputers and Industrial Engineering10.1016/j.cie.2017.09.019113:C(369-381)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.cie.2017.09.019

A hybrid evolutionary approach for the single-machine total weighted tardiness problem
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Hybrid heuristic algorithms for single machine total weighted tardiness scheduling problems

This paper addresses on solving a well known Non Polynomial (NP) hard type problem, namely the single machine total weighted-tardiness problem. The performances of three hybrid heuristic algorithms to solve the single machine scheduling problems with ...
Block approach-tabu search algorithm for single machine total weighted tardiness problem

Problem of scheduling on a single machine to minimize total weighted tardiness of jobs can be described as follows: there are n jobs to be processed, each job has an integer processing time, a weight and a due date. The objective is to minimize the ...
A population-based variable neighborhood search for the single machine total weighted tardiness problem

This paper investigates the single machine total weighted tardiness problem, in which a set of independent jobs with distinct processing times, weights, and due dates are to be scheduled on a single machine to minimize the sum of weighted tardiness of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Industrial Engineering

Computers and Industrial Engineering Volume 108, Issue C

June 2017

241 pages

ISSN:0360-8352

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 June 2017

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ding JDauzère-Pérès SShen LLü Z(2023)A Novel Evolutionary Algorithm for Energy-Efficient Scheduling in Flexible Job ShopsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322279127:5(1470-1484)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3222791
Zakharova Y(2023)Hybrid Evolutionary Algorithm with Optimized Operators for Total Weighted Tardiness ProblemMathematical Optimization Theory and Operations Research10.1007/978-3-031-35305-5_15(224-238)Online publication date: 2-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-35305-5_15
Luo XLi MFeng HFeng N(2017)Intertemporal mixed bundling strategy of information products with network externalityComputers and Industrial Engineering10.1016/j.cie.2017.09.019113:C(369-381)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.cie.2017.09.019

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents