EVALUATION OF A HEURISTIC FOR SCHEDULING INDEPENDENT JOBS ON PARALLEL IDENTICAL PROCESSORS

被引：63

作者：

DOGRAMACI, A ^{[1
]}

SURKIS, J ^{[1
]}

机构：

[1] RUTGERS STATE UNIV,GRAD SCH BUSINESS ADM,NEWARK,NJ 07102

来源：

MANAGEMENT SCIENCE | 1979年 / 25卷 / 12期

关键词：

Compendex;

D O I：

10.1287/mnsc.25.12.1208

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Consideration is given to the problem of scheduling ″n″ independent tasks on ″m″ parallel processors. Each job consists of a single operation with a specific processing time and due data. The processors are identical and the operation of the system is nonpreemptive. The objective is to schedule the jobs in such a way that the total tardiness of the n jobs is as small as possible. For the case of a single processor with n jobs, there exists algorithms which provide optimal solutions. On the other hand currently available optimal scheduling algorithms for multiple processors can handle only small problems. It is found that the heuristic under study provides solutions which are quite close to the optimal ones. The experiments include 560 randomly generated problems that range from ″loose″ to ″tight″ in due dates, with varying numbers of jobs and processors. A nonparametric statistical analysis is presented to generalize the results.

引用

页码：1208 / 1216

页数：9