Multiple objective function on a single machine scheduling problem

Abstract EN

We consider a single machine scheduling problem to minimize a multiple objective function; sum of earliness, tardiness and completion time.

As this problem is complete NP-hard we propose a branch and bound algorithm to obtain an optimal solution.

The implementation of optimizing algorithms dose seen to be promising but it need longer time.

Thus we tackle the problem with local search methods: descent method, simulated annealing and threshold acceptance.

The performance of these heuristic methods is evaluated on a large set of test problems, and the results are also compared with these obtained by genetic algorithm and hybrid method which is combining the simulated annealing with the genetic algorithm.

The best results are obtained with the hybrid method.

We solved the problem optimality with up to 35 jobs and approximately with up to 150000 jobs.