Parameterized Analysis of Scheduling Problems

The main aim of our research was to try to design algorithms that are capable to optimally solve (in reasonable time) an important set of hard scheduling problems in cases where a predefined set of natural parameters of the problem is of a limited size. Such natural parameters may include (among others): the different number of job types and the number of different due dates. The analysis was done by using the parameterized complexity theory, developed by researchers from the computer science community which enables analyzing the hardness of problems with respect to their natural parameters. We complete all our objectives listed in the proposal and continue to work on some other problems.

Our findings have been published in several research papers, including the analysis of several different scheduling problems,. We construct many different parametrized algorithms using different approaches, including n-fold and Integer Linear Programming (ILP) representations of the problem, dynamic programming algorithms and some other algorithms that have been specifically designed to solve specific problems. We found that the W[1]-hard k-sum problem is a good nominee for parametrized reduction in scheduling environment.

Our results have been published in: Omega, Annals of Operations Research, European Journal of Operational Research, Journal of Scheduling and Algorithmica.