A methodology for scheduling independent jobs with due dates on identical, parallel machines is presented. 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. This approach provides a lower bound on the cost, which can be used as a measure of suboptimality. According to an implementation for a work center at Pratt and Whitney, most schedules generated are within 1% of the optima with reasonable CPU times. Furthermore, the method provides valuable job interaction information, which shop floor management uses to answer 'what if' questions, to reconfigure the schedule to accommodate dynamic changes, and to schedule new jobs.>

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.>