Ứng dụng phương pháp nhánh và biên, lập trình giải bài toán tối ưu về trình tự thi công

TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 9, SỐ 6-2006 
Trang 13 
ỨNG DỤNG PHƯƠNG PHÁP NHÁNH VÀ BIÊN, 
 LẬP TRÌNH GIẢI BÀI TOÁN TỐI ƯU VỀ TRÌNH TỰ THI CÔNG 
Phạm Hồng Luân 
Trường Đại học Bách Khoa, ĐHQG-HCM 
(Bài nhận ngày 23 tháng 12 năm 2005, hoàn chỉnh sửa chữa ngày 06 tháng 07 năm 2006) 
TÓM TẮT: Quyết định chọn thứ tự thi công các công trình trong cụm các công trình 
(phân đoạn, đơn nguyên) là một bài toán khó. Có nhiều yếu tố cần phải xem xét như : thời 
gian, nhân lực, điều kiện thuận lợi của diện công tác, máy móc thiết bị thuê hay có sẳn, nguyên 
vật liệu, cấu kiện bán thành phẩm. . . Trong nội dung bài báo, toán tiến độ được xem xét dưới 
khía cạnh là các bảng số ma trận. Kết quả ứng dụng phương pháp nhánh và biên, lập trình giải 
bài toán tối ưu về trình tự thi công sẽ giúp cho các nhà quản lý các đơn vị xây lắp, các chủ đầu 
tư , ban quản lý dự án có thể tham khảo trong trường hợp cần phải ra quyết định để xác định 
trình tự thi công hợp lý các hạng mục công trình sao cho có thể sớm đưa vào sử dụng. 
1. ĐẶT VẤN ĐỀ 
Tiến độ thi công là một trong các nội dung của thiết kế tổ chức thi công, là tài liệu thiết kế 
dựa trên các biện pháp kỹ thuật thi công đã nghiên cứu kỹ nhằm đảm bảo: chất lượng công 
trình, an toàn lao động, hoàn thành trong hạn định và chi phí cho phép. Khi lập ra một tiến độ 
hợp lý chúng ta sẽ rút ngắn được thời gian thi công công trình, sử dụng hiệu quả nguồn tài 
nguyên dẫn đến giá thành công trình giảm, tiết kiệm ngân sách đồng thời sớm đưa các công 
trình xây dựng vào hoạt động. Trong trường hợp một đơn vị xây lắp đảm nhận thi công nhiều 
công trình hoặc hạng mục công trình thì việc xác định thứ tự thi công các công trình mang ý 
nghĩa lớn vì trình tự thi công ảnh hưởng nhiều đến thời gian hoàn tất công trình. 
Với sự phát triển của ngành máy tính hiện nay về tốc độ xử lí cũng như các ngôn ngữ lập 
trình, cùng với sự linh hoạt trong quản lý chúng ta kết hợp một số giải thuật để lập ra một số 
chương trình tính để tự động hóa tính toán nhằm đề xuất nhanh chóng một phương án tối ưu về 
thời gian thi công. 
2. PHƯƠNG PHÁP VÀ NỘI DUNG NGHIÊN CỨU 
Bài toán tiến độ được xem xét dưới khía cạnh là các bảng số ma trận. Phương pháp tiến độ 
là phương pháp thi công dây chuyền. Mô hình hóa các công tác xây dựng, nghiên cứu các cấu 
trúc kỹ thuật và cấp độ của sơ đồ xiên, xây dựng mô hình toán, sử dụng phương pháp tiến độ, 
áp dụng thuật toán Porfilian và ma trận cột Johnson, lập chương trình tính và vẽ bằng ngôn ngữ 
visual basic. Các giai đọan thi công công trình (phần ngầm, phân thân nhà, hoàn thiệân, lắp đặt 
thiết bị...) được mô hình như là các công tác trong tiến độ dây chuyền. 
Trong nhóm các công trình (các đơn nguyên, các hạng mục) thực hiện theo phương pháp thi 
công dây chuyền, khi thay đổi trình tự thi công giữa các công trình (các đơn nguyên, các hạng 
mục) với nhau thì thời gian thi công toàn bộ các công trình (đơn nguyên, phân đoạn) ấy sẽ thay 
đổi [3],[12]. 
2.1. Cấp độ dây chuyền và mô hình công tác xây dựng 
Ở mô hình này, tiến độ thi công là một mặt tọa độ, trục tung là không gian thi công thể hiện 
danh mục đối tượng thi công (phân khu-phân đoạn công trình), trục hoành là thời gian, mặt tọa 
độ mô tả chu kỳ thực hiện các công tác. Thứ tự các công tác tuân theo các qui trình tổ chức và 
kỹ thuật thi công. Tổ chức dây chuyền có những tính chất cơ bản như tính chuyên môn hóa, 
tính điều hòa, tính không chồng chéo và tính ghép sát. Đó là sự phối hợp chặt chẽ giữa các 
công tác theo thời gian và không gian.Sự mở rộng về khái niệm phân đoạn công trình được 
Science & Technology Development, Vol 9, No.6- 2006 
Trang 14 
định danh ở trục tung thành các hạng mục công trình hay các công trình độc lập dẩn đến hình 
thành khái niệm về trình tự thi công các hạng mục công trình hoặc các công trình đó. Cấu trúc 
kỹ thuật và cấp độ dây chuyền thể hiện ở hình 1. 
Hình 1. Sơ đồ tổng quát cấu trúc kỹ thuật và cấp độ dây chuyền 
2.2. Xác định trình tự thi công các công trình theo phương pháp nhánh và biên 
Số liệu về thời gian thi công các công tác tổng hợp (A,B,C,D,) tại các công trình 
(I,II,III,IV,) được trình bày ở dạng bảng số (M 1), trong đó tij là thời gian thực hiện công tác 
tổng hợp i tại công trình j. Từ bảng số M1 tách thành các bảng số M có cặp cột 2 x m . Để đơn 
giản, trình bày trong hình dưới đây thể hiện M1 có n= 4 và m =4. 
Thời gian thi công 
tại hạng mục công 
trình 
Dây chuyền tổng hợp 
I (j=1) A = ( I-1) B = ( i=2) C D ( i= n) 
 II t 11 t n1 
 III t i+1,j-1 
