Abstract: Scheduling problems are, generally speaking, the problems of allocating scarce resources over time to perform a given set of jobs (activities). Due to its practical relevance, the field of scheduling has been one of the most studied fields since the early days of Management Science and Operation Research. Within the field of scheduling, many sub-fields have been studied during the last century, among which project scheduling and single machine scheduling have received special attention. In this dissertation, we mainly contribute in these two mentioned sub-fields. As such, this dissertation includes two parts: the first part includes contributions to complex project scheduling problems and the second part includes contributions to a single machine scheduling problem. In the first part, we contribute (i) by introducing an integrated proactive and reactive resource-constrained project scheduling problem and by proposing several models that can solve the introduced problem, (ii) by presenting two very important classes of reactions and by investigating their relevance in optimal proactive and reactive policies and (iii) by developing a novel branch-and-bound algorithm that solves instances of chance-constrained resource-constrained project scheduling problem. In the second part, we contribute (i) by introducing a generic single machine scheduling problem where the objective is to minimize the total weighted tardiness penalty and solutions are subject to both time-window constraints and precedence constraints, (ii) by proposing several lower bounding schemes for the introduced problem and by investigating the theoretical relevance and the complexities of the proposed lower bounds and (iii) by presenting two branching schemes and a number of dominance rules that combined construct two branch-and-bound algorithms that can solve instances of the introduced problem.

Abstract: This thesis studies order acceptance and scheduling problems in a single-machine environment where the set of jobs contains firm-planned jobs and optional jobs. Each job has a processing time, a release date, a due date, a deadline, a revenue and a weight representing the penalty per unit-time delay when it is completed after its due date but before its deadline. Moreover, an acyclic graph representing the jobs’ precedence relations is given. Our goal is to select and schedule a subset of jobs to maximize the total profit, which is the sum of revenue of selected jobs minus the total weighted tardiness penalty. All firm-planned jobs must be selected and each selected job is executed after all its predecessors. We present an enhanced successive sublimation dynamic programming to solve the problem until optimality. Computational results show that our approach is effective to solve small-sized instances.