Models, algorithms and complexity for scheduling under uncertainty: On the tradeoffs between performance and adaptivity

不确定性下调度的模型、算法和复杂性:性能和适应性之间的权衡

基本信息

项目摘要

The vast majority of scheduling research assumes complete information about the problem instance. In most real-world applications, however, uncertain input that is gradually revealed during schedule execution is an omnipresent issue. Unlike its deterministic counterpart, the diverse field of scheduling under uncertainty is not well understood from an algorithmic point of view. Moreover, most current approaches on algorithm’s design assume arbitrary algorithmic flexibility and neglect practice-driven limitations on adaptivity. In this project we design algorithmic and analytic tools for solving important scheduling problems with uncertain input, such as unreliable machines, stochastic job processing times, or unknown job arrival times. Our major goal is to study thoroughly the tradeoff between the performance of an algorithm and the amount of adaptivity it requires. On the one hand, we aim for best possible algorithms which are potentially highly dynamic, i.e., scheduling decisions may adapt arbitrarily to the instantiated problem data. On the other hand, we are interested in good but simple algorithms that respect practice-driven adaptivity restrictions. We analyze what kind and what amount of adaptivity an algorithm needs to achieve a certain performance guarantee. Our main tools come from approximation algorithms, combinatorial optimization, mathematical programming, and probability theory, and our investigations integrate the concepts of universal and robust solutions. We study fundamental theoretical questions on practically relevant algorithms for problems from stochastic, online, and real-time scheduling.
绝大多数调度研究都假设有关问题实例的完整信息。然而,在大多数现实世界的应用程序中,在计划执行期间逐渐揭示的不确定输入是一个普遍存在的问题。与确定性的对应物不同,从算法的角度来看,不确定性下的调度的不同领域并没有得到很好的理解。此外,当前大多数算法设计方法都假设任意的算法灵活性,而忽略了实践驱动的适应性限制。在这个项目中,我们设计了算法和分析工具,用于解决具有不确定输入的重要调度问题,例如不可靠的机器、随机的作业处理时间或未知的作业到达时间。我们的主要目标是彻底研究算法性能与其所需的适应性之间的权衡。一方面,我们的目标是获得潜在的高度动态的最佳算法,即调度决策可以任意适应实例化的问题数据。另一方面,我们对良好但简单的算法感兴趣,这些算法尊重实践驱动的适应性限制。我们分析算法需要什么样的自适应性和多少自适应性才能实现一定的性能保证。我们的主要工具来自近似算法、组合优化、数学规划和概率论,我们的研究整合了通用和鲁棒解决方案的概念。我们研究随机、在线和实时调度问题的实际相关算法的基本理论问题。

项目成果

期刊论文数量(41)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks
  • DOI:
    10.1109/rtss.2013.31
  • 发表时间:
    2013-12
  • 期刊:
  • 影响因子:
    0
  • 作者:
    V. Bonifaci;A. Marchetti-Spaccamela;Nicole Megow;Andreas Wiese
  • 通讯作者:
    V. Bonifaci;A. Marchetti-Spaccamela;Nicole Megow;Andreas Wiese
Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
  • DOI:
    10.1007/978-3-662-48350-3_73
  • 发表时间:
    2017-01
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Nicole Megow;Julie Meißner;M. Skutella
  • 通讯作者:
    Nicole Megow;Julie Meißner;M. Skutella
Universal Sequencing on a Single Machine
  • DOI:
    10.1007/978-3-642-13036-6_18
  • 发表时间:
    2010-06
  • 期刊:
  • 影响因子:
    0
  • 作者:
    L. Epstein;Asaf Levin;A. Marchetti-Spaccamela;Nicole Megow;Julián Mestre;M. Skutella;L. Stougie
  • 通讯作者:
    L. Epstein;Asaf Levin;A. Marchetti-Spaccamela;Nicole Megow;Julián Mestre;M. Skutella;L. Stougie
On Eulerian extensions and their application to no-wait flowshop scheduling
欧拉扩展及其在无等待流水作业调度中的应用
  • DOI:
    10.1007/s10951-011-0241-1
  • 发表时间:
  • 期刊:
  • 影响因子:
    2
  • 作者:
    W. Höhn;T. Jacobs;N. Megow.
  • 通讯作者:
    N. Megow.
The Power of Recourse for Online MST and TSP
在线 MST 和 TSP 的追索权
  • DOI:
    10.1137/130917703
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
    N. Megow;M. Skutella;J. Verschae;A. Wiese.
  • 通讯作者:
    A. Wiese.
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Professorin Dr. Nicole Megow其他文献

Professorin Dr. Nicole Megow的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Professorin Dr. Nicole Megow', 18)}}的其他基金

Optimization under Explorable Uncertainty
可探索的不确定性下的优化
  • 批准号:
    517912373
  • 财政年份:
  • 资助金额:
    --
  • 项目类别:
    Research Grants

相似国自然基金

固定参数可解算法在平面图问题的应用以及和整数线性规划的关系
  • 批准号:
    60973026
  • 批准年份:
    2009
  • 资助金额:
    32.0 万元
  • 项目类别:
    面上项目
Computational Methods for Analyzing Toponome Data
  • 批准号:
    60601030
  • 批准年份:
    2006
  • 资助金额:
    17.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Algorithms and Complexity for Economic Environments (ACEE)
经济环境的算法和复杂性 (ACEE)
  • 批准号:
    EP/Y003624/1
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Research Grant
FET: SMALL: Quantum algorithms and complexity for quantum algebra and topology
FET:小:量子算法以及量子代数和拓扑的复杂性
  • 批准号:
    2330130
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Communication Complexity of Graph Algorithms (GraphCom)
图算法的通信复杂性(GraphCom)
  • 批准号:
    EP/X03805X/1
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Research Grant
CIF: SMALL: Theoretical Foundations of Partially Observable Reinforcement Learning: Minimax Sample Complexity and Provably Efficient Algorithms
CIF:SMALL:部分可观察强化学习的理论基础:最小最大样本复杂性和可证明有效的算法
  • 批准号:
    2315725
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Tensor decomposition methods for multi-omics immunology data analysis
用于多组学免疫学数据分析的张量分解方法
  • 批准号:
    10655726
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
FET: Medium: Quantum Algorithms, Complexity, Testing and Benchmarking
FET:中:量子算法、复杂性、测试和基准测试
  • 批准号:
    2311733
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
CAREER: Reinforcement Learning-Based Control of Heterogeneous Multi-Agent Systems in Structured Environments: Algorithms and Complexity
职业:结构化环境中异构多智能体系统的基于强化学习的控制:算法和复杂性
  • 批准号:
    2237830
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
i-AKC: Integrated AIRR Knowledge Commons
i-AKC:综合 AIRR 知识共享
  • 批准号:
    10712558
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
Optimizing blood biopsy in cancers with low mutation burden and high structural complexity
优化突变负荷低、结构复杂性高的癌症的血液活检
  • 批准号:
    10789700
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
CAREER: Fine-Grained Complexity and Algorithms for Structured Linear Equations and Linear Programs
职业:结构化线性方程和线性程序的细粒度复杂性和算法
  • 批准号:
    2238682
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了