A modified genetic algorithm for distributed scheduling problems
Tóm tắt
Genetic algorithms (GAs) have been widely applied to the scheduling and sequencing problems due to its applicability to different domains and the capability in obtaining near-optimal results. Many investigated GAs are mainly concentrated on the traditional single factory or single job-shop scheduling problems. However, with the increasing popularity of distributed, or globalized production, the previously used GAs are required to be further explored in order to deal with the newly emerged distributed scheduling problems. In this paper, a modified GA is presented, which is capable of solving traditional scheduling problems as well as distributed scheduling problems. Various scheduling objectives can be achieved including minimizing makespan, cost and weighted multiple criteria. The proposed algorithm has been evaluated with satisfactory results through several classical scheduling benchmarks. Furthermore, the capability of the modified GA was also tested for handling the distributed scheduling problems.
Tài liệu tham khảo
Cavalieri, S. and Gaiardelli, P. (1998) Hybrid genetic algorithms for a multiple-objective scheduling problem. Journal of Intelligent Manufacturing, 9, 361-367.
Dagli, C. H. and Lee, H. C. (1995) A parallel genetic neuro scheduler for job-shop scheduling, in Proceedings of the 13th International Conference on Production Research, Jerusalem, Freund Publishing House, London, pp. 602-604.
Davis, L. (1985) Job shop scheduling with genetic algorithms, in Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications, Carnegie-Mellon University, Pittsburgh, PA, USA, pp. 136-140.
Dorndorf, U. and Pesch, E. (1995) Evolution based learning in a job shop environment. Computers & Operations Research, 22, 25-40.
Fang, H. L., Ross, P. and Corne, D. (1993) A promising genetic algorithm approach to job-shop scheduling, rescheduling and open-shop scheduling problems, in Proceedings of the 5th International Conference on Genetic Algorithm, Urbana, Illinois, pp. 375-382.
Fang, J. and Xi, Y. (1997) Rolling horizon job shop rescheduling strategy in the dynamic environment. International Journal of Advanced Manufacturing Technology, 13(3), 227-232.
Gen, M. and Cheng, R. (1997) Genetic Algorithms and Engineering Design, John Wiley & Sons, Inc., NY.
Ghedjati, F. (1999) Genetic algorithms for the job-shop scheduling problem with unrelated parallel constraints: Heuristic mixing method machines and precedence. Computers & Industrial Engineering, 37, 39-42.
Goldberg, D. E. (1989) Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Publishing Company, Inc., MA.
Jain, A. K. and ElMaraghy, H. A. (1997) Single process plan scheduling with genetic algorithms. Production Planning and Control, 8(4), 363-376.
Jawahar, N., Aravindan, P. and Ponnambalam, S. G. (1998) A genetic algorithm for scheduling flexible manufacturing systems. International Journal of Advanced Manufacturing Technology, 14, 588-607.
Ladd, S. R. (1996) Genetic Algorithms in C ++, M & T Books, New York.
MacCarthy, B. L. and Liu, J. Y. (1993) Addressing the gap in scheduling research: A review of optimization and heuristic methods in production scheduling. International Journal of Production Research, 31(1), 59-79.
Man, Tang, K. S. and Kwong, S. (1996) Genetic algorithms: Concepts and applications. IEEE Transaction on Industrial Electronics, 43(5), 519-534.
Mori, M. and Tseng, C. C. (1997) Genetic algorithm for multi-mode resource constrained project scheduling problem. European Journal of Operation Research, 100(1), 134-141.
Muth, J. F. and Thompson, G. L. (1963) Industrial Scheduling, Prentice-Hall, Englewood Cliffs.
Nakano, R. and Yamada, T. (1991) Conventional genetic algorithm for job shop problems, in Proceedings of the 4th International Conference on Genetic Algorithm, San Diego, pp. 474-479.
Rosenau, M. D. (1996) The PDMA Handbook of New Product Development, Wiley, New York.
Storer, R. H. and Wu, S. D. (1993) Genetic algorithm in problem space for sequencing problems, Operations Research in Production, Planning and Control, Fandel et al. (eds.), Springer-Verlang Publisher, pp. 584-597.
Wang, B. (1997) Integrated product, process and enterprise design, Chapman & Hall, London.
Yamada, T. and Nakano, R. (1992) A genetic Algorithm applicable to large-scale job-shop problems, Parallel Problem Solving from Nature, 2nd Workshop, Brussels, Belgium, Manner and Manderick (eds.), Elsevier Science Publishers, pp. 281-290.
Yamada, T. and Nakano, R. (1995) A genetic algorithm with multi-step crossover for job-shop scheduling problems, in Proceedings of the 1st International Conference on Genetic Algorithms in Engineering Systems, Innovations and Applications, University of Sheffield, UK, pp. 146-151.