Giáo trình Toán rời rạc (Phần 1)

 ®Ønh kh¸c nhau. 
Khi ®ã ta sÏ chän ®•a vµo hµnh tr×nh c¸c c¹nh t•¬ng øng víi c¸c phÇn tö 0 vµ 
ta ®•îc mét hµnh tr×nh T víi chi phÝ thùc tÕ lµ G. NÕu gi¸ trÞ G nhá h¬n tÊt c¶ 
c¸c cËn d•íi cña c¸c nh¸nh ®· bá qua th× hµnh tr×nh nhËn ®•îc lµ hµnh tr×nh 
tèi •u, nÕu kh«ng th× G lín h¬n gi¸ trÞ cËn d•íi cña mét nh¸nh nµo ®ã vµ khi 
®ã th× hµnh tr×nh nhËn ®•îc ch•a ph¶i lµ hµnh tr×nh tèi •u, ta tiÕp tôc ¸p dông 
thuËt to¸n nh¸nh cËn cho nh¸nh nµy ®Ó t×m hµnh tr×nh míi. 
 ¸p dông tiÕp tôc nh÷ng ®iÒu ®ã vµo vÝ dô trªn ta thu ®•îc mét hµnh tr×nh 
®•îc m« t¶ trong h×nh sau: 
 88 
 Tập tất cả Tập hà nh 
 các hành trình không 
 trình chứa 
 (6,3) 
 CËn d•íi = 81 CËn d•íi = 129 
 TËp c¸c TËp c¸c hà nh 
 hà nh tr×nh tr×nh kh«ng chøa 
 chøa (4,6) 
 (6,3) CËn d•íi = 81 
 CËn d•íi = 113 
 TËp c¸c TËp c¸c hà nh 
 hà nh tr×nh tr×nh kh«ng chøa 
 chøa (2,1) 
 (4,6) CËn d•íi = 81 CËn d•íi = 101 
 TËp c¸c hà nh TËp c¸c hà nh tr×nh 
 tr×nh chøa kh«ng chøa 
 (2,1) (1,4) 
 CËn d•íi = 84 
 CËn d•íi = 112 
 TËp c¸c hà nh 
 tr×nh chøa 
 (1,4) 
 CËn d•íi = 84 
 Hµnh tr×nh gåm c¸c c¹nh (6,3); (4,6); (2,1); (1,4); (3,5); (5,2) 
 H×nh 5.3 
 Hà nh tr×nh thu ®•îc theo h×nh 5.3 lµ hµnh tr×nh (1, 4, 6, 3, 5, 2, 1) cã 
chi phÝ G = 104. B©y giê tÊt c¶ c¸c nót cña c©y cã cËn d•íi lín h¬n 104 cã thÓ 
lo¹i bá v× chóng kh«ng chøa hµnh tr×nh rÎ h¬n. 
 Trªn h×nh 5.3 ta thÊy chØ cßn nót cã cËn d•íi 101 lµ cÇn ph¶i xÐt tiÕp. Nót 
nµy t•¬ng øng víi tËp nh÷ng hµnh tr×nh chøa c¸c c¹nh (6,3), (4, 6) vµ kh«ng 
chøa c¹nh (2,1). Ma trËn chi phÝ t•¬ng øng víi nh¸nh nµy lµ: 
 89 
 1 2 4 5 
 1 0 2 30 
 2 13 0 
 3 26 1 0 
 5 0 21 0 
 TiÕp tôc ¸p dông thuËt to¸n nh¸nh cËn cho nh¸nh nµy, ta thu ®•îc hµnh 
tr×nh 1, 4, 6, 3, 2, 5, 1 víi chi phÝ 104 
 Nh• vËy chóng ta thu ®•îc hai hµnh tr×nh tèi •u víi chi phÝ lµ 104. VÝ dô 
trªn cho thÊy r»ng bµi to¸n ng•êi du lÞch cã thÓ cã nhiÒu ph•¬ng ¸n tèi •u. 
Trong thÝ dô nµy hµnh tr×nh ®Çu tiªn t×m ®•îc ®· lµ tèi •u, tÊt nhiªn ®iÒu ®ã 
kh«ng thÓ tr«ng ®îi trong tr•êng hîp tæng qu¸t. §èi víi thÝ dô trªn ta chØ ph¶i 
xÐt 13 nót trong khi tæng sè hµnh tr×nh cña ng•êi du lÞch lµ 120. 
5.3.3. ThuËt to¸n nh¸nh cËn gi¶i bµi to¸n ng•êi du lÞch 
 C¸c b•íc chÝnh cña thuËt to¸n nh¸nh cËn gi¶i bµi to¸n ng•êi du lÞch ®•îc 
m« t¶ trong thñ tôc ®Ö qui TSP sau ®©y. Thñ tôc TSP xÐt hµnh tr×nh bé phËn 
víi Edges c¹nh ®· ®•îc chän vµ tiÕn hµnh t×m kiÕm tiÕp theo. Ta sö dông c¸c 
biÕn: 
Edges - sè c¹nh trong hµnh tr×nh bé phËn ; 
A - ma trËn chi phÝ t•¬ng øng víi kÝch th•íc (n-edges) (n-edges); 
cost -chi phÝ cña hµnh tr×nh bé phËn. 
Mincost - chi phÝ cña hµnh tr×nh tèt nhÊt ®· t×m ®•îc. 
Trong thñ tôc sö dông hà m Reduce(A, K) và thñ tôc BestEdge(A, k, r, c, 
beta) 
 Proceduce TSP(edges, cost, A); 
 begin 
 cost:= cost +reduce(A, n-edges); 
 if edges = n-2 then 
 begin 
 ; 
 Mincost := cost; 
 90 
 ; 
 end 
 else 
 begin 
 BestEdge(A,n-edges,g,c,beta); 
 lowerBound:= cost + beta; 
 ; 
 newA := 
 TSP(edges+1, cost, newA); (* ®i theo nh¸nh tr¸i * ) 
 ; 
 If LowerBound <Mincost then 
 begin (*®i theo nh¸nh ph¶i*) 
 A[r,c]:= ; 
 TSP(edges, cost, A); 
 A[r,c]:=0 ; 
 end; 
 end; 
 ; (* thªm l¹i c¸c h»ng sè rót gän 
 vµo c¸c dßng vµ c¸c cét t•¬ng øng *) 
 end; 
5.4. Bµi to¸n lËp lÞch gia c«ng trªn hai m¸y. ThuËt to¸n Jonhson. 
 Bµi to¸n tèi •u cho viÖc s¾p xÕp lÞch gia c«ng cho mét d©y chuyÒn s¶n xuÊt 
c«ng nghiÖp nÕu ®•îc gi¶i quyÕt sÏ gãp phÇn rÊt lín trong viÖc n©ng cao hiÖu 
qu¶ s¶n xuÊt. Tuy nhiªn víi nh÷ng d©y chuyÒn gåm nhiÒu m¸y, nhiÒu c«ng 
®o¹n th× ®ã lµ mét bµi to¸n khã víi kÝch cì lín, ch•a cã lêi gi¶i trän vÑn. 
 Trong môc nµy ta chØ xÐt bµi to¸n ë d¹ng ®¬n gi¶n nhÊt chØ gåm hai m¸y 
gia c«ng. 
5.4.1. Bµi to¸n lËp lÞch gia c«ng trªn hai m¸y 
 Néi dung bµi to¸n ®•îc ph¸t biÓu nh• sau: 
 91 
 Mçi mét chi tiÕt trong sè n chi tiÕt D 1 , D2,, Dn cÇn ph¶i ®•îc lÇn l•ît 
gia c«ng trªn 2 m¸y A, B. Thêi gian gia c«ng chi tiÕt Di trªn m¸y A lµ ai, trªn 
m¸y B lµ bi (i=1, 2, ..., n). H·y t×m lÞch (tr×nh tù gia c«ng) c¸c chi tiÕt trªn hai 
m¸y sao cho viÖc hoµn thµnh gia c«ng tÊt c¶ c¸c chi tiÕt lµ sím nhÊt cã thÓ 
®•îc. 
 Gi¶ thiÕt r»ng tr×nh tù gia c«ng c¸c chi tiÕt trªn hai m¸y lµ nh• nhau. Khi 
®ã mét lÞch gia c«ng sÏ t•¬ng øng víi mét ho¸n vÞ 
 ( (1), (2),..., (n)) cña n sè tù nhiªn 1, 2,, n. 
 Ký hiÖu Sjx (Starat) vµ Ejx (End) lµ thêi ®iÓm b¾t ®Çu vµ kÕt thóc viÖc gia 
c«ng chi tiÕt j trªn m¸y X, j = 1, 2,, n; x = A, B. Gi¶ sö lµ mét lÞch gia 
c«ng. Theo ®iÒu kiÖn cña bµi to¸n, m¸y A cã thÓ b¾t ®Çu thùc hiÖn c«ng viÖc 
 (1) vµo thêi ®iÓm s (1) 0 vµ c«ng viÖc (k) sau khi thùc hiÖn xong c«ng viÖc 
 (k 1), tøc lµ: 
 S (k) A E (k 1) A , k = 2, 3,, n. (1) 
M¸y B cã thÓ b¾t ®Çu thùc hiªn c«ng viÖc (1) ngay sau khi m¸y A kÕt thóc 
viÖc gia c«ng nã tøc lµ vµo thêi ®iÓm: S ( 1 ) B E ( 1 ) A (2) 
M¸y B cã thÓ b¾t ®Çu viÖc gia c«ng chi tiÕt (k) (k = 2, 3,., n) sau khi c«ng 
viÖc nµy ®•îc thùc hiÖn xong trªn m¸y A vµ ®ång thêi nã ph¶i hoµn thµnh viÖc 
gia c«ng chi tiÕt , tøc lµ: 
 S (k)B max( E (k) A , E (k 1)B ), k= 2, 3,, n. (3) 
 Thêi gian ®Ó hoµn thµnh viÖc gia c«ng tÊt c¶ c¸c chi tiÕt trªn hai m¸y lµ 
T( ) = E (n)B . 
 Râ rµng, víi cè ®Þnh, E( ) ®¹t gi¸ trÞ nhá nhÊt khi tÊt c¶ c¸c dÊu bÊt 
®¶ng thøc ë (1), (2), (3) ®•îc thay b»ng dÊu ®¼ng thøc, tøc lµ: 
 S (1) A 0 , 
 S (k) A E (k 1) A ,k 2,3,...,n, 
 S (1)B E (1) A, (4) 
 S (k)B max( E (k) A , E (k 1)B ) , k = 2, 3,,n. 
nghÜa lµ c¸c m¸y sÏ thùc hiÖn ngay c¸c c«ng viÖc mét khi ®iÒu kiÖn cho phÐp. 
VÝ dô 5.8. XÐt bµi to¸n khi n = 5. Thêi gian gia c«ng c¸c chi tiÕt trªn c¸c m¸y 
®•îc cho trong b¶ng sau: 
 Chi tiÕt 
 D D D 3 D D 5 
 M¸y 1 2 4
 A 3 4 6 5 6 
 B 3 3 2 7 3 
 92 
 Gi¶ sö thùc hiÖn viÖc gia c«ng c¸c chi tiÕt theo lÞch (1, 2, 3, 4, 5). Khi 
®ã, theo c¸c c«ng thøc (4) ta tÝnh ®•îc 
 S1A 0; E1A 3;
 S 2 A 3; E2 A 7;
 S3A 7; E3A 13;
 S 4 A 13; E4 A 18;
 S5 A 18; E5 A 24;
 S1B 3; E1B 6;
 S 2B 7; E2B 10;
 S3B 13; E3B 15;
 S 4B 18; E4B 25;
 S5B 25; E5B 28;
 §Ó biÓu diÔn lÞch gia c«ng ng•êi ta th•êng sö dông s¬ ®å Gantt, trong ®ã 
c¸c m¸y ®•îc biÓu thÞ theo trôc tung, cßn trôc hoµnh ®Ó biÓu diÔn thêi gian. S¬ 
®å Gantt, theo lÞch gia c«ng thu ®•îc trong vÝ dô ®· cho, cã d¹ng trong h×nh 
sau: 
 M¸y 
 B D 1 D 2 D 3 D 4 D 5 
 A D D D D D t 
 H×nh 5.4 
 Thêi gian hoµn thµnh viÖc gia c«ng tÊt c¶ c¸c chi tiÕt theo lÞch thu ®•îc lµ 
