A GRASP-STAR FOR A DIFFICULT SINGLE-MACHINE SCHEDULING PROBLEM

被引：53

作者：

FEO, TA

VENKATRAMAN, K

BARD, JF

机构：

[1] Operations Research Group, Department of Mechanical Engineering, University of Texas at Austin, Austin

来源：

COMPUTERS & OPERATIONS RESEARCH | 1991年 / 18卷 / 08期

关键词：

Machine Shop Practice;

D O I：

10.1016/0305-0548(91)90001-8

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

A greedy randomized adaptive search procedure (GRASP) is presented for an unusually difficult single machine scheduling problem with flow time and earliness Previous methods reported in the literature provide optimal solutions to problems with up to only 14 jobs. GRASP constructs an optimal solution typically within 10 s of CPU time on a personal computer for 58 out of the 60 problems tested with 30 jobs. For the remaining instances, the method provides a solution extremely close to the optimal.

引用

页码：635 / 643

页数：9

共 15 条

[1] AN IMPROVED LOWER BOUND FOR MINIMIZING WEIGHTED COMPLETION TIMES WITH DEADLINES [J].