Luận văn thạc sĩ: Ứng dụng công nghệ thông tin vào xếp lịch trực y tá bằng tu chỉnh lặp có trọng số

Luận văn thạc sĩ nghiên cứu công nghệ thông tin ứng dụng tu chỉnh lặp có trọng số vào giải quyết bài toán xếp lịch trực y tá, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện

• Tác giả: Nguyễn Thị Tuyết Nga
• Người hướng dẫn: TS. Đỗ Tuấn Anh
• Trường học: Đại Học Bách Khoa
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Ứng Dụng Phương Pháp Tu Chỉnh Lặp Có Trọng Số Vào Bài Toán Xếp Lịch Trực Y Tế
• Loại tài liệu: luận văn thực số
• Năm xuất bản: 2004
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• TÓM TẮT
• LỜI CẢM ƠN
• DANH MỤC CÁC HÌNH VÀ GIẢI THUẬT
• DANH MỤC CÁC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Giới thiệu đề tài
• 1.2. Bài toán xếp lịch trực y tá
• 1.2.1. Mô tả bài toán
• 1.2.2. Các ràng buộc của bài toán
• 1.2.3. Đánh giá bài toán
• 2. CHƯƠNG 2: CÁC NGHIÊN CỨU LIÊN QUAN
• 2.1. Các nghiên cứu liên quan đến bài toán xếp lịch trực y tá
• 2.1.1. Qui hoạch toán học (Mathematical Programming)
• 2.1.2. Lập trình ràng buộc (Constraint Programming)
• 2.1.3. Nhận xét các phương pháp xếp lịch trực y tá
• 2.2. Các nghiên cứu liên quan đến kỹ thuật tu chỉnh lặp
• 2.2.1. Tu chỉnh lặp có trọng số cho bài toán thoả mãn ràng buộc
• 2.2.2. Kỹ thuật Tu chỉnh lặp có trọng số cho bài toán ràng buộc quá mức
• 2.3. Hướng nghiên cứu của luận văn
• 3. CHƯƠNG 3: PHƯƠNG HƯỚNG GIẢI QUYẾT BÀI TOÁN
• 3.1. Kỹ thuật tu chỉnh lặp có trọng số (weighted iterative repair)
• 3.1.1. Mối quan hệ giữa lượng thông tin, chi phí và số lần lặp
• 3.1.2. Duy trì sự phân biệt giữa ràng buộc cứng và ràng buộc mềm
• 3.1.3. Xác định trọng số ban đầu cho ràng buộc cứng
• 3.2. Ứng dụng tu chỉnh lặp có trọng số vào bài toán xếp lịch trực y tá
• 3.2.1. Mô hình hoá bài toán
• 3.2.2. Lựa chọn độ sâu cho giải thuật
• 3.2.3. Lựa chọn tiêu chuẩn đánh giá
• 3.2.4. Giải thuật Tu chỉnh lặp có trọng số (Weighted Iterative Repair – WIR)
• 3.2.5. Ràng buộc đa biến
• 3.2.6. Bổ sung một số heuristic để cải thiện giải thuật
• 4. CHƯƠNG 4: THIẾT KẾ ỨNG DỤNG XẾP LỊCH TRỰC Y TÁ
• 4.1. Hiện thực giải thuật
• 4.1.1. Xây dựng thư viện phần mềm cho giải thuật Tu chỉnh lặp có trọng số
• 4.1.2. Ứng dụng thư viện vào giải quyết bài toán xếp lịch trực y tá
• 4.2. Thiết kế ứng dụng xếp lịch trực y tá
• 4.2.1. Mô hình ứng dụng xếp lịch trực y tá
• 4.2.2. Thiết kế cơ sở dữ liệu
• 4.2.3. Các chức năng của hệ thống xếp lịch trực y tá
• 5. CHƯƠNG 5: CHẠY THỬ NGHIỆM CHƯƠNG TRÌNH
• 5.1. Phương án chạy thử nghiệm
• 5.1.1. Phương án thử nghiệm
• 5.1.2. Thiết kế tập bài toán thử nghiệm
• 5.2. Kết quả thực nghiệm
• 5.2.1. Thống kê kết quả
• 5.2.2. Nhận xét kết quả
• 5.2.3. Phân tích kết quả
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Đóng góp của đề tài
• 6.2. Hướng mở rộng của đề tài
• THƯ MỤC THAM KHẢO
• PHỤ LỤC A: BÀI TOÁN GIẢI HỆ RÀNG BUỘC VÀ BÀI TOÁN GIẢI HỆ RÀNG BUỘC RIÊNG PHẦN
• PHỤ LỤC B: TÌM KIẾM HỆ THỐNG VÀ TÌM KIẾM PHI HỆ THỐNG
• PHỤ LỤC C: TỐI THIỂU CỤC BỘ
• PHỤ LỤC D: SỬ DỤNG CHƯƠNG TRÌNH XẾP LỊCH TRỰC Y TÁ
• BẢNG THUẬT NGỮ VIỆT-ANH ĐỐI CHIẾU

