  This PhD thesis summarizes research works on the design of exact algorithms
that provide a worst-case (time or space) guarantee for NP-hard scheduling
problems. Both theoretical and practical aspects are considered with three main
results reported. The first one is about a Dynamic Programming algorithm which
solves the F3Cmax problem in O*(3^n) time and space. The algorithm is easily
generalized to other flowshop problems and single machine scheduling problems.
The second contribution is about a search tree method called Branch & Merge
which solves the 1||SumTi problem with the time complexity converging to
O*(2^n) and in polynomial space. Our third contribution aims to improve the
practical efficiency of exact search tree algorithms solving scheduling
problems. First we realized that a better way to implement the idea of Branch &
Merge is to use a technique called Memorization. By the finding of a new
algorithmic paradox and the implementation of a memory cleaning strategy, the
method succeeded to solve instances with 300 more jobs with respect to the
state-of-the-art algorithm for the 1||SumTi problem. Then the treatment is
extended to another three problems 1|ri|SumCi, 1|dtilde|SumwiCi and F2||SumCi.
The results of the four problems all together show the power of the
Memorization paradigm when applied on sequencing problems. We name it Branch &
Memorize to promote a systematic consideration of Memorization as an essential
building block in branching algorithms like Branch and Bound. The method can
surely also be used to solve other problems, which are not necessarily
scheduling problems.
