Two machine open shop scheduling problems with bi-criteria
type: Item
instance of: scholarly article
title: Two machine open shop scheduling problems with bi-criteria
zbMATH Open document ID: 0830.90072
DOI: 10.1016/0166-218X(94)90144-9
author: Teruo Masuda
author: Hiroaki Ishii
published in: Discrete Applied Mathematics
publication date: 1996-01-14T00:00:00Z
review text: A bi-criteria two machine open shop scheduling problem is considered. The processing of any operation can be interrupted. The two criteria to be minimized are maximum completion time \(C_{\max}\) and maximum lateness \(L_{\max}\). Two basic single criterion problems have already been investigated. For the \(C_{\max}\) criterion the problem was solved by \textit{T. Gonzalez} and \textit{S. Sahni} [J. Assoc. Comput. Machin. 23, 665- 679 (1976; Zbl 0343.68031)], while the \(L_{\max}\) criterion was considered by \textit{E. L. Lawler}, \textit{J. K. Lenstra} and \textit{A. H. G. Rinnooy Kan} [Math. Oper. Res. 6, 153-158 (1981; Zbl 0496.90047)]. These well-known results are used in the paper. It is shown that two cases may occur. In the first case, there exists a unique optimal solution, both criteria being simultaneously optimized. In the second case, nondominated solutions \((C_{\max}, L_{\max})\) lie on the line segment \(L_{\max}= F- C_{\max}\), where \(F\) is computed in \(O(n^2)\) time. In both cases a corresponding schedule can be constructed in \(O(n)\) time.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 626252
zbMATH Keywords: polynomial algorithms
zbMATH Keywords: bi-criteria two machine open shop scheduling
zbMATH Keywords: maximum completion time
zbMATH Keywords: maximum lateness
reviewed by: I. N. Lushchakova
MaRDI profile type: Publication
cites work: Open Shop Scheduling to Minimize Finish Time
cites work: On the interactive solution to a multicriteria scheduling problem
cites work: Q3489778
cites work: Minimizing Maximum Lateness in a Two-Machine Open Shop
cites work: Q3329208
cites work: A bicriterion approach to time/cost trade-offs in sequencing
cites work: Solving a bicriterion scheduling problem
description: scientific article; zbMATH DE number 626252