Accession Number : ADA134880

Title :   Myopic Heuristics for the Single Machine Weighted Tardiness Problem.

Descriptive Note : Interim rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST

Personal Author(s) : Morton,T E ; Rachamadugu,R M V

PDF Url : ADA134880

Report Date : 28 Nov 1982

Pagination or Media Count : 38

Abstract : 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)

Descriptors :   *Algorithms, *Problem solving, Dynamic programming, Heuristic methods, Optimization, Stopping rules(Mathematics)

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE