Multicriteria machine scheduling: Theory, Models and Algorithms

International audienceIn order to solve the on-line problem we consider that the scheduler will act on a regular basis. The situation will be let getting unbalanced and be rebalanced every Δt period. At any decision moment, the hypothesis that the situation will no longer evolve is made, and processes are migrated in consequence. At the next decision moment, this hypothesis can be proven right, and no rebalancing operation is needed, or wrong, and rebalancing must take place. Instead of solving an on-line problem, the scheduler is solving a series of off-line scheduling problems. This lead to a model very close to the Load Rebalancing problem as defined by Aggarwal et al., (2003), yet different by the presence of the memory constraint. Solving the bi-criteria part of the problem can be done using the ε-constraint approach (T'kindt and Billaut, (2002)). The second objective, minimizing the migrations, is made into a new constraint by bounding the amount of migrations allowed. The value of the bound can be determined as the maximum number of processes that can be migrated between two decisions moments. We have proven that this problem is NP-Hard in the strong sense due to the memory constraint (Perotin et al., (2008)). If this constraint is relaxed, the problem can be seen as a Multi Processor Scheduling Problem, where minimizing the makespan minimizes the maximum load. The special case where each job has identical processing time, with related machines, is kown to be polynomial (Garey and Johnson, (1979))