08-05

Using Simulated Annealing for Open Shop Scheduling with Sum Criteria

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

 

Preprint series: 08-05, Preprints

The paper is published: This paper is contained as Chapter 3 in the open access book: Cher Ming Tan (ed.): Simulated Annealing, In-Teh, 2008, 49 - 76, ISBN 978-953-7619-07-7.

MSC:
90B35 Scheduling theory, See also {68M20}

 

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


The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster