Chương 12 : Lịch trinh du an
Thuật ngữ lịch trinh có nhiều dinh nghĩa khác nhau . Trong trường hợp nhà máy hoạt động
tren dự án, người ta tìm cách lên kế hoạch thời gian thực hiện các hoạt động khác nhau của
dự án. Ta gọi đó là lịch trinh dự án. Điều này dua tren các quyết định chiến thuật cũng
như chiến lược . Đối với trường hợp các xưởng sản xuất cac chuoi co quy mo nhỏ và vừa,
thuật ngữ này liên quan đến việc quản lý dây chuyền sản xuất. Quản lý phân xưởng là
quản lý ở cấp độ các hoạt động . Một số định nghĩa và phương pháp là tổng quát cho các
van de này. Để cho dể hiểu , ta sẽ tìm hiểu chúng trong các chương khác nhau Trong
chương này, chúng ta sẽ tập trung vào lịch trinh dự án. Trước hết, chúng ta tìm hiểu thuật
ngữ này.
12.1 Định nghĩa
Dự án : dự án là một tập hợp hoạt động cho phép ta đạt được một mục tiêu rỏ ràng .Điều
phan biet giua dự án va sản xuất là đặc tính don vi và cải tiến , với một mục đích xác định
và giới hạn theo thời gian .
Vi du: xay dung 1 may may can thep, thiet lap he thong thong tin trong xi nghiep, bao tri 1
may bay, phat hanh 1 loai my pham moi, 1 chuyen du hanh vu tru, … la nhung hoat dong
cua du an.
Công việc : công việc là các hoạt động phai duoc thuc hien nhằm mục đích sao cho mục
đích ấn định ban đầu có thể đạt được. Định nghĩa công việc là điểm khó khăn đầu tiên ma
nguoi quan ly dự án phai thuc hien. Ví dụ như đối với dự án xây dựng một toa nha, các
công việc se là “lợp mai che” hoac phai phân tích hoạt động này ra “dựng khung dàn ” , “
đặt ống khói ” và “lợp ngói ”
Tài nguyên : một công việc đòi hỏi nhiều nguyên vật liệu , tài chính và nhân lực để có thể
thực hiện . Những cái đó gọi là tai nguyên (nguon luc). Người ta chia tài nguyên thành hai
loại . Tài nguyên được tiêu thu được gọi là tài nguyên “bi mat” trong quá trình thực hiện
công việc (tiền, nguyen vat lieu…) Tài nguyên sử dụng lai đựơc (máy móc, nguoi thao tac
…) Khi những tài nguyên này là có hạn , người ta phải phan chia chúng giữa các công việc
khac nhau , ta gọi đó là sap xep cac tài nguyên
Ràng buộc giữa các công việc : sau khi phân chia cac công việc, cần phải xac định những
ràng buộc cua các công việc nay. Chúng được chia thành 4 nhóm :
 Ràng buộc về sự liên tục : Đó là ràng buộc tự nhiên nhất Chúng xác định

chuỗi hoạt động (tính lôgic của dự án ). Dạng thường gặp nhất là : Công việc A
cần phải kết thúc trước khi công việc B bắt đầu (Quan hệ kết thúc bắt đầu ) .
Ngoài ra cũng có thể gặp các dạng : Công việc B bắt đầu khi công việc A đat
được ¾ hoặc là Công việc B bắt đầu 3 ngày sau khi công việc A kết thúc (Ví
dụ như ràng buộc của công việc sấy khô)
 Ràng buộc trong một khoảng thời gian : Các công việc có thể thực hiện
trong một khoảng thời gian giới hạn . Ví dụ người thợ nề không thể thực hiện
công việc A trước một ngày nào đó và phải kết thúc công việc trước một ngày nào
đó
Lưu ý : chúng ta da phân biệt ràng buộc về sự liên tục và ràng buộc trong một
khoảng thời gian . Một cách toán học, ràng buộc về sự liên tục thể hiện qua viec
sự bắt đầu (hay kết thúc ) của công việc x phụ thuộc sự bắt đầu (hay kết thúc )
1
của công việc truoc no. Ràng buộc trong một khoảng thời gian thể hiện qua viec
sự bắt đầu (hay kết thúc ) của công việc x phụ thuộc vào một hằng số. Do đó
không có sự khác biệt vè bản chất của các ràng buộc này và vì vậy ta ghép các
ràng buộc này vào một nhóm chung gọi là ràng buộc tiềm năng
 Ràng buộc xung đột : Ràng buộc xung đột không cho phép thực hiện đồng
thời hai công việc A và B . Co các ràng buộc xung đột trong trường hợp sử dụng
chung tài nguyên (Băng chuyền, thiết bị ….) hay các cam ky khác trong viec thực
hiện dong thoi các công việc (lí do bảo mật , lí do hạn chế về không gian ….) Van
de là thực hiện công việc A hay B truoc.
 Ràng buộc tích lũy : người ta nói đến ràng buộc tích lũy khi các công việc
cần có tài nguyên để thực hiện nhưng mà các tài nguyên này là có hạn nhưng
nhiều hơn 1 tài nguyên.Van de se kho hon do voi các ràng buộc xung đột .Xem ví
dụ sau , chúng ta có 5 thợ nề và 5 công việc với các yêu cầu sau :
Công việc A B C D E
Thợ nề 3 4 1 2 1
Để có thể thực hiện công việc này, bat cu luc nao các công việc duoc thực hiện
song song khong duoc qua so 5 thợ nề. Va cac tuong hop sau day se khong the xuat hien:

A//B , A//C//D , A//D//E , B//D ,B//D//E
Lên lịch cho dự án : la chương trình thực hiện các công việc trong dự án theo thời
gian, thõa mãn các ràng buộc và tối ưu hóa một mục đích xác định .Các mục đích chinh
mà chúng ta thường gặp là :
Tối thiểu hóa thời gian tổng cộng của dự án
Đối với 1 ngày kết thúc dự án đã ấn định trước, tối thiểu hóa chi phí thực hiện hay
tối uu cac tài nguyên sử dụng
12.2 Những dieu kien can co trong quản trị dự án
Chương này giới thiệu những phương pháp sử dụng trong việc lên lịch cho dự án mà
không la môn học “thuc hien dự án ”, dieu nay doi hoi 1 tài liệu riêng . Chúng tôi chi nhắc
các điểm quan trọng trong viec phân tích trứơc
12.2.1. Người phụ trách dự án
Trước khi bắt đầu dự án , cần phải xác định rõ ràng mục đích của dự án va chỉ định
người phụ trách dự án . Mục đích phải được chủ dự án đưa ra : Chủ dự án mới biết
cần đạt được cái gì vì chỉ ông ta mới khẳng định mục tiêu da dat duoc hay chua.
Ong ta phai xac dinh ro chinh xac y muon cua minh. Luc đầu cần phải chỉ định một
người phụ trách duy nhất. Người nay phai co quyen han doi voi cac nhan vien tham
gia du an. Ong ta phai co cac pham chat ve nhan dao và tổ chức.
12.2.2 Phân tích nhóm công việc
Bước một của việc thiết kế lịch là phân tích dự án. Nếu so luong công việc cần thực
hiện là rất nhiều, dự án se được phân tích thành những phần lớn, cac phan nay lai
tiep tuc duoc phan thanh nhung phan nho hon va tiep tuc cho den khi chung ta dat
duoc muc do chi tiet mong muon.
2
Khi dự án trải rộng trên một thời gian dài , không phải luôn luôn xác định được
chính xác lúc bắt đầu chi tiết các công việc can đạt được khi dự án kết thúc . Phân
tích du an ở nhiều mức độ khác nhau cho phép lập kế hoạch tổng quát so bo ngay
luc bắt đầu toan bo công việc trong dự án, kế hoạch se duoc xác dinh ro hon khi
cac giai doan den gan. Tuy truong hop, co giai doan trung gian trong quá trình
thành lập kế hoạch. Dần dần , kế hoạch của dự án sẽ được thuc hien, những thông

