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

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. Copyright Springer-Verlag 2011