..

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

Ngô Thị Lan Anh

LẬP LỊCH DỰ ÁN SỬ DỤNG THUẬT TỐN HEURISTIC VÀ
MƠ HÌNH QUẢN TRỊ GIÁ TRỊ THU ĐƯỢC (EVM)

Chuyên ngành: Kỹ thuật phần mềm

LUẬN VĂN THẠC SĨ
KỸ THUẬT PHẦN MỀM

NGƯỜI HƯỚNG DẪN KHOA HỌC
`

PGS.TS Huỳnh Quyết Thắng

Hà Nội – Năm 2016


LỜI CAM ĐOAN
Tôi là Ngô Thị Lan Anh, học viên lớp Cao học KTPM 2014 – 2016 Trường
Đại học Bách khoa Hà Nội – cam kết. Luận văn tốt nghiệp là cơng trình nghiên cứu
của bản thân tơi dưới sự hướng dẫn của thầy PGS-TS Huỳnh Quyết Thắng- Viện
Công nghệ Thông tin và Truyền thông – Đại học Bách Khoa Hà Nội. Các kết quả
trong Luận văn tốt nghiệp là trung thực, khơng sao chép tồn văn của bất kỳ cơng
trình nào khác.

Hà Nội, ngày 16 tháng 10 năm 2016
Học viên: Ngô Thị Lan Anh
Lớp:14AKTPM

1


LỜI CẢM ƠN
Tơi xin bày tỏ lịng biết ơn sâu sắc tới thầy PGS-TS Huỳnh Quyết Thắng –Bộ
môn Công nghệ phần mềm – Viện Công nghệ Thông tin và Truyền thông – Trường
đại học Bách khoa Hà Nội đã hết lòng giúp đỡ, dạy bảo, động viên và tạo mọi điều
kiện thuật lợi cho tơi trong suốt q trình học tập và hồn thành luận văn tốt nghiệp.
Tơi xin chân thành cảm ơn tập thể các thầy, cô giáo trường Đại học Bách
Khoa Hà Nội nói chung và Viện Cơng nghệ Thơng tin và Truyền Thơng nói riêng
đã tận tình giảng dạy truyền đạt cho tôi những kiến thức, kinh nghiệm quý báu trong
suốt những năm học vừa qua.
Tôi xin gửi lời cảm ơn chân thành đến các thầy phản biện và các thầy trong
hội đồng đã trao đổi và góp nhiều chỉ dẫn quý báu, giúp cho luận văn được trình
bày tốt hơn.
Cuối cùng tơi xin gửi lời cảm ơn đến gia đình, người thân và bạn bè đã làm
chỗ dựa vững chắc, động viên giúp đỡ rất nhiều về tinh thần, thời gian để tơi có thể
hồn thành luận văn này.

2


MỤC LỤC

DANH MỤC HÌNH ẢNH ................................................................................ 6

DANH MỤC BẢNG BIỂU .............................................................................. 7
DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT ................................... 8
CHƯƠNG 1. TỔNG QUAN ........................................................................... 10
1.1. Bài toán lập lịch dự án và mơ hình quản trị giá trị thu được ............... 10
1.2. Tình hình nghiên cứu trong và ngoài nước liên quan đến đề tài. ....... 13
1.3. Lý do, sự cần thiết phải tiến hành nghiên cứu. ................................... 13
1.4. Mục tiêu, nội dung nghiên cứu............................................................ 14
1.5. Cách tiếp cận, phương pháp nghiên cứu. ............................................ 15
1.6. Phương tiện, công cụ sử dụng trong mô phỏng và thử nghiệm .......... 16
1.7. Các đóng góp của đề tài ...................................................................... 16
CHƯƠNG 2. LẬP LỊCH DỰ ÁN SỬ DỤNG PHƯƠNG PHÁP HEURISTIC
VÀ MÔ HÌNH QUẢN TRỊ GIÁ TRỊ THU ĐƯỢC ....................................... 17
2. 1. Lập lịch dự án ..................................................................................... 17
2.1.1. Tập các công việc (Activities) ..................................................... 19
2.1.2. Tập các ràng buộc (Constraints).................................................. 20
2.1.3. Nguồn tài nguyên (Resources) .................................................... 20
2.1.4. Đội, nhóm (Teams)...................................................................... 20
2.1.5. Mục tiêu (Objectives) .................................................................. 21
2.2. Phương pháp Heuristic ........................................................................ 22
2.2.1. Khái niệm về phương pháp Heuristic.......................................... 22
2.2.2. Mô tả Heuristic ............................................................................ 23

3


2.2.4. Độ phức tạp của giải thuật ........................................................... 26
2.2.5. Ưu và nhược điểm của giải thuật ................................................ 27
2.3. Mơ hình Quản trị giá trị thu được ....................................................... 27
2.3.1. Giới thiệu về mơ hình Quản trị giá trị thu được .......................... 27
2.3.2. Phương pháp quản lý dự án áp dụng kỹ thuật EVM ................... 28

2.3.3. Đo lường hiệu năng dự án sử dụng mơ hình EVM ..................... 31
2.3.4. Ước tính chi phí hồn thành ........................................................ 32
2.4. Kết hợp mơ hình EVM và phương pháp Heuristic trong lập lịch dự án
.............................................................................................................. 39
2.4.1. Mối quan hệ giữa lập lịch dự án và giám sát dự án. ................... 39
2.4.2. Đề xuất giải pháp lập lịch dự án theo Heuristic và quản trị dự án
theo mơ hình EVM ................................................................................ 40
2.5. Tiểu kết chương 2................................................................................ 48
CHƯƠNG 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ ............................................. 50
3.1. Xây dựng cơng cụ ứng dụng ............................................................... 50
3.1.1. Thuật tốn .................................................................................... 50
3.1.2. Môi trường thử nghệm ................................................................ 51
3.2. Thử nghiệm ......................................................................................... 52
3.3. Đánh giá kết quả .................................................................................. 59
3.4. Tiểu kết chương 3................................................................................ 59
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ...................................................... 61
A. Kết luận ................................................................................................. 61
B. Hướng phát triển .................................................................................... 62

4


DANH MỤC TÀI LIỆU THAM KHẢO ........................................................ 63
PHỤ LỤC ........................................................................................................ 66
1. Các nhân tố ảnh hưởng đến dự án (Stackholders) ................................. 66
2. Các lĩnh vực quản lý trong dự án (Knowledge areas)............................ 67
3. Các hoạt động của dự án (Activities) ..................................................... 68
5. Ước lượng chi phí dự án......................................................................... 72

5



DANH MỤC HÌNH ẢNH

Hình 1.1. Những ngun nhân chính dẫn đến sự thất bại của dự án .............. 10
Hình 2.1. Ràng buộc của tam giác quản lý dự án ........................................... 17
Hình 2.2. Chi phí hồn thành so với thời gian hồn thành ............................. 26
Hình 2.3. Ý nghĩa của các thơng số trong phương pháp giá trị thu được ....... 30
Hình 2.4. Hình mơ tả các giá trị của đo lường hiệu suất cơ bản ..................... 32
Hình 2.5. Mơ tả giá trị của hiệu suất khi chỉ số pf=0...................................... 33
Hình 2.6. Mô tả giá trị của hiệu suất khi chỉ số pf=CPIcum ............................. 34
Hình 2.7. Mơ tả giá trị của hiệu suất khi chỉ số pf=CPIcum*SPIcum................. 35
Hình 2.8. Mơ tả khoảng ước tính chi phí ........................................................ 36
Hình 2.9. Mơ tả khoảng ước tính chi phí có tính chi phí phạt ........................ 38
Hình 2.10. Khoảng ước tính chi phí có tính chi phí phạt, chi phí gián tiếp.... 39
Hình 2.11. Mối quan hệ giữa PV, EV, AC ..................................................... 44
Hình 3.1. sơ đồ hoạt động của chương trình thử nghiệm ............................... 51
Hình 3.2. Mơ tả dữ liệu thử nghiệm của chương trình ................................... 54
Hình 3.3. Lịch trình Heuristic thu được. ......................................................... 54
Bảng 3.4 Bảng theo dõi các giá trị theo lịch trình thu được 29 ngày ............. 55
Hình 3.4. Lịch trình Heuristic mới .................................................................. 56
Hình 3.5. Bảng theo dõi các cơng viêc tại ngày 12......................................... 57
Hình 3.6. Theo dõi các giá trị tích lũy theo từng ngày của PV, EV và AC .... 57
Hình 3.7. Lịch trình thực tế thu được nếu dự án khơng thay đổi hiệu suất. ... 58
Hình 3.8. Biểu đồ thể hiện giá trị tích lũy của PV,EV,AC. ............................ 58

6


DANH MỤC BẢNG BIỂU


Bảng 2.1 Bảng task list mẫu............................................................................ 42
Bảng 2.2 Bảng theo dõi EV dựa trên dữ liệu bảng 2.2 ................................... 42
Bảng 3.1. Bảng tham số chi phí của các đội thực thi công việc ..................... 52
Bảng 3.2. Thời gian thực hiện mỗi công việc ứng với mỗi đội ...................... 53
Bảng 3.3. Quan hệ ưu tiên giữa các công việc ................................................ 53
Bảng 3.4 Bảng theo dõi các giá trị theo lịch trình thu được 29 ngày ............. 55
Bảng 3.5 Bảng theo dõi các giá trị theo lịch trình thu được 25 ngày ............. 56

7


DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT
Thuật
ngữ
AC
ACWP
BAC
BCWP
BCWS
CBB
CPI
CPIcum
CSI
CV
EAC
EAC
ETC
EV
EVM

ICR
MR
OBS
PD

Tiếng anh
Actual value
Actual Cost for
Work Performed
Budget at
completion
Budgeted Cost of
Work Performed
Budgeted Cost of
Work Scheduled
Contract budget
base
Cost Performance
Index
Cumulative CPI
Cost Schedule
Index
Cost variance
Estimated At
Completion
Estimate at
completion
Estimate to
completion
Earned value

Earned Value
Management
Indirect Cost Rate
Management
reserver
Organization
Breakdown
Structure
Project Duration

Ý nghĩa
Chi phí thực tế
Chi phí thực tế cho cơng việc đã thực hiện
Chi phí dự kiến tới thời điểm hồn thành
dự án
Chi phí cho cơng việc đã hồn thành
Chi phí cho cơng việc theo kế hoạch
Căn cứ ngân sách hợp đồng
Chỉ số chi phí thực hiện
Chỉ số hiệu suất chi phí tích lũy
Chỉ số chi phí tiến độ
Chênh lệch chi phí đối với kế hoạch
Chi phí ước tính để hồn thành dự án theo
thực tế
Chi phí ước tính tại thời điểm hồn thành
dự án
Ước tính chi phí cịn cần tới thời điểm
hồn thành dựa án
Giá trị thu được
Quản trị giá trị thu được

Tỉ lệ chi phí gián tiếp cho mỗi đơn vị thời
gian thực hiện dự án
Dự trữ quản lý
Sơ đồ phân tích cấu trúc
Khoảng thời gian hoàn thành dự án

8


Thuật
ngữ
PMB
PV
RAM
SPI
SPIcum
SV
UB
WBS

Tiếng anh
Performance
measurement
baseline
Plan value
Responsibility
Assignment Matrix
Schedule
Performance Index
Cumulative SPI

Schedule variance
Undistributed
budget
Work breakdown
structure

Ý nghĩa
Căn cứ đo lường hiệu suất
Chi phí theo kế hoạch
Ma trận gán trách nhiệm
Chỉ số tiến độ thực hiện
Chỉ số hiệu suất lịch trình tích lũy
Chênh lệch chi phí do thay đổi tiến độ
Ngân sách chưa dải ngân
Cấu trúc phân chia công việc thành các
công việc nhỏ

9


CHƯƠNG 1. TỔNG QUAN
1.1.

Bài toán lập lịch dự án và mơ hình quản trị giá trị thu được
Lợi ích về kinh tế luôn là vấn đề được quan tâm hàng đầu đối với các nhà

đầu tư, một dự án được quản lý tốt sẽ đưa đến tỷ lệ thành công cao hơn do đó quản
lý dự án là một vấn đề thiết thực được quan tâm và áp dụng trong nhiều lĩnh vực.
Trọng tâm xoay quanh quản lý dự án chính là việc quản lý về phạm vi cơng việc,
thời gian, và chi phí. Để quản lý tốt được những vấn đề này thì lập lịch, quản lý và

giám sát dự án là một trong những nội dung quan trọng có ảnh hưởng trực tiếp đến
tiến độ cũng như sự thành công của dự án.
Theo dữ liệu khảo sát của Project Management Institute, Inc. PMI.org/Pulse
trong tài liệu “Capturing the value of project management” đăng vào tháng 1/2015
đã thóng kê các nguyên nhân chính dẫn đến sự thất bại của dự án như sau :

Hình 1.1. Những ngun nhân chính dẫn đến sự thất bại của dự án

10


Từ biểu đồ trên thấy rằng số các nguyên nhân dẫn đến thất bại của dự án có
liên quan nhiều đến quản lý và các ước tính ban đầu về dự án, trong số các nguyên
nhân chính dẫn đến thất bại của dự án được nêu ở trên biểu đồ hình 1.1 thì có tới
11/17 lý do rõ ràng liên quan đến quản lý dự án. Các lý do còn lại: do thay đổi ưu
tiên của tổ chức, phụ thuộc vào tài nguyên , do nguồn lực hạn chế, do cơng việc phụ
thuộc…có thể được coi như những rủi ro mà để quản lý chúng cũng là một phần của
quản lý dự án.
Trong kết quả thống kê của website anagement-statistics-2015/ năm 2015 các dự án công nghệ thông
tin trung bình có tới 45% dự án vượt q ngân sách, 7% dự án bị quá hạn, 56% các
dự án không được như mong đợi. Cứ 6 dự án công nghệ thơng tin thì có 1 dự án
trung bình vượt q 200% ngân sách và bị trễ 70% tiến độ. Từ các con số trên ta
thấy được tác động quan trọng của q trình quản lý tới sự thành cơng hay thất bại
của dự án.Vì những lý do trên mà quản lý dự án đã và đang là một vấn đề thiết thực
được quan tâm và áp dụng trong nhiều lĩnh vực trong cuộc sống.
Quản lý dự án là một quá trình lập kế hoạch, điều phối thời gian, nguồn lực và
giám sát q trình hoạt đơng của dự án nhằm đảm bảo cho dự án hoàn thành đúng
thời hạn trong phạm vị ngân sách được duyệt và đạt được các yêu cầu về kỹ thuật,
chất lượng của sản phẩm, dịch vụ một cách tốt nhất. Việc lập kế hoạch là giai đoạn
thứ nhất của quy trình quản lý dự án và là sự khởi đầu quan trọng để xác định các

phương pháp, tài nguyên và các công việc cần thiết để đạt được mục tiêu của dự án.
Sau giai đoạn đầu lập kế hoạch sẽ là giai đoạn tiếp theo đưa ra lịch trình và ngân
sách của dự án. Lập kế hoạch xác định những việc cần làm và những hạn chế khi
thực hiện dự án, lập lịch trình chỉ ra cách làm và khi nào nó sẽ được làm và làm bởi
ai trong một phạm vi ngân sách đã được xác định. Lập lịch dự án là tìm kiếm cách
tốt nhất để gán các nguồn lực, tài nguyên để thực hiện các hoạt động trong một thời
gian cụ thể thỏa mãn các ràng buộc, mục tiêu đề ra. Đây là một trong những nhiệm
vụ đầu tiên vơ cùng khó khăn vì trong giai đoạn này thì người quản lý phải ước
lượng được thời gian thực hiện công việc, chi phí thực hiện theo đơn vị thời gian

11


(tuần hoặc tháng) cần thiết để hoàn thành nhiệm vụ và nguồn nhân lực sẽ đảm
nhiệm việc thực thi mỗi cơng việc. Ước lượng này càng chính xác bao nhiêu thì khả
năng dự án hồn thiện theo đúng kế hoạch càng lớn bấy nhiêu. Ngồi việc tính tốn
khả năng hồn thành dự án thì việc quản lý quá trình thực thi là rất quan trọng, giúp
cho người quản lý xác định được bức tranh tổng quan về tiến độ, thời gian, chi phí
và những rủi ro phát sinh từ đó đưa ra được các kế sách, giải pháp hợp lý để điều
chỉnh. Tuy nhiên không phải dự án nào cũng có thể tìm ra được một lịch trình tối ưu
mà thay vào đó ta có thể xem xét hoặc sử dụng một lịch trình khả thi có thể chấp
nhận được. Đó chính là tư tưởng của phương pháp Heuristic sẽ được giới thiệu
trong luận văn này để đưa ra được lịch trình khả thi cho dự án.
Đưa tới thành cơng của dự án cịn có yếu tố quan trọng khác đó là q trình
giám sát dự án. Có nhiều phương pháp giám sát khác nhau được áp dụng tùy thuộc
vào độ lớn của dự án và mục tiêu của người quản lý, tuy nhiên đối với những
phương pháp giám sát dự án truyền thống không thể cho biết những phần công việc
hay những công việc nào thực tế đã được hồn thành từ lượng kinh phí đã được bỏ
ra tính tới thời điểm kiểm soát. Việc kiểm soát tiến độ, chi phí chỉ dựa vào sự so
sánh chênh lệch giữa kết quả thu được trong thực tế với kết quả trong kế hoạch dễ

dẫn đến những đánh giá sai về tiến độ của dự án, hoặc không phát hiện ra được
những điểm then chốt để giải quyết vấn đề phát sinh trong q trình thực hiện. Mơ
hình Quản lý giá trị thu được đã khắc phục hạn chế trên. Quản trị giá trị thu được là
một kỹ thuật quản lý dự án để đo lường sự tiến triển (tiến trình thực hiện) của dự án
một cách khách quan. Quản lý giá trị thu được có khả năng kết hợp các phép đo về
phạm vi, tiến độ và chi phí trong một hệ thống tích hợp duy nhất. Áp dụng trong
quá trình hoạt động của dự án, mơ hình quản trị giá trị thu được sẽ cung cấp một
cảnh báo sớm về những vấn đề thực thi dự án cũng như các rủi ro phát sinh. Ngồi
ra, mơ hình quản trị giá trị thu được hứa hẹn cải thiện việc xác định rõ phạm vi dự
án, ngăn chặn sự mất kiểm sốt phạm vi dự án, truyền đạt về tiến trình mục tiêu tới
các bên liên quan và giữ cho đội dự án tập trung vào việc đạt được tiến bộ.

12


Rõ ràng, bằng cách sử dụng các mơ hình quản lý dự án có hiệu quả, lập kế
hoạch, lịch trình phù hợp, một người quản lý dự án có thể cải thiện các cơ hội để dự
án thành công. Do đó việc nghiên cứu mơ hình Quản trị giá trị thu được và kỹ thuật
lập lịch cho dự án là bài tốn ln được các nhà nghiên cứu và quản lý dự án quan
tâm.
1.2. Tình hình nghiên cứu trong và ngồi nước liên quan đến đề tài.
Vì những đóng góp quan trọng mang tính quyết định tới sự thành cơng của dự
án nên đã có rất nhiều các cơng trình nghiên cứu khác nhau về vấn đề lập lịch dự án
và mơ hình quản giá trị thu được.
Trong cuốn sách “Project Scheduling Recent Models, Algorithms and
Applications” đã dành cả chương 7 để nói về cách phân tích tính tốn và sắp xếp
của phương pháp Heuristic để giải quyết vấn đề lập lịch dự án có tài nguyên hạn
chế. Trong phần này tác giả Rainer Kolisch, Sönke Hartmann đã đưa ra giới thiệu
về sơ đồ sinh lịch trình, quy tắc ưu tiên cơ sở của Heuristic.
Nghiên cứu của Yusuf Kanik năm 2005 về lập lịch, đo lường và kiểm soát

hiệu suất của dự án. Đề xuất giải pháp lập lịch sử dụng phương pháp quy hoạch
ngun và ứng dụng mơ hình quản trị giá trị thu được trong quản lý hiệu suất của
dự án.
NasimPeykfalak cũng đã đề xuất việc ứng dụng giá trị thu được trên các dự án
phần mềm vào lập lịch dự án trong bài viết năm 2014 “Uristic algorithms for
Solving the resource-constrainedv project scheduling problem”
Trong nước, đã có một vài nhóm nghiên cứu các phương pháp lập lịch cho dự
án và mơ hình quản trị giá trị thu được. Nhưng tôi chưa thấy kết quả nào được công
bố về lập lịch dự án sử dụng phương pháp Heuristic và mơ hình quản trị giá trị thu
được.
1.3. Lý do, sự cần thiết phải tiến hành nghiên cứu.
Thực tế cho thấy rằng, có rất nhiều dự án thất bại, khơng hồn thành đúng thời
hạn, chi phí có thể vượt mức 100% đến 200%, thậm chí khơng thu lại được bất cứ
lợi ích gì. Lý do thường thấy và cơ bản của sự thất bại đó liên quan đến việc quản lý

13


và lập kế hoạch dự án. Vì vậy để có được một dự án thành cơng nhất thì việc quản
lý dự án nói chung và lập kế hoạch, lịch trình thực hiện dự án nói riêng đóng một
vai trị hết sức quan trọng.
Việc lập lịch trình cho dự án đặc biệt đối với những dự án phức tạp không phải
lúc nào ta cũng tìm được mơt giải pháp tối ưu, tuy nhiên với phương pháp lập lịch
bằng phương pháp Heuristic thì ta sẽ tìm đươc lịch trình khả thi có thể chấp nhận
được. Ngồi việc xác định lộ trình thực hiện dự án thì quản lý dự án sử dụng giá trị
thu được là một phương pháp rất tường minh, có thể được áp dụng rộng rãi trong
quản lý dự án của nhiều lĩnh vực.
1.4. Mục tiêu, nội dung nghiên cứu.
Luận văn đi vào tìm hiểu, nghiên cứu một số thuật tốn lập lịch dự án, phương
pháp Heuristic và mơ hình quản trị giá trị thu được, nhằm nghiên cứu tìm ra giải

pháp quản lý dự án hiệu quả. Để phát triển bài toán lập lịch theo phương pháp ứng
Heuristic và mơ hình Quản trị giá trị thu được chúng tôi đã đề ra các mục tiêu
nghiên cứu sau:
Mục tiêu thứ nhất: Có hiểu biết về phương pháp và kỹ thuật lập lịch dự án,
phương pháp Heuristic, mơ hình Quản trị giá trị thu được.
Mục tiêu thứ hai: Lựa chọn/ đề xuất và mơ phỏng được một q trình lập lịch
án sử dụng Heuristic và mơ hình Quản trị giá trị thu được.
Đối tượng nghiên cứu:
- Lý thuyết về Quản trị dự án phần mềm.
- Phương pháo Heuristic.
- Phương pháp và kỹ thuật lập lịch dự án bằng với Heuristic.
- Các mơ hình giám sát dự án.
- Giải pháp kết hợp giữa lập lịch dự án với mơ hình EVM.
- Các công cụ mô phỏng và thực nghiệm.
Phạm vi nghiên cứu:
Các phương pháp lập lịch cho dự án, phương pháp Heuristic, lý thuyết về quản
trị dự án, mơ hình EVM.

14


Nội dung nghiên cứu
Nội dung nghiên cứu của luận văn gồm phần mở đầu, 3 chương, tài liệu tham
khảo và kết luận:
 Chương 1:
Giới thiệu tổng quan về quản trị dự án, bài toán lập lịch theo phương pháp
heuristic và mơ hình quản trị giá trị thu được. Mục tiêu nội dung, cách tiếp cận và
phương pháp nghiên cứu của luận văn.
 Chương 2:
Trong chương này, trình bày những lý thuyết cơ bản liên quan đến luận văn:

- Lập lịch dự án.
- Phương pháp Heuristic.
- Mơ hình quản trị giá trị thu được EVM.
- Sự kết hợp của mơ hình EVM và phương pháp Heuristic trong lập lịch dự
án, đề xuất quy trình ứng dụng Heuristic và mơ hình EVM trong lập lịch dự án.
 Chương 3:
Trong chương này chúng tôi đưa kết quả thử nghiệm của lập lịch dự án sử
dụng Heuristic và mơ hình Quản trị giá trị thu được đề xuất trong chương 2, tiến
hành phân tích và đánh giá thông qua thử nghiệm với bộ dữ liệu mẫu.
1.5. Cách tiếp cận, phương pháp nghiên cứu.
Đề tài sử dụng phương pháp nghiên cứu tài liệu kết hợp với phương pháp phân
tích., tổng hợp nhằm tổng kết, đánh giá, lựa chọn thuật toán lập lịch dự án. Từ đó,
phương pháp cấu trúc hệ thống được đưa vào để khảo sát, khám phá những đặc tính
mới của mơ hình quản trị liên quan đến chủ đề quản trị dự án. Sau đó, phương pháp
mơ hình hóa và phương pháp thực nghiệm sẽ được sử dụng trong việc đề xuất giải
pháp và thử nghiệm, đánh giá kết quả.
a) Phương pháp phân tích và tổng hợp lý thuyết
Nghiên cứu tài liệu nhằm thu thập những thông tin về:
- Lý thuyết về quản trị dự án.
- Lý thuyết về lập lịch dự án, phương pháp Heuristic.

15


- Các tài liệu về mơ hình EVM, phương pháp nâng cao hiệu quả quản trị dự
án.
- Ngôn ngữ lập trình và cơng cụ dùng để thực nghiệm.
Trong q trình này sử dụng phương pháp phân tích và tổng hợp lý thuyết để
đưa ra khung lý thuyết cho luận văn.
b) Phương pháp điều tra, quan sát, thu thập thông tin đánh giá thực trạng

Nhằm nghiên cứu xây dựng Heuristic, mô hình hóa q trình quản trị theo mơ
hình EVM. Từ đó quan sát dữ liệu đánh giá, đề xuất các giải pháp kỹ thuật nâng cao
hiệu quả quản trị dự án.
c) Phương pháp thực nghiệm:
Thiết kế hệ thống thực hiện thử nghiệm thuật toán lập lịch sử dụng phương
pháp Heuristic đã đề xuất, mơ hình quản trị EVM đã được xây dựng để thu thập dữ
liệu nhằm phân tích, đánh giá hiệu quả đạt được.
1.6. Phương tiện, công cụ sử dụng trong mô phỏng và thử nghiệm
Các phương tiện, công cụ để mơ phỏng và thử nghiệm các thuật tốn lập lịch:
- Sử dụng máy tính, phần mềm Visual Studio 2015 để lập trình xây dựng
chương trình thử nghiệm thuật tốn lập lịch theo phương pháp Heurictic và mơ hình
quản trị giá trị thu được. Xử lý số liệu thu được từ nghiên cứu thực trạng và thử
nghiệm để rút ra kết luận khoa học cho luận văn.
- Phần mềm Microsoft Word để soạn thảo, trình bày nội dung của luận văn….
1.7. Các đóng góp của đề tài
Đề tài đã tìm hiểu được các khái niệm của phương pháp Heuristic và mơ hình
quản trị giá trị thu được
Xây dựng Heuristic áp dụng để lập lịch cho dự án
Đề xuất quy trình lập lịch dự án sử dụng Heuristic và mơ hình quản trị giá trị
thu được
Xây dựng mơ hình thử nghiệm, đưa ra các đánh giá trên cơ sở phân tích mơ
hình

16


CHƯƠNG 2. LẬP LỊCH DỰ ÁN SỬ DỤNG PHƯƠNG PHÁP HEURISTIC
VÀ MƠ HÌNH QUẢN TRỊ GIÁ TRỊ THU ĐƯỢC
2. 1. Lập lịch dự án
Trong 20 năm qua đã ghi nhận sự phát triển nhanh chóng của ngành cơng

nghiệp phần mềm trên tất cả các ngành, lĩnh vực từ số lượng, chất lượng, quy mô
của dự án. Tuy nhiên đi kèm với sự tăng trưởng đó là tỷ lệ thất bại của các dự án
phần mềm. Một số thống kê đáng ngạc nghiên về quản lý dự án do Website
đăng năm 2014 đưa ra đó là: chỉ có 2.5% trong những
cơng ty hồn thành 100% các dự án của họ, trung bình chi phí dành cho dự án vượt
q lên đến 27% so với dự kiến ban đầu và có tới 39% các dự án thất bại do thiếu
kế hoạch về hoạt động, thời gian, nguồn lực. Trong báo cáo năm 2015 nghiên cứu
của Standish Group cho thấy số liệu đáng kinh ngạc 19% số dự án sẽ được hủy bỏ
trước khi chúng được hoàn thành, 52% số dự án sai lệch đối với mục tiêu ban đầu
và chỉ có khoảng 29% các dự án hoàn thành đúng về tiến độ và chi phí. Qua các con
số thống kê trên ta thấy được quản lý dự án chính là chìa khóa để dẫn tới thành cơng
của một dự án. Quản lý dự án tốt phải đảm bảo sự cân bằng giữa các yếu tố về chất
lượng, thời gian thực hiện và chi phí trong phạm vi của dự án.

Hình 2.1. Ràng buộc của tam giác quản lý dự án
Một trong những yếu tố cơ sở trong việc đưa đến quản lý, theo dõi dự án thành
cơng đó chính là vấn đề lập lịch trình cho dự án và giám sát dự án. Lập lịch cho dự
án là việc tìm ra kế hoạch sử dụng các nguồn lực thực hiện công việc cụ thể trong

17


một khoảng thời gian xác định để thực thi được các yêu cầu về mục tiêu và đáp ứng
các ràng buộc cách tốt nhất, hiệu quả nhất. Đây là giai đoạn ban đầu nhưng vô cùng
cần thiết xác định phương pháp, tài nguyên và các công việc cần phải thực hiện để
đạt được mục tiêu của dự án, hình thành lên được cách thức thực thi dự án.
Để lập lịch cho một dự án thì điều đầu tiên phải căn cứ vào phạm vi của dự án
và các công việc đã được xác định trong sơ đồ cấu trúc phân chia công việc, cách
tiếp cận cơ bản của mọi kỹ thuật lập lịch trình đó là xây dựng một ma trận trách
nhiệm dựa trên sự kết hợp giữa WBS và sơ đồ OBS được xác định rõ trách nhiệm

của từng cá nhân, thời gian thực hiện, kinh phí và những vấn đề có thể phát sinh, sơ
đồ này sẽ phải được điều chỉnh khi kế hoạch tương ứng có sự thay đổi. Việc lập kế
hoạch và lịch trình thực hiện dự án có thể được sử dụng như một cơng cụ hữu hiệu
để ngăn ngừa các vấn đề không mong muốn có thể xảy ra, giúp hạn chế sự chậm trễ
tiến độ dự án, giúp tránh chi vượt dự toán.
Để hình thành được một lịch trình cơng việc có 5 bước cơ bản (Quentin W
Fleming and Joel M. Koppelman, 2005)
1. Xác định các hành động: Xác định tất cả các cơng việc cần thiết để hồn
thành sản phẩm, xác định phạm vị công việc dựa trên sơ đồ WBS đã được thơng
qua của dự án.
2. Xác định trình tự của các hoạt động: Xác định các hành động phụ thuộc,
mối quan hệ ưu tiên.
3. Ước tính tài nguyên hoạt động: Xác định các nguồn lực và khả năng của đội
để thực hiện cơng việc
4. Ước tính thời gian hoạt động: Với nguồn lực được giao, bước tiếp theo là
để ước lượng thời gian của mỗi công việc, thời gian của hoạt động là số thời gian
làm việc cần thiết để hồn thành các u cầu của cơng việc đó, điều này có thể được
xác định theo ngày, tuần, và thậm chí cả tháng.
5. Xây dựng lịch trình: Lựa chọn cơng cụ lập lịch. Trong trường hợp cần xem
xét điều chỉnh thì quay lại bước 1.

18


Mục đích để có thể tìm hiểu về vấn đề cơ bản của bài toán, các điều kiện về
thực thi của mơ hình dự án nghiên cứu được mơ tả như sau:
- Dự án được chấp nhận là hoàn thành khi tất cả các hoạt động cấu thành dự
án được hồn thành.
- Các đội có thể được giao nhau nói cách khác là các đội này có thể chứa một
hoặc nhiều thành viên chung.

- Các đội có thành viên chung (giao nhau) không được làm việc tại cùng một
thời điểm.
- Một đội không thể được bắt đầu làm việc trừ khi tất cả những nhiệm vụ
trước của nó được hồn thành.
- Chỉ có một đội được thực thi trên một hoạt động tại một thời điểm
- Thời gian thực hiện từng hoạt động là khác nhau phụ thuộc vào các đội
được yêu cầu.
- Ước tính thời gian thực hiện từng hoạt động sẽ được mỗi đội tính tốn trước
khi lập kế hoạch.
- Một công việc không thể được thực hiện khi cơng việc trước đó liên quan
đến nó chưa được hồn tất.
- Các hoạt động sẽ khơng bị ngắt đoạn.
Các yếu tố đầu tiên cần phải xem xét khi lập lịch cho dự án là (James P.
Clements & Jack Gido (2006)):
2.1.1. Tập các công việc (Activities)
Các công việc là những yếu tố cấu thành một dự án, còn được gọi với những
cái tên khác như nhiệm vụ, hoạt động. Các cơng việc có thể đo lường được ước tính
về các tiêu chí như thời gian, chi phí và nhu cầu nguồn lực. Để hồn thành một dự
án thì tất cả các cơng việc cấu thành dự án phải được hồn thành., các ước tính về
thời gian hoặc chi phí cho một cơng việc có thể phụ thuộc vào các nguồn tài ngun
được sử dụng bởi cơng việc đó. Một cơng việc có thể được phép gián đoạn nhưng
khi khơng được phép thì nó khơng thể dừng lại cho tới khi hoàn thành.

19


Các cơng việc có ước tính về thời gian và dự tốn chi phí phụ thuộc vào trình
độ, kĩ năng của các thành viên trong đội. Chi phí cho mỗi hoạt động cũng phụ thuộc
vào đội được giao thực hiện hoạt động đó do thời gian hồn thành hoạt động đó với
mỗi đội là khác nhau, năng lực và tỷ lệ lao động trực tiếp của mỗi đội cũng khác

nhau. Mỗi cơng việc một khi đã bắt đầu có thể khơng được dừng lại và đội được
gán cơng việc đó cũng khơng được thay đổi cho tới khi hồn thành hoạt động đó.
Các hoạt động có độ ưu tiên và một hoạt không thể bắt đầu khi hoạt động ưu tiên
cao hơn nó chưa hồn thành.
2.1.2. Tập các ràng buộc (Constraints)
Các ràng buộc xác định tính khả thi của một lịch trình. Một lịch trình khả thi
thì nó phải đáp ứng tất cả các ràng buộc. Những ràng buộc thường được mơ tả bằng
đồ thị có hướng trong đó một công việc (activity) được thể hiện bằng một nút và
mỗi quan hệ ưu tiên giữa hai công việc được mô tả bằng một mũi tên có hướng.
Trong lập lịch dự án, ràng buộc thường thấy nhất đó là ràng buộc về nguồn lực và
thời gian sẵn có, về yêu cầu của khách hàng. Ví dụ như một nhân viên chỉ làm việc
một số ngày trong tuần theo kiểu làm bán thời gian
2.1.3. Nguồn tài nguyên (Resources)
Nguồn tài nguyên của dự án thường được phân loại là tài nguyên tái tạo được
và không tái tạo được. Tài nguyên tái tạo được ln sẵn có mà khơng bị cạn kiệt
như máy móc, thiết bị, nhân lực… Tài nguyên không tái tạo được thường bị giới
hạn bởi tầm nhìn và bị cạn kiệt vì chúng đã được sử dụng. Ví dụ như vốn ngân sách
của dự án, nguyên vật liệu phục vụ cho dự án là những loại tài nguyên thuộc dạng
không tái tạo được.
2.1.4. Đội, nhóm (Teams)
Đội, nhóm có thể được định nghĩa là các nguồn nhân lực được sử dụng và cần
thiết cho việc thực hiện các hoạt động. Các nhóm, đội là loại tài nguyên có thể tái
tạo được. Một đội có thể được bao gồm nhiều cá nhân, có trình độ, năng lực làm
việc khác nhau do đó sẽ có sự chênh về lệch khả năng và chi phí cho mỗi đội và sự
chênh lệch đó được đưa vào việc tính tốn ước lượng thời gian cho mỗi cơng việc

20


của đội. Các đội có sẵn ở trong tất cả các giai đoạn của dự án và được phép làm việc

trên một hoạt động tại một thời điểm. Các đội có thể có sự chồng chéo giữa các cá
nhân hay nói cách khác là nhiều đội có thể có chứa cùng một hoặc nhiều cá nhân
chung. Các đội như vậy không thể cùng làm việc một lúc.
2.1.5. Mục tiêu (Objectives)
Một lịch trình được gọi là một lịch trình khả thi khi nó đáp ứng được tất cả các
ràng buộc. Như vậy các ràng buộc sẽ xác định tính khả thi của một lịch trình. Tuy
nhiên, khác với ràng buộc, mục tiêu sẽ xác định sự tối ưu của một lịch trình. Một
lịch trình tối ưu khơng chỉ đáp ứng tất cả những ràng buộc mà cịn là một lịch trình
ít nhất cũng tốt như bất kì lịch trình nào trong các lịch trình khả thi. Tối ưu hóa có lẽ
là mục tiêu nghiên cứu và được áp dụng nhiều nhất trong lập lịch dự án, đặc biệt là
mối quan tâm về giảm thiểu chi phí cũng được sử dụng thường xuyên do ý nghĩa
thiết thực của nó.
Một dự án được đánh giá là thành công dựa trên hiệu quả về chi phí của nó
mang lại khi kết thúc dự án. Chi phí tại thời điểm hồn thành là tổng chi phí lao
động trực tiếp, chi phí gián tiếp và những chi phí bị phạt của dự án.
a) Chi phí lao động trực tiếp – Direct Labor Cost
Là chi phí được trả cho mỗi cá nhân tương ứng với tỷ lệ về thời gian mà cá
nhân đó làm việc cho dự án. Một đội bao gồm nhiều cá nhân và tỷ lệ chi phí lao
động trực tiếp của đội là tổng tỷ lệ chi phí lao động trực tiếp của từng thành viên.
(Chi phí trực tiếp)Dự án=

i*ri

Trong đó: ti biểu thị thời gian mà đội i làm việc cho dự án
ri biểu thị tỷ lệ chi phí lao động trực tiếp của đội i
b) Chi phí gián tiếp – Indirect Costs
Là chi phí phát sinh trong mỗi đơn vị thời gian dự án tiếp tục được thực hiện,
chi phí gián tiếp phát sinh với tỷ lệ gọi là "Tỷ lệ chi phí gián tiếp". Tỷ lệ này là
khơng đổi trong suốt dự án và độc lập với các hoạt động đang thực thi ví dụ như chi
phí th văn phịng, chi phí hỗ trợ nhân sự…

(Chi phí gián tiếp)Dự án= tpj * ric

21


Trong đó: tpj thời gian thực hiện dự án
ric tỷ lệ chi phí gián tiếp.
c) Chi phí bị phạt – Penalty
Là chi phí tiền phạt mà nhà thầu phải trả cho bên liên quan trên mỗi đơn vị
thời gian dự mà án đã quá hạn.
Do đó mục tiêu của việc lập lịch là để tìm ra lịch trình thực hiện sao cho giảm
thiểu tối đa tổng chi phí tại thời điểm hoàn thành dự án trong khi vẫn đáp ứng tất cả
các ràng buộc và mục tiêu của dự án.
2.2. Phương pháp Heuristic
2.2.1. Khái niệm về phương pháp Heuristic
Có rất nhiều các thuật toán khác nhau được sử dụng trong bài toán lập lịch
dự án, tuy nhiên được chia là 2 phương pháp chính đó là : lập lịch theo phương
pháp tối ưu và lập lịch theo phương pháp Heuristic.
Lập lịch theo phương pháp tối ưu thường mất nhiều thời gian, trong thực tế
khơng phải bài tốn nào cũng có lời giải, có nhiều trường hợp có thể chấp nhận các
cách giải thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít phức
tạp và hiệu quả. Chẳng hạn nếu giải một bài toán bằng thuật toán tối ưu địi hỏi máy
tính thực hiện nhiều năm, hoặc khơng chắc chắn ra kết quả thì chúng ta có thể sẵn
lòng chấp nhận một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày
hoặc vài giờ. Phương pháp Heuristic là một sự mở rộng khái niệm thuật tốn về tính
đúng đắn. Tính đúng của thuật tốn khơng cịn bắt buộc đối với một số cách giải bài
toán, nhất là các cách giải gần đúng.. Phương pháp Heuristic thể hiện cách giải bài
toán với các đặc tính sau:
- Thường tìm được lời giải tốt (nhưng khơng chắc là lời giải tốt nhất).
- Thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu,

vì vậy chi phí thấp hơn.
- Thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con
người.

22


Có nhiều cách thức để xây dựng thuật tốn theo phương Heuristic, trong đó
người ta thường dựa vào một số nguyên lý cơ sở như sau:
- Nguyên lý vét cạn thơng minh: khi khơng gian tìm kiếm lớn, ta thường tìm
cách giới hạn lại khơng gian tìm kiếm hoặc thực hiện một kiểu dị tìm đặc biệt dựa
vào đặc thù của bài tốn để nhanh chóng tìm ra mục tiêu.
- Nguyên lý tham lam: Lấy tiêu chuẩn tối ưu (trên phạm vi tồn cục) của bài
tốn để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay
từng giai đoạn) trong quá trình tìm kiếm lời giải.
- Nguyên lý thứ tự: Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý
của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt.
- Hàm Heuristic: Là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng
thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được
cách hành động tương đối hợp lý trong từng bước của thuật giải.
Hiện nay có nhiều thuật toán được ứng dụng trong lập lịch dự án sử dụng theo
phương pháp Heuristic như: Giải thuật tham lam, giải thuật di truyền, giải thuật leo
đồi, thuật toán Tabu Search, giải thuật luyện kim, giải thuật di truyền ..... Trong nội
dung tìm hiểu của luận văn này tơi đã tìm hiểu về phương pháp Heuristic ứng dụng
giải thuật tham lam vào lập lịch dự án.
2.2.2. Mô tả Heuristic
a) Ý tưởng của Heuristic
Như đã trình bày trong phần 2.1 ta đã đưa ra mục tiêu của lập lịch dự án là tìm
ra lịch trình thực hiện sao cho giảm thiểu tối đa tổng chi phí tại thời điểm hồn
thành dự án trong khi vẫn đáp ứng tất cả các ràng buộc và mục tiêu của dự án. Ứng

dụng nguyên lý tham lam để giải quyết bài toán là lập lịch dự án sao cho dự án được
hoàn thành với tổng kinh phí là thấp nhất tương ứng với việc từng nhiệm vụ của dự
án được hoàn thành với chi phí thấp nhất. Khi đó xác định chi phí thực hiện từng
cơng việc các đội với tiêu chí lựa chọn đội thực hiện cơng việc có chi phí thấp nhất.
Sau khi lựa chọn được đội thực hiện công việc, xác định thời gian thực hiện
công việc, xây dựng thứ tự của lịch trình trên cơ sở thực hiện các cơng việc ưu tiên.

23


Nếu thời gian của thực hiện theo lịch trình quá thời gian yêu cầu của dự án thì áp
dụng chi phí phạt.
b) Mơ tả giải thuật (Yusuf Kanik, 2005)
Giải thuật được xây dựng theo nguyên lý tham lam với tư tưởng là lựa chọn
đội thực hiện từng công việc với chi phí nhỏ nhất
Bước 1: Đánh số lần lượt tất cả các công việc của dự án từ công việc đầu tiên
tới cơng việc cuối cùng. Mục đích của bước này là xác định thứ tự hoạt động cũng
như quy tắc ưu tiên cho các công việc.
Bước 2: Xác định chi phí thực hiện mỗi cơng việc của mỗi đội. Chi phí này
được đưa vào tài khoản khi xác định tổng chi phí của cơng việc. Nó bao gồm tổng
cộng của: chi phí trực tiếp, chi phí gián tiếp và chi phí phạt.
Chi phí thực hiện hành động j của đội k được tính là:
C = P*(WDLR + WICL + WPC)
Trong đó:
C: chi phí thực hiện hành động
P: thời gian thực thi hành động j của k (tính theo tuần)
WDLR: Tỷ lệ chi phí lao động trực tiếp hàng tuần của đội k
WICL: Tỷ lệ chi phí gián tiếp hàng tuần của dự án
WPC: Chi phí phạt hàng tuần của dự án
Bước 3: Đối với mỗi hành động xác định sẽ chọn đội thực thi cơng việc đó với

chi phí là nhỏ nhất.
Bước 4: Bắt đầu từ công việc đầu tiên, ấn định mỗi công việc cho đội thực thi
với một chi phí thấp nhất và xác định vị trí trong một phạm vi thời gian theo thứ tự
được xác định ở bước1. Giả định là tất cả các công việc được thực thi tuần tự,
khơng có bất kỳ xử lý song song.
Bước 5: Quản lý được các quan hệ ưu tiên thực sự của mạng lưới dựa án và
hoạt động chuyển dịch hiệu suất các tài nguyên trên phạm vi thời gian. Bắt đầu
chuyển từ công việc đầu tiên của lịch trình tuần tự, tiếp tục theo thứ tự của các cơng
việc trong lịch trình được xây dựng ở bước 4 và gán thời gian bắt đầu của mỗi công

24