A polynomially solvable case of the two-stage open shop problem for three machines
type: Item
instance of: scholarly article
zbMATH Open document ID: 0970.90029
author: K. N. Kashyrskikh
author: Alexander Kononov
author: I. D. Chernykh
author: Sergey Sevastyanov
publication date: 2001-07-22T00:00:00Z
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 1622447
zbMATH Keywords: three-machine open shop problem
zbMATH Keywords: two-stage problem
zbMATH Keywords: polynomial solvability
zbMATH Keywords: efficient scheduling
MaRDI profile type: Publication
title: A polynomially solvable case of the two-stage open shop problem for three machines
published in: Diskretnyĭ Analiz i Issledovanie Operatsiĭ. Seriya 1
review text: The authors study the two-stage open shop problem for three machines with the test of minimum length scheduling. This problem is a restriction of the classical three-machine open shop problem [see \textit{T.~Gonzalez} and \textit{S.~Sahni}, J. Assoc. Comput. Mach. 23, No. 4, 665-679 (1976; Zbl 0343.68031)] in the case of two operations. The authors prove that the problem under consideration is polynomially solvable in the case when \(L_{\max}\geq 3p_{\max}\). Here \(L_{\max}\) and \(p_{\max}\) denote the maximal machine loading and maximal duration of operation. Moreover, the optimal length scheduling equals \(L_{\max}\).NEWLINENEWLINENEWLINEThe authors note that the question on the complexity for the problem is still open.
reviewed by: Vladimir N. Grebenev
description: scientific article; zbMATH DE number 1622447