Automatic Generation of Dispatching Rules for Large Job Shops by Means of Genetic Algorithms
Generating optimized large scale production plans is an important open problem where even small improvements result in significant savings. Application scenarios in the semiconductor industry comprise thousands of machines and hundred thousands of job operations and are therefore among the most challenging scheduling problems regarding their size. In this paper we present a novel approach for automatically creating composite dispatching rules, i.e. heuristics for job sequencing, for makespan optimization in such large scale job shops. The approach builds on the combination of event based simulation and genetic algorithms. We introduce a new set of benchmark instances with proven optima that comprise up to 100000 operations to be scheduled on up to 1000 machines. With respect to this large scale benchmark, we present the results of an experiment comparing well known dispatching rules with automatically created composite dispatching rules produced by our system. It is shown that the proposed system is able to come up with highly effective dispatching rules such that makespan reductions of up to 38% can be achieved, and in fact, often near optimal or even optimal schedules can be produced.
CIMA@ICTAI