Algorithms to solve multicriteria scheduling problems on single machine

Abstract EN

In this paper, we consider the multicriteria scheduling problem with release dates on single machine to minimize three criteria: maximum cost function, noted Ymax ∈ {Cmax ,Tmax } and the sum of completion times, noted Σ C i.

This problem, which is known to be NPhard, is important in practice.

We propose three new algorithms to solve this problem.

Two of these algorithms dealing with hierarchical minimization problem case to find the best possible solution for each of the following two problems 1 / ri / Lex (Cmax ,Tmax , ΣCi ) and 1 / ri / Lex (Cmax, ΣC i, Tmax).

The third one is constructive algorithm based on branch and bound method (BAB) to find some of the efficient solutions when all the three criteria Cmax, Tmax and Σ Ci are of simultaneous interest for the general problem 1 / ri / F (Cmax, Tmax, Σ Ci) Our experimental results indicate that the third proposed algorithm enumerates the set of efficient solutions for the three criteria optimality