A grasp for single machine scheduling with sequence dependent setup costs and linear delay penalties

被引：27

作者：

Feo, TA

Sarathy, K

McGahan, J

机构：

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

[2] Department of Mechanical Engineering, University of Texas, Austin, TX

来源：

COMPUTERS & OPERATIONS RESEARCH | 1996年 / 23卷 / 09期

关键词：

D O I：

10.1016/0305-0548(95)00084-4

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The single machine scheduling (SMS) problem with sequence dependent setup costs and linear delay penalties is readily found in industrial environments. The problem is of interest in manufacturing because any increase in the efficiency of a heavily utilized machine translates directly into cost savings. However, finding good solutions to this NP-hard combinatorial optimization problem has challenged researchers for years in industry and academia. A novel methodology, Greedy Randomized Adaptive Search Procedure (GRASP), is used in this paper to develop an efficient heuristic for the SMS problem. The empirical results of other researchers are used to validate the heuristic's performance. Previous exact approaches using dynamic programming (DP) with branch and bound provide optimal solutions to SMS instances with up to 20 jobs. A clever implementation of tabu search shows success for problems possessing up to 100 jobs. Our heuristic compares favorably to both the DP and tabu search methods with respect to the solution values obtained and the CPU times required. Copyright (C) 1996 Elsevier Science Ltd

引用

页码：881 / 895

页数：15

共 17 条

[1] OPERATIONS SEQUENCING IN DISCRETE PARTS MANUFACTURING [J].