University of Twente Student Theses


Planning in supply networks using aggregated resource feasibility

Mauritz, R.R. (2022) Planning in supply networks using aggregated resource feasibility.

[img] PDF
Abstract:We focus on resolving time and resource conflicts in manufacturing plans while minimising the makespan. This problem is a special case of the Manufacturing Planning Problem (MPP), which can be reduced to the Resource Constrained Project Scheduling Problem (RCPSP). In order to better capture practical settings, we distinguish between detailed and aggregated resource constraints and propose a relaxation of the RCPSP to which we refer as the Window Aggregated Resource Constrained Project Scheduling Problem (WARCPSP). The WARCPSP defines resource feasibility via aggregated resource constraints by requiring that for any time window in a pre-defined window configuration, the total resource requirement does not exceed the total availability. By adjusting the window configuration to practical needs, the planner is able to fully determine the time-dependent level of aggregation. We develop a heuristic Conflict Resolution Algorithm (CRA) that resolves time and resource conflicts in a manufacturing plan using the WARCPSP model. It is designed such that it can be applied to a manufacturing plan at any time and to specific parts only, increasing its practical usage. The algorithm resolves time conflicts by using a special earliest start procedure. Resource conflicts are then resolved in an iterative, time-advancing fashion, each iteration consisting of a forward and a backward pass. Inspired by disjunctive arc-based methods and minimal forbidden sets, the CRA moves activities forward by adding a precedence relation, using priority rules to make local decisions. This forward pass is then followed by a backward pass, which tries to improve the schedule by backward shifting activities. By means of experiments on instances of the PSPLIB library, we show that the CRA is able to produce close-to-optimal solutions with an average run-time that is within the order of seconds, allowing the CRA to be used in a real-time setting to support human planners.
Item Type:Essay (Master)
Togetr B.V., Veenendaal, The Netherlands
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics, 54 computer science
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page