期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 152, 期 3, 页码 758-769出版社
ELSEVIER
DOI: 10.1016/S0377-2217(02)00726-9
关键词
optimization; polyhedral combinatorics; scheduling
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据