tin bổ sung sẽ được cập nhật nên ta có thể phân tích kĩ hơn .
Để ước lượng thời gian ,chúng ta cần xác định đơn vị thời gian. Đơn vị thời gian
đựơc chọn phải nhỏ so với thời gian của dự án để cho phép phan tich chinh xac
nhung cung khong qua nho de so luong bieu dien cac khoang thoi gian co the duoc
su dung de dang va co ý nghĩa vat ly so voi công việc.Thời gian của công việc có
thể duoc tang bởi người phụ trách dự án vì những lí do an toàn .Nếu thời han tổng
cộng cho tu tính toán sơ bộ vượt du doán của nguoi quan lydự án, người phụ trách
phai lam viec lai về những giá trị du doán của ông ta . Với những du lieu thay đổi ,
các tính toán mới cần phải thực hiện .Thời gian trung bình của mỗi công việc
không thể qua nhỏ so voi tần số kiem soat, nếu không co the xảy ra sự trễ nghiêm
trọng mà không biet.
Con co những van de về tổ chức có thể ảnh hưởng đến việc lựa chọn muc do chi
tiết cho dự án: Các vị trí đặt phân xưởng, cac nganh nghe se duoc su dung, tài
nguyên nguyên liệu sử dụng , nhu cầu dụng cụ de thuc hien nhieu cong viec, tren
cung 1 may,…
12.2.3 Sự lien tiep giữa các công việc
 Khi danh sách các công việc đã được thiết lập , nguoi trưởng dự án yêu cầu mỗi
người phụ trách công việc nói len dưới điều kiện nào thì công việc được có thể bắt
đâu , công việc nào là công việc theo sau hay di truoc công việc cua ho. So sánh các
trả lời cho phep xac minh tinh liên kết giữa các công việc với nhau va neu can co
the sua doi hay bo sung phan tich. Để một công việc có thể thực hiện đựơc cần sắp
xếp nguyên vật liệu , tài chính , nhân lực và thông tin .Chung ta phai kiem tra la doi
voi moi công việc, chung da duoc khau truoc do chuan bi cac phuong tien cung nhu
thong tin hay chua. Bước phân tích này co tam quan trọng cơ bản cho lịch trinh của
dự án
12.3 Các ho so
12.3.1 To chuc và kiem soat các ho so
Cuối bước phân tích, chung ta co duoc cac ho so (tren giay hoac trong may tinh) mô tả
cac công việc :
 Thông tin tổng quát (mục đích , người phụ trách …)

 Thời gian dự đoán trong trường hợp đơn giản hoac thời gian ước lượng
trường hợp thống kê
 Danh sách các ràng buộc truoc do
 Các ràng buộc về tài nguyên
 Nếu có thể được các thông tin về giá
Tập hợp các thông tin cung cấp dua den hai mức độ kiem soat và hop thuc hoa.Mức độ 1
bao gồm việc kiem soat sự chính xác của thông tin, đặc biệt là thời gian cần khong duoc du
3
doan qua cao và những cong viec duoc hoan thanh truoc (préraquis) phải dung. Su hop
thuc hoa nay do nguoi thuc hien.
Mức độ 2 bao gồm sự kiểm tra sự liên kết cua toan bo cac ho so. Cần phải bảo đảm trước
tiên rằng các công việc duoc ke den nhu da duoc hoan thanh truoc do se phai co trong ho
so. Giai doan 2 là kiểm tra tính hợp lí kha thi của dự án .Sự lý luan này dua tren các ràng
buộc về sự liên tục . Không thể có mối quan hệ kiểu như sau :



Đối với những dự án nhỏ, sự liên kết nay được kiểm tra bằng cách vẽ sơ đồ dự án .Sơ đồ
hay gặp nhất là dat moi công việc o moi dinh và nối một cung từ A đến B nếu A duoc thuc
hien truoc B .Một cách toán học , Sơ đồ này khong kin. Những sơ đồ này thuong duoc su
dung (muc luc, du tru) va sẽ được thảo luận ở 12.12 . Sau khi da kiểm tra sự liên kết giữa
các công việc, chúng ta giả sử dự án đã được chuẩn hóa có nghĩa là :
 Co diem gia dinh “Bắt đầu ”, co thời gian keo dai la 0, tuong trung luc bat
dau du an (dat vien da dau tien,…)
 Co diem gia dinh “Kết thúc”, co thời gian keo dai la 0, tuong trung luc cham
dut du an (uong ruou mung)
 Đánh số các công việc sao cho
 Công việc “Bắt đầu ” mang số 1
 Công việc “Kết thúc” mang số n
 Công việc bất kỳ x mang số lớn hơn số của những công việc y duoc hoan

thanh truoc nó
12.3.2 Ví dụ
Sau đây ta xét 1 ví dụ: 1 dự án được phân tích thành 10 công việc .Những công việc này
được mã hóa bang 4 kí tự và chúng ta tóm tắt những thông tin cơ bản của ho so theo bảng
dưới đây:
TâChe Précédences Dureé
AcBt
AcMt
Chrp
Fond
Isol
Lazu
MrBt
MrPk
Ouvr
Toit
MrPk
AcMt , MrBt
Chrp ,Ouvr
AcBt ,Fond
AcMt ,Fond
MrPk
Chrp
2
2
2
3
4
2
3

4
5
3
4
B
A C
Chung ta de dang biểu diễn bằng đồ thị va đánh số cac du lieu nhu trong hình 12.1
12.4 Van de cơ bản
Trong van de cơ bản, thời gian thuc hien các công việc là hoàn toàn biết trước .Ngày bắt
đầu dự án cũng được biết trước .Ràng buộc duy nhất mà người ta phai tinh den là những
ràng buộc loại lien tiep: công việc y phải hoàn thành trước khi công việc x bat dau. Chung
ta thay (Phần 12.6.1) rằng rất dễ dàng them vao cac ràng buộc ve thời gian . Cac tai
nguyen được giả định là có sẳn và đủ, ta goi Pred (x) la tap hop nhung công việc duoc
hoàn thành truoc x, va Succ(x), tap hop nhung công việc ngay sau x
Hinh 12.1 Do thi cua du an
12.4.1 Tính toán ngày sớm nhất
Dễ hieu la công việc x không thể bắt dầu khi các công việc trước nó chưa hoàn thành .Vì
vậy duong nhien:
Bắt đầu (x) = Max{Kết thúc (y), y
∈
Pred(x)}
Vi các công việc được đánh số thích hợp, chúng ta có thuật toán để tính ngày sớm nhất như
sau :
Co can su dung mui ten khong, vi trong sach khong thay….
Bắt đầu sớm (1) Ngày bắt đầu dự án
Kết thúc sớm (1) Ngày bắt đầu dự án
Cho x chạy từ 2 đến n
Bắt đầu sớm (x) Max{Kết thúc sớm(y), y
∈
Pred(x)}

Kết thúc sớm (x) Bắt đầu sớm (x) + thời gian làm việc x
Kết thúc
Ngày kết thúc dự án Bắt đầu sớm (n)
14.4.2 Ngày trể nhất
Ngược lại ,nếu ta cố định ngày của những công việc kế tiếp của x , de ton trong cac ngày
này ta phải chú ý de x hoàn thành trước khi các công việc sau của nó bat dau.Vì vậy ta có:
kết thúc(n) ← Min {Bắt đầu (z), Với z
∈
Succ(x)}
Chúng ta có thuật toán để tính ngày trể nhất như sau :
5
Bắt đầu trể (n) Ngày kết thúc dự án
kết thúc trể (n) Ngày kết thúc dự án
Cho x chạy từ n-1 đến 1
kết thúc trể (x) Min {Bắt đầu trể (z), Với z
∈
Succ(x)}
kết thúc trể (n) Ngày kết thúc dự án (x) - thời gian làm việc (x)
kết thúc
Đối với một dự án nhỏ , người ta đi từ trái sang phải 1 lần dựa trên biểu đồ đẫ cho để xác
định ngày sớm nhất , và một lần từ phải sang trái để xác định ngày trể nhất . Neu tinh bang
may tinh, thuật toán dầu dùng ho so của công việc trước nó . Ho so này có được khi ta dua
vao cac dữ liệu.Thuật toán thứ hai sử dụng ho so của những công việc theo sau . Di tu
thuật toán nay sang thuật toán khac thi de dang, nhưng tốn nhiều thời gian và bộ nhớ.
Chúng ta có thể tranh bang cach tinh den thoi gian bat dau cham nhat cua x vao cac ho so
cua cac công việc trước nó. Thuật tóan tot hon se la:
Bắt đầu trể (n) Ngày kết thúc dự án
Cho x chạy từ 1 đến n
kết thúc trể (x) Ngày kết thúc dự án
Cho x từ n đến 2

Bắt đầu trể (x) kết thúc trể (x) - thời gian làm việc (x)
Với moi y
∈
Pred (x)
Nếu kết thúc trể (y) > bắt đầu trể x
kết thúc trể (y) bắt đầu trể x
Kết thúc
Áp dụng vào ví dụ trên thuật toán cho chúng ta kết quả trên bảng 12.1 .Chú ý rang trong
cac kết quả, những ngay ương ứng với luc đầu của ca thoi ky. Gia su rang thoi gian làm
việc duoc tinh theo ngay, thi ngay kết thúc dự án là ngày thứ 14.Theo cách nói thông
thường thi dự án kết thúc vào ngày thứ 13 (vào cuối ngày). Trong bảng kết quả, ta nen
giảm bớt ngày kết thúc trể nhất cua dự án một ngày.
Thieu bang 12.1
12.4.3 Thoi gian an toan
Chúng ta gọi thoi gian an toan là giá trị MT(x)
MT(x) = Bắt đầu trể(x) – bắt đầu sớm (x)
Thoi gian an toan biểu thị kha nang người ta có thể tac dong len x mà không làm thay đổi
ngày kết thúc dự án. Kha nang này có thể tac dong len ngay bắt đầu của x hoặc keo dai
thời gian dự kiến. Hay là ket hop cả hai. Chúng ta gọi công việc khẩn cấp là công việc mà
thoi gian an toan là Zero. Nếu da dat toi giới hạn an toan thi công việc trở thành khẩn cấp,
tuong tu cho vài công việc sau nó. Nếu lai vượt qua giới hạn an toan, số dư sẽ tác động lên
ngày kết thúc dự án ngày và gay su trể nai.
Thoi gian an toan tự do ML của 1 công việc x la hiệu của min ngày bắt đầu sớm nhất của
cac công việc tiếp theo của x , và kết thúc sớm nhất công việc x:
ML(x)= Min { bắt đầu sớm (z)- kết thúc sớm (x), với z
∈
Succ(x)}
6
Thoi gian an toan tự do biểu thị miền chúng ta có thể tac dong len công việc x mà không
ảnh hưởng đến các công việc khác . Mot su trể hon thoi gian an toan tự do (nhưng con it

hon tổng thoi gian an toan) se tác động lên các công việc theo sau va làm giảm bớt cac thoi
gian an toan cua chúng (Vì it nhat 1 công việc theo sau co ngày bắt đầu sớm nhất đã bị
trể). Xét công việc AcBt trong ví dụ. Nó có thể bắt đầu trong khoảng thời gian giữa 0 và 5
mà không làm trể ngày kết thúc dự án . Thoi gian an toan cua no là 5. No chỉ có công việc
tiếp theo là MrBt, công việc nay có thể bắt đầu sớm nhất là 1.AcBt có thể bắt đầu ở 0 hoặc
1 mà không làm thay đổi ngày ở MrBt
x Code Pred Dureé DTôt FTôt
Dtart Ftart
1 DéBut 0 0
0 0 0
2 AcMt 1 2 0
2 1 3
3 Fond 1 3 0
3 0 3
4 AcBt 1 2 0
2 5 7
5 MrPk 2,3 4 3
7 3 7
6 MrBt 3,4 3 3
6 7 10
7 Chrp 5 2 7
9 9 11
8 Ouvr 5 5 7
12 7 12
9 Isol 2,6 4 6
10 10 14
10 Toit 7 3 9
12 11 14
11 Lazu 7,8 2 12
14 12 14

12 Fin 9,10,11 0 14
14 14 14





Bảng 12.2 Thoi gian an toan và Thoi gian an toan tự do
Ngược lại nếu AcBt bất đầu ở 2,3,4 hay 5 thí ngày bắt đầu sớm nhất của MrBt va của cac
công việc tiep theop no sẽ bi thay đổi, du khong làm cho dự án sẻ trễ hơn so với dự định
12.5 Quan sat bang mat thuong
12.5.1 Gian do Gantt.
Phương pháp dau tien được ap dung cho lich trinh co và duoc ap dung tu năm 1910. Mỗi
công việc tượng trưng bởi một thanh co chiều dài tỉ lệ với thời gian hoàn thành công
việc .Bang cach di chuyển thanh nay trên một tấm bảng có rảnh, dầu trái của thanh sau sẽ
nối tiếp đầu phải của thanh tuong trung công việc trước, Với cách này chúng ta sẽ xác định
được ngày sớm nhất khi đi từ trái sang phải , Dung 1 thanh thu hai va di chuyen tu phai
sang trai, chúng ta cũng se xác định được ngày trể nhất .Hệ thống này đòi hỏi sự chú ý
,nhưng nó cho ta kết quả dung .Sự xuất hiện của máy vi tính và những thuật toán logic ,
phương pháp này bi bo roi nhung cach dung gian do truc quan Gantt vẫn còn được các nhà
thuc nghiem quan tâm . Gian đồ Gantt cua ví dụ có thể biểu diễn trong hình 12.2 Và người
ta có thể sử dụng sơ đồ Gantt trong việc sử dụng nguồn lực
Dates 0 1 2 3 4 5 6 7 8 9 10 11 12 13
AcMt
7
Fond
AcBt
MrPk
MrBt
Chrp

Ouvr
Isol
Toit
Lazu
Biểu đồ Gain
12.5.2 Cách trinh bay một dự án
Trong năm 1950 ,3 phương pháp xuất phát gan nhu đồng thời đựơc ap dung cho lich trinh
1. Phương pháp Pert (chương trình đánh giá và quan sát kỉ thuật) được sử dụng cho sự
án tên lửa Polaris (khoảng 10 000 công việc)
2. Phương pháp CPM (phương pháp đường thiet yeu) dựa vào tài liệu của công ty
Dufont
3. Phương pháp tiềm năng do Bernard Roy cho kế hoạch làm du thuyen ở Pháp
Cùng với một dự án , 3 phương pháp di nhien cho cùng kết quả. Sự khác nhau chinh giữa 1
ben la Pert - CPM va ben kia phuong phap tiem nang là ở sơ đồ biểu thị liên quan đến dự
án . Phương pháp tiềm năng chấp nhận sự biễu diển được ứng dụng từ khi bắt đầu chuong
nay, moi công việc duoc the hien qua 1 diem. Sự biểu diễn này là tu nhiên khi chung ta bat
dau tu ho so cua cac công việc trước.Thuật toán sử dụng trong may su dung cách biễu diễn
ngầm nay.
Trong phương pháp Pert - CPM , người ta dua vao lý luan của sơ đồ Gantt:
1. công việc A được biểu thị bởi cung (da,fa).Đỉnh dA chỉ lúc bắt đầu công việc A
,Đỉnh fA: kết thúc công việc A và chiều dài cung (da,fa) là thời gian thực hiện công
việc A
2. Nếu A phai duoc hoàn thành trước khi công việc B bắt đầu ,nó tạo ra một cung ảo
(fa,dB) là thời gian trống
Thieu hinh ve
Sơ đồ dau tien này có ít ưu điểm .Mục đích ke do là khi ta bỏ các cung ảo de có một so do
day đặc (Sơ đồ Pert nổi tiêng ngắn gọn súc tích hơn sơ đồ tiềm năng ). Đối với một dự án ,
có nhiều cách để biểu diển bang so do Pert cực tiểu .Chúng ta cũng chú ý la vie xay dung 1
8
sơ đồ Pert với số lượng cực tiểu các cung là một vấn đề NP hoàn toàn .Mot cach bieu dien

vi du theo sơ đồ Pert được minh họa trong hình 12.3
Thieu hinh ve
Truoc day co nhieu thảo luận để lựa chọn các biểu diển thích hợp. Nhung hien nay, do
khong phai là một vấn đề. Doi voi cac so do nho, hai cach nhin deu rat ro. Nhung khi du an
lon len thi viec quan sat bang sơ đồ chi được thấy rỏ khi có rất ít cac đường bắt chéo nhau
Hien nay, trong từ vựng, từ Pert và lich trinh dự án là tương đương nhau , Mot so nguoi de
nghi xem Pert là viết tắt của từ “Pour Éviter les retards traditionels” (để tránh viec trể)
12.6 Mở rộng
12.6.1 Tính den cac rang buộc ve thời gian
Chúng ta giả sử rằng , với 1 so công việc, chúng ta không thể bắt đầu trước ngày cực tiểu
Début Min (x) và/hay công việc phải hoàn thành trước ngày áp đặt Fin Max .
Ngày cực tiểu để bắt đầu công việc sẽ được thêm vào trong các ràng buộc theo ngày kết
thúc các công việc phía truoc x , ma chúng ta kí hiệu la DP
DP Max {Fin(y),y
∈
Pred(x)}
Début(x) ² Max (Début Min(x),DP)
Tương tự trên ,ngày kết thúc công việc sẽ được thêm vào trong các điều kiện áp đặt lên
thời gian bắt đầu của cac công việc tiep theo FS
FS Min (Début (z),cho z
∈
Succ(x))
Fin(x) Min (Fin Max(x),FS)
Điều này dẫn đến một thay đổi nhỏ trong thuật toán
Ngày bắt đầu sớm nhất
Début Tôt (l) Ngày bắt đầu dự án
Fin Tôt (1) Ngày bắt đầu dự án
Cho x chạy từ 2 đến n
DP Max (fin Tôt (y), cho y
∈

Pred(x))
Début Tôt (x) Max (Début Min (x), DP)
Fin Tôt (x) Début Tôt (x) +Duree(x)
Fin Pour
Data Fin Projet Début Tôt (n)
Ngày trể nhất
Débuttrể (n) = Data Fin Projet
Fintrể (n) = Data Fin Projet
Cho x=n-1 giảm xuống 1
FS =Min (Début trể(z),cho z
∈
Succ(x))
Fin trể(x)= Min (Fin Max (x) ,FS)
Début trể (x)= Fin trể (x) - Duree(x)
Fin pour
(duree: thoi gian thuc hien cong viec)
9
Sử dụng tác động trở lại của hai ràng buộc không giống nhau. Début Min(x) ảnh hưởng
trong cách tính ngày sớm nhất và có thể làm ngày kết thúc trể hơn so với ngàydự kiến
.Ngược lại , FinMax không ảnh hưởng trong cách xác định này .Điều đó có thể đưa den
nhung khoang thoi gian an toan co gia tri âm của 1 so cong viec (những cong viec đôi khi
cuc ky quan trong Hyperetiques) .Trong trường hợp này :
1. hoac chúng ta muốn giữ ngày kết thúc dự án như dự kiến, chúng ta phải giảm thời
gian hoàn thành các cong viec cuc quan trong nay (bang cach chấp nhận chi phi
tang) hoặc thay đổi ngày Fin Max
2. Hoặc cac du lieu da cho khong the thay doi, và ngày kết thúc dự án phải bị trể hơn
dự kiến .Gia su chúng ta có những cong viec cuc quan trong có thoi gian an toan am
-2, -3, -5 .Chúng ta phải làm trể dự án kết thúc đi 5 ngày để có được một phương án
có thể thực thi và tính toán lại ngày trể nhất với những giá trị mới .Chúng ta ghi
nhan rang chỉ những cong viec có thoi gian an toan lúc đầu là –5 bay gio moi tro

nen quan trong
12.6.2 Tính tien do:
Thông thường người ta không làm việc 7 ngày một tuần và 24/24 giờ 1 ngày .Do
đó , phải quy những ngày này ve những ngày làm việc thong thuong, hay la ngày nao , giờ
nao tùy theo muc do tinh te cua dự án .
Tình trạng đơn giản nhất là khi thời gian thuc hien củng là thời gian làm việc trong tuàn và
tất cả những nguoi lien quan deu có cùng 1 lịch làm việc. Điều đó co the thuc hien neu ta
đánh số lên những ngày làm việc va bo qua những ngày nghỉ (cuối tuần , phép năm).
Chúng ta thiet lap ngay mối quan hệ giữa thời gian thực hiện dự án và lịch. Sử dụng lại ví
dụ trên với giả thiết là thời gian bắt đầu dự án là thứ hai 27/4.Thứ sáu 1và 8 tháng năm là
ngày lễ và các ngày thứ bảy sau cũng vậy .Chúng ta có bảng tương ứng sau
Thieu hinh ve
Truong hop se phuc tap hon neu thời gian để làm dự án duoc tinh theo ngay và những ngày
theo lịch dua theo nhieu tham so rất khác nhau .Ví dụ, trong xây dựng , có một vài nhiệm
vụ phải thực hiện liên tục vì lí do kỷ thuật (ví dụ sự đỗ vỡ bê tông của một công trình)
hoặc vì ban chat cong viec (thời gian để khô), trong khi cac nhiệm vụ khác duoc thuc hien
theo cac ngày làm việc quy dinh. Trong nhung tình huống phuc tap nhat, thoi gian lam
viec duoc tinh theo gio cua ngay làm việc quy dinh. va cách tính ngày kết thúc công việc x
dựa trên ngày bắt đầu không còn đúng bang cach cong don thuan, ma qua một hàm trung
gian sẽ cho ngày kết thúc từ việc biết ngày bắt đầu công việc ,thời gian thực hiện dự án và
lịch làm việc.
Nguoc lai, cách tính ngày bắt đầu công việc khi biết ngày kết thúc công việc không còn
đúng theo cách trừ đơn giản nhưng theo một hàm trung gian.
Thi du
10
Một nhiệm vụ cần 40 giờ làm việc và nó phải được thực hiện trong 1 phong, phong nay
duoc su dung boi nhieu bo phan khac nhau.Thời gian làm việc cho 15 ngày toi la:
Thieu hinh ve
Nếu nhiệm vụ được bắt đầu vào sáng 4-5, ngày kết thúc se co duoc bang cach cong tat ca
cac thoi gian lam viec den khi thoi gian nay dat gia tri lon hon 40 h (o day la ngay 12-5).

Vì vậy ta phải đưa ra một hàm tính toán (trong thuật toán Fonction Fin) để có ngày kết
thúc theo lịch dua theo ngay bat dau theo lịch và thời gian thực hiện công việc, tong khi
tuân thu lịch trinh cong việc .Ngược lại ,khi biết ngày kết thúc, phải tính ngày bắt đầu theo
một hàm thứ 2 (Fonction Début) .Thuật toán cho ngày sớm nhất tính theo lịch như sau
Thieu cac ky hieu
12.7. Xác suất PERT:
Một trong những khó khăn của việc ứng dụng kĩ thuật lich trinh nằm ở kien thuc ve thời
gian thực hiện công việc, dự án, theo ban chat, ít khi duoc lặp lại. Vì vậy, nó phải được uoc
luong boi những người có kha nang, những người này thich đưa ra 1 sự ước lượng khoang
thời gian hon la xac dinh no 1 cach chắc chắn. Tuy nhiên, cac khoang thoi gian nay lai có
thể tuân theo 1 quy luật thống kê. Hai phương pháp chính thường được sử dụng:
1. Phương pháp đầu bao gồm sự xác định dang của quy luật xác suất với 1 loạt những
câu hỏi thuộc kiểu sau:
công việc này có thể hoàn thành nhanh nhất trong bao lâu? Câu trả lời là 5 ngày.
Xác suất hoàn thành trong 5 ngày là bao nhiêu? Là 1/10.
Xác suất hoàn thành trong 6 ngày hay ít hơn là bao nhiêu? Là 3/10.
Xác suất hoàn thành trong 7 ngày hay ít hơn là bao nhiêu? Là 3/4.
Xác suất hoàn thành trong 8 ngày hay ít hơn là bao nhiêu? Trong 8 ngày, tất cả se hoàn
thành.
Những câu trả lời này cho phép ta thiết lập quy luật về thời gian thuc hien như sau:
2. Những câu hỏi trên có thể gây nhàm chán. Phương pháp khác chi gồm cac cau hoi
- Thời gian tối thiểu a.
- Thời gian tối đa b.
- Thời gian trung bình n.
Trong ví dụ trên, câu trả lời có thể: 5 ngày, 8 ngày hay 7 ngày. Từ ba điều đã cho ở trên,
người ta xây dựng 1 hàm phân phối thống kê, mà người ta sử dụng theo sau đây. Hai hàm
phân phối thuong hay được sử dụng là quy luật Beta và quy luật tam giác.
(a) Quy luật Beta:
Thời gian
Xác suất kiểm nghiệm

