A novel Hopfield neural network approach for minimizing total weighted tardiness of jobs scheduled on identical machines

This paper explores fast, polynomial time heuristic approxi- mate solutions to the NP-hard problem of scheduling jobs on N identical machines. The jobs are independent and are allowed to be stopped and restarted on another machine at a later time. They have well-dened deadlines, and relative priorities quantied by non-negative real weights. The objective is to nd schedules which minimize the total weighted tar- diness (TWT) of all jobs. We show how this problem can be mapped into quadratic form and present a polynomial time heuristic solution based on the Hopeld Neural Network (HNN) approach. It is demonstrated, through the results of extensive numerical simulations, that this solution outperforms other popular heuristic methods. The proposed heuristic is both theoretically and empirically shown to be scalable to large problem sizes (over 100 jobs to be scheduled), which makes it applicable to grid computing scheduling, arising in elds such as computational biology, chemistry and nance.