T( ) = E5B =28. Tõ h×nh 5.4 nhËn thÊy r»ng trong c¸ch bè trÝ m¸y B thùc hiÖn 
viÖc gia c«ng c¸c chi tiÕt theo lÞch gia c«ng cã nhiÒu kho¶ng thêi gian m¸y 
chÕt (trªn h×nh vÏ ®¸nh dÊu b»ng c¸ch t« mµu sÉm). Râ rµng ta lu«n cã thÓ bè 
trÝ l¹i viÖc gia c«ng cña m¸y B sao cho kh«ng cã c¸c kho¶ng thêi gian chÕt 
 93 
b»ng c¸ch dån chóng vµo ®o¹n ®Çu ®Ó sau ®ã m¸y B ho¹t ®éng liªn tôc vµ viÖc 
nµy kh«ng lµm t¨ng thêi gian hoµn thµnh viÖc gia c«ng (gi¸ trÞ E (n)B ). Ch¼ng 
h¹n, ®Ó tho¸t khái c¸c kho¶ng thêi gian chÕt cña m¸y B trong vÝ dô, ta cã thÓ 
b¾t ®Çu gia c«ng trªn m¸y B vµo thêi ®iÓm d B 10 (tøc lµ b»ng tæng c¸c 
kho¶ng thêi gian chÕt trong h×nh 5.4, céng víi E (1) A ). 
 V× vËy lu«n cã thÓ gi¶ thiÕt r»ng, hai m¸y sÏ thùc hiÖn viÖc gia c«ng mét 
c¸ch liªn tôc. M¸y A b¾t ®Çu thùc hiÖn viÖc gia c«ng vµo thêi ®iÓm d A 0 . 
Gäi d B lµ thêi ®iÓm m¸y B b¾t ®Çu thùc hiÖn viÖc gia c«ng c¸c chi tiÕt. Râ 
rµng ta cã : 
 n
 T( ) d B ( ) b j (5) 
 j 1
Trong ®ã sè h¹ng thø 2 lµ kh«ng phô thuéc vµo lÞch gia c«ng . Ta cÇn t×m 
c«ng thøc tÝnh dB( ). DÔ thÊy lµ dB( ) lµ b»ng tæng cña E (1) A vµ c¸c kho¶ng 
thêi gian chÕt cña m¸y B khi ta bè trÝ m¸y B thùc hiÖn viÖc gia c«ng c¸c chi 
tiÕt theo c«ng thøc (4). V× thÕ, ta cã c«ng thøc sau ®©y ®Ó tÝnh dB( ): 
 dB( ) = max u ( ) 
 1 u n 
Trong ®ã 
 1 ( ) a (1) ,
 u u 1 u = 2, , n. 
 u ( ) a ( j) b ( j) ,
 j 1 j 1
Trong vÝ dô 5.8, ta cã 
 ∆1( ) = 3 
 ∆2( ) = 3 + 4 -3 = 4 
 ∆3( ) = (3 + 4 + 6) - ( 3 + 3) = 7 
 ∆4( ) = (3 + 4 + 6 + 5) - ( 3 + 3 +2) = 10 
 ∆5( ) =(3 + 4 + 6 + 5 + 6) - ( 3 + 3 +2 +7) = 9 
VËy d B ( ) 10. Vµ theo (5) ta ®•îc T( ) = 10 + 18 = 28. 
5.4.2. §Þnh lý Johnson 
 §Ó gi¶i bµi to¸n lËp lÞch cho hai m¸y, ng•êi ta ®· x©y dùng thuËt to¸n dùa 
trªn ®Þnh lý Johnson. 
 94 
Bæ ®Ò 1. Gi¶ sö ( (1),..., (k 1), (k), (k 1),..., (n)) lµ mét lÞch gia c«ng 
cßn ' lµ lÞch gia c«ng thu ®•îc tõ b»ng c¸ch ho¸n vÞ hai phÇn tö (k) vµ 
 (k 1) : 
 ' ( (1),..., (k 1), (k 1), (k),..., (n)) . 
Khi ®ã nÕu 
 min(a (k) ,b (k 1) ) min(b (k) ,a (k 1) ) (6) 
Th× 
 '
 d B ( ) d B ( ). (7) 
