A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem

European Journal of Operational Research - Tập 177 - Trang 1930-1947 - 2007
M. Fatih Tasgetiren1, Yun-Chia Liang2, Mehmet Sevkli3, Gunes Gencyilmaz4
1Department of Management, Fatih University, 34500 Buyukcekmece, Istanbul, Turkey
2Department of Industrial Engineering and Management, Yuan Ze University, No. 135 Yuan-Tung Road, Chung-Li, Taoyuan County, Taiwan 320, ROC
3Department of Industrial Engineering, Fatih University, 34500 Buyukcekmece, Istanbul, Turkey
4Department of Management, Istanbul Kultur University, E5 Karayolu Uzeri, Sirinevler, Istanbul, Turkey

Tài liệu tham khảo

Abido, 2002, Optimal power flow using particle swarm optimization, Electrical Power and Energy Systems, 24, 563, 10.1016/S0142-0615(01)00067-9 Allahverdi, 2002, New heuristics to minimize total completion time in m-machine flowshops, International Journal of Production Economics, 77, 71, 10.1016/S0925-5273(01)00228-6 Bansal, 1977, Minimizing the sum of completion times of n-jobs over M-machines in a flowshop – a branch and bound approach, AIIE Transactions, 9, 306, 10.1080/05695557708975160 Bean, 1994, Genetic algorithm and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 154, 10.1287/ijoc.6.2.154 Brandstatter, 2002, Particle swarm optimization – mass-spring system analogon, IEEE Transactions on Magnetics, 38, 997, 10.1109/20.996256 Campbell, 1970, A heuristic algorithm for the n job, m machine sequencing problem, Management Science, 16, B630, 10.1287/mnsc.16.10.B630 Dannenbring, 1977, An evaluation of flow shop sequencing heuristics, Management Science, 23, 1174, 10.1287/mnsc.23.11.1174 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. Framinan, 2003, An efficient constructive heuristic for flowtime minimisation in permutation flow shops, OMEGA, 31, 311, 10.1016/S0305-0483(03)00047-1 Framinan, 2002, Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation, European Journal of Operational Research, 141, 559, 10.1016/S0377-2217(01)00278-8 Framinan, 2005, Comparison of heuristics for flowtime minimization in permutation flowshops, Computers and Operations Research, 32, 1237, 10.1016/j.cor.2003.11.002 Garey, 1976, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117, 10.1287/moor.1.2.117 Gelders, 1978, Four simple heuristics for scheduling a flow-shop, International Journal of Production Research, 16, 221, 10.1080/00207547808930015 Grabowski, 2004, A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion, Computers and Operations Research, 31, 1891, 10.1016/S0305-0548(03)00145-X Gupta, 1972, Heuristic algorithms for multistage flowshop scheduling problem, AIIE Transactions, 4, 11, 10.1080/05695557208974823 Ho, 1995, Flowshop sequencing with mean flow time objective, European Journal of Operational Research, 81, 571, 10.1016/0377-2217(93)E0353-Y Ho, 1991, A new heuristic for the n-job, M-machine flowshop problem, European Journal of Operational Research, 52, 194, 10.1016/0377-2217(91)90080-F Ignall, 1965, Application of the branch-and-bound technique to some flowshop scheduling problems, Operations Research, 13, 400, 10.1287/opre.13.3.400 Johnson, 1954, Optimal two-and three-stage production schedules, Naval Research Logistics Quarterly, 1, 61, 10.1002/nav.3800010110 J. Kennedy, R.C. Eberhard, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, USA, 1995, pp. 1942–1948. Kennedy, 2001 Liu, 2001, Constructive and composite heuristic solutions to the P∥∑Ci scheduling problem, European Journal of Operational Research, 132, 439, 10.1016/S0377-2217(00)00137-5 Miyazaki, 1980, Analysis for minimizing weighted mean flowtime in flowshop scheduling, Journal of the Operations Research Society of Japan, 23, 118, 10.15807/jorsj.23.118 Miyazaki, 1978, An adjacent pairwise approach to the mean flowtime scheduling problem, Journal of the Operations Research Society of Japan, 21, 287, 10.15807/jorsj.21.287 Mladenovic, 1997, Variable neighborhood search, Computers and Operations Research, 24, 1097, 10.1016/S0305-0548(97)00031-2 Nawaz, 1983, A heuristic algorithm for the m-machine, n-job flow shop sequencing problem, OMEGA, 11, 91, 10.1016/0305-0483(83)90088-9 Nowicki, 1996, A fast tabu search algorithm for the permutation flowshop problem, European Journal of Operational Research, 91, 160, 10.1016/0377-2217(95)00037-2 Ogbu, 1990, The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem, Computers and Operations Research, 17, 243, 10.1016/0305-0548(90)90001-N Onwubolu, 2004, Optimal operating path for automated drilling operations by a new heuristic approach using particle swarm optimisation, International Journal of Production Research, 42, 473, 10.1080/00207540310001614150 Osman, 1989, Simulated annealing for permutation flow shop scheduling, OMEGA, 17, 551, 10.1016/0305-0483(89)90059-5 Palmer, 1965, Sequencing jobs through a multistage process in the minimum total time: A quick method of obtaining a near-optimum, Operational Research Quarterly, 16, 101, 10.1057/jors.1965.8 Rajendran, 1993, Heuristic algorithm for scheduling in a flowshop to minimize total flowtime, International Journal of Production Economics, 29, 65, 10.1016/0925-5273(93)90024-F Rajendran, 1994, A heuristics for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria, International Journal of Production Research, 32, 2541, 10.1080/00207549408957083 Rajendran, 1991, A flowshop scheduling algorithm to minimize total flowtime, Journal of the Operations Research Society of Japan, 34, 28, 10.15807/jorsj.34.28 Rajendran, 1991, An efficient heuristic approach to the scheduling of jobs in a flowshop, European Journal of Operational Research, 61, 318, 10.1016/0377-2217(92)90361-C Rajendran, 1997, An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs, European Journal of Operational Research, 103, 129, 10.1016/S0377-2217(96)00273-1 Rajendran, 2004, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155, 426, 10.1016/S0377-2217(02)00908-6 Reeves, 1993, Improving the efficiency of tabu search for machine sequencing problem, Journal of the Operational Research Society, 44, 375, 10.1057/jors.1993.67 Reeves, 1995, A genetic algorithm for flowshop sequencing, Computers and Operations Research, 22, 5, 10.1016/0305-0548(93)E0014-K Reeves, 1998, Genetic algorithms, path relinking and the flowshop sequencing problem, Evolutionary Computation, 6, 45, 10.1162/evco.1998.6.1.45 Rinnooy Kan, 1976 Salman, 2003, Particle swarm optimization for tast assignment problem, Microprocessors and Microsystems, 26, 363, 10.1016/S0141-9331(02)00053-4 Stafford, 1988, On the development of a mixed integer linear programming model for the flowshop sequencing problem, Journal of Operational Research Society, 39, 1163, 10.1057/jors.1988.193 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. Stützle, 1998, An ant approach to the flowshop problem, 1560 Taillard, 1990, Some efficient heuristic methods for the flowshop sequencing problems, European Journal of Operational Research, 47, 65, 10.1016/0377-2217(90)90090-X Taillard, 1993, Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278, 10.1016/0377-2217(93)90182-M Tasgetiren, 2003, A binary particle swarm optimization algorithm for lot sizing problem, Journal of Economic and Social Research, 5, 1 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, 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. Tasgetiren, 2004, Particle swarm optimization algorithm for permutation flowshop sequencing problem, vol. 3172 Van den Bergh, 2000, Cooperative learning in neural networks using particle swarm optimizers, South African Computer Journal, 26, 84 Wang, 1997, Heuristic approaches for n/m/WF//∑Ci scheduling problems, European Journal of Operational Research, 96, 636, 10.1016/0377-2217(95)00347-9 Watson, 2002, Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance, ORSA Journal of Computing, 14, 98, 10.1287/ijoc.14.2.98.120 Woo, 1998, A heuristic algorithm for mean flowtime objective in flowshop scheduling, Computers and Operations Research, 25, 175, 10.1016/S0305-0548(97)00050-6 T. Yamada, C.R. Reeves, Solving the Cmax permutation flowshop scheduling problem by genetic local search, in: Proceedings of 1998 IEEE International Conference on Evolutionary Computation, 1998, pp. 230–234. 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. Yoshida, 2000, A particle swarm optimization for reactive power and voltage control considering voltage security assessment, IEEE Transactions on Power Systems, 15, 1232, 10.1109/59.898095