Bei vielen praktischen Schedulingproblemen muß neben der Festlegung der Maschinenbelegungszeiten auch das Problem der Transporte der Werkstücke zwischen den einzelnen Maschinen gelöst werden. Eine gängige Technologie zur Abwicklung solcher Transporte ist eine Krananlage, bei der sich die Kräne auf einer über den Maschinen befindlichen gemeinsamen Schiene bewegen.
In der Regel wird die Steuerung der Krananlage bei der Erstellung des Produktionsplanes vernachlässigt und dem Disponenten vor Ort überlassen. Dieser Ansatz ist in Fällen, in denen das Transportsystem einen Engpaß des Produktionsablaufes bildet, nicht gerechtfertigt.
Bereits in der Vergangenheit wurde an unserem Institut die Steuerungsproblematik solcher eindimensionaler Transportsysteme am Beispiel der Krananlage in einer Galvanisierhalle untersucht. Wichtige Nebenbedingungen resultieren aus dem Verbot von Überholvorgängen (alle Kräne fahren auf der gleichen Schiene), sowie aus den gesetzlich und technisch vorgegebenen Mindestabständen zwischen den einzelnen Kräne. Es konnte gezeigt werden, daß das Steuerungsproblem in dem speziellen Fall der Galvanisieranlage effizient zu lösen ist, d.h. es ist möglich, für einen vorgegebenen Schedule in polynomieller Zeit die minimale Anzahl Kräne zu bestimmen, die zu seiner Abarbeitung notwendig sind.