Is a unit-job shop not easier than identical parallel machines?
type: Item
instance of: scholarly article
title: Is a unit-job shop not easier than identical parallel machines?
zbMATH Open document ID: 0908.90173
DOI: 10.1016/S0166-218X(98)00032-8
author: Vadim G. Timkosvky
published in: Discrete Applied Mathematics
publication date: 1998-07-28T00:00:00Z
full work available at URL: dam
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 1180348
zbMATH Keywords: identical parallel machines
zbMATH Keywords: unit-time operations
zbMATH Keywords: polynomial-time reduction
zbMATH Keywords: maximum completion time
zbMATH Keywords: maximum lateness
zbMATH Keywords: total completion time
zbMATH Keywords: total tardiness
zbMATH Keywords: NP-hardness
MaRDI profile type: Publication
cites work: Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
cites work: Scheduling independent tasks to reduce mean finishing time
cites work: Q4658190
cites work: Minimizing Total Tardiness on One Machine is NP-Hard
cites work: Q4016820
cites work: Minimizing mean flow time with release time constraint
cites work: Scheduling chain-structured tasks to minimize makespan and mean flow time
cites work: Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
cites work: `` Strong '' NP-Completeness Results
cites work: Q4198056
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Q4142699
cites work: Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem
cites work: A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem
cites work: An efficient algorithm for a job shop problem
cites work: Total completion time minimization in two-machine job shops with unit-time operations
cites work: Q3217922
cites work: Q4124332
cites work: Q3959420
cites work: Q3929047
cites work: Q3995531
cites work: Computational Complexity of Discrete Optimization Problems
cites work: Q4055377
cites work: Preemptive Scheduling with Release Times, Deadlines, and Due Times
cites work: Scheduling with deadlines and loss functions
cites work: Optimal Preemptive Scheduling on Two-Processor Systems
cites work: Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
cites work: The complexity of shop-scheduling problems with two or three jobs
cites work: Some no-wait shops scheduling problems: Complexity aspect
cites work: Q4841579
cites work: Q3713852
cites work: Q3734131
cites work: A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
description: scientific article; zbMATH DE number 1180348