| dc.description.abstract | Solving optimization problems is normally done with deterministic data. These data are however not always known with certainty. Recoverable robustness handles this uncertainty by modeling it in different scenarios. An initial solution is found and can be made feasible in each scenario by applying a given and simple recovery algorithm to it.
In this thesis the concept of recoverable robustness will be applied to different machine scheduling problems. First it is applied to the problem of minimizing the number of late jobs on one machine where the processing times of the jobs are uncertain. This problem is solved to optimality with the Moore-Hodgson algorithm when all data are certain. Applying recoverable robustness to this problem, where recovery can only be done by making extra jobs late, is proven to be weakly NP-complete when there is only one scenario. To solve the problem, different exact algorithms are developed, including a dynamic programming algorithm with pseudo-polynomial running time for a given number of scenarios. Branch and price is implemented with the use of the separate recovery framework as a lower bound. This algorithm and a branch and bound algorithm are then tested on their performance. When increasing the number of jobs or scenarios, instances quickly fail to be solved within three minutes. Overall branch and bound performs best.
In the field of scheduling with rejection, not all jobs need to be scheduled and some may be rejected which results in some penalty cost. To some of these problems for one machine recoverable robustness is applied. This problem is solved when minimizing the sum of the makespan and the total rejection penalty. The dynamic programming algorithm for minimizing the makespan with rejection when release dates are available is extended to handle the different scenarios of the recoverable robustness problem. Recoverable robustness is also applied on scheduling problems with rejection while minimizing the maximum lateness or maximum tardiness. | |
