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 novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems. (English) Zbl 1175.90199
Summary: This paper proposes a novel hybrid discrete differential evolution (HDDE) algorithm for solving blocking flow shop scheduling problems to minimize the maximum completion time (i.e., makespan). Firstly, in the algorithm, the individuals are represented as discrete job permutations, and new mutation and crossover operators are developed for this representation, so that the algorithm can directly work in the discrete domain. Secondly, a local search algorithm based on insert neighborhood structure is embedded in the algorithm to balance the exploration and exploitation by enhancing the local searching ability. In addition, a speed-up method to evaluate insert neighborhood is developed to improve the efficiency of the whole algorithm. Computational simulations and comparisons based on the well-known benchmark instances of E. Taillard [Eur. J. Oper. Res. 64, No. 2, 278–285 (1993; Zbl 0769.90052)], by treating them as blocking flow shop problem instances with makespan criterion, are provided. It is shown that the proposed HDDE algorithm not only generates better results than the existing tabu search (TS) and TS with multi-moves (TS+M) approaches proposed by J. Grabowski and J. Pempera [Omega 35, No. 3, 302–311 (2007)], but also outperforms the hybrid differential evolution (HDE) algorithm developed by B. Qian et al. [Comput. Oper. Res. 36, No. 1, 209–233 (2009; Zbl 1163.90507)] in terms of solution quality, robustness and search efficiency. Ultimately, 112 out of 120 best known solutions provided by Grabowski and Pempera [loc. cit.] and D. P. Ronconi [Ann. Oper. Res. 138, 53–65 (2005; Zbl 1091.90075)] are further improved by the proposed HDDE algorithm.
MSC:
90B35Scheduling theory, deterministic
90C39Dynamic programming
References:
[1]Taillard, E.: Benchmarks for basic scheduling problems, European journal of operational research 64, 278-285 (1993) · Zbl 0769.90052 · doi:10.1016/0377-2217(93)90182-M
[2]Grabowski, J.; Pempera, J.: The permutation flow shop problem with blocking, A tabu search approach 35, 302-311 (2007)
[3]Qian, B.; Wang, L.; Huang, D. X.; Wang, W. L.; Wang, X.: An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers, Computers and operations research 36, No. 1, 209-233 (2009) · Zbl 1163.90507 · doi:10.1016/j.cor.2007.08.007
[4]Ronconi, D. P.: A branch-and-bound algorithm to minimize the makespan in a flowshop problem with blocking, Annals of operations research 138, No. 1, 53-65 (2005) · Zbl 1091.90075 · doi:10.1007/s10479-005-2444-3
[5]Pinedo, M.: Scheduling: theory, algorithms and systems, (2002)
[6]Wang, L.; Zheng, D. Z.: An effective hybrid heuristic for flow shop scheduling, International journal of advanced manufacturing technology 21, 38-44 (2003)
[7]Pan, Q. -K.; Wang, L.: No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm, International journal of advanced manufacturing technology 39, 796-807 (2008)
[8]Pan, Q. -K.; Tasgetiren, M. F.; Liang, Y. -C.: A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem, Computers and operations research 35, No. 9, 2807-2839 (2008) · Zbl 1144.90393 · doi:10.1016/j.cor.2006.12.030
[9]Ronconi, D. P.: A note on constructive heuristics for the flowshop problem with blocking, International journal of production economics 87, 39-48 (2004)
[10]Grabowski, J.; Pempera, J.: Sequencing of jobs in some production system, European journal of operational research 125, 535-550 (2000) · Zbl 0967.90045 · doi:10.1016/S0377-2217(99)00224-6
[11]Hall, N. G.; Sriskandarajah, C.: A survey of machine scheduling problems with blocking and no-wait in process, Operations research 44, 510-525 (1996) · Zbl 0864.90060 · doi:10.1287/opre.44.3.510
[12]Tonconi, D. P.; Henriques, L. R. S.: Some heuristic algorithms for total tardiness minimization in a flowshop with blocking, OMEGA — international journal of management science 37, No. 2, 272-281 (2009)
[13]Mccormich, S. T.; Pinedo, M. L.; Shenker, S.; Wolf, B.: Sequencing in an assembly line with blocking to minimize cycle time, Operations research 37, 925-936 (1989) · Zbl 0689.90048 · doi:10.1287/opre.37.6.925
[14]Leisten, R.: Flowshop sequencing problems with limited buffer storage, International journal of production research 28, 2085-2100 (1990) · Zbl 0707.90054 · doi:10.1080/00207549008942855
[15]Ronconi, D. P.; Armentano, V. A.: Lower bounding schemes for flowshops with blocking in-process, Journal of the operational research society 52, 1289-1297 (2001) · Zbl 1181.90125 · doi:10.1057/palgrave.jors.2601220
[16]Nawaz, M.; Enscore, E. E. J.; Ham, I.: A heuristic algorithm for the m-machine, n-job flow shop sequencing problem, OMEGA — international journal of management science 11, 91-95 (1983)
[17]Abadi, I. N. K.; Hall, N. G.; Sriskandarajh, C.: Minimizing cycle time in a blocking flowshop, Operations research 48, 177-180 (2000) · Zbl 1106.90334 · doi:10.1287/opre.48.1.177.12451
[18]Caraffa, V.; Ianes, S.; Bagchi, T. P.; Sriskandarajah, C.: Minimizing makespan in a blocking flowshop using genetic algorithms, International journal of production economics 70, 101-115 (2001)
[19]Storn, R.; Price, K.: Differential evolution — a simple and efficient adaptive scheme for global optimization over continuous spaces, Journal of global optimization 11, 341-359 (1997) · Zbl 0888.90135 · doi:10.1023/A:1008202821328
[20]Chang, F. P.; Hwang, C.: Design of digital PID controllers for continuous-time plants with integral performance criteria, Journal of the chinese institute of chemical engineers 35, 683-696 (2004)
[21]Ilonen, J.; Kamarainen, J. K.; Lampinen, J.: Differential evolution training algorithm for feed-forward neural networks, Neural process letters 17, 93-105 (2003)
[22]Storn, R.: Designing digital filters with differential evolution, New ideas in optimization (1999)
[23]Ruzek, B.; Kvasnicka, M.: Differential evolution in the earthquake hypocenter location, Pure and applied geophysics 158, 667-693 (2001)
[24]Qian, B.; Wang, L.; Hu, R.: A hybrid differential evolution for permutation flow-shop scheduling, International journal of advanced manufacturing technology 38, No. 7 – 8, 757-777 (2008)
[25]Onwubolu, G. C.; Davendra, D.: Scheduling flow shops using differential evolution algorithm, European journal of operational research 171, No. 2, 674-692 (2006) · Zbl 1090.90090 · doi:10.1016/j.ejor.2004.08.043
[26]Tasgetiren MF, Pan QK, Suganthan PN, Liang YC. A discrete differential evolution algorithm for the no-wait flowshop problem with total flowtime criterion. In: Proceedings of the 2007 IEEE symposium on computational intelligence in scheduling. p. 251 – 8.
[27]Tasgetiren, M. F.; Sevkli, M.; Liang, Y. C.: A particle swarm optimization and differential algorithm for job shop scheduling problem, International journal of operations research 3, 120-135 (2006) · Zbl 1175.90194
[28]Qian, B.; Wang, L.; Huang, D. X.; Wang, X.: An effective hybrid DE-based algorithm for flow shop scheduling with limited buffers, International journal of production research 36, No. 1, 209-233 (2009) · Zbl 1163.90507 · doi:10.1016/j.cor.2007.08.007
[29]Pan, Q. -K.; Wang, L.: A novel differential evolution algorithm for the no-idle permutation flow shop scheduling problems, European journal of industrial engineering 2, No. 3, 279-297 (2008)
[30]Pan Q-K, Tasgetiren MF, Liang Y-C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. In: Proceedings of the Ninth annual conference on genetic and evolutionary computation, London, England; 2007. p. 126 – 33.
[31]Tasgetiren MF, Pan Q-K, Liang Y-C. A discrete particle swarm optimization algorithm for the generalized traveling salesman problem. In: Proceedings of the ninth annual conference on genetic and evolutionary computation, London, England; 2007. p. 158 – 67.
[32]Grabowski, J.; Pempera, J.: Some local search algorithms for no-wait flow-shop problem with makespan criterion, Computers and operations research 32, 2197-2212 (2005) · Zbl 1068.90058 · doi:10.1016/j.cor.2004.02.009
[33]Taillard, E.: Some efficient heuristic methods for the flow shop sequencing problems, European journal of operational research 47, 65-74 (1990) · Zbl 0702.90043 · doi:10.1016/0377-2217(90)90090-X
[34]Smutncki C. A two-machine permutation flow shop scheduling problem with buffers. OR Spectrum; 1998.
[35]Zhu, Q. -Y.; Qin, A. K.; Suganthan, P. N.; Huang, G. -B.: Evolutionary extreme learning machine, Pattern recognition 38, No. 10, 1759-1763 (2005) · Zbl 1077.68791 · doi:10.1016/j.patcog.2005.03.028