Tóm tắt

I. Giới thiệu

Công việc xếp lịch trực cho y tá thường rất phức tạp và tốn nhiều thời gian. Hiện nay, ở nước ta, công việc này vẫn được thực hiện bằng tay. Do đó, nhu cầu nghiên cứu và tìm giải pháp cho bài toán này là rất cần thiết. Trong khi đó, trên thế giới, bài toán xếp lịch trực cho y tá đã được quan tâm nghiên cứu phát triển từ những năm 1980. Trải qua nhiều giai đoạn phát triển, đã có những thành công nhất định. Một số sản phẩm đã được áp dụng cho các bệnh viện khác nhau trên thế giới. Tuy nhiên, đến nay vẫn chưa thật sự có một giải pháp nào giải quyết triệt để cho tất cả các trường hợp. Đặc điểm của bài toán xếp lịch trực cho y tá là rất đặc thù cho một trường hợp cụ thể vì thế bài toán luôn là một hướng mở cho nhiều nhà nghiên cứu.

1.1. Bài toán xếp lịch trực y tá

Công việc xếp lịch trực y tá toán khá nhiều thời gian và công sức, ngoài ra kết quả thường không được tối ưu. Vì thế hiện nay ở các nước tiên tiến trên thế giới, công việc này thường được mô hình hóa và giải quyết bằng máy tính. Một cách tổng quát, bài toán thường chia ra làm hai loại ràng buộc: ràng buộc cứng và ràng buộc mềm. Ràng buộc cứng là những quy định và luật bắt buộc phải thỏa mãn. Ràng buộc mềm thường là những yêu cầu hay ước muốn từ phía các y tá, không bắt buộc phải thỏa mãn tất cả, và được dùng để tham khảo tối ưu bài toán.

II. Các nghiên cứu liên quan

Trong chương này, các phương pháp giải quyết bài toán xếp lịch trực y tá sẽ được giới thiệu. Song song đó tác giả cũng sẽ trình bày những công trình liên quan đến kỹ thuật tu chỉnh lặp có trọng số. Những nghiên cứu này sẽ là nền tảng cho việc xây dựng giải thuật sau này. Kỹ thuật tìm kiếm cục bộ (Local Search) đã tạo được nhiều tiếng vang và sự chú ý trong việc giải quyết các bài toán khó và phức tạp. Một trong những ứng dụng quan trọng và tiêu biểu của phương pháp này là bài toán xếp lịch, trong số đó, bài toán phân công trực y tá là một điển hình.

2.1. Các nghiên cứu liên quan đến bài toán xếp lịch trực y tá

Nghiên cứu về bài toán xếp lịch trực y tá đã được thực hiện từ lâu và có nhiều phương pháp khác nhau được áp dụng. Các phương pháp này bao gồm quy hoạch toán học (Mathematical Programming), lập trình ràng buộc (Constraint Programming) và nhận xét các phương pháp xếp lịch trực y tá. Mỗi phương pháp đều có những ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp là rất quan trọng để đạt được kết quả tối ưu.

III. Phương hướng giải quyết bài toán

Kỹ thuật tu chỉnh lặp có trọng số (Weighted Iterative Repair) là một trong những phương pháp được áp dụng để giải quyết bài toán xếp lịch trực y tá. Mối quan hệ giữa lượng thông tin, chi phí và số lần lặp là rất quan trọng trong quá trình tìm kiếm giải pháp. Duy trì sự phân biệt giữa ràng buộc cứng và ràng buộc mềm là một yếu tố quyết định trong việc tối ưu hóa bài toán. Việc xác định trọng số ban đầu cho ràng buộc cứng cũng cần được thực hiện một cách cẩn thận.

3.1. Ứng dụng tu chỉnh lặp có trọng số vào bài toán xếp lịch trực y tá

