.png){kind=icon}
Return
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}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Scheduling
Single-machine
Precedence constraints
Exact algorithm
Lagrangian relaxation
Dynamic programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
Cited Papers
ShareSaveShareSaveShareSaveA Parallel Framework for Constraint-Based Bayesian Network Learning via Markov Blanket Discovery
PREAI
ShareSaveShareSaveCredit Market Shocks and Economic Fluctuations: Evidence from Corporate Bond and Stock Markets.png)
OAAI
IF0
OAAIShareSave
View more