Xác suất
5
10%
10%
6
30%
20%
7
75%
55%
8
100%
25%
11
Cách tiếp cận vấn đề njhư vậu đựơc đưa ra bởi Clark (1962). Cách tiếp cận cổ điển này
được trình bày trong rất nhiều sách và trong cac phan men chuyen gia. Hàm mật độ của
quy luật này được đưa ra với a ≤ x ≤ b như sau:
∫
=
++
−−
−−
=
1
0
1
)1(*)(
0()(
)(
t

dtttab
xbax
xf
γαγα
γα
Do thi bieu dien:
Tuân theo quy luật này, người ta có những tính chất sau day cua thời gian thuc hien
công việc:
- Trung bình Moy (d) = (a+b+4n)/4.
- Phương sai Var (d) = (b-a)
2
/36.
-
(b) quy luật tam giác. Hàm mật độ của quy luật này được cho như sau:
Nếu: a < x < n thì:
))((
)(2
)(
aban
ax
xf
−−
−
=
Nếu n < x < b thì:
))((
)(2
)(
abnb
b

xf
−−
=
Do thi bieu dien:
12
n
a
n
a
x
f
(
x
)
b
n
b
a x
f(
x)
b
n
b
x
f(
x)
b
n
b
x

f(x)
b
n
b
x
f(
x)
b
n
b
Hàm phân phối tam
giác
2/(b-a)
Người ta có:
- giá trị trung bình Moy (d) = (a+b+n)/3.
- giá trị phương sai Var (d) = [a(a-n) + b(b-a) + n(n-b)]/18.
Tim ra quy luật ap dung doi voi mỗi cong viec, se giúp co duoc giải pháp của vấn đề, hoac
theo cách phân tích hoặc mô phỏng.
12.7.1. Giải pháp phân tích:
Cách tiếp cận này được đưa ra bởi Clark (cùng với việc sử dụng quy luật Beta). Nó đươc
chia ra làm 3 giai đoạn:
Giai đoạn đầu: với mỗi nhiệm vụ của dự án, người ta sử dụng thời gian thuc hien trung
bình. Người ta tro lai vấn đề về lich trinh trong do cac yeu to da duoc xac dinh.
Giai đoạn hai: tính lich trinh tương ứng và xác định cac con đường quyết định. Gọi
FinProjet là ngày kết thúc dự án tìm được.
Giai đoạn ba: nếu điều kiện của dinh lý giới hạn trung tâm duoc ton trong thì thời gian hoàn
thành dự án tuân theo quy luật phân phối chuẩn:
+ Giá trị trung bình bằng FinProjet.
+ Phương sai bằng tổng phương sai của các nhiệm vụ trên con đường quyết định.
Để nắm được giới hạn của cách tiếp cận này, dieu quan trọng la nhac lai rang lý thuyết giới

hạn trung tâm chỉ ra sự hội tụ theo quy luật những đại lượng biến thiên độc lập X
i
, i = 1,…,
n, có giá trị trung bình M
i
và những giá tri phương sai V
i
tồn tại.
Người ta thường sử dụng chúng để chỉ rang tong cua n biến độc lập co khuynh huong tuan
theo quy luật phân phối chuẩn với giá trị trung bình ∑M
i
và phương sai ∑ V
i
khi n tăng, và
điều này bat chap các biến X
i
thuan theo những quy luật xác suất nao.
Trong trường hợp đã trình bày, X
i
là thời gian hoàn thành nhiệm vụ thứ i trong con đường
quyết định. Để áp dụng phương pháp này, cần phải xác minh 2 điểm cần thiết sau:
1. Quy luật chi phối thời gian hoàn thành của các công việc phải độc lập. Neu cung 1
nguyen nhan co the ảnh hưởng tới thời gian thuc hien dự kiến thi nó không được sử
dụng (Ví dụ: muc độ khả quan hay bi quan dựa trên nguon nhan luc mà người ta có
thể tuyen chon).
2. Lý thuyết này chi đúng nếu số lượng các công việc trong con đường quyết định là
rất lớn (ly thuyet la 30). Những nhà thực hành đưa ra so luong 15 công việc quyết
định, điều này chỉ có trong những dự án lớn.
Ví dụ: chúng ta không thể dùng lại ví dụ thong thuong vì nó không đáp ứng những tieu
chuan mà ta vua đưa ra. Giả sử con đường quyết định đe tính thời gian thuc hien trung bình

gom 15 công việc đuoc cho trong bảng 12.3.
Thời gian hoàn thành dự án theo quy luật phân phối chuẩn với giá trị trung bình 186,67 va
phương sai 39,67, độ lệch là 6,3. Điều này cho phép ta giải quyết được rất nhiều câu hỏi:
1. Dự án sẽ hoàn thành trong khoảng [186,67 – 2*6,30; 186,67 + 2*6,30], hay giữa
174 va 199 ngày với xác suất 95%.
2. Xác suất hoàn thành toi da trong 190 ngày là:
13
Prob (X≤190) = Prob (z ≤ (190 – 186,67)/6,30 = 0,53) = 70,19%.
Bảng 12.3 – Danh sách các công việc co tinh quyết định.
12.7.2. Giải pháp theo mô phỏng:
Người ta đưa ra một số lần rat lớn (500 tới 1000) thời gian hoàn thành toan bo công việc và
người ta tính cung số lần PERT xác định. Mỗi lần, người ta ghi nhan:
- Thời gian hoàn thành dự án.
- Số lần mà 1 nhiệm vụ co tinh quyết định (thông tin này cho phép tính xác suất ve su
quyet dinh của 1 nhiệm vụ, dieu nay tinh te hơn la trong giải pháp phân tích).
Nhiệm vụ a n b Moy(d) Var(d)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

15
8
10
12
9
15
14
6
9
10
8
12
14
8
9
15
10
13
15
11
16
17
8
11
12
10
15
14
9
11

15
13
15
17
13
16
19
9
13
13
11
18
14
12
14
16
10,17
12,83
14,83
11,00
15,83
16,83
7,83
11,00
11,83
9,83
15,00
14,00
9,33
11,17

15,17
4,17
4,17
4,17
2,67
0,17
4,17
1,50
2,67
1,50
1,50
6,00
0,00
2,67
4,17
0,17
Tổng 186,67 39,67
14
Những sự tính toán 1 PERT được cho bởi hàm về thời gian O(m) và được tính rất nhanh.
Vì vậy, giải pháp mô phỏng lúc này sẽ duoc chuong hơn giải pháp phân tích.
12.8 Lịch sản xuất với một tài nguyên tiêu thu:
Chúng ta đề cập truong hop nguồn tài nguyên đựơc tiêu thu rat quan trong, ví dụ là
tiền.Công việc x chỉ có thể bắt đầu được khi chúng ta có 1 lượng ax của nguồn tài nguyên
này .Tài nguyên này được cung cấp theo lich trinh định sẳn
1, 2, 3
µ µ µ
p
µ
với lần lượt
so lượng là

1, 2, 3 b b b bp
. Chac chan la điều kiện cần và đủ để dự án có thể thực hiện được
là tổng lượng tài nguyên cung cấp phải lớn hơn hoặc bằng tổng các nhu cầu :
1 1
p
n
i x
bi ax
= =
≥
∑ ∑
Điều đầu tiên là phải tinh ngày kết thúc nho nhat dự án dưới ràng buộc này của tài
nguyên hay nói cách khác là thời gian trể it nhất .Sau khi giải quyết được điều đó ,chúng ta
cần phải xác định các ngày bắt đầu và kết thúc của mỗi công việc và chắc chắn rằng ngày
kết thúc này phải được thực hiện. Phép tính thời gian trể it nhất được thực hiện bởi giải
thuật của J.Carlick , gọi là giải thuật “dịch chuyển”. Trước hết , ta tính lịch sản xuất mà
không quan tâm đến tài nguyên .Vì ngày bắt đầu thực tế các công việc phụ thuộc vào ngày
đến của tài nguyên ,ý tưởng tự nhiên là có thể bắt đầu cac công việc trể nhất, trong khi hy
vong rang các tài nguyên se đến trong thời gian nay.
Vi vay chung ta se so sanh tong nhu cau dua tren ngày bắt đầu trể nhat va tong cac lần
cung cấp tài nguyên lien tiếp. Dieu nay cho phep xac dinh cac cong viec co the khoi hanh
tre cho den ky han cung cap tai nguyen tiep theo.
Sử dụng lại ví dụ trước đây ,chúng ta giả sử rằng mỗi công việc cần 4 đơn vị tiền và
tiền được cấp 4 lần, mỗt lần 10 đơn vị, vào các ngày 0,4,8 và 12 .Bảng sau sap xep các
công việc theo ngày bắt đầu trể nhất theo thu tu tang dan, tiền cung cấp và nhu cầu tích lũy
và ở cột cuối là thời gian trể của mỗi công việc
x Code Date Versement BesoinS Retard(x)
0 10 0
1 Début 0 10 0
3 Fond 0 10 4 0

2 AcMt 1 10 8 0
5 MrPk 3 10 12 1
4 20 0
4 AcBt 5 20 16 0
6 Ouvr 7 20 20 0
8 MrBt 7 20 24 1
8 30 0
7 Chrp 9 30 28 0
9 Isol 10 30 32 2
10 Toit 11 30 36 1
12 40 0
11 Lazu 12 40 40 0
15
12 Fin 14 40 0
Ta vẽ được trên cùng một đồ thị các đường cong cung cấp tai nguyen và nhu cầu tích lũy
0
5
10
15
20
25
30
35
40
1 2 3 4 5 6 7 8 9 10 11 12
Hinh 12.4 Do thi su cung cap/nhu cau
So sánh các đường cong cung cấp và nhu cầu tích lũy cho thấy 4 điểm mà cầu vuợt quá
cung
1. Vào ngày 3 , không có đủ điều kiện để bắt đầu công việc MrKp .Công việc này
phải đợi đến lần cung cấp tài nguyên tiếp theo vào ngày 4 , đó là trể 1 ngày

2. Vào ngày 7 , công việc MrBt bị trể 1 ngày
3. Vào ngày 10 . công việc Isol đợi 2 ngày
4. Vào ngày 11, công việc Toit phải đợi 1 ngày
Thời gian trể nhất của dự án là giá trị lớn nhất của các lượng trể của từng công
việc .Để được một thời gian khả thi duy nhất là 12+2=14 ngày , J.Carlick đề nghị bắt đầu
của mỗi công việc x là vào ngày bắt đầu trể nhất (x)+2
Tìm lời giải khả thi cho bài toán co dang da thuc, nhưng không đủ trong thực tế .Lời
giải tìm được không cho ta khoang hoat dong an toan. Như trong ví dụ trên , ta thay rằng
công việc Fond có thể bắt đầu vào ngày 0 mà không có vấn đề gì .Tìm tập hợp tất cả các
lời giải khả thi là khó khăn .Trong trường hợp co cung ngày bat dau trể nhất, su trể của
công việc có thể phụ thuộc vào sự phân loại (thi du vao ngay 7, ta co the thay cong viec
MrBt bang cong viec Ouvr). Nhưng giải thuật sau cho phép tìm được một tập hợp con các
lời giải:

Giải thuật 1
Áp dụng thuật toan “Dịch chuyển”
Gán Dmin(x)=Dtart (x)+Retart (x)
Tính Pert không tài nguyên liên quan
Ta lưu ý rằng lượng trể cua mỗi công việc tác động đến cac công việc tiep theo no .Như
vậy lượng trể của công việc MrPk làm dời công việc Ouvr ,và lượng trể của công việc
MrBt trở nên bằng không .Một sự cải thiện là tính toán lại các lượng trể khi một công việc
nào đó bị dời.
16
Giải thuật 2
Áp dụng thuật toán dịch chuyển
Cho x chạy từ 1 đến n
Dat Dmin(x)=Dtart (x)+Retart (x)
Nếu Retart (x) >0 thì áp dụng thuật toán “Dịch chuyển”
Kết thúc vòng lặp
12.9 Van de cac tài nguyên không tieu thu được

12.9.1 Phương pháp tuần tự
Tất cả những van de NP hoàn toàn (xem phụ lục), ke ca khi tất cả các tài nguyên tồn tại
với số lượng bằng 1 (van de roi rac).Do đó không tồn tại giải thuật tìm ra lời giải tối ưu, du
van de nhu the nào, voi thời gian tính toán hợp lý. Trong thực tế người ta sử dụng phuong
phap phat hien. Để có lịch tài nguyên sản xuất, những giải thuật thường được sử dụng là
phương pháp tuần tự hay danh sách các ưu tiên. Nguyên tắc phương pháp tuần tự như sau :
1. Phân lớp các nhóm công việc theo bậc ưu tiên mà người ta ấn định (gọi là các
danh sách ưu tiên)
2. đầu tien, goi t=ngày bắt đầu dự án
3. Lặp lại
Xem xét các công việc theo mức ưu tiên của nó
Tồn tại công việc x, co the được thực hiện ở thời điểm t, nghĩa là:
• Chưa bắt đầu
• Tất cả những công việc tiên quyết của nó đã hoàn chỉnh
• No dã co cac tài nguyên cần thiết
Thuc hien
Cung cap tài nguyên cần thiết cho x
Lên lịch công việc x
Gán t= thời điểm tiếp theo khi do các tài nguyên duoc tu do
Cho đến khi các công việc đều được lên lịch
Ví Dụ
Lay lai thi du truoc, chúng ta co 3 công nhân đa năng và một máy chuyển hàng .Cần một
công nhân cho các công việc 2,7,8,9,10 và 11 và 2 công nhân cho các công việc khác .Máy
chuyển hàng phục vụ cho các công việc 3,5,6. Ghi nhan rang danh sách ưu tiên duoc cho
bởi ngày bắt đầu sớm nhất của lịch sản xuất không tài nguyên .Lịch sản xuất cuối cùng
được cho bởi sơ đồ Gant như sau :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
17
2
11

3 4 5
6
7
9
10
8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Các bậc ưu tiên có thể là
1. Tĩnh :Bậc ưu tiên được xác định và không đổi đến khi kết thúc tính toán
2. Động :Mỗi lần lên lịch sản xuất cho một công việc mới, ta tính đến ngày thực
hiện của nó và tính toán lại tiêu chuẩn ưu tiên đối với các công việc còn lại
Danh sách các ưu tiên có thể là bất kỳ.Tuy nhiên ,nếu công việc y là công việc
truoc của x tốt nhất y nên là ưu tiên trước x để giới hạn việc sửa lại danh sách .Trong
trường hợp này danh sách các ưu tiên cũng bao gồm1 sự phân loại hình học của đồ thị
trước đó ,điều này làm tăng tốc độ xác định các công việc có thể thực hiện được .Danh
sách ưu tiên thuong dung co được nho :
1. Sự xep loại tang dan nhưng ngày sớm nhất (Bắt đầu hay kết thúc) của
Pert không tài nguyên
2. Sự xep loại giam dan những ngày trể nhất (Bắt đầu hay kết thúc) của
Pert không tài nguyên
3. Sự xep loại theo khoang an toan tổng hợp tang dan
4. Sự xep loại theo thời gian thuc hien tang dan
5. Khi co chi phi do su tre, xep loai theo chi phi giam dan,….
Câu hỏi mà người ta muon co trả lời là biết được đâu là tiêu chuẩn tot nhat của sự ưu
tiên ,hoặc ít ra là trong kiểu dự án nào thi một tiêu chuẩn là tốt hơn các tiêu chuẩn khác .Ở
đây , ta không thể trả lời cả câu hỏi đầu tiên cũng nhu câu hỏi thứ hai .Đối với một dự án
cho trước , những kiêm tra thuc hien bằng cách làm thay đổi thời gian của mỗi công việc
chỉ ra ràng tiêu chuẩn có thể đem lại kêt quả toi uu cho van de này nhưng lại co the cho ket
qua xau nhat cho van de tiếp theo.Theo thống kê, sự xep loại theo độ an toan tổng cộng
(MinSlack) cho ta, theo ty le %, nhưng kết quả tốt nhất (nhưng có thể không tốt trong các

trường hợp khác)
Cũng vậy ,trong thực tế ,với tốc độ tính toán nhanh , người ta kiểm tra một cách có
hệ thống nhiều tiêu chuẩn và ta giữ lại nhưng kết quả tốt nhất .Dang khac, nen su dụng kết
quả tìm được bằng phương pháp tuần tự như điểm bắt đầu cho giai doan sau- tối ưu hoa
kieu 2. Điều này nhằm giảm nhẹ những nhược điểm của phương pháp tuần tự.
12.9.2 Ưu nhược điểm của phương pháp tuần tự
Phương pháp tuần tự thi đơn giản khi vận dụng và thời gian tính toán là rất ngắn
(0(n
2
) trong truong hop xau nhat).Về cơ bản đây là phương pháp tối ưu cục bộ: ta su dung
tài nguyên mỗi khi nó được giải phóng .Điều này làm cho việc sử dụng tài nguyên thường
là đúng ,nhưng mà sai lệch vẫn có thể xảy ra.Phương pháp tuần tự đuoc nghien cuu rat
nhieu, ta biết các nhược điểm cơ bản của nó :
18
3
5
6
1. Phương pháp tuần tự khong dua den tối ưu .Xem dự án gồm 6 công việc trong
hình sau
Thời gian thực hiện tuong ung là (4,3,2,4,3,5).Chúng ta chi có một tài nguyên san
sang cho su dung với lượng là 4 và nhu cầu sử dụng là 1 với A,B,D và 2 với C,E,F.
Danh sách ưu tiên có kết quả như sau
Cac do dai bieu dien thoi gian cong viec khong duoc ton trong trong hinh ve, yeu cau ve lai
hinh
1 2 3 4 5 6 7 8 9 10
Kết quả này không tối ưu . Ta chi can xem lời giải sau se thay:
1 2 3 4 5 6 7 8 9 10
Lưu ý rằng có thể loi ich khi 1 tài nguyên không sử dụng vào thời điểm t, để sử
dụng no cho một công việc khác vào thời điểm khác trong tương lai .Đó chính là
trường hợp tren. Nhưng phương pháp tuần tự không làm được điều này vì nó sử

dụng ngay khi tài nguyên được giai phong.
19
A
B
C
F
E
D
F
E
D
A
B
C
F
E
D
A
B
C
2.Nhược điểm thứ nhất của phương pháp này làm nản lòng các nhà toán học hơn
các người sử dụng, trong chung muc ma nhung nguoi nay tìm được một lời giải tốt
du chưa phải lời giải tối ưu .Ngược lại, neu nhin theo quan điểm: nếu ta rút gọn
thời gian của mỗi công việc ,ta sẽ rút ngắn được thời gian của dự án. vay ma dieu
nguoc lai lai xay ra.
Sử dụng lại ví dụ tren nhưng với thời gian thuc hien la 5 ngày cho cong viec B.
Thời gian cua dự án tuong ung là 9 ngày
yeu cau ve lai hinh
1 2 3 4 5 6 7 8 9 10
Nếu chúng ta rút ngắn thêm 2 ngày nữa đối với B,thời gian thực hiện sự án sẽ lên

đến 11 ngày
yeu cau ve lai hinh
1 2 3 4 5 6 7 8 9 10
3.Một điều đáng ngạc nhiên nữa là :khi tăng lượng tài nguyên lên thì cũng có thể
tăng thời gian của dự án. Xem ví dụ nho dưới đây với 3 công việc độc lập và giả
thiết phụ rằng A và B bắt đầu tại 0, C có thể bắt đầu tại 2 .Nếu tài nguyên có lượng
là 3 ,ta kết thúc vào 6 .Nếu ta tăng lên lượng 1 đơn vị ta kết thúc dự án vào 8
R=3 R=4
20
ED
B
A
C
F
E
D
A
B
C
C
A B
B
A
C
1 2 3 4 5 6 1 2 3 4 5 6 7 8
Ta lưu ý rằng cac vấn đề gặp phải ở đây luôn luôn có cùng một nguyên nhân :Đó
là việc tận dụng tài nguyên một cách nhanh nhất có thể Va hau-toi uu kieu 2-opt se
co duoc nho quy tac nay.
12.10 Sự giảm/ Giản do Pert chi phí
Cho dến gio chúng ta chưa tinh den sự phụ thuộc qua lại có thể có giữa thời gian

thực hiện mỗi công việc và chi phí của nó. Đối với một vài dự án , có thể rút ngắn thời
gian dự án bằng cách cung cap cho nó vài phương tien phụ .Sự rút ngắn nay chỉ có thể
thực hiện trong một giới hạn nào đó .Một cách tổng quát ,s ẽ khó khăn và tốn kém hơn khi
giam được ngày thứ hai so với ngày thứ nhất , ngày thứ ba so với ngày thứ hai….Điều này
cho thấy mối quan hệ nghịch biến lồi giữa chi phí va thời gian thực hiện như hình vẽ
Bsup Binf
Có thể giải bài toán này theo cách tối ưu. Chúng ta sẽ giới thiệu phương pháp này
bằng một ví dụ nhỏ mà chúng ta giải quyết từng bước một .Dự án gồm 5 công việc.Ta biết
so ngày duoc dự đoán thong thuong để thực hiện một công việc (duree normale) va thoi
gian thực hiện nhỏ nhất có thể (duree acceleree).Ta giả sử ở đây chi phí tỉ lệ với số ngày
thực hiện
Tâche Précédence Dureé
acelérée
Dureé
Normale
Cou^t /jour
21
Cou^t
Duree’
A
B
C
D
E
A
A
B,C
5
7
1

7
4
7
9
4
8
5
9
10
6
2
8
Chúng ta sẽ biểu diễn các công việc dưới dạng các cung. Bắt đầu dự án với thời
gian thực hiện dự án thong thuong. Dieu nay dan den thoi gian ket thuc la 16 ngay.
D8
A7 C4 E5
B9
Giam 1 ngay cho cac cong viec khong quan trong khong lam giam thoi gian cua du an. Do
đó chỉ cần quan tâm đến các công việc quyet dinh được biễu diễn bằng các cung đậm
nét .Con đường trọng yếu (A,C,E) là duy nhất và chúng ta sẽ rút gắn 1 ngày tren C, C co
chi phí nhỏ nhất la 6 .Va chúng ta có dự án như sau :
Bây giờ ta có hai con đường trọng yếu (A,D) và (A,C,E) .D là công việc có chi phí nhỏ
nhất .Nếu chúng ta xét rút ngắn duy nhất D ,con đường (A,C,E) vẫn luôn luôn có thời gian
là 14 ngày và do đó chúng ta không rut ngắn được thời gian của dự án .Để rút ngắn một
ngày ,cần phải rút ngắn tập hợp các cung trọng yếu sao cho đồ thị nó có ngày bắt đầu và
ngày kết thúc .Những rút ngắn có thể là
A với chi phí 9
C và D với chi phí là 6+2=8
D và E với chi phí là 8+2=10
chúng ta rút gọn D và E vì chi phí nhỏ nhất . Dự án có thời gian là 14 ngày với chi phí là

6+8=14 . Bay gio chúng ta có
Vui long to cac duong dam, vi co y nghia
D8
A7 C3 E5
B9
22
Bây giờ chúng ta có các cung không thể rút gọn hơn được nữa .Một lý luan tương tự nhu
trước cho ta những rút gọn có thể
A+B=9+10=19
A+C+E=9+8+6=23
Với rút gọn nhỏ nhất có giá trị là 19
Tuy nhiên lời giải này không tốt nhất .Rút gọn A+E là đủ để rút ngắn tất cả các con đường
trọng yếu với chi phí là 17 .Điều này tuy nhiên chưa phải là tối ưu .Xem xét ý kiến sau :
Rút ngắn A và E 1 ngày và tăng C (Nó đã được rút gọn trước đây) 1 ngày.Chi phí tổng
cộng là :9-6+8=11 .Đây chính là điểm khéo léo của phương pháp .Dự án bây giờ có thời
gian la 13 ngày với chi phí là 25
D7
A7 C2 E5
B9
D và E đã đạt được thời gian nhỏ nhất .Sự rút gọn có thể duy nhất là A và B với chi phí là
19 .Dự án bây giờ có thời gian là 12 ngày với chi phí là 44
D7
A6 C2 E4
B9
Con đường này gồm toàn các cung có thời gian nhỏ nhất, ta không thể rút ngắn thời gian
dự án được thêm nữa .
Như vậy chúng ta đã có thể nhan định qua ví dụ này, lời giải của so do PERT chi phí nằm
ở việc tìm hiểu các rút gọn nhỏ nhất trong một đồ thị G nào đó (dinh ly Ford va
Fulkerson). Phương pháp duoc su dung thường xuyên nhất trong các sach là phương pháp
xem xét đồ thị bao gồm tập hợp các tác vụ trọng yếu va tìm cach rút ngắn các cung trọng

yếu nay.Với phương pháp này ,để đi từ 14 đến 13 ngày ,ta rút ngắn A+C+E với chi phí là
19 .Đây không phải là một phương pháp tối ưu trong tất cả các trường hợp nhưng có thể su
dung. Ưu điểm của nó lớn nhất là chi sử dụng cac giải thuật cổ điển của Pert và giải thuật
cho luu luong nhieu.
Lời giải tối ưu có thể đạt được bởi một thay đổi nhỏ trong giải thuật cổ điển của Ford va
Fulkerson.
23
Nếu chúng ta vẽ hàm chi phí _thời gian của dự án ,chúng ta nhan xet rang trong ví dụ này
hàm đạt được là nghịch biến lồi .Tính chất này là đúng trong trường hợp tổng quát khi
những hàm chi phí _thời gian của mỗi công việc là nghịch biến lồi
Rút ngắn thời gian tổng cộng của dự án lam tang các chi phí của các công việc
.Mặt khác, nó cũng cho phép rút ngắn vài chi phí cố định ,các chi phí tổng quát ,các chi phí
gián tiếp.Giả sử rằng các chi phí hằng ngày là cố định và bằng 10 mỗi ngày .Chi phí toàn
bộ là
D7
A5 C3 E4
B8
Durée 12 13 14 15 16
Cou^t Fixe
Sur Cou^t
120
44
130
25
140
14
150
6
160
0

Total 164 155 154 156 160
Và dự án có chi phí nhỏ nhất có thời gian là 14 ngày
12.11 Khai thac kết quả
12.11.1 Phân tích con đường trọng yếu
Đối với những công việc trọng yếu , ta không co 1 tu do nào liên quan đến chúng vì
chúng phải bắt đầu và kết thúc vào những ngày cố định.Ta có thể rút ngắn ky han bằng
cách tăng số lượng cac phương tien dau vao cua chung hoặc điều chỉnh kỹ thuật dự tru.
Chac chan rằng chi phí của dự án có hạn ,và độ tu do của các công việc khác giảm xuống,
có thể một hay nhieu con đừong trọng yếu mới xuất hiện
Đối với những công việc không trọng yếu, ta sử dụng thời gian tu do cho phep của
chung ta để cải thiện khả năng sinh lợi của dự án, để giảm chi phí vì ta có thể lựa chọn
ngày thực hiện phù hợp để sử dụng re nhat va tốt nhất tài nguyên của tổ chức.
12.11.2 Kiểm tra
Sau khi khoi dong dự án ,cần phải thành lập bộ phận kiểm tra để kiểm định những
quyết định có được thực hiện hay không .Những thông tin về sự trể hay những khó khăn
ma dự án không dự đoán trựớc cần phải duoc thu thập bởi nhóm Pert để từ đó xây dựng
những quyết định mới . Vào những ngày dự đinh, những nguoi truc tiep se co thông báo
với nhóm Pert ve su tiến triển của dự án. Cac thông tin gom:
• Những ngày bắt đầu hay kết thúc thuc su của các công việc dang thực hiện
hay da hoàn thành trong thoi kỳ trước khi kiểm tra .
• Những ngày dự đoán của các công việc dang thực hiện ngay ngày kiểm tra
• Những quan sát liên quan đối với những sai lệch của dự án so voi dự đoán
24
Nhóm Pert sẽ lập trước danh sách các công việc của dự án, bằng cach xep loai chung theo
nhieu cách khác nhau :
• Theo bậc tang dan của ngày bắt đầu sớm nhất
• Theo bậc tang dan của ngày bắt đầu trễ nhất (neu có thể)
• Theo bậc tang dan của ngày kết thúc sớm nhất (neu có thể)
• Theo bậc tang dan của ngày bắt đầu trể nhất
• Theo muc tu do cho phep tổng cộng tang dan

Bằng cách đánh dấu những ngày bắt đầu thuc su trong danh sách các công việc đã
được phân lớp bởi ngày bắt đầu sớm nhất hay trể nhất, ta kiểm tra sự bắt đầu của các công
việc, cung như sự hoàn thành của nó. Danh sách các công việc được phân lớp theo ngày trể
nhất cho phép phat hiện ngay lập tức những công việc trở thành trọng yếu sau khi bi trể.
So sánh giữa dự đoán với thực tế ,thiết lập từ các công việc đã đựoc phân lớp bởi
muc tu do cho phep tổng cộng, giup xem xet su tiến triển tổng thể của dự án. Các công
việc trọng yếu hay kha trọng yếu duoc xep ở cac hàng trên. Do đó chúng ta phát hiện dễ
dàng những thay đổi bổ sung cho con đường trọng yếu. Dang khac, Hơn nữa những sai
lệch giữa tập hợp các muc tu do cho phep tính toán và muc tu do cho phep thực tế cho
phép đánh giá trạng thái tiến triển của dự án, tức là biết được du an sớm hay trể hơn so với
dự đoán.
Với các thông tin thu thập được, nhóm Pert xác định sai lệch giữa dự đoán vào thực
te và rút ra hệ quả cho tien trinh của dự án Nếu những sai lệch không lam cho các công
việc liên quan tro nen trong yếu thì không can dieu chinh gì dự án .Ngược lại , neu những
sai lệch có liên quan đến các công việc trọng yếu là rất quan trọng, để không xáo trộn lịch
sản xuất dự định cần phải tìm hiểu phương thức để làm dieu chinh.
Trước hết ta tìm hiểu nguyên nhân đi đến những sai lệch đó .Nếu các công việc co liên
quan chưa duoc hoàn thành hay nếu các công việc khac tương tự phải hoàn thành sau đó,
thi viec phân tích các nguyên nhân la cơ bản .Chỉ có phân tích moi có the giup dua ra
quyết định nham ngăn cản cac sai lệch tăng lên hoac lai xay ra, voi giả thiết rằng những
người chịu trách nhiệm của các công việc liên quan duoc tham vấn ve các nguyên nhân và
các phương thức để giảm thiểu ảnh hưởng của vấn đề.
Thứ hai phải tìm cách giam sự trể này. Điều này la vấn đề kinh tế: chi phí tang
them do phai huy động cac phuong tien them để bù đắp sự trể này có được nhà máy chấp
nhận khong, hay chính xác hơn là chi phí này lớn hơn hay nhỏ hơn sự tổn thất mà nhà máy
phải gánh chịu từ sự trễ. Khi những quyết định đạt được, nhóm Pert se hoan chinh lai dự
án với những du bao cho những phần dự án chưa thực hiện được.
Lịch trinh sản xuất mới cũng được thực hiện và phân phối tới tất cả các người phụ
trách của các công việc da có sự điều chỉnh.
12.12 Sơ đồ không kín

Xem một sơ đồ được hình thành từ các đỉnh và duoc noi voi nhau bang các đường
có hướng .Một vòng kín là đường đi xuất pháp từ đỉnh A ,cho phép quay trở lại đỉnh A
25