Tasgetiren, M. Fatih; Liang, Yun-Chia; Sevkli, Mehmet; Gencyilmaz, Gunes A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. (English) Zbl 1110.90044 Eur. J. Oper. Res. 177, No. 3, 1930-1947 (2007). Summary: In this paper, a particle swarm optimization algorithm (PSO) is presented to solve the permutation flowshop sequencing problem (PFSP) with the objectives of minimizing makespan and the total flowtime of jobs. For this purpose, a heuristic rule called the smallest position value (SPV) borrowed from the random key representation of J. C. Bean [ORSA J. Comput. 6, No. 2, 154–160 (1994; Zbl 0807.90060)] was developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems. In addition, a very efficient local search, called variable neighborhood search (VNS), was embedded in the PSO algorithm to solve the well known benchmark suites in the literature. The PSO algorithm was applied to both the 90 benchmark instances provided by E. Taillard [Eur. J. Oper. Res. 64, No. 2, 278–285 (1993; Zbl 0769.90052)] and the 14,000 random, narrow random and structured benchmark instances provided by J. P. Watson, L. Barbulescu, L. D. Whitley and A. E. Howe [Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance, ORSA J. Comput. 14, No. 2, 98–123 (2002)]. For the makespan criterion, the solution quality was evaluated according to the best known solutions provided either by Taillard, or Watson et al. The total flowtime criterion was evaluated with the best known solutions provided by J Liu and C. R. Reeves [Eur. J. Oper. Res. 132, No. 2, 439–452 (2001; Zbl 1134.90389)], and C. Rajendran and H. Ziegler [Eur. J. Oper. Res. 155, No. 2, 426–438 (2004; Zbl 1045.90032)]. For the total flowtime criterion, 57 out of the 90 best known solutions reported by Liu and Reeves, and Rajendran and Ziegler were improved whereas for the makespan criterion, 195 out of the 800 best known solutions for the random and narrow random problems reported by Watson et al. were improved by the VNS version of the PSO algorithm. Cited in 74 Documents MSC: 90B35 Deterministic scheduling theory in operations research Keywords:scheduling; particle swarm optimization; permutation flowshop; variable neighborhood search; makespan; total flowtime Citations:Zbl 0807.90060; Zbl 0769.90052; Zbl 1134.90389; Zbl 1045.90032 PDFBibTeX XMLCite \textit{M. F. Tasgetiren} et al., Eur. J. Oper. Res. 177, No. 3, 1930--1947 (2007; Zbl 1110.90044) Full Text: DOI References: [1] Abido, M. A., Optimal power flow using particle swarm optimization, Electrical Power and Energy Systems, 24, 563-571 (2002) [2] Allahverdi, A.; Aldowaisan, T., New heuristics to minimize total completion time in \(m\)-machine flowshops, International Journal of Production Economics, 77, 71-83 (2002) [3] Bansal, S. P., Minimizing the sum of completion times of \(n\)-jobs over \(M\)-machines in a flowshop – a branch and bound approach, AIIE Transactions, 9, 306-311 (1977) [4] Bean, J. C., Genetic algorithm and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 2, 154-160 (1994) · Zbl 0807.90060 [5] Brandstatter, B.; Baumgartner, U., Particle swarm optimization – mass-spring system analogon, IEEE Transactions on Magnetics, 38, 997-1000 (2002) [6] Campbell, H. G.; Dudek, R. A.; Smith, M. L., A heuristic algorithm for the \(n\) job, \(m\) machine sequencing problem, Management Science, 16, 10, B630-B637 (1970) · Zbl 0194.50504 [7] Dannenbring, D. G., An evaluation of flow shop sequencing heuristics, Management Science, 23, 11, 1174-1182 (1977) · Zbl 0371.90063 [8] R.C. Eberhard, J. Kennedy, A new optimizer using particle swarm theory, in: Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995, pp. 39-43.; R.C. Eberhard, J. Kennedy, A new optimizer using particle swarm theory, in: Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995, pp. 39-43. [9] Framinan, J. M.; Leisten, R., An efficient constructive heuristic for flowtime minimisation in permutation flow shops, OMEGA, 31, 311-317 (2003) [10] Framinan, J. M.; Leisten, R.; Ruiz-Usano, R., Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation, European Journal of Operational Research, 141, 559-569 (2002) · Zbl 1081.90555 [11] Framinan, J. M.; Leisten, R.; Ruiz-Usano, R., Comparison of heuristics for flowtime minimization in permutation flowshops, Computers and Operations Research, 32, 5, 1237-1254 (2005) · Zbl 1074.90017 [12] Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117-129 (1976) · Zbl 0396.90041 [13] Gelders, L. F.; Sambandam, N., Four simple heuristics for scheduling a flow-shop, International Journal of Production Research, 16, 221-231 (1978) [14] Grabowski, J.; Wodecki, M., A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion, Computers and Operations Research, 31, 11, 1891-1909 (2004) · Zbl 1068.68143 [15] Gupta, J. N.D., Heuristic algorithms for multistage flowshop scheduling problem, AIIE Transactions, 4, 11-18 (1972) [16] Ho, J. C., Flowshop sequencing with mean flow time objective, European Journal of Operational Research, 81, 571-578 (1995) · Zbl 0912.90173 [17] Ho, J. C.; Chang, Y.-L., A new heuristic for the \(n\)-job, \(M\)-machine flowshop problem, European Journal of Operational Research, 52, 194-202 (1991) · Zbl 0725.90045 [18] Ignall, E.; Schrage, L., Application of the branch-and-bound technique to some flowshop scheduling problems, Operations Research, 13, 400-412 (1965) [19] Johnson, S. M., Optimal two-and three-stage production schedules, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359 [20] J. Kennedy, R.C. Eberhard, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, USA, 1995, pp. 1942-1948.; J. Kennedy, R.C. Eberhard, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, USA, 1995, pp. 1942-1948. [21] Kennedy, J.; Eberhart, R. C.; Shi, Y., Swarm Intelligence (2001), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA, USA [22] Liu, J.; Reeves, C. R., Constructive and composite heuristic solutions to the ((P\)∥∑C_i\) scheduling problem, European Journal of Operational Research, 132, 439-452 (2001) · Zbl 1134.90389 [23] Miyazaki, S.; Nishiyama, N., Analysis for minimizing weighted mean flowtime in flowshop scheduling, Journal of the Operations Research Society of Japan, 23, 118-132 (1980) · Zbl 0451.90074 [24] Miyazaki, S.; Nishiyama, N.; Hashimoto, F., An adjacent pairwise approach to the mean flowtime scheduling problem, Journal of the Operations Research Society of Japan, 21, 287-299 (1978) [25] Mladenovic, N.; Hansen, P., Variable neighborhood search, Computers and Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119 [26] Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the \(m\)-machine, \(n\)-job flow shop sequencing problem, OMEGA, 11, 1, 91-95 (1983) [27] Nowicki, E.; Smutnicki, C., A fast tabu search algorithm for the permutation flowshop problem, European Journal of Operational Research, 91, 160-175 (1996) · Zbl 0947.90590 [28] Ogbu, F.; Smith, D., The application of the simulated annealing algorithm to the solution of the \(n/m/C\) max flowshop problem, Computers and Operations Research, 17, 3, 243-253 (1990) · Zbl 0694.90059 [29] 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, 3, 473-491 (2004) · Zbl 1176.90178 [30] Osman, I.; Potts, C., Simulated annealing for permutation flow shop scheduling, OMEGA, 17, 6, 551-557 (1989) [31] Palmer, D. S., Sequencing jobs through a multistage process in the minimum total time: A quick method of obtaining a near-optimum, Operational Research Quarterly, 16, 101-107 (1965) [32] Rajendran, C., Heuristic algorithm for scheduling in a flowshop to minimize total flowtime, International Journal of Production Economics, 29, 65-73 (1993) [33] Rajendran, C., A heuristics for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria, International Journal of Production Research, 32, 2541-2558 (1994) · Zbl 0904.90076 [34] Rajendran, C.; Chaudhuri, D., A flowshop scheduling algorithm to minimize total flowtime, Journal of the Operations Research Society of Japan, 34, 28-45 (1991) · Zbl 0736.90044 [35] Rajendran, C.; Chaudhuri, D., An efficient heuristic approach to the scheduling of jobs in a flowshop, European Journal of Operational Research, 61, 318-325 (1991) · Zbl 0757.90036 [36] Rajendran, C.; Ziegler, H., An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs, European Journal of Operational Research, 103, 129-138 (1997) · Zbl 0922.90089 [37] Rajendran, C.; Ziegler, H., Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155, 2, 426-438 (2004) · Zbl 1045.90032 [38] Reeves, C., Improving the efficiency of tabu search for machine sequencing problem, Journal of the Operational Research Society, 44, 4, 375-382 (1993) · Zbl 0775.90238 [39] Reeves, C., A genetic algorithm for flowshop sequencing, Computers and Operations Research, 22, 1, 5-13 (1995) · Zbl 0815.90097 [40] Reeves, C.; Yamada, T., Genetic algorithms, path relinking and the flowshop sequencing problem, Evolutionary Computation, 6, 45-60 (1998) [41] Rinnooy Kan, A. H.G., Machine Scheduling Problems: Classification, Complexity, and Computations (1976), Nijhoff: Nijhoff The Hague · Zbl 0366.90092 [42] Salman, A.; Ahmad, I.; Al-Madani, S., Particle swarm optimization for tast assignment problem, Microprocessors and Microsystems, 26, 363-371 (2003) [43] Stafford, E. F., On the development of a mixed integer linear programming model for the flowshop sequencing problem, Journal of Operational Research Society, 39, 1163-1174 (1988) · Zbl 0663.90046 [44] T. Stützle, Applying iterated local search to the permutation flowshop problem, Technical Report, AIDA-98-04, Darmstad University of Technology, Computer Science Department, Intellctics Group, Darmstad, Germany, 1998.; T. Stützle, Applying iterated local search to the permutation flowshop problem, Technical Report, AIDA-98-04, Darmstad University of Technology, Computer Science Department, Intellctics Group, Darmstad, Germany, 1998. [45] Stützle, T., An ant approach to the flowshop problem, (Proceedings of the 6th European Congress on Intelligent Techniques and Soft Computing (EUFIT’98) (1998), Verlag Mainz: Verlag Mainz Aachen, Germany), 1560-1564 [46] Taillard, E., Some efficient heuristic methods for the flowshop sequencing problems, European Journal of Operational Research, 47, 65-74 (1990) · Zbl 0702.90043 [47] Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278-285 (1993) · Zbl 0769.90052 [48] Tasgetiren, M. F.; Liang, Y.-C., A binary particle swarm optimization algorithm for lot sizing problem, Journal of Economic and Social Research, 5, 2, 1-20 (2003) [49] M.F. Tasgetiren, Y.-C. Liang, M. Sevkli, G. Gencyilmaz, Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem, in: Proceedings of the 4th International Symposium on Intelligent Manufacturing Systems (IMS2004), Sakarya, Turkey, 2004, pp. 431-441.; M.F. Tasgetiren, Y.-C. Liang, M. Sevkli, G. Gencyilmaz, Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem, in: Proceedings of the 4th International Symposium on Intelligent Manufacturing Systems (IMS2004), Sakarya, Turkey, 2004, pp. 431-441. · Zbl 1110.90044 [50] M.F. Tasgetiren, M. Sevkli, Y.-C. Liang, G. Gencyilmaz, Particle swarm optimization algorithm for single machine total weighted tardiness problem, in: Proceedings of the 2004 Congress on Evolutionary Computation (CEC’04), Portland, Oregon, 2004, pp. 1412-1419.; M.F. Tasgetiren, M. Sevkli, Y.-C. Liang, G. Gencyilmaz, Particle swarm optimization algorithm for single machine total weighted tardiness problem, in: Proceedings of the 2004 Congress on Evolutionary Computation (CEC’04), Portland, Oregon, 2004, pp. 1412-1419. · Zbl 1114.90391 [51] Tasgetiren, M. F.; Sevkli, M.; Liang, Y. C.; Gencyilmaz, G., Particle swarm optimization algorithm for permutation flowshop sequencing problem, Lecture Notes in Computer Science, vol. 3172 (2004), Springer-Verlag, pp. 382-390 [52] Van den Bergh, F.; Engelbecht, A. P., Cooperative learning in neural networks using particle swarm optimizers, South African Computer Journal, 26, 84-90 (2000) [53] Wang, C.; Chu, C.; Proth, J.-M., Heuristic approaches for \(n/m\)/WF//∑\(C_i\) scheduling problems, European Journal of Operational Research, 96, 636-644 (1997) · Zbl 0917.90203 [54] 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, 2, 98-123 (2002) · Zbl 1238.90072 [55] Woo, D. S.; Yim, H. S., A heuristic algorithm for mean flowtime objective in flowshop scheduling, Computers and Operations Research, 25, 175-182 (1998) · Zbl 0904.90090 [56] T. Yamada, C.R. Reeves, Solving the \(C_{max}\); T. Yamada, C.R. Reeves, Solving the \(C_{max}\) [57] L.-W. Yeh, Optimal Procurement Policies for Multi-product Multi-supplier with Capacity Constraint and Price Discount, Master thesis, Department of Industrial Engineering and Management, Yuan Ze University, Taiwan, ROC, 2003.; L.-W. Yeh, Optimal Procurement Policies for Multi-product Multi-supplier with Capacity Constraint and Price Discount, Master thesis, Department of Industrial Engineering and Management, Yuan Ze University, Taiwan, ROC, 2003. [58] Yoshida, H.; Kawata, K.; Fukuyama, Y.; Nakanishi, Y., A particle swarm optimization for reactive power and voltage control considering voltage security assessment, IEEE Transactions on Power Systems, 15, 1232-1239 (2000) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.