NP-hardness of compact scheduling in simplified open and flow shops.

DOI10.1016/S0377-2217(00)00022-9zbMath1068.90560MaRDI QIDQ5932026

Krzysztof Giaro

Publication date: 2001

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

NP-completenesscompact schedulingflow shopinterval edge coloringopen shop

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

A note on minimizing maximum lateness in a two-machine no-wait flowshop ⋮ A travelling salesman approach to solve the \(F\)/no-idle/\(C_{max}\) problem ⋮ The simple \(F2//C \max\) with forbidden tasks in first or last position: a problem more complex that it seems ⋮ On Eulerian extensions and their application to no-wait flowshop scheduling ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ A survey of scheduling problems with no-wait in process ⋮ Chromatic scheduling in a cyclic open shop ⋮ Coupled task scheduling with exact delays: literature review and models ⋮ No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths ⋮ No-wait flexible flowshop scheduling with no-idle machines

Cites Work

• Complexity of Scheduling Shops with No Wait in Process
• Reducibility among Combinatorial Problems
• A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
• Compact Scheduling In Open Shop With Zero-One Time Operations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: NP-hardness of compact scheduling in simplified open and flow shops.