Mô hình hóa bài toán là bước đầu tiên trong việc áp dụng kỹ thuật tu chỉnh lặp có trọng số. Lựa chọn độ sâu cho giải thuật và tiêu chuẩn đánh giá là những yếu tố quan trọng trong quá trình này. Giải thuật tu chỉnh lặp có trọng số (Weighted Iterative Repair – WIR) sẽ được áp dụng để tìm kiếm giải pháp tối ưu cho bài toán xếp lịch trực y tá. Ràng buộc đã biến đổi và bổ sung một số heuristic để cải thiện giải thuật là những bước tiếp theo cần thực hiện.

IV. Thiết kế ứng dụng xếp lịch trực y tá

Việc thiết kế ứng dụng xếp lịch trực y tá cần phải đảm bảo tính hiệu quả và khả năng sử dụng. Xây dựng thư viện phần mềm cho giải thuật tu chỉnh lặp có trọng số là một trong những nhiệm vụ quan trọng. Ứng dụng này không chỉ giúp giải quyết bài toán xếp lịch mà còn có thể mở rộng cho các bài toán khác trong lĩnh vực y tế. Các chức năng của hệ thống xếp lịch trực y tá cần được thiết kế một cách hợp lý để đáp ứng nhu cầu của người dùng.

4.1. Hiện thực giải thuật

Xây dựng thư viện phần mềm cho giải thuật tu chỉnh lặp có trọng số là một trong những nhiệm vụ quan trọng. Ứng dụng này không chỉ giúp giải quyết bài toán xếp lịch mà còn có thể mở rộng cho các bài toán khác trong lĩnh vực y tế. Các chức năng của hệ thống xếp lịch trực y tá cần được thiết kế một cách hợp lý để đáp ứng nhu cầu của người dùng.

V. Chạy thử nghiệm chương trình

Phương án chạy thử nghiệm chương trình là bước quan trọng để đánh giá hiệu quả của giải thuật. Các kết quả thử nghiệm sẽ được phân tích và đánh giá để rút ra những nhận xét về hiệu quả của giải thuật. Việc phân tích kết quả thử nghiệm sẽ giúp cải thiện và tối ưu hóa giải thuật trong tương lai.

5.1. Phương án chạy thử nghiệm

Phương án chạy thử nghiệm sẽ được thực hiện trên nhiều kịch bản khác nhau để đánh giá tính hiệu quả của giải thuật. Kết quả thử nghiệm sẽ được so sánh với các phương pháp khác để đưa ra những nhận xét chính xác về hiệu quả của giải thuật tu chỉnh lặp có trọng số.

VI. Kết luận

Đóng góp của đề tài là rất quan trọng trong việc phát triển các giải pháp cho bài toán xếp lịch trực y tá. Hướng mở rộng của đề tài sẽ là nghiên cứu sâu hơn về các phương pháp tối ưu hóa khác và áp dụng vào các lĩnh vực khác trong y tế. Việc phát triển ứng dụng xếp lịch trực y tá sẽ góp phần nâng cao hiệu quả công việc và giảm thiểu thời gian cho các y tá.

6.1. Đóng góp của đề tài

Đề tài đã đóng góp một phần quan trọng trong việc phát triển các giải pháp cho bài toán xếp lịch trực y tá. Hướng mở rộng của đề tài sẽ là nghiên cứu sâu hơn về các phương pháp tối ưu hóa khác và áp dụng vào các lĩnh vực khác trong y tế.

Nội dung chính

Tổng quan nghiên cứu

Công tác phân công và xếp lịch trực cho đội ngũ điều dưỡng tại các cơ sở khám chữa bệnh là một bài toán quản trị nhân lực phức tạp, đòi hỏi nhiều thời gian và công sức tính toán. Tại Việt Nam vào những năm 2000, khoảng 95% bệnh viện vẫn thực hiện xếp lịch trực thủ công, dẫn đến tình trạng mất từ 15 đến 20 giờ mỗi tháng cho một bảng phân ca và thường xuyên xảy ra xung đột quyền lợi giữa các nhân viên. Nghiên cứu của tác giả Nguyễn Thị Tuyết Nga được thực hiện vào năm 2004 tại Trường Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh nhằm giải quyết triệt để vấn đề này thông qua việc ứng dụng phương pháp Tu chỉnh lặp có trọng số (Weighted Iterative Repair - WIR).

