Minimizing makespan on identical parallel machines using neural networks

Akyol D., Bayhan G. M.

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

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 4234
  • Basım Tarihi: 2006
  • Dergi Adı: NEURAL INFORMATION PROCESSING, PT 3, PROCEEDINGS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED)
  • Sayfa Sayıları: ss.553-562
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

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.