Euraxess code:
https://www.euraxess.cz/jobs/415419
Scheduling problems such as the Resource-Constrained Project Scheduling Problem (RCPSP) remains one of the central challenges in combinatorial optimization, particularly in large-scale industrial settings. As instance sizes grow and objective functions become more sophisticated, classical exact or single-strategy heuristic approaches are no longer sufficient. Future progress requires carefully designed hybrid and parallel solution frameworks.
Today, Large Neighborhood Search (LNS) is the dominant heuristic paradigm in modern constraint programming (CP) scheduling solvers such as IBM ILOG CP Optimizer, Google OR-Tools, and OptalCP. Compared to traditional local search, LNS offers improved diversification and a stronger ability to escape local optima by iteratively destroying and repairing large fragments of a schedule. In parallel, Failure-Directed Search (FDS) provides a systematic mechanism for exploring the entire search space using a fail-first principle to prove infeasibility or optimality.
While this combination is highly effective for classical objectives such as makespan minimization, CP solvers become less efficient when handling more complex criteria, such as cost-aware scheduling, or specific constraints, such as sequence dependent setup times. In such cases, purely generic search strategies may struggle to quickly produce high-quality incumbents, which are crucial for pruning the search space.
A promising research direction is the integration of problem-oriented heuristics within the CP solving process. Fast constructive or improvement heuristics tailored to specific RCPSP structures can generate strong feasible solutions early in the search. These solutions provide tight upper bounds that can be injected into the CP model as hard objective constraints, significantly reducing the search space explored by FDS. The stronger the incumbent, the more aggressively the complete search can prune suboptimal regions.
Beyond hybridization, large-scale RCPSP strongly benefits from parallel search architecture. Modern CP solvers, such as OptaCP, support multiple solver workers running concurrently. Instead of replicating identical models across workers, we propose exploiting model diversity: each worker can employ a different CP model formulation, search strategy, or propagation emphasis. For example, one worker may use a time-indexed formulation, another a start-time interval-based model, and another a precedence- or flow-oriented reformulation. Similarly, workers can differ in symmetry braking, variable ordering, restart policies, or LNS neighborhood design.
Such heterogeneous parallelism increases robustness and coverage of the search space. Workers can share global incumbents, objective bounds, and nogoods during execution. When one worker discovers a high-quality solution, all others immediately benefit through tighter pruning. Conversely, proofs of infeasibility or bound improvements obtained by one model can accelerate convergence across the entire portfolio. This cooperative, portfolio-based architecture combines intensification within each worker with diversification across workers.
The proposed research aims to design and analyze these hybrid and parallel CP frameworks namely for large-scale RCPSP. Emphasis will be placed on principled model reformulation, effective bound sharing, and scalable synchronization mechanisms that preserve solver efficiency while maximizing information exchange.
[PER] L. Perron, P. Shaw, V. Furnon, Propagation guided large neighborhood search, in: M. Wallace (Ed.), Principles and Practice of Constraint Programming – CP 2004, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 468–481.
[OPT] ScheduleOpt: OptalCP’s solver landing page (2023). URL https://scheduleopt.com/
[VIL ]P. Vilím, P. Laborie, P. Shaw, Failure-directed search for constraint-based scheduling, in: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research,
Springer, 2015, pp. 437–453.
Interested candidates are invited to submit their applications at:
https://forms.gle/hj7bMTuKM4ghzPC17 [using Postdoc Position ID: 04-Postdoc-Hanzalek]
The application package should contain: