Knowledge Insertion: an Efficient Approach to Reduce Search Effort in Evolutionary Scheduling

Authors

  • Daniel Pandolfi División Tecnología, Unidad Académica Caleta Olivia, Universidad Nacional de La Patagonia Austral , Santa Cruz, Argentina
  • Marta Graciela Lasso División Tecnología, Unidad Académica Caleta Olivia, Universidad Nacional de La Patagonia Austral , Santa Cruz, Argentina
  • María Eugenia de San Pedro División Tecnología, Unidad Académica Caleta Olivia, Universidad Nacional de La Patagonia Austral , Santa Cruz, Argentina
  • Andrea Villagra División Tecnología, Unidad Académica Caleta Olivia, Universidad Nacional de La Patagonia Austral , Santa Cruz, Argentina
  • Raúl Hector Gallard Lab. de Investigación y Desarrollo en Inteligencia Computacional (LIDIC), Universidad Nacional de San Luis, San Luis, Argentina

Keywords:

Average tardiness scheduling problem, Evolutionary scheduling, conventional heuristics, problem specific knowledge

Abstract

Evolutionary algorithms (EAs) are merely blind search algorithms, which only make use of the relative fitness of solutions, but completely ignore the nature of the problem. Their performance can be improved by using new multirecombinative approaches, which provide a good balance between exploration and exploitation. Even though in difficult problems with large search spaces a considerable number of evaluations are required to arrive to near-optimal solutions. On the other hand specialized heuristics are based on some specific features of the problem, and the solution obtained can include some features of optimal solutions. If we insert in the evolutionary algorithm the problem specific knowledge embedded in good solutions (seeds), coming from some other heuristic or from the evolutionary process itself, we can expect that the algorithm will be guided to promising subspaces avoiding a large search. This work shows alternative ways to insert knowledge in the search process by means of the inherent information carried by solutions coming from that specialised heuristic or gathered by the evolutionary process itself. To show the efficiency of this approach, the present paper compares the performance of multirecombined evolutionary algorithms with and without knowledge insertion when applied to selected instances of the Average Tardiness Problem in a single machine environment.

Downloads

Download data is not yet available.

References

[1] Beasley J.E. “Common Due Date Scheduling”, OR Library, http://mscmga.ms.ic.ac.uk/
[2] Crauwels H.A.J., Potts C.N. and Van Wassenhove L.N. “Local search heuristics for the single machine total weighted tardiness scheduling problem”, Informs Journal on Computing 10, 341-350. 1998.
[3] Chen T. and Gupta M., “Survey of scheduling research involving due date determination decision”, European Journal of Operational Research, vol 38, pp. 156-166, 1989.
[4] Eiben A.E., Raué P.E., and Ruttkay Z., “Genetic algorithms with multi-parent recombination”, Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, Springer-Verlag, 1994, number 866 in LNCS, pp. 78-87.
[5] Eiben A.E., Van Kemenade C.H.M., and Kok J.N., “Orgy in the computer: Multi-parent reproduction in genetic algorithms”. Proceedings of the 3rd European Conference on Artificial Life, Springer-Verlag, 1995, number 929 in LNAI, pages 934-945.
[6] Eiben A.E. and. Bäck Th., “An empirical investigation of multi-parent recombination operators in evolution strategies”. Evolutionary Computation, 5(3):347-365, 1997.
[7] Esquivel S., Leiva A., Gallard R., “Multiple Crossover per Couple in Genetic Algorithms”, Proceedings of the Fourth IEEE Conference on Evolutionary Computation (ICEC'97), Indianapolis, USA, April 1997, pp 103-106.
[8] Esquivel S., Leiva A., Gallard R., “Couple Fitness Based Selection with Multiple Crossover per Couple in Genetic Algorithms“. Proceedings of the International Symposium on Engineering of Intelligent Systems (EIS´98), La Laguna, Tenerife, Spain, February 1998, pp 235-241.
[9] Esquivel S., Leiva H., Gallard R., “Multiple crossovers between multiple parents to improve search in evolutionary algorithms”, Proceedings of the Congress on Evolutionary Computation (IEEE). Washington DC, 1999, pp 1589-1594.
[10] Michalewicz M., “Genetic Algorithms + Data Structures = Evolution Programs”. Third revised edition, Springer, 1996.
[11] Morton T., Pentico D., “Heuristic scheduling systems”, Wiley series in Engineering and technology management. John Wiley and Sons, INC, 1993.
[12] Pandolfi D., Vilanova G., M. De San Pedro, A. Villagra, “Multirecombining studs and immigrants in evolutionary algorithm to face earliness-tardiness scheduling problems”. Proceedings of the International Conference in Soft Computing. University of Paisley, Scotland, U.K., June2001, pp.138
[13] Pandolfi D., De San Pedro M., Villagra A., Vilanova G., Gallard R.- “Studs mating immigrants in evolutionary algorithm to solve the earliness-tardiness scheduling problem” . In Cybernetics and Systems of Taylor and Francis Journal, Vol. 33 Nro. 4, pp 391-400 (U.K.) June 2002.
[14] Pandolfi D. De San Pedro M. M., Villagra A., Vilanova G., R. Gallard – “Multirecombining random and seed immigrants in evolutionary algorithms to solve W-T scheduling problems”- In proceedings of CSITeA02, pp 133-138, Iguazu Falls, June 2002, Brazil.
[15] Pinedo M., “Scheduling: Theory, Algorithms and System.” First edition Prentice Hall, 1995.
[16] Rachamadugu R.V., Morton T.E., “Myopic heuristics for the single machine weighted tardiness problem”. GSIA, Carnigie Mellon University, Pittsburgh, PA. 1982., Working paper 30-82-83.
[17] Reeves C., “A genetic algorithm for flow shop sequencing”, Computers and Operations Research, vol 22, pp5-13, 1995.
[18] Tsujimura Y., Gen M., Kubota E.: “Flow shop scheduling with fuzzy processing time using genetic algorithms”. The 11th Fuzzy Systems Symposium, Okinawa,. 1995,.pp 248-252.

Downloads

Published

2004-08-02

How to Cite

Pandolfi, D., Lasso, M. G., San Pedro, M. E. de, Villagra, A., & Gallard, R. H. (2004). Knowledge Insertion: an Efficient Approach to Reduce Search Effort in Evolutionary Scheduling. Journal of Computer Science and Technology, 4(02), p. 109–114. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/903

Issue

Section

Original Articles

Most read articles by the same author(s)