† ‡
, .
. , . ,
. ,
, ,
, , .
Properties of a Disjunctive Graph and flow Shop Scheduling
Shizu Sakakibara† Mario Nakamori‡
The aim of the present paper is to investigate the properties of the disjunctive graph that represents
special kinds of flow shop scheduling problems. We propose a new theoretical lower bound on the length of the
critical path where only some of the disjunctive edges are fixed and show that our new bound is better than
those already known. This enables us to design a new efficient branch and bound algorithm for the flow shop
problems. We also propose the order presentation table, which is effective for special flow shop problems
where certain pause is required between two jobs or some jobs are forbidden to execute in some specified time
intervals, in order to make the disjunctive graph small and, thus, make the computational time small.
disjunctive graph .
, , , ,
. conjunctive Balas , ,
arc , disjunctive . ,
arc . , [Link] , .
Balas ,
[1], .
. ,
, , ,
, . ,
† .
Department of Computer Science, Graduate School, Tokyo 2
A & T University 2.1
Balas[1] ,M ,I
‡
.
Department of Computer Science, Tokyo A & T University
-1-
. F ,
, .
,M I . ( ) , 2.2 Balas
. Balas , ,
Balas [1] , ,
. ,
s t ; .
O1,1, O1,2, , OM,I; 1 ,
; .
m i , F0
Om,,i 1 . I 1 , .
, I Fr , Fr
I(I-1) . , , (i1, j1), (i2, j2),…, (il, jl) ,
s 1) (i1,j1) (j1,i1) ,
, t (i2,j2),…,(il,jl) .
. 2) (i1,j1) , (i2,j2)
(j2,i2) , (i3,j3),…,(il,jl) .
o1,1 o2,1 o3,1
…………
s o1,2 o3,2 o2,2 t l) (i1,j1),…,(il-1,jl-1) , (jl,il) .
o1,3 o3,3 l , .
o2,3
,
1 , .
Balas .
, . (i) Fr
, F .
F i , Fr .
i , (ii) Fr
, .
d[F] , ,
, d[F] s t F* .
--- --- .
d[ F̂ ] = min d[F] b_and_b .
d[ F̂ ] b_and_b ( Fr ){
-2-
v(Fr) ; 4
if ( v(Fr) v*){ ,
d, , ; 1 .
if( d < v*) F* v* ;
1
Fn=Fr;
, 1
while( ){
.
(i, j)= ;
Fc=Fn; Balas[1] ,
Fc (j, i) , Fn (i, j) ; DL .
b_and_b (Fc); DL ,
}}}
. 1 ,
3 .
, Balas[1] , 1 ,
, . [3] ,
, 1, 2, 3,…, 7 3,4,5 .
…, M 2 . CPU 266MHz, 64MB .
1, 2 .
o1,1 o2,1 o3,1
1
s o1,2 o3,2 o2,2 t Balas[1]
o1,3 o3,3 8303.02 20652.68 2.66
o2,3
112877 273773 21.41
2 3, 3 16 19 1
2
,
Balas[1]
(0) , (1), (2)
8.98 21.78 2.43
.
137 311 2.27
(1) (0) ,
0.5 0.5 1
.
5
, ,
(1), (2) , Balas
,
[1] 1
.
. (1)
(2) (0) ,
,
.
, D*
, ,
-3-
( 3). , 1 2 3
. 1 1 2 3
2 2 1 1
w1(1) 3
3 3 3 2
0 5
0 9
s w1(2) 4 t 2 w2(2)
0 2
w1(3)
2 2 , 1 , 1
1 1 . 1 1 2
1 , 2 2
.
, .
w1(1),w1(2),w1(3) ,
6
, w1(1),w1(3) , 8
10 .
, Balas[1] ,
.
5.1
,
,
, ,
D , ,
,
. ,
.
. , ,
[1] [Link], Machine sequencing via disjunctive graphs :
an implicit enumeration algorithm, J. ORSA, 17,
.
941-957 (1969).
4 .
[2] : ,
1 2 3 1 2 3
( ): III, , 1994.
1 1 2 3 1 1 2 2
[3] [Link], [Link], [Link] : Benchmarks for shop
2 2 1 1 2 2 1 3
scheduling problem, European J. Operational
3 3 3 2 3 3 3 1
Research, 109, 137-141 (1998).
3 3, 3 [4] : , , 1986.
[5] , : , , 2002.
[6] OR ( ): OR 2000.
, (1) (2)
[7] [Link], [Link], [Link] : The disjunctive
Balas ,
graph machine representation of the job shop
,
scheduling problem, European J. Operational
5 .
Research,127,317-331 2000
- 4 -E
