A two-machine preemptive openshop scheduling problem: An elementary proof of NP-completeness
type: Item
instance of: scholarly article
title: A two-machine preemptive openshop scheduling problem: An elementary proof of NP-completeness
zbMATH Open document ID: 0920.90072
DOI: 10.1016/S0377-2217(96)00249-4
author: A. A. Gladky
published in: European Journal of Operational Research
publication date: 1999-04-27T00:00:00Z
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 1260415
zbMATH Keywords: mean flow time
zbMATH Keywords: NP-hardness
zbMATH Keywords: two-machine preemptive openshop system
zbMATH Keywords: different ready dates
zbMATH Keywords: strongly NP-complete
MaRDI profile type: Publication
cites work: Q4198056
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: On the complexity of preemptive openshop scheduling problems
full work available at URL: s0377-2217(96)00249-4
OpenAlex ID: W1970923666
Recommended article: Scheduling two-machine preemptive open shops to minimize total completion time
Recommended article: On the complexity of preemptive openshop scheduling problems
Recommended article: On the complexity of preemptive open-shop scheduling problems
Recommended article: Q4239706
Recommended article: A note on the proof of the complexity of the little-preemptive open-shop problem
Recommended article: Non-preemptive two-machine open shop scheduling with non-availability constraints
Recommended article: Q5453295
Recommended article: Q4894072
Recommended article: Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints
description: scientific article; zbMATH DE number 1260415