GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN CỰC TIỂU HOÁ ĐỘ TRỄ

Abstract

Bài toán cực tiểu hoá độ trễ (Minimum Latency Problem – MLP) – hay còn gọi là bài toán thợ sửa chữa lưu động – là một trong những lớp bài toán tối ưu tổ hợp có nhiều ứng dụng trong thực tế. Trong trường hợp tổng quát, MLP được chứng minh là bài toán NP–khó. Hiện nay, đã có nhiều thuật toán giải gần đúng bài toán MLP được đề xuất, song chất lượng lời giải thu được chưa cao. Bài báo trình bày thuật toán phát triển dựa trên sơ đồ của thuật toán di truyền (Genetic Algorithm – GA – thuật toán áp dụng hiệu quả cho lớp bài toán tối ưu tổ hợp) để giải bài toán MLP. Kết quả thực nghiệm cho thấy, thuật toán đề xuất đưa ra được lời giải với chất lượng tốt hơn so với các lời giải của các thuật toán gần đúng tốt nhất hiện biết.