Chøng minh. Do , ' chØ kh¸c nhau ë vÞ trÝ thø k vµ k+1 nªn ta cã 
 '
 u ( ) u ( ) víi u=1,, k-1, k+2,,n. 
Tõ ®ã ®Ó chøng minh (7) ta chØ cÇn chøng tá: 
 ' '
 max( k ( ), k 1 ( )) max( k ( ), k 1 ( )) (8) 
ThËt vËy, bÊt ®¼ng thøc (7) t•¬ng ®•¬ng víi 
 ' '
 max( k ( ) , k 1 ( )  ) max( k ( ) , k 1 ( )  ) (9) 
Víi mäi gi¸ trÞ  . Chän 
 k 1 k 1
  a ( j) b ( j) 
 j 1 j 1
Vµ ®Ó ý r»ng 
 k k 1
 k ( ) a ( j) b ( j) , 
 j 1 j 1
Ta nhËn ®•îc (9) d•íi d¹ng: 
 max( a (k 1) , b (k) ) max( a (k) , b (k 1) ) (10) 
 min(a (k 1) ,b (k) ) min(a (k) ,b (k 1) ) 
 min(a (k) ,b (k 1) ) min(b (k) ,a (k 1) ) 
nghÜa lµ (8) t•¬ng ®•¬ng víi (6) vµ bæ ®Ò ®•îc chøng minh. 
Bæ ®Ò 2. NÕu i, j, k lµ 3 chØ sè tho¶ m·n 
 min(ai ,b j ) min(a j ,bi ) (11) 
 min(a j ,bk ) min(ak ,b j ) (12) 
Th× 
 95 
 min(ai ,bk ) min(ak ,bi ) (13) 
Chøng minh. Gi¶ sö trong (11) ta cã ai b j vµ a j bi , cßn trong (12) ta cã 
a j bk vµ ak b j . Khi ®ã tõ (11) suy ra ai a j , tõ (12) suy ra a j ak . Tøc lµ 
ta cã ai bi , ai bk vµ ai ak , tõ ®ã suy ra cã (13). 
 Chøng minh t•¬ng tù cho c¸c tr•êng hîp cßn l¹i, ta thu ®•îc bæ ®Ò. 
§Þnh lý Jonhson(1954). T( ) ®¹t gi¸ trÞ nhá nhÊt khi lÞch gia c«ng 
 ( (1), (2),..., (n)) tho¶ m·n 
 min(a (k), b (k+1)) min(b (k), a (k+1)) víi mäi k= 1, 2, n-1. (14) 
Chøng minh. Thùc vËy gi¶ sö ' =( '(1), '(2),, '(n)) lµ lÞch gia c«ng tèi 
•u. NÕu kh«ng tháa m·n (14), th× theo bæ ®Ò 1, khi thay ®æi vÞ trÝ cña hai 
phÇn tö liÒn nhau t•¬ng øng trong nã, ta thu ®•îc lÞch gia c«ng míi víi 
d  ( ) kh«ng lín h¬n d  ( ). Qu¸ tr×nh nµy ®•îc lÆp l¹i ®èi víi cho ®Õn 
khi thu ®•îc lÞch tháa m·n (14). Bæ ®Ò 2 b¶o ®¶m viÖc lÆp nh• thÕ lµ kÕt thóc. 
§Þnh lý ®•îc chøng minh. 
 §Þnh lý võa chøng minh chØ cho chóng ta c¬ së x©y dùng thuËt to¸n gi¶i 
bµi to¸n ®Æt ra. Gi¶ sö 
 x = min (ai, bi) ; 1≤i≤n 
 XÐt hai tr•êng hîp: 
 1. NÕu x = a k víi mét cét k nµo ®ã th× ta cã min (a , b j ) min (b , a j ) 
víi mäi j k . V× thÕ chi tiÕt D  ph¶i ®•îc gia c«ng ®Çu tiªn trong lÞch tèi •u. 
 2. NÕu x = bp víi mét p nµo ®ã th× ta cã min (ap, bj) min (bp, aj ) víi mäi 
j p. V× thÕ chi tiÕt Dp ph¶i ®•îc gia c«ng cuèi cïng trong lÞch tèi •u. 
 Tõ ®ã nhËn ®•îc thuËt to¸n sau ®©y 
