Advanced Search

In the job shop scheduling problem $k$-units-$J_m$, there are $m$ machines and each machine has an integer processing time of at most $k$ time units. Each job consists of a permutation of $m$ tasks corresponding to all machines and thus all jobs have an identical dilation $D$. The contribution of this paper are the following results; (i) for $d=o\left(\sqrt{D}\right)$ jobs and every fixed $k$, the makespan of an optimal schedule is at most $D+o\left(D\right)$, which extends the result of [3] for $k=1$; (ii) a randomized on-line approximation algorithm for $k$-units-...

In the job shop scheduling problem -- , there are machines and each machine has an integer processing time of at most time units. Each job consists of a permutation of tasks corresponding to all machines and thus all jobs have an identical dilation . The contribution of this paper are the following results; (i) for $d=o\left(\sqrt{D}\right)$ jobs and every fixed , the makespan of an optimal schedule is at most , which extends the result of [3] for ; (ii) a randomized on-line approximation...