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

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.
Nội dung trích xuất từ tài liệu:
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ềnHoàng Thị Cành và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆ122(08): 47 - 52TỐI ƯU HÓA SƠ ĐỒ MẠNG THEO CHỈ TIÊUTHỜI GIAN VÀ CHI PHÍ SỬ DỤNG THUẬT TOÁN DI TRUYỀNHoàng Thị Cành*, Nguyễn Hồng Tân, Phùng Thế HuânTrường Đại học Công nghệ Thông tin và Truyền thông – ĐH Thái NguyênTÓM TẮTTố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ớitổ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, chiphí 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 raphươ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ạtGIỚ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ứunhiều trên thế giới. Các bài toán tối ưu về thờigian, 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ảnlý dự án liên quan đến lập kế hoạch, điềuchỉ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ềmMicrosoft Project, nhưng phần mềm chỉ giảiquyết được vấn đề tối ưu hoá trên từng lĩnhvự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ềnkinh tế thị trường có tính cạnh tranh khốc liệtvề 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 ưuhoá theo chỉ tiêu thời gian - chi phí, tuy nhiêncòn tiềm ẩn nhiều mặt hạn chế, như: quá trìnhtối ưu hóa làm xuất hiện nhiều đường găngmớ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ệndự án là một vấn đề rất quan trọng. Hoànthà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ề kinhtế và chính trị. Đây là một vấn đề quan trọng*Tel: 01682 324556, Email: htcanh@ictu.edu.vnmà người làm công tác tổ chức, quản lý cácdự á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 chiphí phạt để tìm ra phương án tối ưu khả thi.PHƯƠNG PHÁP SƠ ĐỒ MẠNGSơ đồ mạng (SĐM) là một đồ thị bao gồmtoàn bộ khối lượng của cả dự án, nó ấn địnhmột cách logic trình tự kỹ thuật và mối quanhệ về tổ chức giữa các công việc, ấn định thờigian 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ủadự án trong thời gian đã định.ES (Earliest Start of an activity): là thời điểmsớ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 iLS (Lastest Start of an activity): là thời điểmmuộn nhất để cho công việc bắt đầu mà47Hoàng Thị Cành và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆ122(08): 47 - 52không làm ảnh hưởng đến sự hoàn thành củadự án trong thời gian đã định.MÔ HÌNH BÀI TOÁN TỐI ƯU HÓA THEOCHỈ TIÊU THỜI GIAN - CHI PHÍCách xác định các thông số trên SĐM [2,7]:Trong thực tế, nhiều dự án muốn đẩy nhanhthời gian thực hiện, để làm được điều này taphả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 đườnggăng thường làm cho chi phí của dự án tănglên. Bài toán được đặt ra là: tìm phương án rútngắn thời gian thực hiện các công việc với chiphí tăng lên là nhỏ nhất.Xác định EO và ES:EO của sự kiện đầu tiên: EO1 = 0Tại các sự kiện j chỉ có một công việc đến:EO j  EOi  tijTại các sự kiện j có nhiều công việc đến:EO j  Max EOi  tijiVới các công việc giả thì cũng tính như trênnhưng tij=0Xác định LO và LS:Tại sự kiện cuối cùng ta có:EOCuôi  LOCuôiLSij  LO j  tijNếu chỉ có một công việc ij xuất phát từ sựkiện i ta có: LOi  LSijNếu có nhiều công việc xuất phát từ sự kiện i ta có: LOi  Min LSij  Min LOj  tijiiPhân tích kết quả trên sơ đồ mạng: Thời giantối thiểu để hoàn thành dự án chính bằngEOcuố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ộtcô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 giantối thiểu để hoàn thành dự án.F  LSij  ESij hay F  LSij  EOiCông việc găng là công việc có F=0. Đườnggă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áccô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 đườn ...