5.4.3. ThuËt to¸n Johnson 
 1. Chia c¸c chia tiÕt thµnh hai nhãm: Nhãm N1 gåm c¸c chi tiÕt Di tháa 
 m·n ai < bi tøc lµ min(ai, bi) ®¹t ®•îc t¹i ai, vµ nhãm N2 gåm c¸c chi tiÕt Di 
tháa m·n ai > bi, tøc lµ min(ai, bi) ®¹t ®•îc t¹i bi. C¸c chi tiÕt Di tháa m·n ai= 
bi xÕp vµo nhãm nµo còng ®•îc. 
 9 6 
 2. S¾p xÕp c¸c chi tiÕt trong N1 theo chiÒu t¨ng dÇn cña c¸c ai vµ s¾p xÕp 
c¸c chi tiÕt trong N2 theo chiÒu gi¶m dÇn cña c¸c bi. 
 3. Nèi N2 vµo ®u«i N1. D·y thu ®•îc (däc tõ tr¸i sang ph¶i) sÏ lµ lÞch gia 
c«ng tèi •u. 
 Trë l¹i gi¶i bµi to¸n trong vÝ dô 5.8 theo thuËt to¸n Johnson: C¸c kÕt qu¶ 
®•îc tÝnh trong tõng b•íc nh• sau: 
 1. Chia nhãm: N1 = {D1, D4}; N2 = { D2, D3, D5} 
 2. S¾p xÕp N1 theo chiÒu t¨ng dÇn cña c¸c ai vµ s¾p xÕp N2 theo chiÒu 
gi¶m dÇn cña c¸c bi: 
 N1 = {D1, D4} 
 N2 = { D2, D5, D3} 
 3. Nèi N2 vµo ®u«i cña N1, ta ®•îc lÞch gia c«ng tèi •u: 
 = (D1, D4, D2, D5, D3). 
 S¬ ®å Gantt cña lÞch nµy ®•îc cho bëi h×nh 5.5 víi thêi gian hoµn thµnh 
viÖc gia c«ng lµ T( ) = 26: 
 M¸y 
 B D1 D4 D2 D5 D3 
 A D1 D4 D2 D5 D3 
 t 
 H×nh 5.5 
Cã thÓ cã nhiÒu lÞch tèi •u, chóng cã thÓ kh¸c nhau vÒ thêi ®iÓm b¾t ®Çu cña 
m¸y B nh•ng ®Òu chung mét thêi ®iÓm kÕt thóc. Ch¼ng h¹n mét lÞch tèi •u 
kh¸c cña vÝ dô trªn lµ ’ = (D 4 , D 1 , D5, D2, D 3 ) víi s¬ ®å Gantt cho bëi h×nh 
5.6: 
 M¸y 
 B D4 D1 D5 D2 D3 
 A D4 D1 D5 D2 D3 t 
 H×nh 5.6 
 97 
Chó ý 
 1. Cã thÓ chøng minh ®•îc r»ng lÞch gia c«ng d•íi d¹ng mçi m¸y mét 
tr×nh tù gia c«ng riªng kh«ng dÉn tíi viÖc hoµn thµnh gia c«ng c¸c chi tiÕt sím 
h¬n. V× vËy, thuËt to¸n Johnson vÉn cho kÕt qu¶ ®óng cña bµi to¸n mµ kh«ng 
cÇn cã gi¶ thiÕt r»ng tr×nh tù gia c«ng trªn hai m¸y ph¶i nh• nhau. 
 2. Kh«ng thÓ thu ®•îc ®Þnh lý t•¬ng tù nh• ®Þnh lý Johnson cho tr•êng 
hîp bµi to¸n 3 m¸y hoÆc nhiÒu h¬n.Trong tr•êng hîp tæng qu¸t, hiÖn nay ch•a 
cã ph•¬ng ph¸p h÷u hiÖu nµo ®Ó gi¶i chóng ngoµi viÖc sö dông ph•¬ng ph¸p 
nh¸nh cËn. 
Mét sè tr•êng hîp riªng cã thÓ dÉn vÒ bµi to¸n 2 m¸y. 
 XÐt bµi to¸n gia c«ng n chi tiÕt trªn 3 m¸y theo thø tù A, B, C víi b¶ng 
