### Job scheduling with forbidden setups and two objectives using genetic algorithms and penalties

Abstract

One of the most important tasks in service and manufacturing systems is how to schedule arriving jobs such that some
criteria will be satisfied. Up to now there have been defined a great variety of scheduling problems as well as
corresponding models and solution approaches. Most models suffer from such more or less restrictive assumptions like
single machine, unique processing times, zero set-up times or a single criterion. On the other hand some classical
approaches like linear or dynamic programming are practicable for small-size problems only. Therefore over the past years
we can observe an increasing application of heuristic search methods. But scheduling problems with multiple machines, forbidden
setups and multiple objectives are scarcely considered. In our paper we apply a Genetic Algorithm to such a problem which
was found at a continuous casting plant. Because of the forbidden setups the probability for a random generated schedule to
be feasible is nearly zero. To resolve this problem we use three kinds of penalties, a global, a local and a combined approach.
For performance investigations of these penalty types we applied our approaches to a real world test instance with 96 jobs,
three machines and two objectives. We tested five different penalty levels with 51 independent runs to evaluate the impact
of the penalties.