no-wait4(1).pdf

(158 KB) Pobierz
Makespan Minimization in No-Wait Flow Shops: a
Polynomial Time Approximation Scheme
∗
M. Sviridenko
†
Abstract
We investigate the approximability of no-wait permutation flow shop scheduling
problem under the makespan criterion. We present a polynomial time approxima-
tion scheme (PTAS) for problem on any
fixed
number of machines.
1
Introduction
Problem statement.
A
job shop
is a multi-stage production process with the property
that all jobs have to pass through several stages. There are
n
jobs
J
j
, with
j
= 1,
. . . , n,
where each job
J
j
is a chain of
m
j
operations
O
1j
, . . . , O
m
j
j
. Every operation
O
ij
is
preassigned to one of
m
stages
M
1
, . . . , M
m
of the production process. The operation
O
ij
has to be processed for
p
ij
time units at its stage; the value
p
ij
is called its
processing
time
or its
length.
We will consider a basic model where there is exactly one machine
available for each stage; to simplify the presentation we will identify the stage with the
corresponding machine. In a feasible schedule for the
n
jobs, at any moment in time every
job is processed by at most one machine and every machine executes at most one job. For
each job
J
j
, operation
O
i−1,j
always is processed before operation
O
ij
, and each operation
is processed without interruption on the machine to which it was assigned. A
flow shop
is a special case of the job shop where each job has exactly one operation in each stage,
and where all jobs pass through the stages in the same order
M
1
→
M
2
→ · · · →
M
m
. In
an
open shop
the ordering of the operations in a job is not fixed and may be chosen by
the scheduler.
In this paper, we are mainly interested in shop problems under the
no-wait constraint.
In such a no-wait shop, there is no waiting time allowed between the execution of con-
secutive operations of the same job. Once a job has been started, it has to be processed
Joint preliminary version of this paper appeared in proceedings of FOCS00 [23] and contained some
additional nonapproximability results for no-wait shop scheduling problems.
†
IBM T. J. Watson Research Center, Yorktown Heights, P.O. Box 218, NY 10598, USA; Email:
sviri@us.ibm.com
∗
1
without interruption, operation by operation, until it is completed. In a no-wait flow
shop instance without operations of length zero, any feasible schedule is a
permutation
schedule,
i.e., a schedule in which each machine processes the jobs in the same order.
In the
no-wait permutation flow shop
problem, only permutation schedules are feasible
schedules. Our goal is to find a feasible schedule that minimizes the
makespan
(or
length)
C
max
of the schedule, i.e., the maximum completion time among all jobs. The minimum
∗
makespan among all feasible schedules is denoted by
C
max
.
Complexity of shop problems.
The computational complexity of the classical shop
problems (without the no-wait constraint) is easy to summarize: They are polynomially
solvable on two machines, and they are
N P-hard
on three and more machines; see e.g.
Lawler, Lenstra, Rinnooy Kan & Shmoys [11]. For no-wait shops, the situation is more
interesting. Sahni & Cho [19] proved that the no-wait job shop and the no-wait open shop
problem are strongly
N P-hard,
even if there are only two stages and if each job consists
of only two operations. The no-wait permutation flow shop problem can be formulated
as an asymmetric traveling salesman problem (ATSP); see e.g. Piehler [15], Wismer [25].
For two machines, the distance matrix of this ATSP has a very special combinatorial
structure, and the famous subtour patching technique of Gilmore & Gomory [5] yields an
O(n
log
n)
time algorithm for the two-machine no-wait flow shop. R¨ck [17] proves that
o
the three-machine no-wait flow shop is strongly
N P-hard,
refining the previous complex-
ity result by Papadimitriou & Kanellakis [12] for four machines. Hall & Sriskandarajah
[8] provide a thorough survey of complexity and algorithms for no-wait scheduling.
Approximability of shop problems.
We say that an approximation algorithm
has
performance ratio
or
worst case ratio
ρ
for some real
ρ >
1, if it always delivers
∗
a solution with makespan at most
ρC
max
. Such an approximation algorithm is then
called a
ρ-approximation
algorithm. A family of polynomial time (1 +
ε)-approximation
algorithms over all
ε >
0 is called a
polynomial time approximation scheme
(PTAS).
The approximability of the the classical shop problems (without the no-wait con-
straint) is fairly well understood: If the number of machines is a fixed value that is not
part of the input, then the flow shop (Hall [7]), the open shop (Sevastianov & Woeginger
[20]), and the job shop (Jansen, Solis-Oba & Sviridenko [9]) possess a PTAS. On the
other hand, if the number of machines is part of the input, then none of the three shop
problems has a PTAS unless
P
=
N P
(Williamson & al. [24]).
Prior to our work, only a few results were known on the approximability of the no-wait
shop problems: For all shop problems on
m
machines, sequencing the jobs in arbitrary
order yields a (trivial) polynomial time
m-approximation
algorithm. R¨ck & Schmidt
o
[18] improve on this for the no-wait flow shop and give an
⌈m/2⌉-approximation
algo-
rithm. Papadimitriou & Kanellakis [12], Glass, Gupta & Potts [6], and Sidney, Potts &
Sriskandarajah [21] study various generalizations and modifications of the no-wait flow-
shop problem on two machines. For all these generalizations the authors manage to design
approximation algorithms with performance guarantees strictly better than two, by build-
2
ing on the algorithm of Gilmore & Gomory [5]. Agnetis [1] introduces an approximation
algorithm for the no-wait flow shop with only a small number of
distinct
job-types; as
the number of jobs in every job-type grows, the performance guarantee of this algorithm
tends to one. Sidney & Sriskandarajah [22] obtain a 3/2-approximation algorithm for
the two-machine no-wait open shop problem. The preliminary joint version of this paper
[23] contains few non-approximability results due to G. Woeginger. He proved that the
no-wait job shop problem on three machines with at most three operations per job and
the no-wait job shop problem on two machines with at most five operations per job does
not have a PTAS unless
P
=
N P
.
Results and organization of this paper.
We design a PTAS for the no-wait
permutation flow shop problem when the number
m
of machines is fixed. This result first
uses several job partition and rounding steps, and then exploits the connection of the no-
wait flow shop to the asymmetric traveling salesman problem. In Section 2 we recall and
discuss this connection between no-wait flow shop and the ATSP. In Section 3 we derive
the PTAS. Some of our rounding and job partition steps seem to be very close to the
rounding and job partition steps in the PTAS’s for the classical shop problems [7, 9, 20]
but our technique cannot be generalized to the no-wait job shop problem because of the
negative result due to G. Woeginger [23]. The paper concludes with the statement of
several open problems in Section 4.
2
The no-wait permutation flow shop and the ATSP
It is well known (see e.g. Piehler [15] or Wismer [25]) that the no-wait permutation flow
shop problem can be modeled as a special case of the asymmetric traveling salesman prob-
lem (ATSP) with the triangle inequality: We add a
dummy
job
J
0
with zero processing
times on all machines to a given flow shop instance. By
G
we denote the complete, arc-
weighted, directed graph with vertex set
{J
0
, J
1
, . . . , J
n
}
and with the following weights
(or
distances
or
lengths)
d
qj
on the arc from job
J
q
to
J
j
. We stress the fact that in
general
d
qj
=
d
jq
.
i
m
m
m
m
d
qj
=
i=1,...,m
max
{
k=1
p
kq
+
k=i
p
kj
} −
k=1
p
iq
= max
{
i=1,...,m
k=i
p
kj
−
k=i+1
p
kq
}.
(1)
The intuition behind the definition of the distances in (1) is the following. Assume that
in some schedule job
J
q
completes at time
t,
and that job
J
q
is followed by job
J
j
, without
unnecessary idle time between the two jobs. Then
J
j
completes at time
t
+
d
qj
. With
this it is easy to see that every feasible permutation schedule of the no-wait flow shop
problem corresponds to a directed Hamiltonian cycle
C
in the digraph
G,
such that the
makespan of the schedule equals the length of
C.
Conversely, if we delete the in-going arc
of vertex
J
0
from some Hamiltonian cycle
C
in
G,
then the resulting Hamiltonian path
corresponds to a feasible permutation schedule with the same length.
3
The following observations on the distances
d
qj
are straightforward to verify.
Observation 2.1
For every job
J
j
, denote by
ℓ
j
=
(i) For all
0
≤
j, q
≤
n, ℓ
j
−
ℓ
q
≤
d
qj
≤
ℓ
j
holds.
(ii) For all
0
≤
j, k, q
≤
n, d
qj
≤
d
qk
+
d
kj
, i.e., the distances
d
qj
fulfill the triangle
inequality.
(iii) If one of the values
p
ij
changes to
p
ij
+ ∆,
then the length of any ATSP tour (and
the makespan of the corresponding feasible schedule) changes by at most
±∆.
Because of this correspondence between permutation schedules and ATSP tours, the
result by Frieze, Galbiati & Maffioli [4] on the ATSP with triangle inequality yields
an
O(log n)-approximation
algorithm for the no-wait permutation flow shop problem.
Recently, Carr & Vempala [2] gave some theoretical evidence for the existence of a 4/3-
approximation algorithm for the ATSP with triangle inequality. Of course, such a result
would immediately yield a 4/3-approximation algorithm for the no-wait permutation
flow shop on an arbitrary number of machines. We remark that the strongest known
negative result for the general ATSP with the triangle inequality is due to Papadimitriou
& Vempala [14]. They prove that unless
P
=
N P,
the ATSP with triangle inequality
cannot have a polynomial time approximation algorithm with performance guarantee
better than 41/40. However, this negative result does not seem to carry over to the
no-wait flow shop.
m
k=1
p
kj
its overall length.
3
Approximability of the no-wait flow shop
Throughout this section we consider an instance
I
of the no-wait permutation flow shop
problem where the number
m
of machines is a fixed constant and not part of the input. By
ℓ
j
=
m
p
ij
we denote the total length of job
J
j
. Let
L
i
=
n
p
ij
be the load of machine
i=1
j=1
∗
M
i
, and let
L
max
= max
i
L
i
be the maximum machine load. Clearly,
L
max
≤
C
max
.
Let
ε >
0 be a fixed precision parameter. Our goal is to find a near optimal schedule
∗
for instance
I
whose makespan is at most (1 +
const
·
ε)C
max
for some fixed positive
constant
const
that only depends on
m.
Clearly, this will yield the PTAS. We will use
log
x
to denote the logarithm base 1 +
ε
of
x.
By
α
we denote a rational number with
ε
m/ε
≤
α
≤
ε
whose exact value will be fixed below. From now on we will assume that
the number
n
of jobs is sufficiently large to satisfy
(2
1/m
−
1) log
n
≥
1 + log(m/ε)
and
αn
≥
log
m
n.
(3)
(2)
4
If
n
does not fulfill (2) and (3), then it is bounded by a constant in
m
and
ε;
such
an instance of constant size can be solved in constant time by global enumeration. We
partition the set of jobs into three subsets as follows.
B
=
{J
j
|
αL
max
/
log
m
n
≤
ℓ
j
},
M
=
{J
j
|
ε
·
αL
max
/
log
m
n < ℓ
j
< αL
max
/
log
m
n},
S
=
{J
j
|
ℓ
j
≤
ε
·
αL
max
/
log
m
n}.
The jobs in
B
are called
big jobs,
the jobs in
M
are called
medium jobs,
and the jobs in
S
are called
small jobs.
For the operations of big, medium, and small jobs we use a similar
notation: the operations of big jobs are called
big operations,
while operations of medium
and small jobs are called
medium
and
small operations,
respectively, independently of
their actual sizes. Since
n
ℓ
j
≤
mL
max
, the number of big jobs is upper bounded as
j=1
|B| ≤
m
log
m
n
≤
ε
−m/ε
m
log
m
n.
α
(4)
Sevastianov & Woeginger [20] show that the value
α
can be chosen so that
ℓ
j
≤
εL
max
.
J
j
∈M
(5)
This is done as follows. Consider the sets
M(k)
of medium jobs with respect to
α
=
ε
k
,
where
k
is some positive integer. Note that for
k
=
k
′
the two sets
M(k)
and
M(k
′
) are
disjoint. Since the total length of all jobs is at most
mL
max
, there exists a value
k
∗
≤
m/ε
for which
M
=
M(k
∗
) satisfies the inequality (5). We set
α
=
ε
k
∗
. Finally, we define
.
β
=
m
2
log
m
n /
(εα)
(6)
Starting from the flow shop instance
I
=
I
(0)
, we will now define a sequence of instances
I
(1)
,
I
(2)
,
I
(3)
,
I
(4)
. The instance
I
(x+1)
always is a rounded and slightly simplified version
(x)
of instance
I
(x)
. In instance
I
(x)
, the processing times are
p
ij
, the optimal makespan
(x)
is
C
max
, the digraph for the underlying ATSP is
G
(x)
, and so on. In order to get a
near optimal schedule for instance
I
(x)
, it will always be sufficient to get a near optimal
schedule for the simplified instance
I
(x+1)
. Hence, by constructing a PTAS for
I
(4)
we
will establish the existence of the desired PTAS for the no-wait permutation flow shop
on a fixed number of machines.
3.1
How to round the instance
In the first rounding step, we remove all medium jobs from
I
and thus produce instance
AP
I
(1)
. If we have a near optimal schedule with makespan
C
max
X
for the big and small jobs
in instance
I
(1)
, then we may append the medium jobs in arbitrary order at the end of
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin