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.