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

Hoàng Thị Cành và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 47 - 52 47 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*, Nguyễn Hồng Tân, Phùng Thế Huân Trường Đại học Công nghệ Thông tin và Truyền thông – ĐH Thái Nguyên TÓM TẮT 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 đố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 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ế 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ự 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 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 phương án tối ưu. 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 GIỚI THIỆU* Phương pháp tối ưu hóa, lý thuyết đồ thị là một lĩnh vực nghiên cứu rộng lớn, có nhiều ứng dụng và đang được quan tâm nghiên cứu nhiều trên thế giới. Các bài toán tối ưu về thời gian, chi phí dựa trên cơ sở lý thuyết đồ thịvà các chương trình phần mềm hỗ trợ việc quản lý dự án liên quan đến lập kế hoạch, điều chỉnh và tối ưu hoá tiến độ thực hiện kế hoạch đã có [1,3,5]. Tiêu biểu là phần mềm Microsoft Project, nhưng phần mềm chỉ giải quyết được vấn đề tối ưu hoá trên từng lĩnh vực [1,7]. Trong khi đó, bài toán tối ưu hoá theo chỉ tiêu thời gian và chi phí trên sơ đồ mạng đang là vấn đề đáng quan tâm trong nền kinh tế thị trường có tính cạnh tranh khốc liệt về giá thành [1]. Với chương trình WinQSB đã bước đầu giải quyết được bài toán tối ưu hoá theo chỉ tiêu thời gian - chi phí, tuy nhiên còn tiềm ẩn nhiều mặt hạn chế, như: quá trình tối ưu hóa làm xuất hiện nhiều đường găng mới đây là vấn đề bất cập trong công tác tổ chức thực hiện dự án [4,7]. Chỉ tiêu về mặt thời gian và chi phí thực hiện dự án là một vấn đề rất quan trọng. Hoàn thành dự án đúng thời hạn với chi phí nhỏ nhất sẽ mang lại những kết quả to lớn về kinh tế và chính trị. Đây là một vấn đề quan trọng * Tel: 01682 324556, Email: htcanh@ictu.edu.vn mà người làm công tác tổ chức, quản lý các dự án cùng nhiều nhà khoa học quan tâm. Vì vậy bài báo này đề xuất một giải pháp sử dụng thuật toán di truyền và phương pháp chi phí phạt để tìm ra phương án tối ưu khả thi. PHƯƠNG PHÁP SƠ ĐỒ MẠNG Sơ đồ mạng (SĐM) là một đồ thị bao gồm toàn bộ khối lượng của cả dự án, nó ấn định một cách logic trình tự kỹ thuật và mối quan hệ về tổ chức giữa các công việc, ấn định thời gian thực hiện các công việc và tối ưu hóa kế hoạch đề ra [2]. Các thông số chính trên SĐM[2,4]: EO (Earliest Occurrence of an Event): là thời điểm sớm nhất để cho sự kiện xảy ra khi tất cả các công việc trước sự kiện đều hoàn thành. LO (Lastest Occurrence of an Event): là thời điểm muộn nhất để cho sự kiện xảy ra mà không làm ảnh hưởng đến sự hoàn thành của dự án trong thời gian đã định. ES (Earliest Start of an activity): là thời điểm sớm nhất để cho công việc bắt đầu. ES của công việc ij = EO của sự kiện i LS (Lastest Start of an activity): là thời điểm muộn nhất để cho công việc bắt đầu mà Hoàng Thị Cành và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 47 - 52 48 không làm ảnh hưởng đến sự hoàn thành của dự án trong thời gian đã định. Cách xác định các thông số trên SĐM [2,7]: Xác định EO và ES: EO của sự kiện đầu tiên: EO1 = 0 Tại các sự kiện j chỉ có một công việc đến: ijj iEO EO t  Tại các sự kiện j có nhiều công việc đến:  ijaxj i i EO M EO t  Với các công việc giả thì cũng tính như trên nhưng tij=0 Xác định LO và LS: Tại sự kiện cuối cùng ta có: ô ôi ij ij Cu i Cu j EO LO LS LO t    Nếu chỉ có một công việc ij xuất phát từ sự kiện i ta có: ijiLO LS Nếu có nhiều công việc xuất phát từ sự kiện i ta có:    ij j iji i i LO Min LS Min LO t   Phân tích kết quả trên sơ đồ mạng: Thời gian tối thiểu để hoàn thành dự án chính bằng EOcuối.Thời gian dự trữ của các công việc (Float): F là khoảng thời gian tối đa mà một công việc có thể chậm chễ so với kế hoạch đã định mà không làm ảnh hưởng tới thời gian tối thiểu để hoàn thành dự án. ij ijESF LS  hay ij iEOF LS  Công việc găng là công việc có F=0. Đường găng: là đường nối liền từ sự kiện đầu tiên đến sự kiện cuối cùng với điều kiện tất cả các công việc nằm trên đó là các công việc găng [2,8]. Nhận xét: Mỗi SĐM có ít nhất một đường găng. Tổng thời gian của các công việc nằm trên đường găng chính là thời gian tối thiểu để hoàn thành dự án. Nếu 1 công việc trên đường găng bị trễ thì toàn bộ công việc sẽ bị trễ theo. Do vậy muốn rút ngắn thời gian hoàn thành dự án thì nhà quản lý phải tập trung các giải pháp làm giảm thời gian các công việc trên đường găng. MÔ HÌNH BÀI TOÁN TỐI ƯU HÓA THEO CHỈ TIÊU THỜI GIAN - CHI PHÍ Trong thực tế, nhiều dự án muốn đẩy nhanh thời gian thực hiện, để làm được điều này ta phải tìm cách rút ngắn thời gian đường găng, mà các biện pháp rút ngắn thời gian đường găng thường làm cho chi phí của dự án tăng lên. Bài toán được đặt ra là: tìm phương án rút ngắn thời gian thực hiện các công việc với chi phí tăng lên là nhỏ nhất. Thiết lập các mối liên hệ cho bài toán: Để ước lượng tij ta dùng các loại thời gian sau: a là thời gian để hoàn thành công việc trong điều kiện tốt nhất; b là thời gian để hoàn thành công việc trong điều kiện xấu nhất; m là thời gian để hoàn thành công việc trong điều kiện bình thường. bma  . Ta có: Kỳ vọng thời gian: 4 6 e a m b t    Nếu không xác định được m: 2 3 6 e a b t   ij et t  Phương sai của thời gian thực hiện công việctij: 2 2 ij 6 b a         Theo lý thuyết xác suất thống kê, phương sai của toàn bộ dự án: 2 2 ij  THUẬT TOÁN DI TRUYỀN Thuật toán di truyền (TTDT) thực hiện tìm kiếm lời giải tối ưu dựa trên cơ chế chọn lọc và di truyền tự nhiên. Quần thể trải qua quá trình tiến hóa: ở mỗi thế hệ lại tái sinh các lời giải tương đối tốt, trong khi các lời giải tương đối xấu bị mất dần đi. Để phân biệt các lời giải thích nghi khác nhau, hàm mục tiêu được dùng để đóng vai trò thích nghi môi trường. Một cá thể trong giải thuật di truyền biểu diễn một giải pháp của bài toán. Quần thể là một tập hợp các cá thể có cùng một số đặc điểm nào đó. Trong TTDT quần thể là một tập các lời giải của một bài toán. Các toán tử di truyền trong TTDT bao gồm[8]: Hoàng Thị Cành và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 47 - 52 49 Lai ghép là sự kết hợp các tính trạng của bố mẹ để sinh ra các thế hệ con. Đây được coi là một sự tổ hợp lại các tính chất (thành phần) trong hai lời giải cha mẹ nào đó để sinh ra một lời giải mới mà có đặc tính mong muốn là tốt hơn thế hệ cha mẹ. Chọn lọc là quá trình chọn lọc các cá thể trong quần thể. Đây chính là cách chọn các cá thể có độ thích nghi tốt để đưa vào thế hệ tiếp theo hoặc để lai ghép, với mục đích là sinh ra các cá thể mới tốt hơn. Đột biến là một sự biến đổi tại một (hay một số) gen của nhiễm sắc thể ban đầu để tạo ra một nhiễm sắc thể mới. Đột biến có thể tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban đầu. Tuy nhiên, trong TTDT thì ta luôn muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua từng thế hệ. Các tham số trong TTDT bao gồm [8]: Xác suất lai ghép: Nếu xác suất lai ghép là Pc, khi đó khả năng để một cá thể được lai ghép là Pc. Xác suất đột biến: Nếu xác suất đột biến là Pm, khi đó khả năng để mỗi gen của một nhiễm sắc thể bất kỳ bị đột biến là Pm. Tác dụng của toán tử đột biến là ngăn ngừa giải thuật di truyền rơi vào tình trạng cực trị địa phương, tuy nhiên nếu thực hiện đột biến với xác suất quá cao sẽ biến giải thuật di truyền thành giải thuật tìmkiếm ngẫu nhiên. Kích thước quần thể cho biết có bao nhiêu cá thể trong một quần thể. Nếu có quá ít cá thể thì sẽ làm giảm không gian tìm kiếm của thuật giải và dễ rơi vào các cục bộ địa phương, như vậy sẽ dễ xảy ra trường hợp bỏ qua những lời giải tốt. HÀM PHẠT TTDT là phương pháp thích hợp với các bài toán tối ưu với điều kiện không ràng buộc. Tuy nhiên thực tế việc giải các bài toán tối ưu thường chứa một hay nhiều ràng buộc, việc áp dụng TTDT vào các bài toán tối ưu có ràng buộc thường dẫn đến tối ưu cục bộ. Nhiều phương pháp đã được đề xuất để giải quyết trong đó phương pháp hàm phạt (Penalty Function) là phương pháp được sử dụng phổ biến do có khả năng tùy biến và thích hợp với nhiều thuật toán tìm kiếm [6]. Hình 1. Mô hình thuật toán di truyền Hàm phạt là phương pháp biến đổi từ bài toán có ràng buộc thành bài toán không ràng buộc thông qua việc biến đổi hàm mục tiêu như sau:       Fxxpxf Fxxf xf p )()( )( )( Trong đó: F: miền khả thi; fp(x): hàm phạt; f(x): hàm mục tiêu; p(x): giá trị phạt. Trong công thức trên, nếu không có vi phạm điều kiện xảy ra, p(x)=0 và fp(x)= f(x). Ngược lại, nếu có vi phạm điều kiện xảy ra, p(x)>0. Khi p(x) càng lớn dẫn đến fp(x) cũng có giá trị lớn theo tương ứng, khi đó fp(x)có khoảng cách rất xa so với f(x) dẫn đến dễ dàng loại bỏ. LẬP TRÌNH TÍNH TOÁN Hàm mục tiêu được đề xuất: )( pt CCCMin  Hoàng Thị Cành và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 47 - 52 50 Trong đó Ct là chi phí thực được xác định theo công thức:    N ji ijt CC 1, ; Cp là Chi phí phạt được xác định theo công thức: TGCGTĐ CPGT TGCTGRN CPCCPRN CPRNDVC p     (cụ thể: CPRNDV: Chi phí rút ngắn đơn vị; CPRN: Chi phí rút ngắn; CPC: Chi phí chuẩn; CPGT: Chi phí gia tăng; TGRN: Thời gian rút ngắn; TGC: Thời gian chuẩn; TGCGTĐ: Thời gian cắt giảm tối đa). Các bước rút ngắn thời gian hoàn thành dự án sử dụng thuật toán di truyềnnhư sau: Bước 1: Khởi tạo bài toán. Lập sơ đồ mạng. Xác định đường găng chuẩn và các công việc găng. Tạo quần thể tổ hợp các đường găng ban đầu. Bước 2: Tính toán chi phí ứng với mỗi tổ hợp. Tính chi phí thực, chi phí phạt, tổng chi phí. Bước 3: Đánh giá độ thích nghi – kiểm tra điều kiện dừng: Lựa chọn các công việc trên đường găng mà có chi phí rút ngắn đơn vị nhỏ nhất và cắt giảm thời gian thực hiện công việc này theo yêu cầu và trong phạm vi tối đa cho phép. Sắp xếp các tổ hợp theo chi phí, nếu thỏa mãn điều kiện dừng: Dừng chương trình, xuất kết quả; nếu không thỏa điều kiện dừng thực hiện tiếp bước 4. Bước 4: Tạo quần thể tổ hợp mới bằng TTDT. Thực hiện cơ chế chọn lọc, lai ghép, đột biến. Tạo ra quần thể tổ hợp Pt+1 từ quần thể tổ hợp Pt. Kiểm tra lại đường găng: Nếu đường găng cũ vẫn tồn tại thì lặp lại bước 2, nếu không thì tìm đường găng mới và lặp lại cho đến khi đạt được mục tiêu rút ngắn cho trước. Kiểm nghiệm chương trình: Bảng 1. Bảng số liệu đầu vào Hình 2. Lưu đồ thuật toán đề xuất Thực hiện bài toán với xác suất lai ghép:1; xác suất đột biến: 0,1; tỷ lệ loại bỏ sau mỗi vòng lặp: 10%; tỷ lệ hội tụ lời giải: 10%.Các thông số của dự án trên sơ đồ mạng được thể hiện như sau: Hình 3. Sơ đồ mạng dự án trước và sau khi rút ngắn Hoàng Thị Cành và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 47 - 52 51 Kết quả tính toán thử nghiệm khi thực hiện rút ngắn tối đa thời gian thực hiện dự án trên: Hình 4. Kết quả tính toán thử nghiệm Thực hiện tối ưu SĐM bằng mô hình đã lập với mục tiêu rút ngắn tối đa thời gian thực hiện và chi phí gia tăng là nhỏ nhất, chương trình đã phân bổ lại thời gian và chi phí tối ưu để thực hiện dự án, kết quả trong bảng 2. Bảng 2. So sánh thời gian - chi phí thực hiện bình thường và trường hợp đã tối ưu theo mô hình đã lập Đánh giá kết quả: Chi phí triển khai dự án ban đầu ước lượng là: 45.000.000 VNĐ và hoàn thành trong vòng 10 tuần. Sau khi đã được tối ưu hóa thì thời gian hoàn thành dự án còn 6 tuần (giảm 40%), với tổng chi phí là: 49.000.000 VNĐ, chi phí gia tăng nhỏ nhất sau khi rút ngắn thời gian thực hiện là 4.000.000 VNĐ (tăng 8,9%). Kết quả tính toán này rất có ý nghĩa về mặt thực tiễn giúp cho nhà quản lý dự án có những quyết định đúng đắn trong chỉ đạo thực hiện dự án. KẾT LUẬN Việc ứng dụng thuật toán di truyền đã giúp tìm được kết quả tương đối tối ưu chỉ từ một số lượng hữu hạn các tổ hợp ban đầu, giảm thiểu thời gian tính toán của bài toán. Phương pháp chi phí phạt ngoài việc giúp gia tăng tốc độ hội tụ còn giúp gia tăng không gian tìm kiếm lời giải cho bài toán, tránh rơi vào lời giải tối ưu cục bộ. Chương trình tính toán mô phỏng đã không làm xuất hiện thêm đường găng mới, nên ít làm ảnh hưởng đến thời gian dự trữ của toàn bộ dự án. Kết quả thực nghiệm cho thấy giải pháp đã đề xuất là khả thi và có triển vọng, đảm bảo việc thực hiện dự án bám sát với thực tế, kết quả tính toán tối ưu hơn về mặt chi phí tạo thế mạnh cạnh tranh trong hoạt động kinh doanh cho doanh nghiệp. TÀI LIỆU THAM KHẢO 1. Barry Benatorand Albert Thumann (2003), Project Management and Leadership Skills for Engineering and Construction Projects, The Fairmont Press, the United States of America. 2. Murray B.Woolf (2007), Faster Construction Projects with CPM Scheduling, The McGraw-Hill Companies, the United States of America. 3. Flavio Cozzi (2008), Industrial Project Management: Planning, Design, and Construction, Stefano Tonchia University of Udine. 4. Thomas Euher (2003), Programming and scheduling techniques, Unsw Press,the United States of America. 5. Keith Potts (2008), Construction Cost Management: Learning from case studies, by Taylor & Francis Group, in the USA and Canada. 6. Ozgur Yeniay (2005), Penalty Function methods for contrained optimizaion with genetic algorithms, Mathematicaland Computation Application, vol 10, NO.1, pp 45-56, 2005. 7. Kathy Schwalbe (2002), Information Technology Project Management, 4th ed., Course Technology, ISBN 0-619-03528-5. 8. Nguyễn Đình Thúc (2002), lập trình tiến hóa, Nxb Giáo dục, 2002 Hoàng Thị Cành và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 47 - 52 52 SUMMARY NETWORK DIAGRAM OPTIMIZATION UNDER STANDARD OF TIME AND COST BY USING GENETIC ALGORITHMS Hoang Thi Canh*, Nguyen Hong Tan, Phung The Huan College of Information and Communication Technology – TNU Optimizing the network diagram under standard of time and costisone of the effective solutions to shortening the execution time of each task list or an entire project with the lowest total cost. This method is meaningful and necessary in order to bring high economic efficiency in the organization, planning and implementation of projects in the market economy, which always has highly competition on price. This paper presents optimization methods according to criteria of time, cost on network diagrams using genetic algorithms combined with penalty cost method to find the optimal and feasible alternative. Keywords: Optimizing network diagrams, optimizing time, optimizing cost, genetic algorithms, penalty function Ngày nhận bài:11/7/2014; Ngày phản biện:21/7/2014; Ngày duyệt đăng: 25/8/2014 Phản biện khoa học: TS. Vũ Vinh Quang – Trường Đại học Công nghệ Thông tin & Truyền thông - ĐHTN * Tel: 01682 324556, Email: htcanh@ictu.edu.vn