Add to ORKGWe present a polynomial (1 + #epsilon#)-approximation scheme for the strongly NP-hard problem of scheduling n jobs in a two-machine flow-shop subject to release dates. This scheme is based on a dynamic programming approach applied to a problem with rounded release dates and processing times. In comparison with the known Hall's polynomial approximation scheme, our scheme has a better time complexity estimation for small #epsilon# and sufficiently large n. (orig.)Available from TIB Hannover: RR 4487(1995,1) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman
We discuss scheduling problems with m identical machines and n jobs where each job has to be assigne...
In a recent paper [Theoretical Computer Science 363, 257–265], He, Zhong and Gu considered the non-r...
Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein, and Wein presented the rst polyno...
We consider the problem of scheduling n independent jobs on m identical machines that operate in par...
AbstractIn this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)...
In this paper we present a polynomial time approximation scheme for the job shop scheduling problem ...
The strongly NP-hard scheduling problem of minimizing the maximum lateness on one machine subject to...
AbstractThe two-machine flow-shop sequencing problem with arbitrary release dates of jobs and the mi...
International audienceOften the problem of determining an optimal or approximate production schedule...
We consider the following scheduling problem. There arem parallel machines andn independent jobs. Ea...
. In the job shop scheduling problem we are given m machines and n jobs; a job consists of a sequenc...
AbstractWe consider a polynomial-time algorithm for the following scheduling problem: Given two mach...
The two-machine flow-shop sequencing problem with arbitrary release dates of jobs and the minimum ma...
We discuss scheduling problems with m identical machines and n jobs where each job has to be assigne...
In a recent paper [Theoretical Computer Science 363, 257–265], He, Zhong and Gu considered the non-r...
Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein, and Wein presented the rst polyno...
We consider the problem of scheduling n independent jobs on m identical machines that operate in par...
AbstractIn this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)...
In this paper we present a polynomial time approximation scheme for the job shop scheduling problem ...
The strongly NP-hard scheduling problem of minimizing the maximum lateness on one machine subject to...
AbstractThe two-machine flow-shop sequencing problem with arbitrary release dates of jobs and the mi...
International audienceOften the problem of determining an optimal or approximate production schedule...
We consider the following scheduling problem. There arem parallel machines andn independent jobs. Ea...
. In the job shop scheduling problem we are given m machines and n jobs; a job consists of a sequenc...
AbstractWe consider a polynomial-time algorithm for the following scheduling problem: Given two mach...
The two-machine flow-shop sequencing problem with arbitrary release dates of jobs and the minimum ma...
We discuss scheduling problems with m identical machines and n jobs where each job has to be assigne...
In a recent paper [Theoretical Computer Science 363, 257–265], He, Zhong and Gu considered the non-r...
Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein, and Wein presented the rst polyno...