thêi gian ai, bi, ci i = 1, 2,, n, tháa m·n: 
 max bi min ai hoÆc max bi minci 
 1 i n 1 i n 1 i n 
 1 i n 
tøc lµ thêi gian gia c«ng cña m¸y B kh¸ nhá so víi A hoÆc C. 
 Khi ®ã, lÞch gia c«ng tèi •u trªn 3 m¸y sÏ trïng víi lÞch gia c«ng tèi •u trªn 
2 m¸y: m¸y thø nhÊt víi thêi gian ai + bi vµ m¸y thø hai víi thêi gian bi + ci 
(chó ý r»ng chØ cã lÞch tèi •u cña chóng lµ trïng nhau cßn thêi gian gia c«ng 
cña chóng lµ kh¸c nhau). 
VÝ dô 5.9. Cho 5 chi tiÕt D1, D2, D3, D4, D5 ®•îc lÇn l•ît gia c«ng trªn ba 
m¸y A, B, C víi thêi gian nh• sau: 
 Chi tiÕt 
 D1 D2 D3 D4 D5 
 M¸y 
 A 7 11 8 7 6 
 B 6 5 3 5 3 
 C 4 12 7 8 3 
T×m lÞch gia c«ng tèi •u vµ vÏ s¬ ®å Gantt. 
Gi¶i: Ta cã max bi = 6 min ai = 6, do ®ã bµi to¸n ®•îc dÉn vÒ viÖc t×m lÞch 
gia c«ng tèi •u trªn 2 m¸y ', ': 
 Chi tiÕt 
 D1 D2 D3 D4 D5 
 M¸y 
 A’ 13 16 11 12 9 
 B’ 10 17 10 13 6 
 98 
 LÞch gia c«ng tèi •u 5 chi tiÕt trªn 2 m¸y A' , B' t×m ®•îc theo thuËt to¸n 
Johnson lµ = (D4, D2, D1, D3, D5) vµ ®ã còng lµ lÞch gia c«ng tèi •u cña 5 
chi tiÕt ®· cho trªn 3 m¸y A, B, C. Theo lÞch ®ã thêi gian hoµn thµnh viÖc gia 
c«ng 5 chi tiÕt lÇn l•ît trªn 3 m¸y A, B, C lµ T( ) = 49 vµ s¬ ®å Gantt cho bëi 
h×nh d•íi ®©y: 
 M¸y 
 C 4 2 1 3 5 
 B 4 2 1 3 5 
 A 4 2 1 3 5 t 
 H×nh 5.7 
 99 
 bµi tËp ch•¬ng 5 
1. Dïng thuËt to¸n nh¸nh cËn t×m hµnh tr×nh tèi •u cho bµi to¸n ng•êi du lÞch 
víi ma trËn chi phÝ nh• sau: 
 7 6 5 8 
 3 9 8 6 
 C = 6 5 7 3 
 8 7 5 6 
 10 9 8 6 
2. Dïng thuËt to¸n nh¸nh cËn t×m hµnh tr×nh tèi •u cho bµi to¸n ng•êi du lÞch 
víi ma trËn chi phÝ nh• sau: 
 7 11 6 8 
 4 9 12 7 
 C = 16 8 5 10 
 6 7 9 16 
 15 9 18 5 
3. ¸p dông thuËt to¸n nh¸nh cËn cho bµi to¸n c¸i tói 
4. Cho c¸c chi tiÕt D1, D2, D3, D4, D5 ®•îc lÇn l•ît gia c«ng trªn hai m¸y 
A, B víi thêi gian nh• sau: 
 Chi tiÕt 
 D1 D2 D3 D4 D5 
 M¸y 
 A 4 3 5 6 7 
 B 3 3 8 4 2 
 T×m c¸c lÞch gia c«ng tèi •u vµ vÏ s¬ ®å Gantt. 
5. Cho 5 chi tiÕt D1, D2, D3, D4, D5 ®•îc lÇn l•ît gia c«ng trªn ba m¸y A, 
B, C víi thêi gian nh• sau: 
 Chi tiÕt 
 D1 D2 D3 D4 D5 
 M¸y 
 A 6 8 7 9 11 
 B 5 4 6 2 3 
 C 10 9 8 12 7 
 T×m lÞch gia c«ng tèi •u vµ vÏ s¬ ®å Gantt. 
 100