A genetic algorithm for flowshop scheduling with multiple objectives
Tóm tắt
In this paper, we study the permutation flowshop scheduling problem with the objectives of minimizing the makespan and total flowtime of jobs. An attempt is made to solve the multi-objective problem by using the Proposed Genetic Algorithm (ProGA). In order to evaluate the ProGA, we have made use of benchmark flowshop scheduling problems, and the heuristically non-dominated solutions for these problems are obtained from each of the existing methodologies and the ProGA. These non-dominated solutions are combined to obtain a net heuristic non-dominated front for a given problem. It is found that most of the solutions on the net non-dominated front are yielded by the ProGA, bringing out the superiority of the proposed genetic algorithm.
Tài liệu tham khảo
Ishibuchi, H., T. Yoshida, and T. Murata, (2003). “Balance between Genetic Search and Local Search in Memetic Algorithms for Multiobjective Permutation Flowshop Scheduling”, IEEE Trans. on Evolutionary Computation, 7, 204–223.
Chang, P.-C, Hsieh, J.-C, and Lin, S.G. (2002). “The development of gradual priority weighting approach for the multi-objective flowshop scheduling problem,” International Journal of Production Economics, 79, 171–183.
Deb, K. (2001) Multi-Objective Optimization using Evolutionary Algorithms, 1st ed., Chichester: John Wiley and Sons, UK.
Liu, J, and Reeves, C. R. (2001). “Constructive and composite heuristic solutions to the P//”C i scheduling problem,” European Journal of Operational Research, 132, 439–452.
Bagchi, T. (1999). Multi objective scheduling by genetic algorithms, Boston: Kluwer Academic Publishers.
Ishibuchi, H, and Murata, T. (1998). “A multi-objective genetic local search algorithm and its application to flowshop scheduling,” IEEE Transactions on Systems, Man and Cybernetics - Part C: Applications and Review, 28, 392–403.
Deo, N. (1997). System simulation with digital computer, New Delhi: Prentice-Hall of India Private Limited, India.
Fonseca, C. M, and Fleming, P. J. (1993). “Genetic Algorithms for Multi-objective Optimization: Formulation, Discussion and Generalization,” In S. Forrest (Editor), Proceedings of the 5th International Conference on Genetic Algorithms, 416–423.
Rajendran, C. (1993). “Heuristic algorithm for scheduling in a flowshop to minimize total flowtime,” International Journal of Production Economics, 29, 65–73.
Taillard, E. (1993). “Benchmarks for basic scheduling problems,” European Journal of Operational Research, 64, 278–285.
Nawaz, M, Enscore, Jr., E.E, and Ham, I. (1983). “A heuristic algorithm for the m-machine, n-job flowshop sequencing problem,” OMEGA, 11, 91–95.
Garey, M. R, Johnson, D. S, and Sethi, R. (1976). “Complexity of flowshop and jobshop scheduling.” Mathematics of Operations Research, 1, 117–129.
Campbell, H.G, Dudek, R.A, and Smith, M.L. (1970). “A heuristic algorithm for the n-job, m-machine sequencing problem,” Management Science, 16, B630–B637.
Ignall, E, and Scharge, L. (1965). “Application of the branch-and-bound technique to some flowshop scheduling problems,” Operations Research, 16, 400–412.
Johnson, S.M. (1954). “Optimal two- and three-stage production schedules with setup times included,” Naval Research Logistics Quarterly, 1, 61–68.