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. | Hoàng Thị Cành và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 47 - 52 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ự
