Encoding OAS

Abstract

In many real world scheduling problems there exist hard deadlines after which tasks can no longer be performed. Conversely, not all tasks are necessarily required to be scheduled. Furthermore, the problem investigated in this thesis includes sequence dependent setup times, an aspect reminiscent of the Travelling Salesperson problem. These elements are the underlying additions of the Order Acceptance and Scheduling with Sequence Dependent Setup Times, and introduce additional difficulties to the problem of scheduling. Given the complexity of this problem, it is surprising no evaluation of black-box approaches has been performed. This thesis investigates the applicability, strengths and weaknesses of black-box optimization approaches to various instances of this problem. Two hints were provided in order to improve performance initially. The Time hint informs the approaches of the completion time of the last order in the evaluated schedule, while the Bounds hint leaks information about the release time and deadlines of each order. Both have notable up- and downsides with regards to performance. For the identified weaknesses improvements to the most promising approach, Permutation GOMEA, are proposed and evaluated. These improvements include the addition of various local search approaches, including one derived from an exact approach. The most notable result is a new approach based of GOMEA, named qGOMEA, which shows performance beyond that of any of the evaluated algorithms, including the current state-of-the-art of the Order Acceptance and Scheduling problem. Furthermore, applicability to other permutation problems was shown by improved performance on benchmark functions.