zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A hybrid differential evolution and tree search algorithm for the job shop scheduling problem. (English) Zbl 1235.90068
Summary: The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. In terms of the objective function, most existing research has been focused on the makespan criterion. However, in contemporary manufacturing systems, due-date-related performances are more important because they are essential for maintaining a high service reputation. Therefore, in this study we aim at minimizing the total weighted tardiness in JSSP. Considering the high complexity, a hybrid differential evolution (DE) algorithm is proposed for the problem. To enhance the overall search efficiency, a neighborhood property of the problem is discovered, and then a tree search procedure is designed and embedded into the DE framework. According to the extensive computational experiments, the proposed approach is efficient in solving the job shop scheduling problem with total weighted tardiness objective.
MSC:
90B35Scheduling theory, deterministic
90C27Combinatorial optimization
WorldCat.org
Full Text: DOI
References:
[1] J. K. Lenstra, A. H. G. R. Rinnooy Kan, and P. Brucker, “Complexity of machine scheduling problems,” Annals of Discrete Mathematics, vol. 1, pp. 343-362, 1977. · Zbl 0353.68067 · doi:10.1016/S0167-5060(08)70743-X
[2] I. Essafi, Y. Mati, and S. Dauzère-Pérès, “A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem,” Computers and Operations Research, vol. 35, no. 8, pp. 2599-2616, 2008. · Zbl 1177.90155 · doi:10.1016/j.cor.2006.12.019
[3] 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, vol. 194, no. 3, pp. 637-649, 2009. · Zbl 1163.90004 · doi:10.1016/j.ejor.2007.10.063
[4] E. Nowicki and C. Smutnicki, “An advanced tabu search algorithm for the job shop problem,” Journal of Scheduling, vol. 8, no. 2, pp. 145-159, 2005. · Zbl 1154.90479 · doi:10.1007/s10951-005-6364-5
[5] J. Q. Li, Q. K. Pan, P. N. Suganthan, and T. J. Chua, “A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem,” The International Journal of Advanced Manufacturing Technology, vol. 52, no. 5-8, pp. 683-697, 2011. · doi:10.1007/s00170-010-2743-y
[6] D. Y. Sha and C.-Y. Hsu, “A hybrid particle swarm optimization for job shop scheduling problem,” Computers & Industrial Engineering, vol. 51, no. 4, pp. 791-808, 2006. · doi:10.1016/j.cie.2006.09.002
[7] G. Moslehi and M. Mahnam, “A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search,” International Journal of Production Economics, vol. 129, no. 1, pp. 14-22, 2011. · doi:10.1016/j.ijpe.2010.08.004
[8] M. Seo and D. Kim, “Ant colony optimisation with parameterised search space for the job shop scheduling problem,” International Journal of Production Research, vol. 48, no. 4, pp. 1143-1154, 2010. · Zbl 1197.90228 · doi:10.1080/00207540802538021
[9] L. N. Xing, Y. W. Chen, P. Wang, Q. S. Zhao, and J. Xiong, “A knowledge-based ant colony optimization for flexible job shop scheduling problems,” Applied Soft Computing Journal, vol. 10, no. 3, pp. 888-896, 2010. · doi:10.1016/j.asoc.2009.10.006
[10] K. L. Huang and C. J. Liao, “Ant colony optimization combined with taboo search for the job shop scheduling problem,” Computers and Operations Research, vol. 35, no. 4, pp. 1030-1046, 2008. · Zbl 1180.90123 · doi:10.1016/j.cor.2006.07.003
[11] J. Gao, L. Sun, and M. Gen, “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems,” Computers & Operations Research, vol. 35, no. 9, pp. 2892-2907, 2008. · Zbl 1144.90379 · doi:10.1016/j.cor.2007.01.001
[12] R. Tavakkoli-Moghaddam, M. Azarkish, and A. Sadeghnejad-Barkousaraie, “A new hybrid multi-objective Pareto archive PSO algorithm for a bi-objective job shop scheduling problem,” Expert Systems with Applications, vol. 38, no. 9, pp. 10812-10821, 2011. · Zbl 1202.68075 · doi:10.1016/j.eswa.2011.02.050
[13] M. Singer and M. Pinedo, “A computational study of bound techniques for the total weighted tardiness in job shops,” IIE Transactions, vol. 30, no. 2, pp. 109-118, 1998.
[14] E. Kutanoglu and I. Sabuncuoglu, “An analysis of heuristics in a dynamic job shop with weighted tardiness objectives,” International Journal of Production Research, vol. 37, no. 1, pp. 165-187, 1999. · Zbl 0939.90008 · doi:10.1080/002075499191995
[15] S. J. Mason, J. W. Fowler, and W. M. Carlyle, “A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops,” Journal of Scheduling, vol. 5, no. 3, pp. 247-262, 2002. · Zbl 1009.90045 · doi:10.1002/jos.102
[16] L. Mönch and R. Drießel, “A distributed shifting bottleneck heuristic for complex job shops,” Computers and Industrial Engineering, vol. 49, no. 3, pp. 363-380, 2005. · doi:10.1016/j.cie.2005.06.004
[17] S. Kreipl, “A large step random walk for minimizing total weighted tardiness in a job shop,” Journal of Scheduling, vol. 3, no. 3, pp. 125-138, 2000. · Zbl 0969.90045 · doi:10.1002/(SICI)1099-1425(200005/06)3:3<125::AID-JOS40>3.0.CO;2-C
[18] M. Singer, “Decomposition methods for large job shops,” Computers & Operations Research, vol. 28, no. 3, pp. 193-207, 2001. · Zbl 0964.90020 · doi:10.1016/S0305-0548(99)00098-2
[19] K. M. J. Bontridder, “Minimizing total weighted tardiness in a generalized job shop,” Journal of Scheduling, vol. 8, no. 6, pp. 479-496, 2005. · Zbl 1123.90022 · doi:10.1007/s10951-005-4779-7
[20] R. Tavakkoli-Moghaddam, M. Khalili, and B. Naderi, “A hybridization of simulated annealing and electromagnetic-like mechanism for job shop problems with machine availability and sequence-dependent setup times to minimize total weighted tardiness,” Soft Computing, vol. 13, no. 10, pp. 995-1006, 2009. · doi:10.1007/s00500-008-0367-z
[21] R. Storn and K. Price, “Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces,” Journal of Global Optimization, vol. 11, no. 4, pp. 341-359, 1997. · Zbl 0888.90135 · doi:10.1023/A:1008202821328
[22] E. Mezura-Montes, J. Velázquez-Reyes, and C. A. Coello Coello, “Modified differential evolution for constrained optimization,” in Proceedings of the IEEE Congress on Evolutionary Computation, pp. 25-32, July 2006.
[23] L. Wang and L.-P. Li, “Fixed-structure H\infty controller synthesis based on differential evolution with level comparison,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 1, pp. 120-129, 2011. · doi:10.1109/TEVC.2010.2077300
[24] M. Vasile, E. Minisci, and M. Locatelli, “An inflationary differential evolution algorithm for space trajectory optimization,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 2, pp. 267-281, 2011. · doi:10.1109/TEVC.2010.2087026
[25] M. Sharma, M. Pandit, and L. Srivastava, “Reserve constrained multi-area economic dispatch employing differential evolution with time-varying mutation,” International Journal of Electrical Power and Energy Systems, vol. 33, no. 3, pp. 753-766, 2011. · doi:10.1016/j.ijepes.2010.12.033
[26] V. C. Mariani, L. S. Coelho, and P. K. Sahoo, “Modified differential evolution approaches applied in exergoeconomic analysis and optimization of a cogeneration system,” Expert Systems with Applications, vol. 38, no. 11, pp. 13886-13893, 2011. · doi:10.1016/j.eswa.2011.04.194
[27] N. Noman and H. Iba, “Accelerating differential evolution using an adaptive local search,” IEEE Transactions on Evolutionary Computation, vol. 12, no. 1, pp. 107-125, 2008. · doi:10.1109/TEVC.2007.895272
[28] C.-W. Chiang, W.-P. Lee, and J.-S. Heh, “A 2-Opt based differential evolution for global optimization,” Applied Soft Computing Journal, vol. 10, no. 4, pp. 1200-1207, 2010. · doi:10.1016/j.asoc.2010.05.012
[29] W. Gong, Z. Cai, and L. Jiang, “Enhancing the performance of differential evolution using orthogonal design method,” Applied Mathematics and Computation, vol. 206, no. 1, pp. 56-69, 2008. · Zbl 1157.65384 · doi:10.1016/j.amc.2008.08.053
[30] G. Onwubolu and D. Davendra, “Scheduling flow shops using differential evolution algorithm,” European Journal of Operational Research, vol. 171, no. 2, pp. 674-692, 2006. · Zbl 1090.90090 · doi:10.1016/j.ejor.2004.08.043
[31] B. Qian, L. Wang, R. Hu, W.-L. Wang, D.-X. Huang, and X. Wang, “A hybrid differential evolution method for permutation flow-shop scheduling,” The International Journal of Advanced Manufacturing Technology, vol. 38, no. 7, pp. 757-777, 2008. · doi:10.1007/s00170-007-1115-8
[32] Q.-K. Pan, M. F. Tasgetiren, and Y.-C. Liang, “A discrete differential evolution algorithm for the permutation flowshop scheduling problem,” Computers & Industrial Engineering, vol. 55, no. 4, pp. 795-816, 2008. · doi:10.1016/j.cie.2008.03.003
[33] L. Wang, Q.-K. Pan, P. N. Suganthan, W.-H. Wang, and Y.-M. Wang, “A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems,” Computers &Operations Research, vol. 37, no. 3, pp. 509-520, 2010. · Zbl 1175.90199 · doi:10.1016/j.cor.2008.12.004
[34] S. D. Wu, E. S. Byeon, and R. H. Storer, “A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness,” Operations Research, vol. 47, no. 1, pp. 113-124, 1999. · Zbl 0979.90030 · doi:10.1287/opre.47.1.113
[35] K. V. Price, R. M. Storn, and J. A. Lampinen, Differential Evolution: A Practical Approach to Global Optimization, Springer, Berlin, Germany, 2005. · Zbl 1186.90004
[36] C. Rego and R. Duarte, “A filter-and-fan approach to the job shop scheduling problem,” European Journal of Operational Research, vol. 194, no. 3, pp. 650-662, 2009. · Zbl 1162.90016 · doi:10.1016/j.ejor.2007.12.035
[37] R. Bellman, “On a routing problem,” Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87-90, 1958. · Zbl 0081.14403 · doi:10.1093/qjmam/11.2.159
[38] U. K. Chakraborty, Advances in Differential Evolution, Springer, Berlin, Germany, 2008. · Zbl 1153.68510