Constructive heuristic algorithms for the open shop problem (Q1310611)

The \(m\)-machine open shop scheduling problem without preemption is considered. Two type of heuristic algorithms to minimize the maximum completion time (makespan) are proposed. Heuristics of the first type generate so-called rank-minimal schedules. Their time complexity varies from \(O((\max\{n,m\})^ 3\log(\max\{n,m\}))\) to \(O((\max\{n,m\})^ 4)\), where \(n\) is the number of jobs. The second type heuristic is a special restricted branch and bound algorithm. Its time complexity is \(O(n^ 2 m^ 2)\). Presented algorithms are tested on different benchmark problems.