Constructive heuristic algorithms for the open shop problem
type: Item
instance of: scholarly article
title: Constructive heuristic algorithms for the open shop problem
zbMATH Open document ID: 0796.90031
DOI: 10.1007/BF02243845
published in: Computing
publication date: 1994-09-26T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 482255
zbMATH Keywords: makespan
zbMATH Keywords: \(m\)-machine open shop scheduling
zbMATH Keywords: heuristic
zbMATH Keywords: maximum completion time
zbMATH Keywords: branch and bound
Wikidata QID: Q57634033
author: Heidemarie Bräsel
author: Thomas Tautenhahn
author: Frank Werner
reviewed by: Ya. M. Shafransky
MaRDI profile type: Publication
cites work: On the number of feasible schedules of the open-shop-problem-an application of special latin rectangles
cites work: Q3496141
cites work: Tabu Search—Part I
cites work: Open Shop Scheduling to Minimize Finish Time
cites work: Q3899811
cites work: Benchmarks for basic scheduling problems
cites work: Insertion techniques for the heuristic solution of the job shop problem
description: scientific article; zbMATH DE number 482255