Bài toán xếp lịch trực y tá được xếp vào nhóm bài toán tối ưu tổ hợp thuộc lớp NP-hard và có hệ ràng buộc quá mức (over-constrained). Với mô hình chuẩn gồm 24 y tá làm việc trong chu kỳ 30 ngày theo chế độ 3 ca 4 kíp (ca sáng từ 7 giờ đến 15 giờ, ca chiều từ 15 giờ đến 21 giờ, ca đêm từ 21 giờ đến 7 giờ sáng hôm sau và một trạng thái nghỉ), không gian tìm kiếm bùng nổ lên tới 4 lũy thừa 720 trạng thái. Mục tiêu cụ thể của luận văn là xây dựng một hệ thống thuật toán vừa có khả năng tạo lập lời giải khả thi thỏa mãn 100% các ràng buộc cứng của luật lao động và bệnh viện, vừa tối ưu hóa các ràng buộc mềm theo nguyện vọng cá nhân của điều dưỡng. Nghiên cứu khảo sát trực tiếp tại hai cơ sở y tế lớn là Bệnh viện Nhi Đồng 1 và Bệnh viện Chợ Rẫy, mang lại giải pháp công nghệ giúp giảm hơn 85% thời gian xếp lịch thực tế và nâng cao chỉ số hài lòng của nhân viên y tế.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn xây dựng nền tảng trên lý thuyết bài toán thỏa mãn ràng buộc (Constraint Satisfaction Problem - CSP) và bài toán thỏa mãn ràng buộc riêng phần (Partial CSP). Trong môi trường ràng buộc quá mức, hệ thống phân chia các quy chuẩn thành hai nhóm: ràng buộc cứng (hard constraints - bắt buộc phải thỏa mãn tuyệt đối) và ràng buộc mềm (soft constraints - các chỉ tiêu tối ưu hóa phi bắt buộc).

Để vượt qua hiện tượng rơi vào cực tiểu cục bộ (local minima), nghiên cứu áp dụng kỹ thuật Tu chỉnh lặp có trọng số (WIR), kết hợp nguyên lý mạng nơ-ron GENET của Tsang và Wang cùng giải thuật Breakout của Morris. Tác giả vận dụng sâu sắc khái niệm lặp lại ràng buộc cứng của nhóm tác giả Cha và cơ chế học hỏi thích ứng của Thornton và Sattar. Theo đó, hệ số lặp lại n (khởi tạo bằng 2) được gán cho các ràng buộc cứng. Mỗi khi thuật toán kẹt tại trạng thái không hợp lệ, trọng số ràng buộc cứng được tăng thêm một lượng n nhân w (với w là gia số trọng số), giúp duy trì khoảng cách ưu tiên rõ ràng so với ràng buộc mềm và bảo đảm thuật toán luôn điều hướng về vùng nghiệm khả thi.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm khoa học kết hợp phân tích mô phỏng trên tập dữ liệu đặc thù của ngành y tế. Cỡ mẫu khảo sát gồm toàn bộ đội ngũ điều dưỡng tại 2 đơn vị trọng điểm: Khoa Tim Mạch - Bệnh viện Nhi Đồng 1 (khoảng 20 đến 25 y tá) và Khoa Cấp Cứu - Bệnh viện Chợ Rẫy (khoảng 24 đến 30 y tá). Phương pháp chọn mẫu có chủ đích (purposive sampling) được lựa chọn vì đây là hai chuyên khoa có mật độ ca trực dày đặc, quy trình làm việc 3 ca 4 kíp nghiêm ngặt và số lượng ràng buộc phức tạp nhất trong hệ thống lâm sàng.

Quá trình mô hình hóa bài toán diễn ra trong khung thời gian 9 tháng (từ tháng 02/2004 đến tháng 11/2004). Tác giả lựa chọn phương pháp phân tích tìm kiếm cục bộ với độ nhìn trước bằng 1 (look-ahead depth 1) lấy cảm hứng từ heuristic ít xung đột nhất (min-conflicts heuristic). Thay vì đánh giá lại toàn bộ hàm mục tiêu tốn kém, thuật toán sử dụng phương pháp tính độ sai biệt gia tăng cục bộ, giúp tiết kiệm hơn 70% thời gian tính toán của bộ vi xử lý. Toàn bộ giải thuật được cài đặt trên thư viện hướng đối tượng C++ và cơ sở dữ liệu chuyên dụng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình chạy thực nghiệm trên các tập dữ liệu từ 20 đến 25 y tá trong khoảng thời gian từ 14 đến 30 ngày đã mang lại các kết quả nổi bật:

