.png){kind=icon}
返回
An exact algorithm for the identical parallel machine scheduling problem
.png){kind=icon}
PRE
AI
DOI：10.1016/S0377-2217(02)00726-9.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The NP-hard classical deterministic scheduling problem of minimizing the makespan on identical parallel machines is considered. The polyhedral structure of the problem is analyzed, and strong valid inequalities are identified for fixed values of the makespan. Thus, partial linear descriptions of the associated polytope are obtained and used to build an exact algorithm. Linear programming relaxations are solved iteratively until the integer solution is reached. The algorithm includes a preprocessing phase which reformulates the problem and simplifies it. Different constructive rules have been tried out in the computation of upper bound values and the incidence of this choice is reported. Computational results show that the proposed algorithm yields, in a short computational time, optimal solutions in almost all tested cases. (C) 2002 Elsevier B.V. All rights reserved.
Keyword:
optimization
polyhedral combinatorics
scheduling
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
没有更多内容
没有更多内容