Myopic Heuristics for the Single Machine Weighted Tardiness Problem

摘要

It is well known that the single machine weighted tardiness problem is NP-complete. Hence, it is unlikely that there exist polynomially bounded algorithms to solve this problem. Further, the problem is of great practical significance. We develop myopic heuristics for this problem; these heuristics have been tested against competing heuristics, against a tight lower bound, and where practical, against the optimum, with uniformly good results. Also, these heuristics can be used as dispatching rules in practical situations. In our efforts to seek optimum solutions we develop a hybrid dynamic programming procedure (a modified version of Baker's procedure) which provides lower and upper bounds when it becomes impractical to find the optimum solution. Further, stopping rules are developed for identifying optimal first job/jobs. (Author)