prof. Dr. Ing. Zdeněk Hanzálek

prof. Dr. Ing. Zdeněk Hanzálek

Ing. Jan Pokorný

Department of Theoretical Computer Science

Manufacturers continuously strive to optimise production schedules to minimise costs. Whilst traditional scheduling models assume a fixed project structure, many real-world projects are inherently flexible, offering multiple approaches to producing various subtasks. The Resource-Constrained Project Scheduling Problem with Alternative Subgraphs (RCPSP-AS) extends conventional scheduling models to facilitate the description and efficient scheduling of such flexible production processes. The problem is stated as follows: There is a set of resources and a project represented by a directed acyclic graph, whose vertices represent activities with predetermined durations and resource demands, and whose edges represent precedence relations between activities. Some activities are branching points where a single successor must be selected. The objective is to select and schedule a valid subset of activities such that resource capacities are not violated, whilst minimising some objective function. This thesis explores the utility of constraint programming for solving RCPSP-AS under two objective functions: the project makespan and weighted tardiness. Building upon prior formulations for integer linear programming, this thesis formulates a constraint definition of RCPSP-AS. An implementation in OR-Tools CP-SAT is presented that beats current best known solutions to 33% ASLIB problem instances with a runtime of just 10 s. Since no dataset is available for the RCPSP-AS problem with weighted tardiness, a new dataset is proposed in this thesis, simulating simplified real-world production lines with ongoing product output. The performance of the developed CP-SAT solution is evaluated on this benchmark. A warmstart procedure for the weighted tardiness problem, using simplified instances to hint at feasible starting solutions, is developed and its impact on solution performance is analysed.