A Large Neighborhood Search Heuristic for the Cumulative Scheduling Problem with Time-Dependent Resource Availability

Nhan Quy Nguyen (1) , Farouk Yalaoui (1) , Lionel Amodeo (1) , Hicham Chehade (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

This paper addresses the cumulative scheduling problem with time-dependent total resource availability. In this problem, tasks are completed by accumulating enough amounts of resources. Our model is time-indexed due to the variation of the total resource availability. A Large neighborhood search (LNS) approach is developed. As an extension of our previous work, this paper contributes a new request removal method and an integration of a simulated annealing procedure to the LNS. Through the computational results, those modifications reduce the derived gap between the worst solutions and also the average derived gap.

Domains: Computer Science [cs]; Operations Research [cs.RO]

Nhan Quy Nguyen, Farouk Yalaoui, Lionel Amodeo, Hicham Chehade. A Large Neighborhood Search Heuristic for the Cumulative Scheduling Problem with Time-Dependent Resource Availability. Intelligent Information and Database Systems, 10752, pp.707-715, 2018, Lecture Notes in Computer Science, 978-3-319-75420-8. ⟨10.1007/978-3-319-75420-8_66⟩. ⟨hal-02477188⟩