IV (j=m) t ij 
Bảng M1 
D a ïn g 
d a ây c h u y e àn
N h o ùm c o ân g t r ìn h
C o ân g t r ìn h ñ o äc la äp
C a ùc g ia i ñ o a ïn k y õ t h u a ät
M o ät d a ïn g M o ät c o ân g v ie äc
c o ân g t a ùc d o m o ät t o å ñ o äi
( th a øn h p h a àn ) c h u y e ân n g h ie äp 
t h ö ïc h ie än
Ñ ô n
T o å h ô ïp c o ân g t r ìn h
ñ ô n n g u y e ân
 n h ie àu h a ïn g m u ïc ,
C o ân g t r ìn h , t o øa n h a ø
C o ân g t r ìn h
K y õ th u a ät
 M o ät b o ä p h a än k e át 
 c a áu c o ân g t r ìn h
M o ät q u a ù t r ìn h k .t
C ô c a áu - t h a øn h p h a àn S a ûn p h a åm
T o ån g h ô ïp
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 9, SỐ 6-2006 
Trang 15 
tách 2 cột A,B của M1 tách 2 cột B,C của M1 tách 2 cột C,D của M1 
A 
 ( i=1) 
B 
= ( i=2) B ( i=2) C C D ( i = n) 
I t 11 I I t n1 
II II t i+1,j-1 II t i+1,j-1 
III t ij III t ij III 
IV t 1m IV IV t nm 
 Bảng M: AB Bảng M: BC Bảng M: CD 
