Acquisition of Dispatching Rules for Job-Shop Scheduling Problem by Artificial Neural Networks Using PSO
Yasumasa Tamura*, Masahito Yamamoto*, Ikuo Suzuki**,
and Masashi Furukawa***
*Graduate School of Information Science and Technology, Hokkaido University, North 14, West 9, Kita-ku, Sapporo, Hokkaido 060-0814, Japan
**Department of Computer Science, Kitami Institute of Technology
***Department of System and Informatics, Faculty of Business Administration and Information Science, Hokkaido Information University
A Job-shop Scheduling Problem (JSP) constitutes the basic scheduling problem that is observed in manufacturing systems. In conventional JSP, feature values of work and queue times are used to formulate dispatching rules for scheduling. In this paper, an Artificial Neural Network (ANN) is used to create an index for job priority. Furthermore, in order to optimize the output of the ANN, Particle Swarm Optimization (PSO) is used in unsupervised learning of the synaptic weights for the ANN. The functions of the proposed method are discussed in this paper.
-  R. W. Conway, W. L. Maxwell, and L. W. Miller, “Theory of scheduling,” Courier Dover Publications, 2003.
-  S. French, “Sequencing and scheduling: an introduction to the mathematics of the job-shop,” Chichester: Ellis Horwood, 1982.
-  E. G. Coffman and J. L. Bruno, “Computer and jobshop scheduling theory,” John Wiley & Sons, 1976.
-  M. Zweben and M. Fox, “Intelligent Scheduling,” Morgan Kaufmann Publishers Inc., 1994.
-  E. Ignall and L. Schrage, “Application of the branch and bound technique to some flow-shop scheduling problems,” Operations research, Vol.13, No.3, pp. 400-412, 1965.
-  M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Mathematics of operations research, Vol.1, No.2, pp. 117-129, 1976.
-  M. R. Garey and D. S. Johonson, “Computers and Intractability – A Guide to the Theory of NPCompleteness,” Freeman and Company, 1979.
-  J. Adams, E. Balas, and D. Zawack, “The shifting bottleneck procedure for job shop scheduling,” Management science, Vol.34, No.3, pp. 391-401, 1988.
-  A. El-Bouri and P. Shah, “A neural network for dispatching rule selection in job shop,” The Int. J. of Advanced Manufacturing Technology, Vol.37, Issue 3, pp. 342-349, 2006.
-  E. Toru, F. Oba, and S. Toyooka, “Dynamic Job Shop Scheduling Using A Neural Network,” Initiatives of Precision Engineering at the Beginning of a Millennium, Springer US, pp. 862-866, 2002.
-  A. H. G. R. Kan, “Machine Scheduling Problems: Classification, Complexity and Computations,” Stenfert Kroese, 1976.
-  B. Giffler and G. L. Thomposon, “Algorithms for Solving Production Scheduling Problems,” Operation Research, Vol.8, No.4, pp. 487-503, 1960.
-  J. H. Holland, “Adaptation in Natural and Artificial Systems,” MIT Press, 1992.
-  H. G. Beyer and H. P. Schwefel, “Evolution Strategies – A comprehensive introduction,” Natural Computing, Vol.1, Issue 1, pp. 3-52, 2002.
-  J. Kennedy and R. Eberhart, “Particle swarm optimization,” IEEE Int. Conf. on Neural Networks, Vol.4, pp. 1942-1948, 1995.
-  J. Yu, S.Wang, and L. Xi, “Evolving artificial neural networks using an improved PSO and DPSO,” Neurocomputing, Vol.71, Issue 4, pp. 1054-1060, 2008.
-  D. Applegate and W. Cook, “A Computational Study of the Job-Shop Scheduling Problem,” ORSA J. on Computing, Vol.3, No.2, pp. 149-156, 1991.