INVESTIGATING PARALLEL GENETIC ALGORITHMS ON JOB SHOP SCHEDULING PROBLEMS
- Format: Ms Word Document
- Pages: 78
- Price: N 5,000
- Chapters: 1-5
- Download Full and Complete Project
ABSTRACT
This paper describes a GA for job shop scheduling problems. Using the Giffler and Thompson algorithm, we created two new operators, THX crossover and mutation, which better transmit temporal relationships in the schedule. The approach produced excellent results on standard benchmark job shop scheduling problems. We further tested many models and scales of parallel GAs in the context of job shop scheduling problems. In our experiments, the hybrid model consisting of coarse-grain GAs connected in a fine-grain-GA-style topology performed best, appearing to integrate successfully the advantages of coarse-grain and fine-grain GAs.
References
-
[1]Bierwirth, C. “A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms,” OR-Spektrum, Special Issue: Applied Local Search, Pesch, E. and Vo, S. (eds), vol. 17, No. 213, pp. 87–92, 1995.Google Scholar
-
[2]Davis, L., “Job-Shop Scheduling with Genetic Algorithms,” Proc. Int’l Conf. on Genetic Algorithms and their Applications, pp. 136–149, Lawrence Erlbaum, Hillsdale, NJ, 1985.Google Scholar
-
[3]Dorndorf, U. and Pesch, E. “Combining Genetic-and Local Search for Solving the Job Shop Scheduling Problem,” APMOD93 Proc. Preprints, pp. 142–149, Budapest, Hungary, 1993.Google Scholar
-
[4]Dorndorf, U. and Pesch, E. “Evolution Based Learning in a Job Shop Scheduling Environment,” Computers Operations Research, vol. 22, pp. 25–40, 1995.CrossRefGoogle Scholar
-
[5]Fang, H., Ross, P. and Corne, D., “A Promising Genetic Algorithm Approach to Job-Shop Scheduling, Rescheduling, and Open-Shop Scheduling Problems,” Proc. Fifth Int’l Conf. on Genetic Algorithms, pp. 375–382, Morgan Kaufmann, San Mateo, CA, 1993.Google Scholar
-
[6]Giffler, J. and Thompson, G.L., “Algorithms for Solving Production Scheduling Problems,” Operations Research, Vol. 8, pp. 487–503, 1960.Google Scholar
-
[7]Goodman, E. D. An Introduction to GALOPPS, Technical Report GARAGe95-06-01, Genetic Algorithms Research and Applications Group, Michigan State University, 1995.Google Scholar
-
[8]Juels, A. and Wattenberg, M. “Stochastic Hillclimbing as a Baseline Method for Evaluating Genetic Algorithms,” Technical Report csd-94-834, University of California at Berkeley, 1994.Google Scholar
-
[9]Kobayashi, S., Ono, I., and Yamamura, M. “An Efficient Genetic Algorithm for Job Shop Scheduling Problems,” Proc. Sixth Int’l Conf. on Genetic Algorithms, pp. 506–511, Morgan Kaufmann, San Mateo, CA, 1995.Google Scholar
-
[10]Lin, S.-C., Punch, W.F., and Goodman, E.D., “Coarse-Grain Parallel Genetic Algorithms: Categorization and New Approach,” IEEE SPDP, pp. 28–39, 1994.Google Scholar
-
[11]Manderick, B. and Spiessens, P. “Fine-Grained Parallel Genetic Algorithms,” Proc. Third Int’l Conf. on Genetic Algorithms, pp. 428–433, Morgan Kaufmann, San Mateo, CA, 1989.Google Scholar
-
[12]Mattfeld, D. C., Kopfer, H., and Bierwirth, C. “Control of Parallel Population Dynamics by Social-Like Behavior of GA-Individuals,” Parallel Problem Solving from Nature, 3, pp. 15–24, Springer-Verlag, Berlin, Heidelberg, 1994.Google Scholar
-
[13]Muhlenbein, H. “Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization,” Proc. Third Int’l Conf. on Genetic Algorithms, pp. 416–421, Morgan Kaufmann, San Mateo, CA, 1989.Google Scholar
-
[14]Nakano, R. and Yamada, T. “Conventional Genetic Algorithms for Job-Shop Problems,” Proc. Fourth Int’l Conf. on Genetic Algorithms, pp. 474–479, Morgan Kaufmann, San Mateo, CA, 1991.Google Scholar
-
[15]Storer, R. H., Wu, S.D., and Vaccari, R. “New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling,” Management Science, vol. 38, pp. 1495–1509, 1992.Google Scholar
-
[16]Tanese, R., “Distributed Genetic Algorithms,” Proc. Third Int’l Conf. on Genetic Algorithms, pp. 434–440, Morgan Kaufmann, San Mateo, CA, 1989.Google Scholar
-
[17]Whitley, D., Starkweather, T, and Shaner, D., “The Traveling Salesman and Sequence Scheduling: Quality Solutions Using Genetic Edge Recombination,” Handbook of Genetic Algorithms, Davis, L. (ed), pp. 350–372, Van Nostrand Reinhold, New York, NY, 1991.Google Scholar
-
[18]Yamada, T. and Nakano, R. “A Genetic Algorithm Applicable to Large-Scale JobShop Problems,” Parallel Problem Solving from Nature, 2, pp. 281–290, North-Holland, Amsterdam, 1992.Google Scholar
-
[19]Grabowski, J., Nowicki, E., and Zdrzalka, S. “A Block Approach for Single Machine Scheduling with Release Date and Due Date,” European J. Oper. Res., vol. 26, pp. 278–285, 1986.CrossRefGoogle Scholar
-
[20]Adams, J., Balas, E., and Zawack, D. “The Shifting Bottleneck Procedure in Job Shop Scheduling,” Management Science, vol. 34, pp. 391–401, 1988.Google Scholar
-
[21]Caelier, J. and Pinson, E., “An Algorithm for Solving the Job-shop Problem,” Management Science, vol. 35, pp. 164–176, 1989.Google Scholar
-
[22]Baker, J.R. and McMahon, G.B., “Scheduling the General Job-shop,” Management Science, vol. 31, pp. 594–598, 1985.Google Scholar
