Algorithms for minclique scheduling problems

被引：20

作者：

Jurisch, B

Kubiak, W

Jozefowska, J

机构：

[1] MEM UNIV NEWFOUNDLAND,FAC BUSINESS ADM,ST JOHNS,NF A1C 5S7,CANADA

[2] POZNAN TECH UNIV,INST COMP SCI,PL-60965 POZNAN,POLAND

来源：

DISCRETE APPLIED MATHEMATICS | 1997年 / 72卷 / 1-2期

关键词：

single/multiple machine scheduling; minimum weighted clique; dynamic programming; spectral algorithms; tabu search;

D O I：

10.1016/S0166-218X(96)00040-6

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We consider a family of well-known scheduling problems that reduce to the problem of finding a minimum weighted clique in a complete weighted graph with negative weights and self-loops allowed. We present a uniform algorithmic approach to finding optimal as well as suboptimal solutions for these problems. Also, we report results of computational tests for suboptimal algorithms developed in the paper.

引用

页码：115 / 139

页数：25

共 23 条

[1]

[Anonymous], 1990, KNAPSACK PROBLEMS

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3] AN ALGORITHM FOR PARTITIONING THE NODES OF A GRAPH [J].