Summary
In this chapter, we propose an approach for solving the job shop scheduling problem using a cultural algorithm. Cultural algorithms are evolutionary computation methods that extract domain knowledge during the evolutionary process. Additional to this extracted knowledge, the proposed approach also uses domain knowledge given “a priori” (based on specific domain knowledge available for the job shop scheduling problem). The proposed approach is compared with respect to a Greedy Randomized Adaptive Search Procedure and to a Parallel Genetic Algorithm. The cultural algorithm proposed is able to produce competitive results with respect to the two approaches previously indicated at a significantly lower computational cost than at least one of them and without using any sort of parallel processing.
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
J. Adams, E. Balas, and D. Zawack. The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3):391–401, 1988.
Renata M. Aiex, S. Binato, and Mauricio G.C. Resende. Parallel GRASP with path-relinking for job shop scheduling. Parallel Computing, 29(4):393–430, 2003.
Tapan P. Bagchi. Multiobjective Scheduling by Genetic Algorithms. Kluwer Academic Publishers, New York, September 1999. ISBN 0–7923–8561–6.
Kenneth R. Baker. Introduction to Sequencing and Scheduling. John Wiley & Sons, New York, 1974.
J.W. Barnes and J.B. Chambers. Solving the Job Shop Scheduling Problem using Tabu Search. IIE Transactions, 27(2):257–263, 1995.
J. E. Beasley. OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069–1072, 1990.
C. Bierwirth. A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms. OR Spektrum, 17:87–92, 1995.
J. Carlier and E. Pinson. An algorithm for solving the Job-Shop problem. Management Science, 35(2): 164–176, 1989.
Olivier Catoni. Solving Scheduling Problems by Simulated Annealing. SIAM Journal on Control and Optimization, 36(5): 1539–1575, September 1998.
R. Cheng, M. Gen, and Y. Tsujimura. A tutorial survey of job-shop scheduling problems using genetic algorithms: I. Representation. Computers and Industrial Engineering, 30:983–997, 1996.
R. Cheng, M. Gen, and Y. Tsujimura. A tutorial survey of job-shop scheduling problems using genetic algorithms: II. Hybrid genetic search strategies. Computers and Industrial Engineering, 36(2):343–364, 1999.
Chan-Jin Chung and Robert G. Reynolds. CAEP: An Evolution-based Tool for Real-Valued Function Optimization using Cultural Algorithms. Journal on Artificial Intelligence Tools, 7(3):239–292, 1998.
Carlos A. Coello Coello. Theoretical and Numerical Constraint-Handling Techniques used with Evolutionary Algorithms: A Survey of the State of the Art. Computer Methods in Applied Mechanics and Engineering, 191 (11–12) : 1245–1287, January 2002.
Carlos A. Coello Coello and Ricardo Landa Becerra. Adding Knowledge and Efficient Data Structures to Evolutionary Programming: A Cultural Algorithm for Constrained Optimization. In W.B. Langdon, E. Cantu-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A.C. Schultz, J. F. Miller, E. Burke, and N. Jonoska, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’2002), pages 201–209, San Francisco, California, July 2002. Morgan Kaufmann Publishers.
Alberto Colorni, Marco Dorigo, Vittorio Maniezzo, and Marco Trubian. Ant system for Job-shop scheduling. JORBEL-Belgian Journal of Operations Research, Statistics and Computer Science, 34:39–53, 1994.
Xunxue Cui, Miao Li, and Tingjian Fang. Study of Population Diversity of Multiobjective Evolutionary Algorithm Based on Immune and Entropy Principles. In Proceedings of the Congress on Evolutionary Computation 2001 (CEC’2001), volume 2, pages 1316–1321, Piscataway, New Jersey, May 2001. IEEE Service Center.
W. H. Durham. Caevolution: Genes, Culture, and Human Diversity. Stanford University Press, Stanford, California, 1994.
David B. Fogel. Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. The Institute of Electrical and Electronic Engineers, New York, 1995.
Lawrence J. Fogel. Artificial Intelligence through Simulated Evolution. Forty Years of Evolutionary Programming. John Wiley & Sons, Inc., New York, 1999.
Benjamin Franklin and Marcel Bergerman. Cultural algorithms: Concepts and experiments. In Proceedings of the 2000 Congress on Evolutionary Computation, pages 1245–1251, Piscataway, New Jersey, 2000. IEEE Service Center.
Fred Glover and Manuel Laguna. Tabu Search. Kluwer Academic Publishers, Norwell Massachusetts, 1998.
David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.
José Fernando Gonçalves and N.C. Beirao. Urn algoritmo genético baseado em chaves aleatórias para sequenciamiento de operaçoes. Revista Revista Associação Portuguesa de Desenvolvimento e Investigação Operational,19:123–137, 1999. (in Portuguese).
Emma Hart and Peter Ross. The Evolution and Analysis of a Potential Antibody Library for Use in Job-Shop Scheduling. In David Corne, Marco Dorigo, and Fred Glover, editors, New Ideas in Optimization, pages 185–202. McGraw-Hill, London, 1999.
Emma Hart, Peter Ross, and J. Nelson. Producing robust schedules via an artificial immune system. In Proceedings of the 1998 IEEE International Conference on Evolutionary Computation (ICEC’98), pages 464–469, Anchorage, Alaska, 1998. IEEE Press.
John H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, Michigan, 1975.
Xidong Jin and Robert G. Reynolds. Using Knowledge-Based Evolutionary Computation to Solve Nonlinear Constraint Optimization Problems: a Cultural Algorithm Approach. In 1999 Congress on Evolutionary Computation, pages 1672–1678, Washington, D.C., July 1999. IEEE Service Center.
Albert Jones and Luis C. Rabelo. Survey of Job Shop Scheduling Techniques. NISTIR, National Institute of Standards and Technology, 1998.
E.G. Coffman Jr. Computer and Job Shop Scheduling Theory. John Wiley and Sons, 1976.
Stephen R. Lawrence. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement). Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1984. (Unpublished).
David S. Johnson, Michael R. Garey. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W H Freeman & Co., June 1979. ISBN 0–7167–1045–5.
Zbigniew Michalewicz. A Survey of Constraint Handling Techniques in Evolutionary Computation Methods. In J. R. McDonnell, R. G. Reynolds, and D. B. Fogel, editors, Proceedings of the 4th Annual Conference on Evolutionary Programming, pages 135–155. The MIT Press, Cambridge, Massachusetts, 1995.
Zbigniew Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, New York, third edition, 1996.
Zbigniew Michalewicz and Marc Schoenauer. Evolutionary Algorithms for Constrained Parameter Optimization Problems. Evolutionary Computation, 4(1):1–32, 1996.
Tom Mitchell. Version Spaces: An Approach to Concept Learning. PhD thesis, Computer Science Department, Stanford University, Stanford, California, 1978.
J.F. Muth and G.L. Thompson. Industrial Scheduling. Prentice-Hall, Englewood Cliffs, New Jersey, 1963.
Ryohei Nakano and Takeshi Yamada. Conventional Genetic Algorithm for Job Shop Problems. In R. K. Belew and L. B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms (ICGA-91), pages 474–479, San Mateo, California, 1991. University of California, San Diego, Morgan Kaufmann Publishers.
M. Pinedo. Scheduling: Theory, Algorithms and Systems. Prentice Hall, Englewood Cliffs, 1995.
A. C. Renfrew. Dynamic Modeling in Archaeology: What, When, and Where? In S. E. van der Leeuw, editor, Dynamical Modeling and the Study of Change in Archaelogy. Edinburgh University Press, Edinburgh, Scotland, 1994.
Robert G. Reynolds. An Introduction to Cultural Algorithms. In A. V. Sebald and L. J. Fogel, editors, Proceedings of the Third Annual Conference on Evolutionary Programming, pages 131–139. World Scientific, River Edge, New Jersey, 1994.
Robert G. Reynolds. Cultural algorithms: Theory and applications. In David Corne, Marco Dorigo, and FVed Glover, editors, New Ideas in Optimization, pages 367–377. McGraw-Hill, London, UK, 1999.
S. Ronald. Genetic algorithms and permutation-encoded problems: Diversity preservation and a study of multimodality. PhD thesis, The University of South Australia, 1995.
S. Ronald. Robust encodings in genetic algorithms. In D. Dasgupta & Z. Michalewicz, editor, Evolutionaty Algorithms in Engineering Applications, pages 30–44. Springer-Verlag, 1997.
Franz Rothlauf. Representations for Genetic and Evolutionary Algorithms. Physica-Verlag, New York, 2002.
E. Taillard. Parallel tabu search technique for the jobshop scheduling problem. Technical Report ORWP 89111, Ecole Polytechnique Federale, Lausanne, Switzerland, 1989.
P.J.M. van Laarhoven, E.H.L. Aarts, and J.K. Lenstra. Job shop scheduling by simulated annealing. Operations Research, 40:113–125, 1992.
Takeshi Yamada and Ryohei Nakano. Job-shop scheduling. In A. M. S. Zalzala and P. J. Fleming, editors, Genetic Algorithms in Engineering Systems, IEE Control Engineering Series, chapter 7, pages 134–160. The Institution of Electrical Engineers, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Becerra, R.L., Coello, C.A.C. (2005). A Cultural Algorithm for Solving the Job Shop Scheduling Problem. In: Jin, Y. (eds) Knowledge Incorporation in Evolutionary Computation. Studies in Fuzziness and Soft Computing, vol 167. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-44511-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-44511-1_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-06174-5
Online ISBN: 978-3-540-44511-1
eBook Packages: EngineeringEngineering (R0)