CONSTRUCTIVE HEURISTIC ALGORITHMS FOR THE OPEN SHOP PROBLEM

In this paper we consider constructive heuristic algorithms for the op en shop problem with minimization of the schedule length. By means of investigations of the structure of a feasible solution two types of he uristic algorithms are developed: construction of a rank-minimal sched ule by solving successively weighted maximum cardinality matching prob lems and construction of an approximate schedule by applying insertion techniques combined with beam search. All presented algorithms are te sted on benchmark problems from the literature. Our computational resu lts demonstrate the excellent solution quality of our insertion algori thm, especially for greater job and machine numbers. For 29 of 30 benc hmark problems with at least 10 jobs and 10 machines we improve the be st known values obtained by tabu search.