1- Thành lập Ma trận 2 cột Johnson từ bảng M:AB, M:BC, M:CD là các ma trận tương 
ứng M JAB; MJBC; MJCD. Ma Trận này chỉ ra được thứ tự các hàng I, II, III, IV ( tham khảo 
tài liệu [1] ). 
2- Xây dựng cây porfiriant : Từ ma trận M1 ( n=4; m=4) xác định thời gian thực hiện công 
trình theo trình tự I, II, III, IV trong điều kiện liên tục về tài nguyên là M I, II, III, IV ; ( tham khảo 
tài liệu [1,2, 5, 7])- hình 2. 
3- Các ma trận M I, M II, M III, M IV là ma trận có m hàng , n cột và tương ứng là các 
ma trận có hàng đầu tiên m=1 là các giá trị ở hàng: I (m=1), II (m=2), III (m=3), IV (m=4) của 
ma trận M1; các giá trị còn lại có giá trị tương ứng theo các ma trận 2 cột Jonhson M JAB; 
MJBC; MJCD. Tính các ma trận M I, M II, M III, M IV theo điều kiện liên tục về tài nguyên 
có thời gian là M I, M II, M III, M IV . 
4- Nhánh phát sinh từ M I, M II, M III, M IV trong cây porfiriant là nhánh có giá trị nhỏ 
nhất trong M I, M II, M III, M IV ( ví dụ: nhánh M I ). Từ đây lập các ma trận M I,II ; M I,III ; 
M I,IV. 
5- Ma trận M I,II ; M I,III ; M I,IV là ma trận có m hàng , n cột và tương ứng là các ma 
trận có hàng đầu tiên và thứ 2 là các giá trị ở hàng: I (m=1), II (m=2); I (m=1), III (m=3), I 
(m=1), IV (m=4) của ma trận M1; các giá trị còn lại có giá trị tương ứng theo các ma trận 2 cột 
Jonhson M JAB; MJBC; MJCD. Tính các ma trận M I,II ; M I,III ; M I,IV theo điều kiện liên tục 
về tài nguyên có thời gian là M I,II, M I, III, M I,IV 
6- Nhánh phát sinh kế tiếp từ M I,II ; M I,III ; M I,IV trong cây porfiriant là nhánh có giá 
trị nhỏ nhất trong M I,II, M I, III, M I,IV ( ví dụ: nhánh M I,IV ). Từ đây lập các ma trận M I,IV,II 
; M I,IV,III . 
7- Lập lại các bước tương tự như bước 5, 6 cho đến khi kết thúc. 
Hình 2. Cây porfiriant – Sơ đồ nhánh 
M I, II, III, IV = 48 
M I = 41 M II = 44 M III =43 M IV = 48 
M I, II = 44 
M I, III = 45 
M I, IV = 42 M II,IV = 
M II, III = 
M II, I = 
M III, IV = 
M III, II = 
M III, I = 
M I, IV, III, II = 43 
M I, IV,II,III = 42 
Science & Technology Development, Vol 9, No.6- 2006 
Trang 16 
Ví dụ áp dụng : Thời gian thi công của các dây chuyền tổng hợp A (thi công tầng ngầm); B 
(thi công phần thân nhà) ; C (thi công mái) ; D ( thi công các công tác hoàn thiện và hạ tầng 
ngoài nhà) cho các công trình I, II, III, IV cho trong bảng M1 (4x4 ) sau: 
Baûng M1
Thôøi gian thi coâng taïi 
caùc coâng trình A B C D
I 5 2 1 9
II 5 4 2 3
III 6 3 2 8
IV 8 7 9 1
Caùc coâng taùc toång hôïp
Daây chuyeàn
Bảng M1.Số liệu 4 dây chuyền tổng hợp, 4 công trình (ví du áp dụng)ï 
Bước 2 : Thành lập ma trận 2 cột Johnson 
A B B C C D 
IV 8 7 IV 7 9 I 1 9
II 5 4 II 4 2 II 2 3
III 6 3 III 3 2 III 2 8
I 5 2 I 2 1 IV 9 1 
Bước 3 : Thành lập các bước trung gian M I, M II, M III, M IV 
A D A D
I 5 9 II 5 3
 8 7 7 9 2 3 8 7 7 9 1 9
 5 4 4 2 2 8 5 3 3 2 2 8
 6 3 3 2 9 1 6 2 2 1 9 1
