M. Sc. Andreas Hipp (Chair of Business Administration, HSU)
Hybrid flow shop (HFS) scheduling problems as a flow shop production layout adding parallel machines on at least one stage of operation represent popular systems in real-world production environments. In our work, we focus on the no-wait HFS scheduling problem. The no-wait constraint leads to the requirement of processing jobs continuously without any waiting time between subsequent stages as soon as they enter the production system. We focus on a two-stage HFS with two machines in the first stage and a single machine in the second stage, as found in steel or chemical industries. It is proved that even the 2-stage HFS is NP-hard so that fast, high-quality solutions may not be readily generated in practical cases. We apply a decomposition approach using several typical heuristics to find a suitable job sequence for our layout. Initially, assignment rules were implemented to schedule the jobs on the machines in the determined sequence – as it is normally done for this type of problem. This 2-stage solution approach is applied to a testbed with up to 200 jobs.
Although the tackled HFS scheduling problem is NP-hard, we found out that the assignment problem with a given job sequence can be solved to optimality for the 2-stage no-wait HFS layout. Together with the hpc.bw project group at the Helmut Schmidt University, we want to generate efficient code for our formulated assignment algorithm and apply it to the entire testbed. Finally, we aim to gain insight into the speed and performance gaps between the exact algorithm and the heuristic assignment rules by running the instances on the HPC servers.