JACIII Vol.17 No.5 pp. 731-738
doi: 10.20965/jaciii.2013.p0731


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

March 20, 2013
June 26, 2013
September 20, 2013
job-shop scheduling problem, dispatching rules, artificial neural network, particle swarm optimization

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.

Cite this article as:
Yasumasa Tamura, Masahito Yamamoto, Ikuo Suzuki, and
and Masashi Furukawa, “Acquisition of Dispatching Rules for Job-Shop Scheduling Problem by Artificial Neural Networks Using PSO,” J. Adv. Comput. Intell. Intell. Inform., Vol.17, No.5, pp. 731-738, 2013.
Data files:
  1. [1] R. W. Conway, W. L. Maxwell, and L. W. Miller, “Theory of scheduling,” Courier Dover Publications, 2003.
  2. [2] S. French, “Sequencing and scheduling: an introduction to the mathematics of the job-shop,” Chichester: Ellis Horwood, 1982.
  3. [3] E. G. Coffman and J. L. Bruno, “Computer and jobshop scheduling theory,” John Wiley & Sons, 1976.
  4. [4] M. Zweben and M. Fox, “Intelligent Scheduling,” Morgan Kaufmann Publishers Inc., 1994.
  5. [5] 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.
  6. [6] 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.
  7. [7] M. R. Garey and D. S. Johonson, “Computers and Intractability – A Guide to the Theory of NPCompleteness,” Freeman and Company, 1979.
  8. [8] 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.
  9. [9] 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.
  10. [10] 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.
  11. [11] A. H. G. R. Kan, “Machine Scheduling Problems: Classification, Complexity and Computations,” Stenfert Kroese, 1976.
  12. [12] B. Giffler and G. L. Thomposon, “Algorithms for Solving Production Scheduling Problems,” Operation Research, Vol.8, No.4, pp. 487-503, 1960.
  13. [13] J. H. Holland, “Adaptation in Natural and Artificial Systems,” MIT Press, 1992.
  14. [14] H. G. Beyer and H. P. Schwefel, “Evolution Strategies – A comprehensive introduction,” Natural Computing, Vol.1, Issue 1, pp. 3-52, 2002.
  15. [15] J. Kennedy and R. Eberhart, “Particle swarm optimization,” IEEE Int. Conf. on Neural Networks, Vol.4, pp. 1942-1948, 1995.
  16. [16] 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.
  17. [17] 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.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 05, 2021