MI = 41 M II =44
B
2 1
C B C
4 2
A D A D
III 6 8 IV 8 1
 8 7 7 9 1 9 5 4 4 2 1 9
 5 4 4 2 2 3 6 3 3 2 2 3
 5 2 2 1 9 1 5 2 2 1 2 8
M III =43 M IV =48
B C
7 9
B
3 2
C
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 9, SỐ 6-2006 
Trang 17 
Bước 4 : Thành lập các bước trung gian M I, II, M I,III, M I, IV 
A D A D
I 5 9 I 5 9
II 5 3 III 6 8
 8 7 7 9 2 8 8 7 7 9 2 3
 6 3 3 2 9 1 5 4 4 2 9 1
 M I, II = 44 M I,III = 45
A D
I 5 9
IV 8 1
5 4 4 2 2 3
6 3 3 2 2 8
M I,IV = 42
7 9
B C
2 1
4 2 3 2
B
2 1
C B C
2 1
Bước 5 : Thành lập M I, IV, II, III, M I, IV, III, II 
A B C D A B C D
I 5 2 1 9 I 5 2 1 9
IV 8 7 9 1 IV 8 7 9 1
II 5 4 2 3 III 6 3 2 8
III 6 3 2 8 II 5 4 2 3
M I,IV,II,III = 42 M I,IV,III,II = 43 
Kết quả giải ví dụ trên theo nhiều phương pháp tổng kết như sau: 
− Phương pháp bài toán “không ngừng sử dụng tài nguyên” , thứ tự : I, II, III, IV - thời 
gian hoàn tất 48 đơn vị thời gian. 
− Phương pháp “bài toán ưu tiên” thứ tự I, III, IV, II - thời gian hoàn tất 45 đơn vị thời 
gian. 
− Phương pháp “chọn ngẫu nhiên” và giải theo pp bài toán “không ngừng sử dụng tài 
nguyên” thứ tự I, IV, III, II - thời gian hòan tất 43 đơn vị thời gian. 
- Phương pháp bài toán nhánh và biên ( Jonhson - nhánh và biên) thứ tự I, IV, II, III - 
thời gian hoàn tất 42 đơn vị thời gian. 
− Phương pháp hoán vị so sánh n ! = 4! = 24 phương án. thứ tự I, IV, II, III - thời gian 
hoàn tất 42 đơn vị thời gian. 
2.3 Chương trình tự động hóa tính toán và các biểu đồ tiến độ 
2.3.1 Chọn chương trình VISUAL BASIC 
Trước đây theo nghiên cứu của tác giả về việc sử dụng chương trình MATLAB để giải bài 
toán tối ưu hóa thi công, nhóm nghiên cứu nhận thấy rằng chương trình MATLAB có những 
ưu điểm nổi bật như: 
Science & Technology Development, Vol 9, No.6- 2006 
Trang 18 
- Khả năng xử lý về ma trận rất mạnh. 
- Khả năng xử lý về đồ thị rất tốt. 
- Giao diện, tạo menu khá tốt. 
Tuy nhiên chương trình MATLAB có các giới hạn: 
- Khả năng truy cập các bảng biểu, chẳng hạn như để tạo một bảng nhập số liệu ban đầu, 
với MATLAB, số hàng số cột của bảng phải là còn số nhất định phù hợp với màn hình do trong 
Matlab không tạo ra những thanh trượt (scroll bar) để kéo rộng màn hình. 
- Matlab không xuất ra các đuôi .exe 
- Khó tạo ra phần mềm hoàn chỉnh để có thể cài đặt được. 
Thay vào đó những hạn chế của Matlab được bổ sung bởi VISUAL BASIC. Cụ thể: 
- Xử lý giao diện tạo menu cực kỳ mạnh mẽ. 
- Bảng biểu để truy nhập có thể tạo được các thanh trượt qua lại, trên dưới do đó không 
giới hạn số hàng số cột của mảng truy cập. Tương tự như vậy đối với bảng xuất. 
- Có thể tạo được mảng động. Đây là ưu điểm của visual basic. Bằng tính chất này 
chường trình cấp phát bộ nhớ tiết kiệm tùy yêu cầu của người sử dụng, không nhất thiết cấp sẵn 
bộ nhớ nhất định ban đầu. 
- Visual basic là ngôn ngữ lập trình theo sự kiện, trực quan, sáng sủa, dễ theo dõi và gỡ 
rối. 
- Tạo file.exe dễ dàng. 
- Tạo đĩa install rất đơn giản và nhanh chóng. Chương trình sau khi biên dịch có thể cài 
dặt bất kỳ mà không nhất thiết có Visual basic. 
2.3.2 Chương trình Tự động hóa tiến độ - hướng dẫn sử dụng 
Sau khi chương trình được cài đặt, chương trình sẽ hỏi việc chọn lựa phương pháp tổ chức 
tiến độ thi công: Dây chuyền hay mạng?. Sau mỗi lần nhập liệu các menu hướng dẫn liên tục 
hiện ra. Sau khi nhập đầy đủ số liệu là việc chọn bài toán để giải. 
Các bài toán để tính bao gồm: 
• Bài toán 1 :”liên tục về tài nguyên” 
• Bài toán 2 :”liên tục về diện công tác” 
• Bài toán 3 :”thời gian thi công ngắn nhất theo trình tự ban đầu của bài toán: không liên 
tục về tài nguyên không liên tục về diện công tác” 
• Bài toán chọn trình tự thi công: 
* Phương pháp hoán vị 
* Phương pháp Nhánh và biên-Johnson 
* Phương pháp hệ số ưu tiên 
2.3.3 Áp dụng 
Khởi động chương trình TỐI ƯU HÓA TIẾN ĐỘ, nhập số liệu (thời gian thực hiện tại các 
hạng mục công trình, số lượng và giá trị các tài nguyên) theo lời nhắc của chương trình, chọn 
bài toán Johnson và giải . 
Chương trình cho ngay bảng số liệu nhập để kiểm tra, kết quả và hiển thị kết quả bảng tính, 
biểu đồ tài nguyên : nhân lực, thiết bị; các hệ số điều hòa nhân lực và lao động, các bảng tiến 
độ dạng dây chuyềnCác kết quả của ví dụ nêu trên được xuất trên màn hình như sau: 
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 9, SỐ 6-2006 
Trang 19 
Hình 3. Xuất kết quả của ví dụ áp dụng Hình 4. Hiển thị số liệu nhập: thời gian,tài 
nguyên (nhân công, thiết bị), thời gian giải bài 
toán 
Hình 5. Hiển thị kết quả tính toán: thời gian khởi và kết của các dây chuyền tổng hợp tại các công 
trình. Tg = 42 
Science & Technology Development, Vol 9, No.6- 2006 
Trang 20 
Hình 6. Hiển thị bảng tổng tiến độ thi công tại các công trình, Biểu đồ tài nguyên thứ 1: nhân 
công, hệ số k1 = 2,154 ,k2 = 0,203, Atb = 8,357 , Tg = 42 
Hình 7. Hiển thị bảng tổng tiến độ thi công tại các công trình, Biểu đồ tài nguyên thứ 2: Thiết 
bị, hệ số k1 = 2,291 ,k2 = 0,189, Atb = 3,929 , Tg = 42 
3. NHẬN XÉT VÀ KẾT LUẬN 
Để nâng cao hiệu quả vốn đầu tư xây dựng không chỉ bằng cách đổi mới công nghệ sản 
xuất, biện pháp kỹ thuật thi công, sử dụng hiệu quả máy móc thiết bị mà còn cần phải thay đổi 
phương pháp sản xuất, tổ chức lao động khoa học. Khi tổ chức thi công nhóm công trình, thay 
đổi trình tự thi công các công trình (các đơn nguyên, các phân đoạn) thì thời gian thi công toàn 
bộ cũng sẽ thay đổi. Việc chọn ra một trình tự thi công nào đó có thời gian thi công ngắn nhất 
đồng thời đáp ứng các điều kiện thực tế có được của đơn vị xây lắp-sản xuất đều mang lại ý 
nghĩa kinh tế, xã hội sâu sắc. 
Quyết định chọn thứ tự thi công các công trình trong cụm các công trình (phân đoạn, đơn 
nguyên) là một điều khó khăn. Có nhiều yếu tố cần phải xem xét như : thời gian, nhân lực, 
thực tế thuận lợi của diện công tác hay địa bàn thi công, máy móc thiết bị thuê hay có sẵn, 
nguyên vật liệu, cấu kiện bán thành phẩm . Việc xác định trình tự thi công hợp lý về thời gian 
thi công toàn bộ công trình và lập trình tự động hóa tính toán sẽ giúp cho các nhà quản lý các 
đơn vị xây lắp, các chủ đầu tư, ban quản lý dự án có thể tham khảo trong trường hợp cần phải 
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 9, SỐ 6-2006 
Trang 21 
ra quyết định để xác định trình tự thi công hợp lý các hạng mục công trình sao cho có thể sớm 
đưa vào sử dụng. 
Phần nghiên cứu có thể chỉ ra các nghiệm đúng tuyệt đối hoặc những nghiệm tốt hơn với 
nhiều lời giải so sánh khác nhau sẽ là thước đo cho việc chọn lựa thêm nhiều phương án khác 
và ràng buộc khác ngoài ràng buộc về thời gian hoàn tất công trình. 
APPLICATION OF PORFIRIANT METHOD AND COMPUTER 
PROGRAMMING IN DETERMINING THE SEQUENCE OF CONSTRUCTION 
BUILDINGS EXECUTION 
Pham Hong Luan 
University of Technology, VNU- HCM 
ABSTRACT: The sequence of construction buildings execution affects the required time 
of the construction project accomplishment. Setting the sequence of construction buildings 
execution in shortest time is complicated. Thanks to the high ability of computer, application 
of porfiriant method and computer-programming gives an optimum solution even with the 
complicated scheduled plans. The application will be helpful to the owners, designers, 
contractors in deciding the sequence of construction buildings execution with the aim of 
accomplishment the whole project in earliest time. 
TÀI LIỆU THAM KHẢO 
[1]. B.A. Aphanasep, Thuật toán tính toán dây chuyền, NXB Lêning grad, 1990. 
[2]. Dikman, Tổ chức kế hoạch và quản lý thi công trong xây dựng, NXB Lêning grad, 
1982. 
[3]. Trương Ngọc Diệp, Trần Thế San, Sổ tay người thiết kế và thi công công trình xây 
dựng, NXB TP HCM, 1996. 
[4]. L.V.Kiểm, Phạm Hồng Luân, Các bài toán Quản lý Kinh doanh Xây dựng, NXB 
ĐHQG TP HCM, 2002. 
[5]. Đinh Xuân Lâm, Giáo trình học và thực hành Microsoft Visual Basic cơ bản, NXB 
Thống Kê, 2000. 
[6]. Phạm Hồng Luân, Tự động hóa tiến độ ma trận, Đề tài cấp Bộ 2004. 
[7]. Nguyễn Đình Thám, Lập kế hoạch tổ chức và chỉ đạo thi công, 2001. 
[8]. Đặng Quang Tuấn, Lập trình cơ sở dữ liệu Visual Basic 6.0, NXB Trẻ, 2001.