Nội dung chính của bài viết là trình bày các kết quả nghiên cứu về thuật toán xấp xỉ và giải thuật di truyền, trên cơ sở xây dựng và phân tích mô hình bài toán lập lịch tại các phòng khám của các bệnh viện, đề xuất các thuật toán xấp xỉ để giải quyết mô hình bài toán, tiến hành thử nghiệm trên mô hình cụ thể để khẳng định tính hiệu quả của các thuật toán đã đề xuất. | KẾT QUẢ XÂY DỰNG THUẬT TOÁN XẤP XỈ GIẢI MÔ HÌNH LẬP LỊCH TẠI BỆNH VIỆN Vũ Vinh Quang1 Phạm Thanh Huyền2 1 Trường Đại học Công nghệ thông tin và Truyền thông Đại học Thái Nguyên 2 Khoa Công nghệ thông tin Trường Đại học Hạ Long Email vvquang@ Ngày nhận bài 22 9 2022 Ngày nhận bài sửa sau phản biện 11 11 2022 Ngày chấp nhận đăng 15 11 2022 TÓM TẮT Trong thực tế mô hình lập lịch là một mô hình tối ưu được nhiều nhà nghiên cứu quan tâm do độ phức tạp lớn và tính ứng dụng cao trong thực tế. Việc tìm lời giải tối ưu trong thời gian đa thức là một thách thức lớn do đó trong thực tế người ta thường nghiên cứu một số lời giải gần tối ưu được thực hiện bằng các thuật toán xấp xỉ mà điển hình là các thuật toán tham lam và thuật toán tiến hóa dựa trên cơ chế của giải thuật di truyền. Nội dung chính của bài báo là trình bày các kết quả nghiên cứu về thuật toán xấp xỉ và giải thuật di truyền trên cơ sở xây dựng và phân tích mô hình bài toán lập lịch tại các phòng khám của các bệnh viện đề xuất các thuật toán xấp xỉ để giải quyết mô hình bài toán tiến hành thử nghiệm trên mô hình cụ thể để khẳng định tính hiệu quả của các thuật toán đã đề xuất. Từ khóa bài toán lập lịch độ phức tạp thuật toán giải thuật di truyền thuật toán tham lam tính toán tiến hóa. THE FINDINGS ON CONSTRUCTING A NEW APPROXIMATION ALGORITHM TO SOLVE THE HOSPITAL S SCHEDULING MODEL ABSTRACT In reality the scheduling model is an optimal model that many researchers are interested in due to its great complexity and high applicability in practice. Finding out the optimal solution in polynomial time is a big challenge therefore scientists frequently study some near-optimal solutions implemented by approximation algorithms typically greedy and evolutionary algorithms based on the mechanics of genetic algorithms. The main content of this paper is to present the research findings on approximation algorithms and genetic algorithms. On the basis of constructing and analyzing the scheduling model in the .
