A framework for the complexity of high-multiplicity scheduling problems

被引：26

作者：

Brauner, N

Crama, Y

Grigoriev, A

Van de Klundert, J

机构：

[1] IMAG, Lab Leibniz, F-38031 Grenoble, France

[2] Univ Liege, HEC Management Sch, B-4000 Liege, Belgium

[3] Maastricht Univ, Dept Quantitat Econ, NL-6200 MD Maastricht, Netherlands

[4] Maastricht Univ, Dept Math, NL-6200 MD Maastricht, Netherlands

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2005年 / 9卷 / 03期

基金：

加拿大自然科学与工程研究理事会; 美国国家科学基金会;

关键词：

computational complexity; design of algorithms; scheduling; high multiplicity;

D O I：

10.1007/s10878-005-1414-7

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The purpose of this note is to propose a complexity framework for the analysis of high multiplicity scheduling problems. Part of this framework relies on earlier work aiming at the definition of output-sensitive complexity measures for the analysis of algorithms which produce "large" outputs. However, different classes emerge according as we look at schedules as sets of starting times, or as related single-valued mappings.

引用

页码：313 / 323

页数：11

共 28 条

[11]

GRIGORIEV A, 2003, THESIS MAASTRICHT U

[12] A POLYNOMIAL ALGORITHM FOR AN INTEGER QUADRATIC NONSEPARABLE TRANSPORTATION PROBLEM [J].

HOCHBAUM, DS ;

SHAMIR, R ;

SHANTHIKUMAR, JG .

MATHEMATICAL PROGRAMMING, 1992, 55 (03) :359-371

[13] MINIMIZING THE NUMBER OF TARDY JOB UNITS UNDER RELEASE TIME CONSTRAINTS [J].

HOCHBAUM, DS ;

SHAMIR, R .

DISCRETE APPLIED MATHEMATICS, 1990, 28 (01) :45-57

[14] STRONGLY POLYNOMIAL ALGORITHMS FOR THE HIGH MULTIPLICITY SCHEDULING PROBLEM [J].

HOCHBAUM, DS ;

SHAMIR, R .

OPERATIONS RESEARCH, 1991, 39 (04) :648-653

[15] Makespan minimization for flow-shop problems with transportation times and a single robot [J].

Hurink, J ;

Knust, S .

DISCRETE APPLIED MATHEMATICS, 2001, 112 (1-3) :199-216

[16] ON GENERATING ALL MAXIMAL INDEPENDENT SETS [J].

JOHNSON, DS ;

YANNAKAKIS, M ;

PAPADIMITRIOU, CH .

INFORMATION PROCESSING LETTERS, 1988, 27 (03) :119-123

[17] LEVEL SCHEDULES FOR MIXED-MODEL ASSEMBLY LINES IN JUST-IN-TIME PRODUCTION SYSTEMS [J].

KUBIAK, W ;

SETHI, S .

MANAGEMENT SCIENCE, 1991, 37 (01) :121-122

[18]

Kubiak W., 1994, International Journal of Flexible Manufacturing Systems, V6, P137, DOI 10.1007/BF01328809

[19] GENERATING ALL MAXIMAL INDEPENDENT SETS - NP-HARDNESS AND POLYNOMIAL-TIME ALGORITHMS [J].

LAWLER, EL ;

LENSTRA, JK ;

KAN, AHGR .

SIAM JOURNAL ON COMPUTING, 1980, 9 (03) :558-565

[20] A polynomial algorithm for multiprocessor scheduling with two job lengths [J].

McCormick, ST ;

Smallwood, SR ;

Spieksma, FCR .

MATHEMATICS OF OPERATIONS RESEARCH, 2001, 26 (01) :31-49

← 1 2 3 →