Minimizing makespan on identical parallel machines using neural networks

Akyol D., Bayhan G. M.

NEURAL INFORMATION PROCESSING, PT 3, PROCEEDINGS, vol.4234, pp.553-562, 2006 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 4234
  • Publication Date: 2006
  • Journal Name: NEURAL INFORMATION PROCESSING, PT 3, PROCEEDINGS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED)
  • 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.