Time complexity and linear-time approximation of the ancient two-machine flow shop
type: Item
instance of: scholarly article
title: Time complexity and linear-time approximation of the ancient two-machine flow shop
zbMATH Open document ID: 0909.90180
author: Günter Rote
author: Gerhard J. Woeginger
published in: Journal of Scheduling
publication date: 1998-11-01T00:00:00Z
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 1216802
zbMATH Keywords: flow shop
zbMATH Keywords: no wait in progress
zbMATH Keywords: computational complexity
zbMATH Keywords: algebraic computation tree
zbMATH Keywords: lower bounds
zbMATH Keywords: makespan minimization
zbMATH Keywords: two-machine flow shop
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
OpenAlex ID: W2145999379
Recommended article: The two-machine total completion time flow shop problem
Recommended article: The two-machine flowshop total completion time problem: improved lower bounds and a branch-and-bound algorithm
Recommended article: Approximation algorithms for two-machine flow shop scheduling with batch setup times
Recommended article: Complexity results and approximation algorithms for the two machine no-wait flow-shop with limited machine availability
Recommended article: Q3475121
Recommended article: Lower bounds for minimizing total completion time in a two-machine flow shop
Recommended article: Q4924332
Recommended article: An asymptotic two-phase algorithm to minimize total flow time for a two-machine flowshop
Recommended article: A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints
Recommended article: A SIMPLE LOWER BOUND FOR TOTAL COMPLETION TIME MINIMIZATION IN A TWO-MACHINE FLOWSHOP
DOI: 10.1002/(SICI)1099-1425(1998100)1:3%3C149::AID-JOS10%3E3.0.CO;2-4
full work available at URL: https://doi.org/10.1002/(sici)1099-1425(1998100)1:3%3C149::aid-jos10%3E3.0.co
description: scientific article; zbMATH DE number 1216802