Schedule generation and reconfiguration for parallel machines

The authors present a methodology for scheduling independent jobs with due dates on identical parallel machines. The jobs have different levels of importance and various processing times on the machines, and the objective is to minimize the total weighted job tardiness of the schedule. Since the problem is NP-hard, the goal is not to obtain the optimal schedule. Rather, an efficient near-optimal algorithm based on Lagrangian relaxation is presented. A nice feature of this approach is that it provides a lower bound on the cost, which can be used as a measure of suboptimality. On most problems tested, results are within 1% of the optima and have reasonable CPU times. Furthermore, the method provides job interaction information, which is then used to provide quick answers to `what if´ questions, to reconfigure the schedule to accommodate dynamic changes, and also to schedule jobs