Abstract
In this work we confront the job shop scheduling problem by means of Genetic Algorithms. Our contribution is mainly the generation of a heuristic initial population from domain specific knowledge provided by a probabilitic method. Experimental results show that a Genetic Algorithm that uses a heuristic initial population outperforms not only the same algorithm when using a random initial population, but also other search strategies that exploit the same class of heuristic information.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Dorndorf, U., Pesch, E.: Evolution based learning in a job shop scheduling environment. Computers & Opeerations Research, Vol. 22 (1995) 25–40
Fang, H.L., Ross, P., Corne, D.: A promising genetic algorithm approach to job-shop scheduling, rescheduling, and open-shop scheduling problems. In: Proceedings of the Fifth International Conference On Genetic Algorithms (1993) 375–382
Goldberg, D.: Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, Reading, MA (1985)
Grefenstette, J. J.: Incorporating problem specific knowledge in genetic algorithms. In: Genetic Algorithms and Simulated Annealing. Morgan Kaufmann (1987) 42–60
Larrosa, J., Messeguer, P.: Generic CSP Techniques for the Job-Shop Problem. In: Methodology and Tools in Knowledge-Based Systems. L.N. in Artificial Intelligence 1415. Eds. J. Mira, A.P. del Pobil, and M. Ali. Springer (1998) 46–55
Parreño, J., Gómez, A. Priore, P.: FMS loading and Scheduling problem solving using genetic algorithms. In: INFORMS XXXIV. Barcelona (1997) 156–166.
Puente, J., Varela, R., Vela, C.R. Alonso, C.: A Parallel Logic Programming Approach to Job Shop Scheduling Constraint Satisfaction Problems. AGP’98. La Coruña Spain (1998) 29–41.
Sadeh, N., Fox, M.S.: Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem. Artificial Intelligence, Vol. 86 (1996) 1–41
Storer, R.H., Wu, S.D., Vaccari, R.: Local Search in Problem Space for Sequencing Problems. in: Fandel, G, Gudlledge, T., Jones, A.: New Directions for Operations Research in Manufacturing. Springer Verlag, Berlin Heidelberg (1992) 587–597
Syswerda, G. Schedule Optimization Using Genetic Algorithms. In: Handbook of Genetic Algorithms. Ed. L. Davis, Van Nostrand Reinhold New York (1991) 332–349.
Vela, C. R., Alonso, C. L., Varela, R., Puente, J.: A Genetic Approach to Computing Independent AND Parallelism in Logic Programming. IWANN’97. (1997) 566–575
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Varela, R., Gomez, A., Vela, C.R., Puente, J., Alonso, C. (1999). Heuristic generation of the initial population in solving job shop problems by evolutionary strategies. In: Mira, J., Sánchez-Andrés, J.V. (eds) Foundations and Tools for Neural Modeling. IWANN 1999. Lecture Notes in Computer Science, vol 1606. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0098227
Download citation
DOI: https://doi.org/10.1007/BFb0098227
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66069-9
Online ISBN: 978-3-540-48771-5
eBook Packages: Springer Book Archive