Deciding when to process the jobs of a project while satisfying technical requirements and reaching good performance criteria is an optimization task known as scheduling. At different stages of the same project, from early planning to actual execution, scheduling problems are solved in order to make decisions that may be impactful at various timescales. Large projects that involve multiple actors and require long-term planning are particularly prone to uncertainty due to imperfect knowledge and complex organization. Because of unpredicted changes in the project, previously made decisions may become inapplicable or obsolete so they have to be changed. However, altering what was initially planned should be avoided as it is often difficult or costly. Coherence from one decision stage to another is therefore essential for a project to run properly. This thesis studies scheduling problems that aim at achieving such coherence, either by seeking robust solutions that can resist uncertainty or by conforming to previously made decisions as best as possible.
A first part is dedicated to a particular notion of two-stage robustness called anchor robustness. In the two-stage robustness paradigm, part of the decisions are made during a first stage, followed by an uncertainty realization after which second-stage decisions can be used to recover solution feasibility. Anchor robustness in particular aims at guaranteeing that some of the first-stage decisions are anchored, meaning that they can remain unchanged despite uncertainty. In the context of scheduling, anchor robustness guarantees that some jobs keep the same starting time at second stage than at first stage. Anchor robustness is studied in the presence of non-availability periods that prevent some jobs from being processed on some time intervals. A rescheduling problem is considered where a maximum number of jobs must keep the starting times they were given in a baseline schedule. This problem, previously studied under precedence constraints only, is shown to remain polynomial under additional non-availability constraints. The anchor-robust scheduling problem that aims at building a baseline schedule where some jobs are anchored was studied in the case of processing time uncertainty. Complexity results and solution methods are generalized to the case of uncertain non-availability periods. A single-machine anchor-robust problem is then considered in order to study anchor robustness in combination with resource constraints. This follows a previous work on a more general anchor-robust counterpart of the Resource-Constrained Project Scheduling Problem. An in-depth structural analysis of the single-machine special case leads to solution methods that handle instances of significantly larger size.
The second part of the thesis focusses on resource considerations, starting with resource leveling. In resource leveling problems, usual capacity constraints are replaced with a penalization of irregular resource use in the objective. A particular resource leveling criterion called total overload cost penalizes resource use above a given level. A variety of problems combining this criterion with classical scheduling constraints and parameter restrictions are studied. Complexity results are presented that include NP-hardness proofs and polynomial-time algorithms for special cases. For some problems proved to be NP-hard, the complexity study is further developed in terms of approximation, thus revealing more tractable cases. Lastly, a two-stage robust problem is considered that aims at finding a time-varying resource capacity function, called workload. This workload should be robust in the sense that it must be sufficient to schedule a set of independent jobs with availability intervals under processing time uncertainty.