A framework for the complexity of high-multiplicity scheduling problems

N. Brauner; Y. Crama; A. Grigoriev; J. Van De Klundert

doi:10.1007/s10878-005-1414-7

A framework for the complexity of high-multiplicity scheduling problems

N. Brauner
, Y. Crama
, A. Grigoriev
, J. Van De Klundert

Research output: Contribution to journal › Article › peer-review

31 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	313-323
Number of pages	11
Journal	Journal of Combinatorial Optimization
Volume	9
Issue number	3
DOIs	https://doi.org/10.1007/s10878-005-1414-7
State	Published - May 2005
Externally published	Yes

Keywords

Computational complexity
Design of algorithms
High multiplicity
Scheduling

Access to Document

10.1007/s10878-005-1414-7

Cite this

@article{e7d185f2393e4dcba8962ed21df051e0,

title = "A framework for the complexity of high-multiplicity scheduling problems",

abstract = "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.",

keywords = "Computational complexity, Design of algorithms, High multiplicity, Scheduling",

author = "N. Brauner and Y. Crama and A. Grigoriev and \{Van De Klundert\}, J.",

note = "Funding Information: The second author acknowledges the partial financial support of ONR (grant N00014-92-J-1375), NSF (grant DMS-98-06389), and research grants from the Natural Sciences and Engineering Research Council of Canada (NSERC). The fourth acknowledges support from the EU project APPOL (IST-1999-14084). Funding Information: This research was carried out while the first author was visiting the University of Li{\`e}ge in the framework of a postdoctoral project supported by the European Network DONET (contract number ERB TMRX-CT98-0202).",

year = "2005",

month = may,

doi = "10.1007/s10878-005-1414-7",

language = "English",

volume = "9",

pages = "313--323",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - A framework for the complexity of high-multiplicity scheduling problems

AU - Brauner, N.

AU - Crama, Y.

AU - Grigoriev, A.

AU - Van De Klundert, J.

N1 - Funding Information: The second author acknowledges the partial financial support of ONR (grant N00014-92-J-1375), NSF (grant DMS-98-06389), and research grants from the Natural Sciences and Engineering Research Council of Canada (NSERC). The fourth acknowledges support from the EU project APPOL (IST-1999-14084). Funding Information: This research was carried out while the first author was visiting the University of Liège in the framework of a postdoctoral project supported by the European Network DONET (contract number ERB TMRX-CT98-0202).

PY - 2005/5

Y1 - 2005/5

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Design of algorithms

KW - High multiplicity

KW - Scheduling

UR - https://www.scopus.com/pages/publications/22044439833

U2 - 10.1007/s10878-005-1414-7

DO - 10.1007/s10878-005-1414-7

M3 - Article

AN - SCOPUS:22044439833

SN - 1382-6905

VL - 9

SP - 313

EP - 323

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

A framework for the complexity of high-multiplicity scheduling problems

Abstract

Keywords

Access to Document

Fingerprint

Cite this