Two machine open shop scheduling problems with bi-criteria (Q1331894): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Open Shop Scheduling to Minimize Finish Time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the interactive solution to a multicriteria scheduling problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3489778 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimizing Maximum Lateness in a Two-Machine Open Shop / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3329208 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A bicriterion approach to time/cost trade-offs in sequencing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Solving a bicriterion scheduling problem / rank | |||
Normal rank |
Latest revision as of 17:30, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two machine open shop scheduling problems with bi-criteria |
scientific article |
Statements
Two machine open shop scheduling problems with bi-criteria (English)
0 references
14 January 1996
0 references
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.
0 references
polynomial algorithms
0 references
bi-criteria two machine open shop scheduling
0 references
maximum completion time
0 references
maximum lateness
0 references