Time complexity and linear-time approximation of the ancient two-machine flow shop

DOI10.1002/(SICI)1099-1425(1998100)1:3%3C149::AID-JOS10%3E3.0.CO;2-4MaRDI QIDQ1268836zbMATH OpenOpenAlexFDO

Authors Günter Rote, Gerhard J. Woeginger

Publication date 1 November 1998

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/(sici)1099-1425(1998100)1:3%3C149::aid-jos10%3E3.0.co;2-4

zbMATH Keywords

computational complexitylower boundsapproximation algorithmsflow shopmakespan minimizationtwo-machine flow shopalgebraic computation treeno wait in progress

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The two-machine total completion time flow shop problem
• The two-machine flowshop total completion time problem: improved lower bounds and a branch-and-bound algorithm
• Approximation algorithms for two-machine flow shop scheduling with batch setup times
• Complexity results and approximation algorithms for the two machine no-wait flow-shop with limited machine availability
• scientific article; zbMATH DE number 4143766
• Lower bounds for minimizing total completion time in a two-machine flow shop
• Two-machine flow-shop scheduling problems with minimizing the total completion times
• An asymptotic two-phase algorithm to minimize total flow time for a two-machine flowshop
• A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints
• A SIMPLE LOWER BOUND FOR TOTAL COMPLETION TIME MINIMIZATION IN A TWO-MACHINE FLOWSHOP

Cited in

(4)

• The simple \(F2//C \max\) with forbidden tasks in first or last position: a problem more complex that it seems
• On two-machine flow shop scheduling
• On Eulerian extensions and their application to no-wait flowshop scheduling
• Algorithms and Computation

This page was built for publication: Time complexity and linear-time approximation of the ancient two-machine flow shop

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1268836)