INVESTIGATING PARALLEL GENETIC ALGORITHMS ON JOB SHOP SCHEDULING PROBLEMS

INVESTIGATING PARALLEL GENETIC ALGORITHMS ON JOB SHOP SCHEDULING PROBLEMS

 

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. [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. [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. [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. [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. [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. [6]
    Giffler, J. and Thompson, G.L., “Algorithms for Solving Production Scheduling Problems,” Operations Research, Vol. 8, pp. 487–503, 1960.Google Scholar
  7. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [22]
    Baker, J.R. and McMahon, G.B., “Scheduling the General Job-shop,” Management Science, vol. 31, pp. 594–598, 1985.Google Scholar

Download Full and Complete Project

About admin

Check Also

DESIGN AND IMPLEMENTATION OF AN ONLINE BARCODE ATTENDANCE SYSTEM

FREE PROJECT TOPICS ON DESIGN AND IMPLEMENTATION OF AN ONLINE BARCODE ATTENDANCE SYSTEM Format: Ms …

DESIGN AND CONSTRUCTION OF CONTENT BASED IMAGE DIGITAL DETECTIVE SYSTEM

DESIGN AND CONSTRUCTION OF CONTENT BASED IMAGE DIGITAL DETECTIVE SYSTEM Format: Ms Word Document Pages: …

AUTOMATED PASSENGER LOADING SYSTEM (A CASE STUDY OF CHISCO TRANSPORTATION COMPANY OWERRI, IMO STATE)

AUTOMATED PASSENGER LOADING SYSTEM (A CASE STUDY OF CHISCO TRANSPORTATION COMPANY OWERRI, IMO STATE) Format: …

DESIGN AND IMPLEMENTATION OF AN ONLINE DRIVING SCHOOL MANAGEMENT SYSTEM (A CASE STUDY OF AA DRIVING SCHOOL, UYO)

DESIGN AND IMPLEMENTATION OF AN ONLINE DRIVING SCHOOL MANAGEMENT SYSTEM (A CASE STUDY OF AA …

DESIGN AND IMPLEMENTATION OF A COMPUTERIZED RECYCLING SYSTEM FOR PROTECTING THE GREEN ENVIRONMENT

DESIGN AND IMPLEMENTATION OF A COMPUTERIZED RECYCLING SYSTEM FOR PROTECTING THE GREEN ENVIRONMENT Format: Ms …

DESIGN AND IMPLEMENTATION OF A COMPUTERIZED GRADE EVALUATION SYSTEM (CASE STUDY OF UNIVERSITY OF IBADAN)

DESIGN AND IMPLEMENTATION OF A COMPUTERIZED GRADE EVALUATION SYSTEM (CASE STUDY OF UNIVERSITY OF IBADAN) …

Leave a Reply

Your email address will not be published. Required fields are marked *