Tối ưu hóa sơ đồ mạng theo chỉ tiêu thời gian và chi phí sử dụng thuật toán di truyền

Hoàng Thị Cành và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 122(08): 47 - 52<br /> <br /> TỐI ƯU HÓA SƠ ĐỒ MẠNG THEO CHỈ TIÊU<br /> THỜI GIAN VÀ CHI PHÍ SỬ DỤNG THUẬT TOÁN DI TRUYỀN<br /> Hoàng Thị Cành*, Nguyễn Hồng Tân, Phùng Thế Huân<br /> Trường Đại học Công nghệ Thông tin và Truyền thông – ĐH Thái Nguyên<br /> <br /> TÓM TẮT<br /> Tối ưu hoá theo chỉ tiêu thời gian và chi phí trên sơ đồ mạng là một trong những giải pháp tương<br /> đối hữu hiệu nhằm rút ngắn thời gian thực hiện từng danh mục công việc hay toàn bộ dự án với<br /> tổng chi phí thấp nhất. Đây là phương pháp có ý nghĩa và cần thiết nhằm mang lại hiệu quả kinh tế<br /> cao trong việc tổ chức, lên kế hoạch và thực hiện dự án trong nền kinh tế thị trường luôn có sự<br /> cạnh tranh về giá thành. Bài báo này trình bày phương pháp tối ưu hóa theo chỉ tiêu thời gian, chi<br /> phí trên sơ đồ mạng sử dụng thuật toán di truyền kết hợp với phương pháp chi phí phạt để tìm ra<br /> phương án tối ưu.<br /> Từ khóa: Tối ưu hóa sơ đồ mạng, tối ưu thời gian, tối ưu chi phí, thuật toán di truyền, hàm phạt<br /> <br /> GIỚI THIỆU*<br /> Phương pháp tối ưu hóa, lý thuyết đồ thị là<br /> một lĩnh vực nghiên cứu rộng lớn, có nhiều<br /> ứng dụng và đang được quan tâm nghiên cứu<br /> nhiều trên thế giới. Các bài toán tối ưu về thời<br /> gian, chi phí dựa trên cơ sở lý thuyết đồ thịvà<br /> các chương trình phần mềm hỗ trợ việc quản<br /> lý dự án liên quan đến lập kế hoạch, điều<br /> chỉnh và tối ưu hoá tiến độ thực hiện kế hoạch<br /> đã có [1,3,5]. Tiêu biểu là phần mềm<br /> Microsoft Project, nhưng phần mềm chỉ giải<br /> quyết được vấn đề tối ưu hoá trên từng lĩnh<br /> vực [1,7]. Trong khi đó, bài toán tối ưu hoá<br /> theo chỉ tiêu thời gian và chi phí trên sơ đồ<br /> mạng đang là vấn đề đáng quan tâm trong nền<br /> kinh tế thị trường có tính cạnh tranh khốc liệt<br /> về giá thành [1]. Với chương trình WinQSB<br /> đã bước đầu giải quyết được bài toán tối ưu<br /> hoá theo chỉ tiêu thời gian - chi phí, tuy nhiên<br /> còn tiềm ẩn nhiều mặt hạn chế, như: quá trình<br /> tối ưu hóa làm xuất hiện nhiều đường găng<br /> mới đây là vấn đề bất cập trong công tác tổ<br /> chức thực hiện dự án [4,7].<br /> Chỉ tiêu về mặt thời gian và chi phí thực hiện<br /> dự án là một vấn đề rất quan trọng. Hoàn<br /> thành dự án đúng thời hạn với chi phí nhỏ<br /> nhất sẽ mang lại những kết quả to lớn về kinh<br /> tế và chính trị. Đây là một vấn đề quan trọng<br /> *<br /> <br /> Tel: 01682 324556, Email: htcanh@ictu.edu.vn<br /> <br /> mà người làm công tác tổ chức, quản lý các<br /> dự án cùng nhiều nhà khoa học quan tâm. Vì<br /> vậy bài báo này đề xuất một giải pháp sử<br /> dụng thuật toán di truyền và phương pháp chi<br /> phí phạt để tìm ra phương án tối ưu khả thi.<br /> PHƯƠNG PHÁP SƠ ĐỒ MẠNG<br /> Sơ đồ mạng (SĐM) là một đồ thị bao gồm<br /> toàn bộ khối lượng của cả dự án, nó ấn định<br /> một cách logic trình tự kỹ thuật và mối quan<br /> hệ về tổ chức giữa các công việc, ấn định thời<br /> gian thực hiện các công việc và tối ưu hóa kế<br /> hoạch đề ra [2].<br /> Các thông số chính trên SĐM[2,4]:<br /> <br /> EO (Earliest Occurrence of an Event): là thời<br /> điểm sớm nhất để cho sự kiện xảy ra khi tất cả<br /> các công việc trước sự kiện đều hoàn thành.<br /> LO (Lastest Occurrence of an Event): là thời<br /> điểm muộn nhất để cho sự kiện xảy ra mà<br /> không làm ảnh hưởng đến sự hoàn thành của<br /> dự án trong thời gian đã định.<br /> ES (Earliest Start of an activity): là thời điểm<br /> sớm nhất để cho công việc bắt đầu.<br /> ES của công việc ij = EO của sự kiện i<br /> LS (Lastest Start of an activity): là thời điểm<br /> muộn nhất để cho công việc bắt đầu mà<br /> 47<br /> <br /> Hoàng Thị Cành và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 122(08): 47 - 52<br /> <br /> không làm ảnh hưởng đến sự hoàn thành của<br /> dự án trong thời gian đã định.<br /> <br /> MÔ HÌNH BÀI TOÁN TỐI ƯU HÓA THEO<br /> CHỈ TIÊU THỜI GIAN - CHI PHÍ<br /> <br /> Cách xác định các thông số trên SĐM [2,7]:<br /> <br /> Trong thực tế, nhiều dự án muốn đẩy nhanh<br /> thời gian thực hiện, để làm được điều này ta<br /> phải tìm cách rút ngắn thời gian đường găng,<br /> mà các biện pháp rút ngắn thời gian đường<br /> găng thường làm cho chi phí của dự án tăng<br /> lên. Bài toán được đặt ra là: tìm phương án rút<br /> ngắn thời gian thực hiện các công việc với chi<br /> phí tăng lên là nhỏ nhất.<br /> <br /> Xác định EO và ES:<br /> EO của sự kiện đầu tiên: EO1 = 0<br /> Tại các sự kiện j chỉ có một công việc đến:<br /> <br /> EO j  EOi  tij<br /> <br /> Tại các sự kiện j có nhiều công việc đến:<br /> <br /> EO j  Max EOi  tij<br /> i<br /> <br /> Với các công việc giả thì cũng tính như trên<br /> nhưng tij=0<br /> Xác định LO và LS:<br /> Tại sự kiện cuối cùng ta có:<br /> EOCuôi  LOCuôi<br /> LSij  LO j  tij<br /> Nếu chỉ có một công việc ij xuất phát từ sự<br /> kiện i ta có: LOi  LSij<br /> Nếu có nhiều công việc xuất phát từ sự kiện i<br /> <br />  <br /> <br /> <br /> <br /> ta có: LOi  Min LSij  Min LOj  tij<br /> i<br /> <br /> i<br /> <br /> <br /> <br /> Phân tích kết quả trên sơ đồ mạng: Thời gian<br /> tối thiểu để hoàn thành dự án chính bằng<br /> EOcuối.Thời gian dự trữ của các công việc<br /> (Float): F là khoảng thời gian tối đa mà một<br /> công việc có thể chậm chễ so với kế hoạch đã<br /> định mà không làm ảnh hưởng tới thời gian<br /> tối thiểu để hoàn thành dự án.<br /> F  LSij  ESij hay F  LSij  EOi<br /> Công việc găng là công việc có F=0. Đường<br /> găng: là đường nối liền từ sự kiện đầu tiên<br /> đến sự kiện cuối cùng với điều kiện tất cả các<br /> công việc nằm trên đó là các công việc găng<br /> [2,8].<br /> Nhận xét: Mỗi SĐM có ít nhất một đường<br /> găng. Tổng thời gian của các công việc nằm<br /> trên đường găng chính là thời gian tối thiểu để<br /> hoàn thành dự án. Nếu 1 công việc trên đường<br /> găng bị trễ thì toàn bộ công việc sẽ bị trễ theo.<br /> Do vậy muốn rút ngắn thời gian hoàn thành<br /> dự án thì nhà quản lý phải tập trung các giải<br /> pháp làm giảm thời gian các công việc trên<br /> đường găng.<br /> 48<br /> <br /> Thiết lập các mối liên hệ cho bài toán:<br /> Để ước lượng tij ta dùng các loại thời gian sau:<br /> a là thời gian để hoàn thành công việc trong<br /> điều kiện tốt nhất; b là thời gian để hoàn thành<br /> công việc trong điều kiện xấu nhất; m là thời<br /> gian để hoàn thành công việc trong điều kiện<br /> bình thường. a  m  b .<br /> Ta có: Kỳ vọng thời gian:<br /> <br /> a  4m  b<br /> Nếu không xác định được m:<br /> 6<br /> 2a  3b<br /> te <br />  tij  te<br /> 6<br /> te <br /> <br /> Phương sai của thời gian thực hiện công<br /> <br /> ba<br /> việctij:   <br /> <br />  6 <br /> <br /> 2<br /> <br /> 2<br /> ij<br /> <br /> Theo lý thuyết xác suất thống kê, phương sai<br /> của toàn bộ dự án:  2   ij2<br /> <br /> <br /> <br /> THUẬT TOÁN DI TRUYỀN<br /> Thuật toán di truyền (TTDT) thực hiện tìm<br /> kiếm lời giải tối ưu dựa trên cơ chế chọn lọc<br /> và di truyền tự nhiên. Quần thể trải qua quá<br /> trình tiến hóa: ở mỗi thế hệ lại tái sinh các lời<br /> giải tương đối tốt, trong khi các lời giải tương<br /> đối xấu bị mất dần đi. Để phân biệt các lời<br /> giải thích nghi khác nhau, hàm mục tiêu được<br /> dùng để đóng vai trò thích nghi môi trường.<br /> Một cá thể trong giải thuật di truyền biểu diễn<br /> một giải pháp của bài toán. Quần thể là một<br /> tập hợp các cá thể có cùng một số đặc điểm<br /> nào đó. Trong TTDT quần thể là một tập các<br /> lời giải của một bài toán.<br /> Các toán tử di truyền trong TTDT bao<br /> gồm[8]:<br /> <br /> Hoàng Thị Cành và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Lai ghép là sự kết hợp các tính trạng của bố<br /> mẹ để sinh ra các thế hệ con. Đây được coi là<br /> một sự tổ hợp lại các tính chất (thành phần)<br /> trong hai lời giải cha mẹ nào đó để sinh ra<br /> một lời giải mới mà có đặc tính mong muốn là<br /> tốt hơn thế hệ cha mẹ.<br /> <br /> 122(08): 47 - 52<br /> <br /> trong đó phương pháp hàm phạt (Penalty<br /> Function) là phương pháp được sử dụng phổ<br /> biến do có khả năng tùy biến và thích hợp với<br /> nhiều thuật toán tìm kiếm [6].<br /> <br /> Chọn lọc là quá trình chọn lọc các cá thể<br /> trong quần thể. Đây chính là cách chọn các cá<br /> thể có độ thích nghi tốt để đưa vào thế hệ tiếp<br /> theo hoặc để lai ghép, với mục đích là sinh ra<br /> các cá thể mới tốt hơn.<br /> Đột biến là một sự biến đổi tại một (hay một<br /> số) gen của nhiễm sắc thể ban đầu để tạo ra<br /> một nhiễm sắc thể mới. Đột biến có thể tạo ra<br /> một cá thể mới tốt hơn hoặc xấu hơn cá thể<br /> ban đầu. Tuy nhiên, trong TTDT thì ta luôn<br /> muốn tạo ra những phép đột biến cho phép cải<br /> thiện lời giải qua từng thế hệ.<br /> Các tham số trong TTDT bao gồm [8]:<br /> Xác suất lai ghép: Nếu xác suất lai ghép là<br /> Pc, khi đó khả năng để một cá thể được lai<br /> ghép là Pc.<br /> Xác suất đột biến: Nếu xác suất đột biến là<br /> Pm, khi đó khả năng để mỗi gen của một<br /> nhiễm sắc thể bất kỳ bị đột biến là Pm. Tác<br /> dụng của toán tử đột biến là ngăn ngừa giải<br /> thuật di truyền rơi vào tình trạng cực trị địa<br /> phương, tuy nhiên nếu thực hiện đột biến với<br /> xác suất quá cao sẽ biến giải thuật di truyền<br /> thành giải thuật tìmkiếm ngẫu nhiên.<br /> Kích thước quần thể cho biết có bao nhiêu cá<br /> thể trong một quần thể. Nếu có quá ít cá thể<br /> thì sẽ làm giảm không gian tìm kiếm của thuật<br /> giải và dễ rơi vào các cục bộ địa phương, như<br /> vậy sẽ dễ xảy ra trường hợp bỏ qua những lời<br /> giải tốt.<br /> HÀM PHẠT<br /> TTDT là phương pháp thích hợp với các bài<br /> toán tối ưu với điều kiện không ràng buộc.<br /> Tuy nhiên thực tế việc giải các bài toán tối ưu<br /> thường chứa một hay nhiều ràng buộc, việc áp<br /> dụng TTDT vào các bài toán tối ưu có ràng<br /> buộc thường dẫn đến tối ưu cục bộ. Nhiều<br /> phương pháp đã được đề xuất để giải quyết<br /> <br /> Hình 1. Mô hình thuật toán di truyền<br /> <br /> Hàm phạt là phương pháp biến đổi từ bài toán<br /> có ràng buộc thành bài toán không ràng buộc<br /> thông qua việc biến đổi hàm mục tiêu như sau:<br /> <br /> f ( x)<br /> xF<br /> <br /> f p ( x)  <br />  f ( x)  p( x) x  F<br /> Trong đó: F: miền khả thi; fp(x): hàm phạt;<br /> f(x): hàm mục tiêu; p(x): giá trị phạt.<br /> Trong công thức trên, nếu không có vi phạm<br /> điều kiện xảy ra, p(x)=0 và fp(x)= f(x). Ngược<br /> lại, nếu có vi phạm điều kiện xảy ra, p(x)>0.<br /> Khi p(x) càng lớn dẫn đến fp(x) cũng có giá trị<br /> lớn theo tương ứng, khi đó fp(x)có khoảng cách<br /> rất xa so với f(x) dẫn đến dễ dàng loại bỏ.<br /> LẬP TRÌNH TÍNH TOÁN<br /> Hàm mục tiêu được đề xuất:<br /> <br /> Min (C  C t  C p )<br /> 49<br /> <br /> Hoàng Thị Cành và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 122(08): 47 - 52<br /> <br /> Trong đó Ct là chi phí thực được xác định theo<br /> công thức: Ct <br /> <br /> N<br /> <br />  Cij<br /> <br /> ; Cp là Chi phí phạt<br /> <br /> i , j 1<br /> <br /> được xác định theo công thức:<br /> C p  CPRNDV <br /> <br /> CPRN  CPC<br /> CPGT<br /> <br /> TGRN  TGC TGCGTĐ<br /> <br /> (cụ thể: CPRNDV: Chi phí rút ngắn đơn vị;<br /> CPRN: Chi phí rút ngắn; CPC: Chi phí chuẩn;<br /> CPGT: Chi phí gia tăng; TGRN: Thời gian rút<br /> ngắn; TGC: Thời gian chuẩn; TGCGTĐ: Thời<br /> gian cắt giảm tối đa).<br /> Các bước rút ngắn thời gian hoàn thành dự<br /> án sử dụng thuật toán di truyềnnhư sau:<br /> Bước 1: Khởi tạo bài toán. Lập sơ đồ mạng.<br /> Xác định đường găng chuẩn và các công<br /> việc găng. Tạo quần thể tổ hợp các đường<br /> găng ban đầu.<br /> Bước 2: Tính toán chi phí ứng với mỗi tổ hợp.<br /> Tính chi phí thực, chi phí phạt, tổng chi phí.<br /> Bước 3: Đánh giá độ thích nghi – kiểm tra<br /> điều kiện dừng: Lựa chọn các công việc trên<br /> đường găng mà có chi phí rút ngắn đơn vị nhỏ<br /> nhất và cắt giảm thời gian thực hiện công việc<br /> này theo yêu cầu và trong phạm vi tối đa cho<br /> phép. Sắp xếp các tổ hợp theo chi phí, nếu<br /> thỏa mãn điều kiện dừng: Dừng chương trình,<br /> xuất kết quả; nếu không thỏa điều kiện dừng<br /> thực hiện tiếp bước 4.<br /> Bước 4: Tạo quần thể tổ hợp mới bằng TTDT.<br /> Thực hiện cơ chế chọn lọc, lai ghép, đột biến.<br /> Tạo ra quần thể tổ hợp Pt+1 từ quần thể tổ<br /> hợp Pt. Kiểm tra lại đường găng: Nếu đường<br /> găng cũ vẫn tồn tại thì lặp lại bước 2, nếu<br /> không thì tìm đường găng mới và lặp lại cho<br /> đến khi đạt được mục tiêu rút ngắn cho trước.<br /> <br /> Hình 2. Lưu đồ thuật toán đề xuất<br /> <br /> Thực hiện bài toán với xác suất lai ghép:1;<br /> xác suất đột biến: 0,1; tỷ lệ loại bỏ sau mỗi<br /> vòng lặp: 10%; tỷ lệ hội tụ lời giải: 10%.Các<br /> thông số của dự án trên sơ đồ mạng được thể<br /> hiện như sau:<br /> <br /> Kiểm nghiệm chương trình:<br /> Bảng 1. Bảng số liệu đầu vào<br /> <br /> Hình 3. Sơ đồ mạng dự án trước và sau khi rút ngắn<br /> <br /> 50<br /> <br /> Hoàng Thị Cành và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Kết quả tính toán thử nghiệm khi thực hiện<br /> rút ngắn tối đa thời gian thực hiện dự án trên:<br /> <br /> 122(08): 47 - 52<br /> <br /> cho nhà quản lý dự án có những quyết định<br /> đúng đắn trong chỉ đạo thực hiện dự án.<br /> KẾT LUẬN<br /> <br /> Hình 4. Kết quả tính toán thử nghiệm<br /> <br /> Thực hiện tối ưu SĐM bằng mô hình đã lập<br /> với mục tiêu rút ngắn tối đa thời gian thực<br /> hiện và chi phí gia tăng là nhỏ nhất, chương<br /> trình đã phân bổ lại thời gian và chi phí tối ưu<br /> để thực hiện dự án, kết quả trong bảng 2.<br /> Bảng 2. So sánh thời gian - chi phí thực hiện bình<br /> thường và trường hợp đã tối ưu theo mô hình đã lập<br /> <br /> Đánh giá kết quả: Chi phí triển khai dự án<br /> ban đầu ước lượng là: 45.000.000 VNĐ và<br /> hoàn thành trong vòng 10 tuần. Sau khi đã<br /> được tối ưu hóa thì thời gian hoàn thành dự<br /> án còn 6 tuần (giảm 40%), với tổng chi phí là:<br /> 49.000.000 VNĐ, chi phí gia tăng nhỏ nhất<br /> sau khi rút ngắn thời gian thực hiện là<br /> 4.000.000 VNĐ (tăng 8,9%). Kết quả tính<br /> toán này rất có ý nghĩa về mặt thực tiễn giúp<br /> <br /> Việc ứng dụng thuật toán di truyền đã giúp<br /> tìm được kết quả tương đối tối ưu chỉ từ một<br /> số lượng hữu hạn các tổ hợp ban đầu, giảm<br /> thiểu thời gian tính toán của bài toán. Phương<br /> pháp chi phí phạt ngoài việc giúp gia tăng tốc<br /> độ hội tụ còn giúp gia tăng không gian tìm<br /> kiếm lời giải cho bài toán, tránh rơi vào lời<br /> giải tối ưu cục bộ. Chương trình tính toán mô<br /> phỏng đã không làm xuất hiện thêm đường<br /> găng mới, nên ít làm ảnh hưởng đến thời gian<br /> dự trữ của toàn bộ dự án. Kết quả thực<br /> nghiệm cho thấy giải pháp đã đề xuất là khả thi<br /> và có triển vọng, đảm bảo việc thực hiện dự án<br /> bám sát với thực tế, kết quả tính toán tối ưu hơn<br /> về mặt chi phí tạo thế mạnh cạnh tranh trong<br /> hoạt động kinh doanh cho doanh nghiệp.<br /> TÀI LIỆU THAM KHẢO<br /> 1. Barry Benatorand Albert Thumann (2003),<br /> Project Management and Leadership Skills for<br /> Engineering and Construction Projects, The<br /> Fairmont Press, the United States of America.<br /> 2. Murray B.Woolf (2007), Faster Construction<br /> Projects with CPM Scheduling, The McGraw-Hill<br /> Companies, the United States of America.<br /> 3. Flavio Cozzi (2008), Industrial Project<br /> Management: Planning, Design, and Construction,<br /> Stefano Tonchia University of Udine.<br /> 4. Thomas Euher (2003), Programming and<br /> scheduling techniques, Unsw Press,the United<br /> States of America.<br /> 5. Keith Potts (2008), Construction Cost<br /> Management: Learning from case studies, by<br /> Taylor & Francis Group, in the USA and Canada.<br /> 6. Ozgur Yeniay (2005), Penalty Function<br /> methods for contrained optimizaion with genetic<br /> algorithms,<br /> Mathematicaland<br /> Computation<br /> Application, vol 10, NO.1, pp 45-56, 2005.<br /> 7. Kathy Schwalbe (2002), Information<br /> Technology Project Management, 4th ed., Course<br /> Technology, ISBN 0-619-03528-5.<br /> 8. Nguyễn Đình Thúc (2002), lập trình tiến hóa,<br /> Nxb Giáo dục, 2002<br /> <br /> 51<br /> <br />