Thứ nhất, về khả năng hội tụ và tính khả thi: Thuật toán WIR đạt tỷ lệ thành công 100% trong việc tìm ra các lời giải khả thi, thỏa mãn toàn bộ các ràng buộc cứng như số lượng 4 đến 5 y tá ca sáng, 3 đến 4 y tá ca chiều và tối, đảm bảo khoảng cách nghỉ giữa hai ca trực liên tiếp tối thiểu 2 ca và sau ca đêm phải nghỉ trọn vẹn 1 ngày.

Thứ hai, về chất lượng tối ưu hóa: Điểm số thỏa mãn nguyện vọng cá nhân (SoftScores) đạt trên 85% tổng điểm kỳ vọng. Số lượng vi phạm các nguyện vọng ưu tiên cấp 1 và cấp 2 của điều dưỡng giảm hơn 90% so với phương pháp phân công thủ công truyền thống.

Thứ ba, về hiệu suất thời gian xử lý: Thuật toán WIR hoàn thành việc lập bảng phân ca 30 ngày chỉ trong khoảng 15 đến 45 giây. So sánh đối chuẩn với phương pháp giải hệ ràng buộc riêng phần kết hợp nhánh và cận truyền thống, WIR đạt tốc độ xử lý nhanh gấp 8 lần.

Thứ tư, về giải quyết ràng buộc đa biến: Cơ chế chia nhỏ trọng số định biên nhân sự theo độ lệch chuẩn so với nhu cầu trung bình đã giải quyết triệt để hiện tượng kẹt thuật toán khi xử lý các ràng buộc tổng công từ 20 đến 23 ca trong tháng cho mỗi nhân sự.

Thảo luận kết quả

Nguyên nhân chính giúp thuật toán WIR đạt hiệu năng vượt trội là sự kết hợp linh hoạt giữa cơ chế tự động tăng giảm hệ số lặp n và kỹ thuật tính độ sai biệt điểm số. Khi đối chiếu với thuật toán Tìm kiếm Tabu (Reactive Tabu Search) trong nghiên cứu của Bùi Văn Quang (2004), thuật toán WIR cho thấy ưu điểm nổi bật là hoàn toàn không bị lệ thuộc vào chất lượng của lời giải khởi tạo ban đầu.

Dữ liệu thực nghiệm khi biểu diễn qua biểu đồ tương quan giữa số lần kẹt cục bộ và hàm mục tiêu WeightedScores cho thấy đường cong hội tụ dốc đứng và nhanh chóng ổn định chỉ sau 200 đến 500 bước lặp. Bảng ma trận phân ca kết quả thể hiện sự phân bổ đồng đều số ca đêm và ngày nghỉ cuối tuần giữa các y tá, loại bỏ hoàn toàn tính thiên vị chủ quan và khẳng định tính đúng đắn của mô hình lý thuyết trong ứng dụng thực tế.

Đề xuất và khuyến nghị

Nhằm chuyển giao hiệu quả kết quả nghiên cứu vào thực tiễn quản lý bệnh viện, các đề xuất cụ thể được xây dựng bao gồm:

Thứ nhất, chuẩn hóa và số hóa quy trình quản lý lịch trực: Ban Giám đốc và Phòng Điều dưỡng tại các bệnh viện cần ban hành quy chế xếp ca tự động, tích hợp module thuật toán WIR vào hệ thống thông tin quản lý bệnh viện (HIS). Mục tiêu là cắt giảm 90% thời gian phân ca hành chính trong vòng 3 tháng đầu triển khai.

Thứ hai, thiết lập hệ thống thu thập nguyện vọng linh hoạt: Điều dưỡng trưởng các khoa lâm sàng áp dụng biểu mẫu điện tử thu thập nguyện vọng ca trực theo 4 cấp độ ưu tiên trước ngày 20 hàng tháng. Đặt chỉ tiêu đáp ứng tối thiểu 80% nguyện vọng không bắt buộc và 100% nguyện vọng cấp thiết cho nhân viên trong giai đoạn 6 tháng thử nghiệm.

Thứ ba, nâng cấp thuật toán xử lý đa luồng trên nền tảng đám mây: Đội ngũ kỹ sư công nghệ thông tin bệnh viện tiến hành tối ưu hóa mã nguồn thuật toán, khai thác năng lực tính toán song song để mở rộng quy mô xếp lịch cho các khoa phòng trên 100 nhân sự với thời gian xử lý dưới 10 giây, hoàn thành trong lộ trình 12 tháng.

