CONSTRUCTIVE HEURISTIC ALGORITHMS FOR THE OPEN SHOP PROBLEM

In this paper we consider constructive heuristic algorithms for the open shop problem with minimization of the schedule length. By means of investigations of the structure of a feasible solution two types of heuristic algorithms are developed: construction of a rank-minimal schedule by solving successively weighted maximum cardinality matching problems and construction of an approximate schedule by applying insertion techniques combined with beam search. All presented algorithms are tested on benchmark problems from the literature. Our computational results demonstrate the excellent solution quality of our insertion algorithm, especially for greater job and machine numbers. For 29 of 30 benchmark problems with at least 10 jobs and 10 machines we improve the best known values obtained by tabu search.