Zurück zu den Preprints des Jahres 2008


2008-05

Using Simulated Annealing for Open Shop Scheduling with Sum Criteria

by Andresen, M., Bräsel, H., Plauschin, M., Werner, F..


Series: 2008-05, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
This work considers the problem
of scheduling n jobs on m machines in an open shop environment. For any job, there may be given a release date, a job weight and a due date. It is also assumed that the processing times of all non-preemptive operations of the jobs are given in advance.
We consider several objective functions which are all special cases of the problem of minimizing total weighted tardiness subject to given release dates.
This contribution continues and extends recent work by Andresen et al. (2008) on the heuristic solution of open shop problems with minimizing mean flow time.
The focus of this work is on simulated annealing algorithms.
Several neighborhoods are suggested and tested
together with
the control parameters of the algorithm on different problem types.
In particular, we investigate the influence of release dates, processing times, job weights, due dates and the ratio of n and m on the selection of an appropriate simulated annealing algorithm by comparing
96 simulated annealing variants relative to each other.
Extensive computational results are presented for nearly
8,000 open shop instances with up to 30 jobs and 30 machines, respectively. Moreover,
we also perform a comparison of simulated annealing with three variants of a genetic algorithm.

Keywords:
Open shop scheduling; sum criteria; simulated annealing; genetic algorithm; comparative study

This paper was published in:
This paper is contained as Ch