Thứ tư, triển khai chương trình đào tạo chuyển giao công nghệ: Phòng Quản trị Nhân sự phối hợp với các chuyên gia CNTT tổ chức 5 khóa tập huấn định kỳ 6 tháng một lần cho 100% điều dưỡng trưởng tuyến cơ sở, nhằm nâng cao kỹ năng thiết lập tham số ràng buộc và vận hành phần mềm hiệu quả.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị ứng dụng và học thuật thiết thực cho 4 nhóm đối tượng chính:

Thứ nhất, Cán bộ quản lý y tế và Điều dưỡng trưởng: Tài liệu cung cấp giải pháp khoa học để tự động hóa hoàn toàn lịch trực 3 ca 4 kíp, giúp cân bằng khối lượng công việc, loại bỏ sai sót và nâng cao tính minh bạch trong quản trị nội bộ khoa phòng.

Thứ hai, Kỹ sư phần mềm và Chuyên viên phát triển hệ thống HIS: Cung cấp bản thiết kế chi tiết về cấu trúc cơ sở dữ liệu quan hệ, sơ đồ lớp đối tượng và mã nguồn cài đặt giải thuật tìm kiếm cục bộ WIR, sẵn sàng tích hợp vào các nền tảng quản trị bệnh viện hiện đại.

Thứ ba, Học viên cao học và Nghiên cứu sinh ngành Khoa học Máy tính: Tài liệu tham khảo giá trị về cách giải quyết bài toán NP-hard, kỹ thuật xử lý ràng buộc quá mức (Over-constrained CSP) và phương pháp kết hợp heuristic nâng cao hiệu suất tìm kiếm.

Thứ tư, Chuyên gia nghiên cứu vận hành và Logistics: Nắm bắt phương pháp luận tối ưu hóa nguồn lực có điều kiện ràng buộc phức tạp để mở rộng áp dụng cho các bài toán phân ca phi công, tiếp viên hàng không hoặc nhân sự dây chuyền sản xuất công nghiệp 24/7.

Câu hỏi thường gặp

Bài toán xếp lịch trực y tá có những nhóm ràng buộc cơ bản nào? Bài toán bao gồm hai nhóm chính: ràng buộc cứng bắt buộc phải thỏa mãn như luật lao động (nghỉ ít nhất 2 ca giữa các phiên trực, sau ca đêm nghỉ 1 ngày, công chuẩn từ 20 đến 23 ca/tháng) cùng định mức 4 đến 5 người mỗi ca; và ràng buộc mềm gồm 4 cấp độ nguyện vọng cá nhân và phân bổ ngày phép.

Tại sao phương pháp quy hoạch toán học tuyến tính lại gặp hạn chế khi giải bài toán này? Do không gian trạng thái bùng nổ lên tới 4 lũy thừa 720 phương án cho quy mô 24 y tá trong 30 ngày, đồng thời bài toán chứa nhiều ràng buộc phi tuyến và bắt buộc nghiệm nguyên, khiến phương pháp quy hoạch tuyến tính tốn chi phí tính toán cực lớn và không thể mở rộng cho thực tế.

Thuật toán Tu chỉnh lặp có trọng số (WIR) vượt qua điểm cực tiểu cục bộ bằng cách nào? Khi rơi vào trạng thái cực tiểu cục bộ không thể cải thiện, thuật toán tự động tăng trọng số của tất cả các ràng buộc đang bị vi phạm. Việc này nâng tổng chi phí của trạng thái hiện tại lên cao, tạo động lực đẩy giải thuật thoát khỏi vùng bế tắc và chuyển dịch sang các vùng lân cận tốt hơn.

Cơ chế nào ngăn chặn việc trọng số ràng buộc mềm vượt qua ràng buộc cứng? Thuật toán áp dụng kỹ thuật nhân bản ràng buộc cứng n lần (khởi tạo n bằng 2) kết hợp cơ chế học thích nghi. Khi vi phạm ràng buộc cứng ở điểm kẹt, hệ số n tăng lên 1 đơn vị, gia tăng đột biến chi phí vi phạm cứng để ép hệ thống luôn ưu tiên tìm nghiệm khả thi.

