.png){kind=icon}
返回
An exact algorithm for the precedence-constrained single-machine scheduling problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2013.02.048.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors' previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness-tardiness problems, and most instances with 100 jobs of the former problem. (C) 2013 Elsevier B.V. All rights reserved.
Keyword:
Scheduling
Single-machine
Precedence constraints
Exact algorithm
Lagrangian relaxation
Dynamic programming
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
A Parallel Framework for Constraint-Based Bayesian Network Learning via Markov Blanket Discovery
PREAI
分享收藏Credit Market Shocks and Economic Fluctuations: Evidence from Corporate Bond and Stock Markets.png)
OAAI
IF0
OAAI分享收藏
查看更多内容