Báo cáo khoa học: "CáC bài toán quy hoạch lịch trong xây dựng và ph-ơng pháp giải"

Chia sẻ: Nguyễn Phương Hà Linh Nguyễn Phương Hà Linh | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

64
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Do đặc điểm của sản xuất xây dựng, các bài toán quy hoạch lịch trong xây dựng th-ờng lớn và rất phức tạp. Vì vậy, việc sử dụng các ph-ơng pháp toán học quen thuộc nh- quy hoạch tuyến tính, quy hoạch động, lý thuyết phục vụ đám đông v.v…

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo khoa học: "CáC bài toán quy hoạch lịch trong xây dựng và ph-ơng pháp giải"

C¸C bμi to¸n quy ho¹ch lÞch trong x©y dùng vμ ph−¬ng ph¸p gi¶i TS. bïi träng cÇu Bé m«n X©y dùng c¬ së h¹ tÇng Khoa C«ng tr×nh - Tr−êng §¹i häc GTVT Tãm t¾t: Do ®Æc ®iÓm cña s¶n xuÊt x©y dùng, c¸c bμi to¸n quy ho¹ch lÞch trong x©y dùng th−êng lín vμ rÊt phøc t¹p. V× vËy, viÖc sö dông c¸c ph−¬ng ph¸p to¸n häc quen thuéc nh− quy ho¹ch tuyÕn tÝnh, quy ho¹ch ®éng, lý thuyÕt phôc vô ®¸m ®«ng v.v… ®Ó gi¶i c¸c bμi to¸n quy ho¹ch lÞch trong x©y dùng th−êng kh«ng mang l¹i kÕt qu¶ mong muèn. Bμi b¸o nμy tr×nh bμy kh¸i qu¸t vÒ c¸c bμi to¸n quy ho¹ch lÞch trong x©y dùng, ®Ò xuÊt ph−¬ng h−íng gi¶i, vμ giíi thiÖu mét gi¶i thuËt (heuristics) m¹nh cho phÐp gi¶i gÇn ®óng mét líp réng c¸c bμi to¸n quy ho¹ch lÞch trong x©y dùng. Summary: Schedule programming problems in construction are usually big and complicated due to particular characteristics of construction production. Therefore, the use of conventional mathematic methods such as linear programming, dynamic programming, queueing theory, etc., to solve the schedule programming problems in construction does not give satisfied results as expected. This paper briefly presents the schedule programming problems in construction, proposes a solving strategy, and introduces a strong heuristics that can be applied to solving a wide range of the schedule programming problems in construction. Do ®Æc ®iÓm cña s¶n xuÊt x©y dùng, c¸c bµi to¸n quy ho¹ch lÞch trong x©y dùng th−êng i. më ®Çu lín (M vµ n lín) vµ rÊt phøc t¹p. V× vËy, viÖc Bµi to¸n quy ho¹ch lÞch trong tæ chøc thi sö dông c¸c ph−¬ng ph¸p to¸n häc quen c«ng vµ tæ chøc x©y dùng, gäi t¾t lµ c¸c bµi thuéc nh− quy ho¹ch tuyÕn tÝnh, quy ho¹ch to¸n quy ho¹ch lÞch trong x©y dùng, ®−îc m« ®éng, lý thuyÕt phôc vô ®¸m ®«ng v.v… ®Ó t¶ mét c¸ch ng¾n gän vµ chÝnh x¸c nh− sau. gi¶i c¸c bµi to¸n quy ho¹ch lÞch trong x©y Gi¶ sö cÇn thùc hiÖn n c«ng viÖc trªn mét hÖ dùng th−êng kh«ng mang l¹i kÕt qu¶ mong thèng gåm M m¸y. C«ng viÖc ë ®©y cã thÓ lµ muèn do kh«ng thÓ m« h×nh ho¸ chÝnh x¸c bµi mét c«ng t¸c, mét h¹ng môc c«ng tr×nh, mét to¸n. Trong mét sè tr−êng hîp “®¬n gi¶n”, cã c«ng tr×nh cÇn x©y dùng v.v… cßn m¸y cã thÓ thÓ m« h×nh ho¸ chÝnh x¸c vÊn ®Ò ®Æt ra th× lµ mét m¸y thi c«ng, mét tæ, mét ®éi s¶n xuÊt, bµi to¸n trë thµnh ®éng, phi tuyÕn víi nhiÒu hoÆc thËm chÝ mét xÝ nghiÖp x©y l¾p v.v... rµng buéc qu¸ phøc t¹p tíi møc, nh− ®· ®−îc VÊn ®Ò ®Æt ra cho c¸c bµi to¸n quy ho¹ch lÞch chøng minh, lµ kh«ng thÓ gi¶i ®−îc. Bµi b¸o trong x©y dùng lµ cÇn bè trÝ c¸c c«ng viÖc cho nµy sÏ tr×nh bµy kh¸i qu¸t vÒ c¸c bµi to¸n quy tõng m¸y theo mét lÞch c«ng t¸c nµo ®ã tho¶ ho¹ch lÞch trong x©y dùng, ®Ò xuÊt ph−¬ng m·n c¸c yªu cÇu vÒ c«ng nghÖ vµ rµng buéc h−íng gi¶i vµ giíi thiÖu mét gi¶i thuËt m¹nh vÒ thêi gian, c¸c nguån tµi nguyªn v.v… nh»m cho phÐp gi¶i gÇn ®óng mét líp réng c¸c bµi ®¹t ®−îc mét hoÆc mét vµi tiªu chuÈn tèi −u to¸n quy ho¹ch lÞch trong x©y dùng. ®· ®Þnh.
xuÊt c«ng nghiÖp vµ c¸c ngµnh kh¸c nªn c¸c ii. ph©n lo¹i c¸c bμi to¸n quy bµi to¸n quy ho¹ch lÞch trong x©y dùng cã hai ho¹ch lÞch trong x©y dùng ®Æc ®iÓm riªng, rÊt kh¸c biÖt nh− sau: Cã thÓ chia c¸c bµi to¸n quy ho¹ch lÞch 1. §Æc ®iÓm thø nhÊt trong x©y dùng thµnh c¸c líp bµi to¸n sau ®©y: C¸c bµi to¸n quy ho¹ch lÞch trong x©y 1. C¸c bµi to¸n s¾p thø tù dùng th−êng lín (tøc lµ M vµ n lín). Lµ c¸c bµi to¸n ®· biÕt tr−íc sù ph©n bæ 2. §Æc ®iÓm thø thø hai c¸c c«ng viÖc cho c¸c m¸y. VÊn ®Ò ®Æt ra lµ C¸c bµi to¸n quy ho¹ch lÞch trong x©y s¾p xÕp thø tù thùc hiÖn c¸c c«ng viÖc cho dùng th−êng rÊt phøc t¹p so víi c¸c bµi to¸n tõng m¸y mét c¸ch hîp lý nhÊt ®Ó ®¹t ®−îc quy ho¹ch lÞch trong c«ng nghiÖp vµ c¸c mét hay nhiÒu tiªu chuÈn tèi −u ®· ®Þnh. §©y ngµnh kh¸c. TÝnh phøc t¹p cña c¸c bµi to¸n lµ líp bµi to¸n ®¬n gi¶n nhÊt. quy ho¹ch lÞch trong x©y dùng thÓ hiÖn ë c¸c 2. C¸c bµi to¸n ph©n bæ ®iÓm sau: Lµ c¸c bµi to¸n ®ßi hái ph©n bæ c¸c c«ng - ViÖc thùc hiÖn c¸c c«ng viÖc ph¶i tu©n viÖc cho tõng m¸y víi gi¶ thiÕt lµ c¸c m¸y cã theo mét tr×nh tù c«ng nghÖ nhÊt ®Þnh. ThÝ dô: thÓ thùc hiÖn nhiÒu c«ng viÖc kh¸c nhau nh»m ph¶i ghÐp v¸n khu«n, ®Æt cèt thÐp xong míi ®¹t ®−îc mét hay nhiÒu tiªu chuÈn tèi −u ®· cã thÓ ®æ bª - t«ng. ®Þnh. §©y lµ líp bµi to¸n phøc t¹p h¬n nhiÒu. - Kh«ng gian lµm viÖc cña c¸c m¸y lu«n 3. C¸c bµi to¸n phèi hîp thay ®æi v× trong s¶n xuÊt x©y dùng, s¶n phÈm Lµ hçn hîp cña hai bµi to¸n trªn. §©y lµ ®øng yªn cßn m¸y mãc vµ con ng−êi ph¶i di líp bµi to¸n phøc t¹p nhÊt nh−ng l¹i th−êng chuyÓn däc theo mÆt trËn c«ng t¸c vµ gi÷a gÆp nhÊt trong thùc tÕ thiÕt kÕ tæ chøc thi c«ng c¸c c«ng tr×nh. §iÒu nµy ®ßi hái ph¶i ph©n vµ tæ chøc x©y dùng c¸c c«ng tr×nh. chia kh«ng gian ho¹t ®éng cho c¸c m¸y theo thêi gian mét c¸ch nhÞp nhµng, ¨n khíp. Ngoµi ra, cã thÓ chia ra c¸c bµi to¸n quy ho¹ch lÞch trong x©y dùng thµnh líp c¸c bµi - Cã lo¹i m¸y chØ cã thÓ thùc hiÖn mét vµi to¸n tiÒn ®Þnh vµ líp c¸c bµi to¸n bÊt ®Þnh. c«ng viÖc, thËm chÝ chØ mét lo¹i c«ng viÖc, C¸c bµi to¸n tiÒn ®Þnh lµ c¸c bµi to¸n mµ thêi nh− m¸y ®Çm chØ cã thÓ dïng ®Ó ®Çm. Tuy gian thùc hiÖn c¸c c«ng viÖc trªn c¸c m¸y lµ nhiªn l¹i cã nh÷ng lo¹i m¸y cã thÓ thùc hiÖn x¸c ®Þnh cßn c¸c bµi to¸n bÊt ®Þnh lµ c¸c bµi nhiÒu c«ng viÖc cïng mét lóc hoÆc liªn tiÕp to¸n mµ, vÒ mÆt lý thuyÕt, tån t¹i thêi gian nh− mét ®éi x©y l¾p tæng hîp hay mét sè lo¹i thùc hiÖn cña Ýt nhÊt mét c«ng viÖc bëi mét m¸y ®a n¨ng. Ngoµi ra còng x¶y ra tr−êng m¸y nµo ®ã lµ bÊt ®Þnh. hîp nhiÒu m¸y cã thÓ cïng thùc hiÖn song song mét c«ng viÖc khi mÆt trËn c«ng t¸c cña c¸c c«ng viÖc lµ ®éc lËp. iii. C¸c ®Æc ®iÓm cña c¸c bμi to¸n quy ho¹ch lÞch trong x©y dùng - Cã c¸c gi¸n ®o¹n thêi gian vÒ mÆt c«ng nghÖ khi thùc hiÖn mét hoÆc nhiÒu c«ng viÖc, Trong x©y dùng, quy ho¹ch lÞch lµ mét ch¼ng h¹n nh− chØ cã thÓ dì v¸n khu«n vµ cét trong nh÷ng vÊn ®Ò quan träng nhÊt khi thiÕt chèng sau khi ®· ®æ bª t«ng mét thêi gian nµo kÕ tæ chøc thi c«ng, tæ chøc x©y dùng c¸c ®ã ®Ó bª t«ng ®· ®«ng cøng vµ ®¹t tíi c−êng c«ng tr×nh còng nh− khi lËp kÕ ho¹ch s¶n xuÊt ®é cho phÐp th¸o dì. cña c¸c tæ chøc x©y l¾p cã quy m« lín. Do ®Æc ®iÓm cña s¶n xuÊt x©y dùng kh¸c víi s¶n - Qu¸ tr×nh s¶n xuÊt mang tÝnh bÊt ®Þnh cao,
chÞu nhiÒu ¶nh h−ëng cña c¸c yÕu tè tù nhiªn. v. Gi¶i thuËt míi gi¶i c¸c bμi to¸n quy ho¹ch lÞch trong x©y dùng V× nh÷ng lý do trªn, khi sö dông c¸c ph−¬ng ph¸p to¸n häc quen thuéc nh− quy Trong bµi b¸o nµy chóng t«i giíi thiÖu mét ho¹ch tuyÕn tÝnh, quy ho¹ch ®éng, lý thuyÕt gi¶i thuËt míi, rÊt m¹nh, cho phÐp gi¶i mét líp phôc vô ®¸m ®«ng v.v… ®Ó gi¶i c¸c bµi to¸n réng c¸c bµi to¸n quy ho¹ch lÞch trong x©y quy ho¹ch lÞch trong x©y dùng th−êng kh«ng dùng. Thùc chÊt, ®ã lµ ph−¬ng ph¸p m« pháng mang l¹i kÕt qu¶ mong muèn. Lý do lµ khi m« c¶i tiÕn dÇn tõng b−íc theo kiÓu ®Ö quy. h×nh ho¸ to¸n häc ®Ó ®−a c¸c bµi to¸n vÒ §Ó giíi thiÖu gi¶i thuËt mét c¸ch ng¾n d¹ng quen thuéc ®Ó gi¶i th× th−êng ph¶i chÊp gän, chóng t«i chØ xÐt tr−êng hîp ®¬n gi¶n nhËn nhiÒu gi¶ thiÕt “th« b¹o” dÉn tíi kÕt qu¶ nhÊt: bµi to¸n quy ho¹ch lÞch ë d¹ng tiÒn ®Þnh, thu ®−îc kh«ng phï hîp víi thùc tÕ s¶n xuÊt. lµ bµi to¸n s¾p thø tù víi môc tiªu tèi −u lµ cùc Ng−îc l¹i, nÕu m« h×nh ho¸ mét c¸ch chÆt tiÓu ho¸ c¸c sai lÖch gi÷a nhu cÇu sö dông vµ chÏ, chÝnh x¸c, s¸t thùc tÕ th× bµi to¸n trë kh¶ n¨ng hiÖn cã vÒ mét lo¹i tµi nguyªn thµnh ®éng, phi tuyÕn víi nhiÒu rµng buéc v« kh«ng thÓ hoÆc kh«ng nªn dù tr÷ (nh− ®iÖn, ®Þnh, rÊt phøc t¹p mµ hiÖn nay viÖc gi¶i nh÷ng khÝ nÐn, nh©n lùc…) trong qu¸ tr×nh thi c«ng bµi to¸n nh− vËy lµ kh«ng thÓ thùc hiÖn ®−îc. mét c«ng tr×nh x©y dùng. Gi¶ sö, ®Ó thi c«ng mét c«ng tr×nh x©y iv. Ph−¬ng h−íng gi¶i c¸c bμi to¸n dùng, cÇn ph¶i hoµn thµnh n c«ng viÖc víi M quy ho¹ch lÞch trong x©y dùng m¸y nµo ®ã. HiÓn nhiªn r»ng, khi lËp kÕ §Ó cã thÓ gi¶i h÷u hiÖu c¸c bµi to¸n quy ho¹ch lÞch hay kÕ ho¹ch tiÕn ®é ban ®Çu, gäi ho¹ch lÞch trong x©y dùng víi nh÷ng ®Æc ®iÓm lµ ph−¬ng ¸n I - ph−¬ng ¸n ®èi s¸nh, c¸c chØ phøc t¹p nh− ®· tr×nh bµy ë trªn, theo ý kiÕn tiªu sau ®©y ®· ®−îc x¸c ®Þnh: cña chóng t«i, chiÕn l−îc chung ®Ó gi¶i c¸c - Thêi gian hoµn thµnh cña c«ng viÖc i bµi to¸n quy ho¹ch lÞch trong x©y dùng lµ nµo ®ã lµ T(i), i = 1 - n tr−íc hÕt x©y dùng c¸c kÕ ho¹ch lÞch ban ®Çu (th−êng gäi lµ kÕ ho¹ch tiÕn ®é thi c«ng) ë - Thêi ®iÓm khëi c«ng sím nhÊt vµ thêi d¹ng s¬ ®å m¹ng, s¬ ®å ngang hoÆc s¬ ®å ®iÓm hoµn thµnh muén nhÊt cho phÐp cña c«ng xiªn, b¶o ®¶m c¸c yªu cÇu vÒ c«ng nghÖ, kü viÖc i lµ A(i) vµ B(i). Nh− vËy, nÕu c«ng viÖc i thuËt thi c«ng, c¸c rµng buéc vÒ thêi gian, tµi ®−îc khëi c«ng vµo thêi ®iÓm C(i), ta sÏ cã: nguyªn vµ phï hîp víi thùc tÕ s¶n xuÊt. Sau C(i) ≥ A(i) (1) ®ã t×m c¸c thuËt to¸n (algorithms) hoÆc c¸c C(i) + T(i) ≤ B(i) (2) gi¶i thuËt (heuristics) ®Ó tèi −u ho¸ kÕ ho¹ch ®· lËp theo mét hoÆc mét vµi môc tiªu tèi −u - Nhu cÇu vÒ tµi nguyªn ®ang xÐt ®Ó nµo ®ã trªn c¬ së c¸c dù tr÷ thêi gian vµ c¸c hoµn thµnh c«ng viÖc i trong kú j lµ q(ij), víi kh¶ n¨ng ph©n bæ l¹i c«ng viÖc mµ vÉn kh«ng mét kú cã thÓ lµ 1 ngµy, 7 ngµy, 10 ngµy hoÆc ph¸ vì c¸c yªu cÇu vÒ c«ng nghÖ, kü thuËt thi thËm chÝ lµ mét th¸ng v.v... DÔ dµng thÊy c«ng hoÆc vi ph¹m c¸c rµng buéc vÒ thêi r»ng, tæng nhu cÇu vÒ tµi nguyªn ®ang xÐt ë gian, tµi nguyªn v.v… B»ng c¸ch nµy, cã thÓ kú j lµ ∑ q(ij), ∀ i = 1 - n. kh«ng x¸c ®Þnh ®−îc ph−¬ng ¸n tèi −u nh−ng - Gäi kh¶ n¨ng vÒ tµi nguyªn ®ang xÐt chóng ta cã thÓ t×m ®−îc ph−¬ng ¸n gÇn tèi trong kú j lµ S(j). Gi¶ sö c«ng tr×nh cÇn thi c«ng −u, tho¶ m·n ®−îc mäi yªu cÇu vÒ c«ng nghÖ trong m kú ta cã j = 1 - m. VÊn ®Ò ®Æt ra lµ cÇn thi c«ng vµ c¸c rµng buéc vÒ thêi gian, tµi s¾p xÕp thø tù c¸c c«ng viÖc sao cho mäi: nguyªn giíi h¹n hiÖn cã.
H(j) = ⎢∑q(ij) - S(j)⏐ → min ®iÒu kiÖn (1) vµ (2). Cã thÓ dÔ dµng thÊy r»ng, (3) nÕu c«ng viÖc h cã dù tr÷ thêi gian cho phÐp lµ ∀ i = 1 - n; j =1 - m G, ta sÏ cã G c¸ch x©y dùng ph−¬ng ¸n II. hay: min (max (H(j)) (4) 4. B−íc 4: TÝnh c¸c tham sè ®Æc tr−ng §Ó cã thÓ lËp tr×nh gi¶i bµi to¸n nµy, ta cho ph−¬ng ¸n II hoµn toµn t−¬ng tù nh− ®· ®−a vµo c¸c tham sè sau: x¸c ®Þnh cho ph−¬ng ¸n I: + x(ij) = 1 nÕu c«ng viÖc i ®−îc thùc hiÖn - xII(ij) trong kú j, vµ - HII(j) = ⎢∑qII(ij) – S(j)⏐; ∀ i = 1 - n; j = 1 - m + x(ij) = 0 trong tr−êng hîp ng−îc l¹i (5) - LII = ∑ HII(j); ∀ j = 1 - m Nh− vËy, cã thÓ ph¸t biÓu bµi to¸n d−íi - YII = max [HII(j)] – min [HII(j)]; d¹ng sau ®©y: 5. B−íc 5: So s¸nh vµ chän ph−¬ng ¸n: CÇn t×m c¸c cÆp (ij) tho¶ m·n x(ij) = 1 - NÕu HII(j) ≤ HI(j) ∀ j = 1 - m th× ph−¬ng sao cho: ¸n II tèt h¬n ph−¬ng ¸n I. §©y lµ ®iÒu hiÓn H(j) = ⎢∑q(ij) – S(j)⏐ → min nhiªn nh−ng tr−êng hîp nµy Ýt khi xÈy ra trong ∀i = 1 - n; j = 1 - m thùc tÕ. NÕu tån t¹i Ýt nhÊt mét kú l nµo ®ã mµ: HII(l) > HI(l) ∀ j = 1 - m, hay: min (max(H(j))) ta chuyÓn sang so s¸nh LI vµ LII. Tr×nh tù gi¶i bµi to¸n nh− sau: - NÕu LI > LII th× ph−¬ng ¸n II tèt h¬n 1. B−íc 1: TÝnh c¸c gi¸ trÞ sau cña kÕ ph−¬ng ¸n I vµ ng−îc l¹i. NÕu LI = LII, ta ho¹ch tiÕn ®é ban ®Çu (cña ph−¬ng ¸n I hay chuyÓn sang so s¸nh YI vµ YII ph−¬ng ¸n ®èi s¸nh): - xI(ij) NÕu YI > YII th× ph−¬ng ¸n II tèt h¬n ph−¬ng ¸n I, vµ ng−îc l¹i. - HI(j) = ⎢∑qI(ij) – S(j)⏐; ∀i = 1 - n; j = 1 - m NÕu ®Õn b−íc nµy, ta cã YI = YII th× hai (6) ph−¬ng ¸n nãi chung lµ nh− nhau nh−ng cã - LI = ∑ HI(j); ∀ j = 1 - m (7) thuËt to¸n kh«ng ®æi (kh«ng tr×nh bµy ë ®©y) I I I - Y = max [H (j)] – min [H (j)]; (8) chøng tá r»ng, ®Ó gi¶i thuËt héi tô nhanh, ta nªn chän ph−¬ng ¸n I vµ bá ph−¬ng ¸n II. CÇn chó ý r»ng, c¸c gi¸ trÞ q(ij) ®−îc x¸c ®Þnh dÔ dµng trªn c¬ së khèi l−îng c«ng viÖc 6. B−íc 6: T¹o lËp ph−¬ng ¸n míi tõ vµ ®Þnh møc hao phÝ tµi nguyªn ®ang xÐt, cßn ph−¬ng ¸n tèt h¬n ®· chän vµ tiÕp tôc so c¸c ký hiÖu I vµ II trªn ®Çu c¸c tham sè chØ c¸c s¸nh, ®¸nh gi¸ nh− ®· tr×nh bµy. gi¸ trÞ cÇn x¸c ®Þnh cña c¸c ph−¬ng ¸n I vµ II HiÓn nhiªn, trong qu¸ tr×nh so s¸nh sÏ t−¬ng øng. x¶y ra mét trong hai tr−êng hîp sau: 2. B−íc 2: X¸c ®Þnh kú k ∀ 1≤ k ≤ m cã: a. Tr−êng hîp 1: Ph−¬ng ¸n I tèt h¬n H (k) ≥ H (j); ∀ j = 1 - m I ph−¬ng ¸n II: ta tiÕp tôc thay ®æi thêi ®iÓm (9) khëi c«ng cña c«ng viÖc h víi mäi kh¶ n¨ng 3. B−íc 3: T¹o lËp ph−¬ng ¸n II b»ng cã thÓ vµ lÆp l¹i qu¸ tr×nh tÝnh to¸n nh− ®· c¸ch thay ®æi thêi ®iÓm khëi c«ng (vµ nh− vËy tr×nh bµy. tÊt nhiªn sÏ lµm thay ®æi thêi ®iÓm hoµn Sau khi ®· sö dông mäi kh¶ n¨ng thay thµnh) cña c«ng viÖc h trªn c¬ së dù tr÷ thêi ®æi mµ ph−¬ng ¸n I vÉn tèt h¬n ph−¬ng ¸n II gian cho phÐp cña c«ng viÖc nµy, tho¶ m·n c¸c ta xö lý nh− sau:
Gi÷ nguyªn ph−¬ng ¸n I vµ t¹o lËp vI. KÕt luËn ph−¬ng ¸n míi trªn c¬ së thay ®æi thêi ®iÓm Bµi b¸o ®· tr×nh bµy m« h×nh to¸n häc, khëi c«ng cña c«ng viÖc h’ nh− ®· tr×nh bµy ë c¸c ®Æc ®iÓm cña c¸c bµi to¸n quy ho¹ch lÞch trªn víi ®iÒu kiÖn: trong x©y dùng, ®Ò xuÊt ph−¬ng h−íng gi¶i vµ q(i,k) ≤ q(h’,k) ≤ q(h,k) (10) giíi thiÖu mét gi¶i thuËt cho phÐp gi¶i gÇn ®óng c¸c bµi to¸n quy ho¹ch lÞch trong x©y dùng. Cã ∀ i = 1,…, n, vµ i ≠ h thÓ thÊy r»ng, gi¶i thuËt nµy còng cã thÓ gi¶i Sau ®ã lÆp l¹i qu¸ tr×nh tÝnh to¸n nh− ®· ®−îc c¸c bµi to¸n quy ho¹ch lÞch ë c¸c d¹ng tr×nh bµy theo c¸c b−íc ë trªn. phøc t¹p h¬n nh−: tèi −u ho¸ nhiÒu lo¹i tµi nguyªn cã thÓ dù tr÷ ®−îc (nh− xi m¨ng, g¹ch, NÕu thùc hiÖn víi mäi c«ng viÖc trong kú s¾t thÐp…), rót ng¾n tèi ®a thêi gian thi c«ng, k mµ ph−¬ng ¸n I vÉn tèt h¬n ph−¬ng ¸n II ta gi¶m tèi ®a gi¸ thµnh x©y l¾p c«ng tr×nh hoÆc quay vÒ b−íc 2 thùc hiÖn qu¸ tr×nh tÝnh to¸n tèi −u ®a môc tiªu: thêi gian - gi¸ thµnh - tµi t−¬ng tù cho kú k’ víi ®iÒu kiÖn: nguyªn vµ xÐt c¸c bµi to¸n ë d¹ng bÊt ®Þnh, lµ HI(j) ≤ HI(k’) ≤ HI(k) (11) bµi to¸n ph©n bæ hoÆc phèi hîp. ∀ j=1,…,n; j ≠ k vµ k’ ≠ k XÐt vÒ mÆt tin häc, so víi ph−¬ng ph¸p Monte - Carlo, cã thÓ chøng minh r»ng, gi¶i vµ lÆp l¹i qu¸ tr×nh to¸n t−¬ng tù nh− ®· tr×nh thuËt nµy cho phÐp gi¶m rÊt ®¸ng kÓ ®é phøc bµy ë trªn . t¹p cña thuËt to¸n. MÆc dï gi¶i thuËt ®−îc m« b. Tr−êng hîp 2: NÕu ph−¬ng ¸n II tèt t¶ kh¸ ®¬n gi¶n vµ ng¾n gän nh−ng khèi l−îng h¬n ph−¬ng ¸n I, ta bá ph−¬ng ¸n I chän tÝnh to¸n lµ rÊt lín vµ hiÓn nhiªn lµ chóng ta ph−¬ng ¸n II vµ t¹o lËp ph−¬ng ¸n míi tõ kh«ng thÓ thùc hiÖn gi¶i thuËt nµy b»ng tay. ph−¬ng ¸n II ®Ó so s¸nh víi ph−¬ng ¸n II vµ Gi¶i thuËt sÏ phøc t¹p h¬n nhiÒu víi khèi chän ph−¬ng ¸n tèt h¬n nh− ®· tr×nh bµy. l−îng tÝnh to¸n rÊt lín khi gi¶i c¸c bµi to¸n phøc t¹p h¬n. Tuy nhiªn, víi cÊu h×nh rÊt Toµn bé qu¸ tr×nh tÝnh to¸n sÏ ®−îc lÆp ®i m¹nh cña c¸c m¸y tÝnh ®iÖn tö hiÖn nay th× lÆp l¹i vµ gi¶i thuËt sÏ héi tô khi kh«ng thÓ t¹o khèi l−îng tÝnh to¸n rÊt lín ®ã l¹i lµ c«ng viÖc ph−¬ng ¸n míi. §©y lµ mét gi¶i thuËt ®Ö quy chiÕm kh«ng nhiÒu thêi gian, nhÊt lµ khi nhiÒu møc. Xin b¹n ®äc tù chøng minh tÝnh héi kh«ng thÓ hiÖn qu¸ tr×nh tÝnh to¸n b»ng tô cña gi¶i thuËt vµ x¸c ®Þnh ®é phøc t¹p cña Graphic trªn mµn h×nh. gi¶i thuËt th«ng qua sè phÐp tÝnh cÇn thiÕt. Khi triÓn khai gi¶i thuËt vµ viÕt ch−¬ng tr×nh, b¹n cÇn chuyÓn ch−¬ng tr×nh ®Ö quy trªn sang ch−¬ng tr×nh lÆp t−¬ng ®−¬ng. §Ó viÕt Tµi liÖu tham kh¶o ch−¬ng tr×nh cho gi¶i thuËt nµy, theo kinh [1]. E.M. Willis. Scheduling Construction Projects. nghiÖm cña chóng t«i, b¹n nªn sö dông ng«n John Wiley and Sons, Inc., N.Y. 1996 ng÷ Pascal hoÆc mét ng«n ng÷ kiÓu cã cÊu tróc ®Ó dÔ dµng viÕt ch−¬ng tr×nh lÆp t−¬ng [2]. P., Bratley, and L. Benntt. A Guide to ®−¬ng ®−îc khai triÓn tõ ch−¬ng tr×nh ®Ö quy. Simulation, Spinger Verlag, N.Y M. Toµn bé qu¸ tr×nh tèi −u ho¸ cã thÓ ®−îc thÓ [3]. J. Jackson. Computers in Construction hiÖn sinh ®éng trªn m¸y nh− vÏ tõng b−íc Plaaning and Control. Allen & Uniwin London 1998 trªn giÊy vµ cho phÐp ng−êi sö dông theo dâi [4]. J.C. Phillips and E. Davis. Project Mangement vÕt cña ch−¬ng tr×nh, t−¬ng tù nh− khi gi¶i bµi with CPM, PERT and Precedence Diagramming., to¸n s¾p xÕp th¸p Hµ néi quen thuéc. 3rd ed., Van Nostrand Reinhold Co., N.Y 1989♦