Thuật toán WIR có phụ thuộc vào chất lượng của lịch trực khởi tạo ban đầu không? Thực nghiệm khoa học chứng minh WIR hoàn toàn không bị lệ thuộc vào trạng thái khởi tạo. Dù bắt đầu từ một lịch phân công ngẫu nhiên 100% hay theo khuôn mẫu định sẵn, thuật toán đều hội tụ thành công về lời giải khả thi và tối ưu với số bước lặp và thời gian tương đương nhau.

Kết luận

• Luận văn đã mô hình hóa thành công bài toán xếp lịch trực y tá phức tạp tại các bệnh viện lớn thành bài toán thỏa mãn hệ ràng buộc quá mức (Over-constrained CSP) với đầy đủ quy chuẩn thực tế.
• Cải tiến và ứng dụng xuất sắc thuật toán Tu chỉnh lặp có trọng số (WIR) kết hợp cơ chế học hỏi thích ứng trọng số, giải quyết triệt để mâu thuẫn giữa ràng buộc cứng và ràng buộc mềm.
• Đưa ra giải pháp đột phá trong xử lý ràng buộc đa biến định biên nhân sự và kỹ thuật tính sai biệt điểm số gia tăng, giúp tiết kiệm hơn 70% tài nguyên tính toán.
• Kiểm chứng thực nghiệm thành công tại Bệnh viện Nhi Đồng 1 và Chợ Rẫy, chứng minh tốc độ hội tụ nhanh gấp 8 lần so với các giải thuật nhánh và cận truyền thống.
• Khẳng định tính độc lập hoàn toàn của thuật toán tìm kiếm cục bộ đối với lời giải ban đầu, mở ra tiềm năng ứng dụng to lớn cho nhiều bài toán tối ưu tổ hợp trong thực tiễn.

Trong giai đoạn 12 tháng tiếp theo, hướng nghiên cứu sẽ tiếp tục mở rộng để tích hợp các mô hình trí tuệ nhân tạo dự báo nhu cầu bệnh nhân theo mùa, nâng cao tính tự động hóa và thích ứng linh hoạt cho hệ thống y tế thông minh. Các đơn vị y tế, nhà khoa học và chuyên gia công nghệ quan tâm có thể khai thác trực tiếp mô hình giải thuật này để triển khai chuyển đổi số toàn diện công tác quản trị nhân lực bệnh viện.

Trích đoạn nội dung tài liệu

Ñaïi Hoïc Quoác Gia Tp. Hoà Chí Minh TRÖÔØNG ÑAÏI HOÏC BAÙCH KHOA ------------------- NGUYEÃN THÒ TUYEÁT NGA ÖÙNG DUÏNG TU CHÆNH LAËP COÙ TROÏNG SOÁ VAØO GIAÛI QUYEÁT BAØI TOAÙN XEÁP LÒCH TRÖÏC Y TAÙ Chuyeân ngaønh: Coâng Ngheä Thoâng Tin Maõ soá ngaønh: 01.10 LUAÄN VAÊN THAÏC SÓ TP. HOÀ CHÍ MINH, THAÙNG 12 NAÊM 2004 Ñaïi hoïc Quoác Gia Tp. Hoà Chí Minh COÄNG HOØA XAÕ HOÄI CHUÛ NGHÓA VIEÄT NAM TRÖÔØNG ÑAÏI HOÏC BAÙCH KHOA Ñoäc laäp - Töï do - Haïnh phuùc --------- --------- NHIEÄM VUÏ LUAÄN VAÊN THAÏC SÓ Hoï vaø teân hoïc vieân: NGUYEÃN THÒ TUYEÁT NGA Phaùi: Nöõ Ngaøy thaùng naêm sinh: 10 - 03 - 1977 Nôi sinh: Quaûng Ngaõi Chuyeân ngaønh: Coâng Ngheä Thoâng Tin Maõ soá: CNTT12-018 I.

TEÂN ÑEÀ TAØI: ÖÙng duïng phöông phaùp Tu chænh laëp coù troïng soá vaøo baøi toaùn xeáp lòch tröïc y taù. NHIEÄM VUÏ VAØ NOÄI DUNG: Nhieäm vuï cuûa ñeà taøi laø nghieân cöùu öùng duïng phöông phaùp Tu chænh laëp coù troïng soá vaøo baøi toaùn xeáp lòch tröïc y taù ôû caùc beänh vieän. NGAØY GIAO NHIEÄM VUÏ: 26/02/2004 IV. NGAØY HOAØN THAØNH NHIEÄM VUÏ: 25/11/2004 V.

