# 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 discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. (English) Zbl 1144.90393
Summary: A discrete particle swarm optimization (DPSO) algorithm is presented to solve the no-wait flowshop scheduling problem with both makespan and total flowtime criteria. The main contribution of this study is due to the fact that particles are represented as discrete job permutations and a new position update method is developed based on the discrete domain. In addition, the DPSO algorithm is hybridized with the variable neighborhood descent (VND) algorithm to further improve the solution quality. Several speed-up methods are proposed for both the swap and insert neighborhood structures. The DPSO algorithm is applied to both 110 benchmark instances of E. Taillard [Eur. J. Oper. Res. 64, No. 2, 278–285 (1993; Zbl 0769.90052)] by treating them as the no-wait flowshop problem instances with the total flowtime criterion, and to 31 benchmark instances provided by J. Carlier [RAIRO, Rech. Opér. 12, 333–350 (1978; Zbl 0401.90052)], J. Heller [Oper. Res. 8, 178–184 (1960; Zbl 0092.27910)], and C. R. Reeves [Comput. Oper. Res. 22, No. 1, 5–13 (1995; Zbl 0815.90097)] for the makespan criterion. For the makespan criterion, the solution quality is evaluated according to the reference makespans generated by Ch. Rajendran [J. Oper. Res. Soc. 45, No. 4, 472–478 (1994; bl 0799.90060)] whereas for the total flowtime criterion, it is evaluated with the optimal solutions, lower bounds and best known solutions provided by A. Fink and St. Voß [Eur. J. Oper. Res. 151, No. 2, 400–414 (2003; Zbl 1052.90030)]. The computational results show that the DPSO algorithm generated either competitive or better results than those reported in the literature. Ultimately, 74 out of 80 best known solutions provided by Fink and Voß [loc. cit.] were improved by the VND version of the DPSO algorithm.
##### MSC:
 90B35 Scheduling theory, deterministic 90C59 Approximation methods and heuristics
