A promising hybrid GA/heuristic approach for open-shop scheduling problems

Abstract

. Many problems in industry are a form of openshop scheduling problem (OSSP). We describe a hybrid approach to this problem which combines a Genetic Algorithm (GA) with simple heuristic schedule building rules. Excellent performance is found on some benchmark OSS problems, including improvements on previous best-known results. We describe how our approach can be simply amended to deal with the more complex style of open shop scheduling problems which occur in industry, and discuss issues relating to further improvement of performance and integration of the approach into industrial job shop environments. 1 INTRODUCTION The Open-Shop Scheduling Problem (OSSP) is a complex and common industrial problem [6]. OSSPs arise in an environment where there is a collection of operations to perform on one or more machines. Efficient production and manufacturing demands effective methods to optimise various aspects of a schedule, usually focussing on the total time taken to process all of the oper...