.png){kind=icon}
.png){kind=icon}
Return
An iterative time-bucket refinement algorithm for a high-resolution resource-constrained project scheduling problem
.png){kind=icon}
OA
AI
DOI：10.1111/itor.12445.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider a resource-constrained project scheduling problem originating in particle therapy for cancer treatment, in which the scheduling has to be done in high resolution. Traditional mixed integer linear programming techniques such as time-indexed formulations or discrete-event formulations are known to have severe limitations in such cases, that is, growing too fast or having weak linear programming relaxations. We suggest a relaxation based on partitioning time into so-called time-buckets. This relaxation is iteratively solved and serves as basis for deriving feasible solutions using heuristics. Based on these primal and dual solutions and bounds, the time-buckets are successively refined. Combining these parts, we obtain an algorithm that provides good approximate solutions soon and eventually converges to an optimal solution. Diverse strategies for performing the time-bucket refinement are investigated. The approach shows excellent performance in comparison to the traditional formulations and a metaheuristic.
Keywords:
resource-constrained project scheduling
time-bucket relaxation
mixed integer linear programming
matheuristics
particle therapy
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.9
Papers:
1.8K
Citations:
3.7K