Constructive heuristics for technology-driven Resource Constrained Scheduling Problem
Paweł B. Myszkowski, Michał Przewoźniczek, Marek Skowroński
Citation: Proceedings of the 2015 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 5, pages 119–127 (2015)
Abstract. In this paper, we define a new practical technology-driven Resource Constrained Scheduling Problem (t-RCPSP). We propose three approaches, applying constructive heuristics to tackle effectively the practical application of RCPSP. In the RCPSP formulation, the constraints are defined to design the tasks in the spaces constructed by non- and renewable resources, without violating the precedence relationships and technologies in real world problem that exists in Plastic and Rubber Processing company. The difficulty of t-RCPSP is NP-hard and we proposed three constructive specialized methods: duration based heuristics (DBH), locally optimal resource usage PEC and NEH heuristic adaptation. The paper presents results of computational experiments that show the effectiveness of the proposed approaches.