๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem

โœ Scribed by Petra Schuurman; Gerhard J. Woeginger

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
148 KB
Volume
237
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper we investigate the two-stage multiprocessor ow shop scheduling problem F2(P)| โ€ข |Cmax, where the numbers m1 and m2 of machines available in the two stages are part of the input. We demonstrate the existence of a polynomial time approximation scheme for this problem.

This result solves the simplest case of an open problem that has been posed by Leslie Hall in a recent paper . An extension of our algorithm yields an approximation scheme for the closely related two-stage multiprocessor job shop problem.

๐Ÿ“œ SIMILAR VOLUMES

A parallel approximation scheme for the
A parallel approximation scheme for the multiprocessor scheduling problem
โœ Ricardo C. Corrรชa ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 433 KB

In this paper, a parallel branch-and-bound approach for ยฎnding approximate solutions to a general version of the multiprocessor scheduling problem is presented and analyzed. In this approach, a list heuristic and a genetic algorithm are used to ยฎnd solutions to the subproblems enumerated during the

A polynomial-time algorithm for the two-
A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
โœ Vadim G. Timkovsky ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 1014 KB

We consider a polynomial-time algorithm for the following scheduling problem: Given two machines, where each machine can process at most one job at a time; a set of jobs, where each job can start on or after its release date and consists of a chain of unit-time operations such that the machines have