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
基金
加拿大自然科学与工程研究理事会; 美国国家科学基金会;
关键词
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 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]   Minimizing service and operation costs of periodic scheduling [J].
Bar-Noy, A ;
Bhatia, R ;
Naor, JS ;
Schieber, B .
MATHEMATICS OF OPERATIONS RESEARCH, 2002, 27 (03) :518-544
[3]   Complexity of one-cycle robotic flow-shops [J].
Brauner, N ;
Finke, G ;
Kubiak, W .
JOURNAL OF SCHEDULING, 2003, 6 (04) :355-371
[4]   The maximum deviation just-in-time scheduling problem [J].
Brauner, N ;
Crama, Y .
DISCRETE APPLIED MATHEMATICS, 2004, 134 (1-3) :25-50
[5]  
BRAUNER N, 2001, 0110 GEMME U LIEG
[6]   High multiplicity in earliness-tardiness scheduling [J].
Clifford, JJ ;
Posner, ME .
OPERATIONS RESEARCH, 2000, 48 (05) :788-800
[7]   Parallel machine scheduling with high multiplicity [J].
Clifford, JJ ;
Posner, ME .
MATHEMATICAL PROGRAMMING, 2001, 89 (03) :359-383
[8]   THE TRAVELING SALESMAN PROBLEM WITH MANY VISITS TO FEW CITIES [J].
COSMADAKIS, SS ;
PAPADIMITRIOU, CH .
SIAM JOURNAL ON COMPUTING, 1984, 13 (01) :99-108
[9]   THE COMPLEXITY OF VERTEX ENUMERATION METHODS [J].
DYER, ME .
MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (03) :381-402
[10]   ON POLYNOMIAL SOLVABILITY OF THE HIGH MULTIPLICITY TOTAL WEIGHTED TARDINESS PROBLEM [J].
GRANOT, F ;
SKORINKAPOV, J .
DISCRETE APPLIED MATHEMATICS, 1993, 41 (02) :139-146