##### 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] Carlier, J.: Ordonnancements a contraintes disjonctives, RAIRO recherche operationelle 12, 333-351 (1978) · Zbl 0401.90052 [3] Heller, J.: Some numerical experiments for an M$×J$ flow shop and its decision-theoretical aspects, Operations research 8, 178-184 (1960) · Zbl 0092.27910 · doi:10.1287/opre.8.2.178 [4] Reeves, C.: A genetic algorithm for flowshop sequencing, Computers and operations research 22, 5-13 (1995) · Zbl 0815.90097 · doi:10.1016/0305-0548(93)E0014-K [5] Rajendran, C.: A no-wait flowshop scheduling heuristic to minimize makespan, Journal of the operational research society 45, 472-478 (1994) · Zbl 0799.90060 [6] Fink, A.; Voß, S.: Solving the continuous flow-shop scheduling problem by metaheuristics, European journal of operational research 151, 400-414 (2003) · Zbl 1052.90030 · doi:10.1016/S0377-2217(02)00834-2 [7] 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 [8] Hall, N. G.; Sriskandarayah, 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 [9] 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 [10] Raaymakers, W.; Hoogeveen, J.: Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing, European journal of operational research 126, 131-151 (2000) · Zbl 0970.90034 · doi:10.1016/S0377-2217(99)00285-4 [11] Garey, M. R.; Johnson, D. S.: Computers and intractability: a guide to the theory of NP-completeness, (1979) [12] Bonney, M. C.; Gundry, S. W.: Solutions to the constrained flowshop sequencing problem, Operational research quarterly 24, 869-883 (1976) · Zbl 0345.90020 · doi:10.1057/jors.1976.176 [13] King, J. R.; Spachis, A. S.: Heuristics for flowshop scheduling, International journal of production research 18, 343-357 (1980) [14] Gangadharan, R.; Rajendran, C.: Heuristic algorithms for scheduling in no-wait flowshop, International journal of production economics 32, 285-290 (1993) [15] Rajendran, C.; Chaudhuri, D.: Heuristic algorithms for continuous flow-shop problem, Naval research logistics 37, 695-705 (1990) · Zbl 0707.90052 · doi:10.1002/1520-6750(199010)37:5<695::AID-NAV3220370508>3.0.CO;2-L [16] Aldowaisan, T.; Allahverdi, A.: New heuristics for no-wait flowshops to minimize makespan, Computers and operations research 30, 1219-1231 (2003) · Zbl 1047.90053 · doi:10.1016/S0305-0548(02)00068-0 [17] Schuster, C. J.; Framinan, J. M.: Approximative procedure for no-wait job shop scheduling, Operations research letters 31, 308-318 (2003) · Zbl 1041.90019 · doi:10.1016/S0167-6377(03)00005-1 [18] Chen, C. -L.; Neppalli, R. V.; Aljaber, N.: Genetic algorithms applied to the continuous flowshop problem, Computers and industrial engineering 30, 919-929 (1996) [19] Eberhart RC, Kennedy J. A new optimizer using particle swarm theory. In: Proceedings of the sixth international symposium on micro machine and human science, Nagoya, Japan; 1995. p. 39 – 43. [20] Abido, M. A.: Optimal power flow using particle swarm optimization, Electrical power and energy systems 24, 563-571 (2002) [21] Brandstatter, B.; Baumgartner, U.: Particle swarm optimization — mass-spring system analogue, IEEE transactions on magnetics 38, 997-1000 (2002) [22] Salman, A.; Ahmad, I.; Al-Madani, S.: Particle swarm optimization for task assignment problem, Microprocessors and microsystems 26, 363-371 (2003) [23] Tasgetiren, M. F.; Liang, Y. C.: A binary particle swarm optimization algorithm for lot sizing problem, Journal of economic and social research 5, No. 2, 1-20 (2003) [24] Tasgetiren MF, Sevkli M, Liang YC, Gencyilmaz G. Particle swarm optimization algorithm for single machine total weighted tardiness problem. In: Proceedings of the 2004 congress on evolutionary computation (CEC2004), Portland, Oregon, USA; 2004. p. 1412 – 9. [25] Tasgetiren, M. F.; Sevkli, M.; Liang, Y. C.; Gencyilmaz, G.: Particle swarm optimization algorithm for permutation flowshop sequencing problem, Proceedings of the fourth international workshop on ant colony optimization and swarm intelligence (ANTS2004). Lecture notes in computer science, Brussels, Belgium 3172, 382-390 (2004) [26] Tasgetiren MF, Sevkli M, Liang YC, Gencyilmaz G. Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem. In: Proceedings of the fourth international symposium on intelligent manufacturing systems (IMS2004), Sakarya, Turkey; 2004. p. 431 – 41. [27] Tasgetiren, M. F.; Liang, Y. C.; Sevkli, M.; Gencyilmaz, G.: Particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, European journal of operational research 177, 1930-1947 (2007) · Zbl 1110.90044 · doi:10.1016/j.ejor.2005.12.024 [28] Onwubolu, G. C.; Clerc, M.: Optimal operating path for automated drilling operations by a new heuristic approach using particle swarm optimisation, International journal of production research 42, No. 3, 473-491 (2004) · Zbl 1176.90178 · doi:10.1080/00207540310001614150 [29] Kennedy, J.; Eberhart, R. C.; Shi, Y.: Swarm intelligence, (2001) [30] Nawaz, M.; Jr, E. E. Enscore; Ham, I.: A heuristic algorithm for the m-machine, n-job flow shop sequencing problem, Omega 11, No. 1, 91-95 (1983) [31] Mladenovic, N.; Hansen, P.: Variable neighborhood search, Computers and operations research 24, 1097-1100 (1997) · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2 [32] Watson, J. P.; Barbulescu, L.; Whitley, L. D.; Howe, A. E.: Contrasting structured and random permutation flowshop scheduling problems: search space topology and algorithm performance, ORSA journal of computing 14, No. 2, 98-123 (2002) [33] Montgomery, D. C.: Design and analysis of experiments, (2000) [34] Devore, J. L.: Probability and statistics for engineering and the sciences, (2000) [35] Fink, A.; Voß, S.: Hotframe: a heuristic optimization framework, Optimization software class libraries, 81-154 (2002) [36] Clerc M. Discrete particle swarm optimization for traveling salesman problem. nbsp;http://clerc.maurice.free.fr/pso/nbsp;. · Zbl 1139.90415 [37] Picard, J. -C.; Queyranne, M.: The time dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Operations research 26, 86-110 (1978) · Zbl 0371.90066 · doi:10.1287/opre.26.1.86