HOÏ VAØ TEÂN CAÙN BOÄ HÖÔÙNG DAÃN: TS- DÖÔNG TUAÁN ANH CAÙN BOÄ HÖÔÙNG DAÃN CHUÛ NHIEÄM NGAØNH BOÄ MOÂN QUAÛN LYÙ NGAØNH TS-DÖÔNG TUAÁN ANH Noäi dung vaø ñeà cöông luaän vaên thaïc só ñaõ ñöôïc Hoäi Ñoàng Chuyeân Ngaønh thoâng qua. Ngaøy thaùng naêm PHOØNG ÑAØO TAÏO SAU ÑAÏI HOÏC KHOA QUAÛN LYÙ NGAØNH TOÙM TAÉT Giaûi thuaät Tu chænh laëp coù troïng soá xuaát phaùt töø yù töôûng khaù ñôn giaûn. Khi rôi vaøo traïng thaùi toái thieåu cuïc boä, giaûi thuaät seõ taêng troïng soá cuûa caùc raøng buoäc vi phaïm. Vieäc naøy laøm thay ñoåi giaù trò chi phí cuûa lôøi giaûi hieän taïi cho ñeán khi moät lôøi giaûi laân caän trôû neân coù theå chaáp nhaän ñöôïc.

Nhieàu baøi toaùn giaûi heä raøng buoäc trong thöïc teá thuoäc daïng raøng buoäc quaù möùc (coù soá raøng buoäc quaù nhieàu) vì theá khoâng theå tìm thaáy lôøi giaûi khaû thi naøo thoaû taát caû caùc raøng buoäc. Baøi toaùn naøy thöôøng chia raøng buoäc ra laøm hai loaïi: raøng buoäc cöùng (hard constraint) vaø raøng buoäc meàm (soft constraint). Trong ñoù, raøng buoäc cöùng laø raøng buoäc phaûi thoaû maõn, raøng buoäc meàm laø raøng buoäc khoâng baét buoäc phaûi thoaû maõn. Muïc tieâu cuûa baøi toaùn laø thoaû maõn taát caû raøng buoäc cöùng vaø toái thieåu soá raøng buoäc meàm vi phaïm.

Ñaëc ñieåm naøy cuûa baøi toaùn raøng buoäc quaù möùc ñaõ gaây khoù khaên cho kyõ thuaät Tu chænh laëp coù troïng soá. Bôûi vì, giaûi thuaät naøy duøng troïng soá ñeå phaân bieät raøng buoäc cöùng vaø raøng buoäc meàm. Tuy nhieân, trong suoát quaù trình tìm kieám, vieäc taêng troïng soá cuûa raøng buoäc vi phaïm seõ laøm “meùo moù” troïng soá ban ñaàu chæ ñoä quan troïng töông ñoái giöõa caùc raøng buoäc. Keát quaû laø troïng soá cuûa raøng buoäc meàm coù theå ngang baèng hay lôùn hôn raøng buoäc cöùng.

Vì theá, giaûi thuaät seõ khoâng theå tìm thaáy lôøi giaûi khaû thi. Ñeå coù theå öùng duïng giaûi thuaät Tu chænh laëp coù troïng soá vaøo baøi toaùn xeáp lòch tröïc y taù, taùc giaû seõ döïa vaøo khaùi nieäm “laëp laïi” raøng buoäc cuûa Cha et al. vaø choïn xaây döïng giaûi thuaät theo höôùng “hoïc hoûi” cuûa Thornton vaø Sattar. Maëc khaùc, khoâng gioáng nhö caùc phöông phaùp giaûi quyeát cho baøi toaùn xeáp lòch tröïc y taù tröôùc, taùc giaû choïn höôùng tieáp caän ñeå giaûi thuaät Tu chænh laëp coù troïng soá vöøa coù chöùc naêng xaây döïng lôøi giaûi khaû thi vöøa coù chöùc naêng toái öu lôøi giaûi.

Ñoàng thôøi qua ñoù taùc giaû cuõng muoán chöùng minh raèng caùc giaûi thuaät tìm kieám cuïc boä hoaøn toaøn khoâng bò leä thuoäc vaøo lôøi giaûi ban ñaàu. Trang i Giôùi thieäu ABSTRACT Weighted iterative repair technique originates from a simple idea. When stucking on a local optimum solution, the algorithm will increase weights of all violated constraints.