Chương 12: Lịch trình dự án

Chia sẻ: Hoang Trong Tuan | Ngày: | Loại File: DOC | Số trang:31

Thêm vào BST

Báo xấu

270
lượt xem 74
download

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

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 ....

Chủ đề:

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

Lưu

Nội dung Text: Chương 12: Lịch trình dự án

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 1
thúc ) 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 3
du 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 : B A C Đố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 2 AcMt 2 Chrp MrPk 2 Fond 3 Isol AcMt , MrBt 4 Lazu Chrp ,Ouvr 2 MrBt AcBt ,Fond 3 MrPk AcMt ,Fond 4 Ouvr MrPk 5 Toit Chrp 3 4
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 8
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 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 9
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) 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. 10
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 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: Thời gian 5 6 7 8 Xác suất kiểm 10% 30% 75% 100% nghiệm 10% 20% 55% 25% Xác suất 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. 11
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: 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: ( x − a ) α (b − x0 γ f ( x) = 1 (b − a ) α +γ +1 * ∫ t α (1 − t ) γ dt t =0 Do thi bieu dien: nn x a a f 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( x − a ) f ( x) = (n − a )(b − a) Nếu n < x < b thì: 2(b) f ( x) = (b − n)(b − a ) Do thi bieu dien: x f(x) Hàm phân phối tam 2/(b-a) giác a x x x 12 f( f( f(
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 Xi, i = 1,…, n, có giá trị trung bình Mi và những giá tri phương sai Vi 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 ∑Mi và phương sai ∑ Vi khi n tăng, và điều này bat chap các biến Xi thuan theo những quy luật xác suất nao. Trong trường hợp đã trình bày, Xi 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. 13
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à: Prob (X≤190) = Prob (z ≤ (190 – 186,67)/6,30 = 0,53) = 70,19%. Nhiệm vụ a n b Moy(d) Var(d) 1 8 10 13 10,17 4,17 2 10 13 15 12,83 4,17 3 12 15 17 14,83 4,17 4 9 11 13 11,00 2,67 5 15 16 16 15,83 0,17 6 14 17 19 16,83 4,17 7 6 8 9 7,83 1,50 8 9 11 13 11,00 2,67 9 10 12 13 11,83 1,50 10 8 10 11 9,83 1,50 11 12 15 18 15,00 6,00 12 14 14 14 14,00 0,00 13 8 9 12 9,33 2,67 14 9 11 14 11,17 4,17 15 15 15 16 15,17 0,17 Tổng 186,67 39,67 Bảng 12.3 – Danh sách các công việc co tinh quyết định. 14
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). 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à b1, b 2, b3...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 : p n ∑ bi ≥ ∑ ax i =1 x =1 Đ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 15
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 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 40 35 30 25 20 15 10 5 0 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: 16
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. 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 17
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 : 2 6 10 8 11 3 4 5 7 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 3 5 6 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 độ 18
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(n2) 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ó : 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 A F B E C D 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 C D E B A F 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: 19
C D E B F A 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. 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 D C E A B 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 C D E B A F 1 2 3 4 5 6 7 8 9 10 20