.png){kind=icon}
返回
Dominance-based linear formulation for the Anchor-Robust Project Scheduling Problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2021.02.034.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In project scheduling under processing times uncertainty, the Anchor-Robust Project Scheduling Problem is to find a baseline schedule of bounded makespan and a max-weight subset of jobs whose starting times are guaranteed. The problem was proven NP-hard even for budgeted uncertainty. In the present work we design mixed-integer programming (MIP) formulations that are valid for a variety of uncertainty sets encompassing budgeted uncertainty. A new dominance among solutions is proposed, resulting into an MIP formulation. We further study the combinatorial structure of the problem. Non-trivial polynomial cases under budgeted uncertainty are exhibited, where the dominance-based formulation yields a polyhedral characterization of integer solutions. In more general cases, the dominance-based formulation is shown to be tighter than all previously known formulations. In numerical experiments we investigate how the formulation performs on instances around the polynomial cases, for both budgeted uncertainty sets and more elaborate uncertainty sets involving several budgets. (c) 2021 Elsevier B.V. All rights reserved.
Keyword:
Project scheduling
Combinatorial optimization
Mixed-integer programming
Robust 2-stage optimization
Polyhedral characterization
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏
查看更多内容