Minimizing makespan on identical parallel machines using neural networks

Akyol D. E., Bayhan G. M.

13th International Conference on Neural Information Processing, ICONIP 2006, Hong Kong, China, 3 - 06 October 2006, pp.553-562 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume:
  • Doi Number: 10.1007/11893295_61
  • City: Hong Kong
  • Country: China
  • Page Numbers: pp.553-562
  • Dokuz Eylül University Affiliated: Yes

Abstract

This paper deals with the problem of minimizing the maximum completion time (makespan) of jobs on identical parallel machines. A Hopfield type dynamical neural network is proposed for solving the problem which is known to be NP-hard even for the case of two machines. A penalty function approach is employed to construct the energy function of the network and time evolving penalty coefficients are proposed to be used during simulation experiments to overcome the tradeoff problem. The results of proposed approach tested on a scheduling problem across 3 different datasets for 5 different initial conditions show that the proposed network converges to feasible solutions for all initialization schemes and outperforms the LPT (longest processing time) rule. © Springer-Verlag Berlin Heidelberg 2006.