Optimization of Genetic Operators for Scheduling Problems

António Ferrolho; Manuel Crisóstomo

doi:10.20965/jaciii.2007.p1092

single-jc.php

« previous

JACIII Vol.11 No.9 pp. 1092-1098

doi: 10.20965/jaciii.2007.p1092

(2007)

Paper:

Views over last 60 days: 417

Optimization of Genetic Operators for Scheduling Problems

António Ferrolho^* and Manuel Crisóstomo^**

^*Dept. of Electrotechnical Engineering, Superior School of Technology, Polytechnic Institute of Viseu, 3504-510 Viseu, Portugal

^**Institute of Systems and Robotics, Dept. of Electrical and Computer Science Engineering, University of Coimbra, Polo II, 3030-290 Coimbra, Portugal

Received:

February 15, 2007

Accepted:

June 14, 2007

Published:

November 20, 2007

Keywords:

scheduling, genetic algorithms, crossover operators, mutation operators

Abstract

Genetic algorithms (GA) can provide good solutions for scheduling problems. But, when a GA is applied to scheduling problems various crossovers and mutations operators can be applicable. This paper presents and examines a new concept of genetic operators for scheduling problems. A software tool called hybrid and flexible genetic algorithm (HybFlexGA) was developed to examine the performance of various crossover and mutation operators by computing simulations of job scheduling problems.

Cite this article as:

A. Ferrolho and M. Crisóstomo, “Optimization of Genetic Operators for Scheduling Problems,” J. Adv. Comput. Intell. Intell. Inform., Vol.11 No.9, pp. 1092-1098, 2007.

Data files:

References

[1] T. Abdul-Razaq, C. Potts, and L. V. Wassenhove, “A survey for the Single-Machine Scheduling Total WT Scheduling Problem,” Discrete Applied Mathematics, 26, pp. 235-253, 1990.
[2] K. Baker, “Introduction to Sequencing and Scheduling,” Wiley, New York, 1974.
[3] A. Ferrolho and M. Crisóstomo, “Genetic Algorithms: concepts, techniques and applications,” WSEAS Transactions on Advances in Engineering Education, 2, pp. 12-19, 2005.
[4] A. Ferrolho and M. Crisóstomo, “Scheduling and Control of Flexible Manufacturing Cells Using Genetic Algorithms,” WSEAS Transactions on Computers, 4, pp. 502-510, 2005.
[5] D. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison-Wesley, 1989.
[6] E. Lawer, “A pseudopolinomial algorithm for Sequencing Jobs to Minimize Total Tardiness,” Annals of Discrete Mathematics, pp. 331-342, 1977.
[7] A. Madureira, C. Ramos, and S. Silva, “A GA based scheduling system for dynamic single machine problem,” In Proc. of the 4th IEEE Int. Symposium on Assembly and Task Planning Soft Research Park, pp. 262-267, 2001.
[8] B. Manderick and P. Spiessens, “How to select genetic operators for combinatorial optimization problems by analyzing their fitness landscape,” J. M. Zurada, R. J. Marks II, and C. J. Robinson (Eds.), Computational Intelligence Imitating Life, IEEE Press, pp. 170-181, 1994.
[9] T. Murata and H. Ishibuchi, “Performance Evaluation of Genetic Algorithms for Flowshop Scheduling Problems,” In Proc. of the 1st IEEE Int. Conf. on Evolutionary Computation, pp. 812-817, 1994.
[10] T. Murata and H. Ishibuchi, “Positive and Negative Combination Effects of Crossover and Mutation Operators in Sequencing Problems,” In Proc. IEEE Int. Conf. Evol. Computation, pp. 170-175, 1996.
[11] J. Oliver, D. Smith, and J. Holland, “A study of permutation crossover operators on the traveling salesman problem,” In Proc. of the Second ICGA, pp. 224-230, 1987.
[12] C. Potts and L. V. Wassenhove, “Single Machine Tardiness Sequencing Heuristics,” IIE Transactions, 23(4), pp. 346-354, 1991.
[13] G. Syswerda, “Scheduling optimization using genetic algorithms,” L. Davis (Ed.), Handbook of Genetic Algorithms, pp. 332-349, 1991.
[14] M. E. Thomas and D. W. Pentico, “Heuristic Scheduling Systems,” John Wiley & Sons, 1993.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] T. Abdul-Razaq, C. Potts, and L. V. Wassenhove, “A survey for the Single-Machine Scheduling Total WT Scheduling Problem,” Discrete Applied Mathematics, 26, pp. 235-253, 1990.

[2] [2] K. Baker, “Introduction to Sequencing and Scheduling,” Wiley, New York, 1974.

[3] [3] A. Ferrolho and M. Crisóstomo, “Genetic Algorithms: concepts, techniques and applications,” WSEAS Transactions on Advances in Engineering Education, 2, pp. 12-19, 2005.

[4] [4] A. Ferrolho and M. Crisóstomo, “Scheduling and Control of Flexible Manufacturing Cells Using Genetic Algorithms,” WSEAS Transactions on Computers, 4, pp. 502-510, 2005.

[5] [5] D. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison-Wesley, 1989.

[6] [6] E. Lawer, “A pseudopolinomial algorithm for Sequencing Jobs to Minimize Total Tardiness,” Annals of Discrete Mathematics, pp. 331-342, 1977.

[7] [7] A. Madureira, C. Ramos, and S. Silva, “A GA based scheduling system for dynamic single machine problem,” In Proc. of the 4th IEEE Int. Symposium on Assembly and Task Planning Soft Research Park, pp. 262-267, 2001.

[8] [8] B. Manderick and P. Spiessens, “How to select genetic operators for combinatorial optimization problems by analyzing their fitness landscape,” J. M. Zurada, R. J. Marks II, and C. J. Robinson (Eds.), Computational Intelligence Imitating Life, IEEE Press, pp. 170-181, 1994.

[9] [9] T. Murata and H. Ishibuchi, “Performance Evaluation of Genetic Algorithms for Flowshop Scheduling Problems,” In Proc. of the 1st IEEE Int. Conf. on Evolutionary Computation, pp. 812-817, 1994.

[10] [10] T. Murata and H. Ishibuchi, “Positive and Negative Combination Effects of Crossover and Mutation Operators in Sequencing Problems,” In Proc. IEEE Int. Conf. Evol. Computation, pp. 170-175, 1996.

[11] [11] J. Oliver, D. Smith, and J. Holland, “A study of permutation crossover operators on the traveling salesman problem,” In Proc. of the Second ICGA, pp. 224-230, 1987.

[12] [12] C. Potts and L. V. Wassenhove, “Single Machine Tardiness Sequencing Heuristics,” IIE Transactions, 23(4), pp. 346-354, 1991.

[13] [13] G. Syswerda, “Scheduling optimization using genetic algorithms,” L. Davis (Ed.), Handbook of Genetic Algorithms, pp. 332-349, 1991.

[14] [14] M. E. Thomas and D. W. Pentico, “Heuristic Scheduling Systems,” John Wiley & Sons, 1993.

Optimization of Genetic Operators for Scheduling Problems

António Ferrolho* and Manuel Crisóstomo**

António Ferrolho^* and Manuel Crisóstomo^**