[Back]

G. Raidl:
"An Iterative Time-Bucket Refinement Algorithm for a Resource-Constrained Project Scheduling Problem";
Talk: TU Graz, Institute for Discrete Mathematics, TU Graz, Institute for Discrete Mathematics (invited); 2017-03-21.

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, i.e., 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 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 doing the time-bucket refinement are investigated. The approach shows excellent performance in comparison to the traditional formulations and a GRASP metaheuristic.