GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG TRONG HỖ TRỢ LẬP LỊCH ĐIỀU HÀNH CÔNG TÁC BỆNH VIỆN

Tóm tắt

Bài báo nghiên cứu đề xuất xây dựng mô hình bài toán hỗ trợ ra quyết định: hỗ trợ lập lịch công tác tại Bệnh viện. Đối với bài toán này, nhiều cán bộ cần được phân công trực, mỗi người có thể thực hiện nhiều nhiệm vụ khác nhau; mỗi thời điểm chỉ thực hiện duy nhất một nhiệm vụ. Trong khi đó, thời gian trực của các cán bộ phải tương đương nhau.

Để giải quyết, đầu tiên chúng tôi mô hình hóa toán học bài toán với 2 tập ràng buộc: cứng và mềm. Dựa trên mô hình toán học, chúng tôi thiết kế giải thuật di truyền để tìm các lời giải cho bài toán. Sau đó chúng tôi tiến hành chạy thử nghiệm nhiều lần trên bộ dữ liệu thực để kiểm tra phương án tốt nhất. Kết quả thu được kiểm nghiệm so sánh với kết quả của thuật toán leo đồi.

In this paper, we propose a model for a decision support problem: staff scheduling at the hospital. For this problem, a wide range of schedules will be applied for different kind of staff; each person may perform many various tasks but a single task at a certain point of time. Meanwhile, working time for staff is set equally.

Regarding the possible solution, we first try to derive a mathematical formulation of the problem with 2 sets of constraints: hard and soft. Based on the formulation, we design a genetic algorithm for finding solutions for this problem. To validate the proposal, we run multiple tests on a real dataset. The testing results are compared with findings of hill-climbing algorithm.

1. Giới thiệu

Giải thuật di truyền (GA) là một trong những mô hình tính toán phổ biến và thành công nhất trong lĩnh vực tính toán thông minh. Cùng với các kỹ thuật tính toán thông minh khác như tính toán mờ (fuzzy computing), mạng Nơ-ron (neural networks), hệ đa tác tử (multi agent systems), trí tuệ bầy đàn (swarm intelligence), giải thuật di truyền ngày càng phát triển, được áp dụng rộng rãi trong các lĩnh vực của cuộc sống. Có thể nói, GA đã bước đầu được áp dụng thành công trong các trường hợp, mà việc mô tả toán học cho bài toán gặp rất nhiều khó khăn. Ví dụ: các hệ thống phức hợp (complex systems) với các hàm mục tiêu ẩn và các mối ràng buộc phức tạp, các bài toán thiết kế với các hàm mục tiêu quá phức tạp không tuyến tính, hay các bài toán lập kế hoạch/lập lịch với không gian tìm kiếm NP-khó (NP-hard). Người đọc có thể xem thêm thông tin chi tiết tại [7].

Trong lĩnh vực lập lịch, giải thuật di truyền đã thu hút được rất nhiều các nghiên cứu và đề xuất. L do cho xu hướng này có thể thấy là bài toán lập lịch nhìn chung thuộc lớp các bài toán NP-khó và vì vậy, rất cần các giải thuật xấp xỉ [1]. Tính đến nay có rất nhiều các đề xuất sử dụng giải thuật di truyền cho bài toán lập lịch [2], [3], [4], [5], [6], [8], [9]. Tuy nhiên, một điều cần phải chỉ rõ ở đây là bài toán lập lịch là một trong những bài toán mà có nhiều thể loại đa dạng, mỗi một thể loại cần có thiết kế giải thuật di truyền đặc biệt. Về cơ bản, bài toán lập lịch được coi như là việc gán các mốc thời gian (time slots) thực hiện cho các công việc (tasks) sao cho phù hợp với khả năng về tài nguyên (resources). Tuy nhiên, sự đa dạng thể hiện ở các thể loại ràng buộc khác nhau và mỗi một bài toán thực tế sẽ có những ràng buộc đặc trưng riêng. Chính vì vậy, mà các nghiên cứu đề xuất giải thuật di truyền cho bài toán lập lịch luôn luôn là một chủ đề nóng.

Trong khuôn khổ bài báo này, các tác giả đã tìm hiểu bài toán lập lịch công tác tại Bệnh viện Mắt Trung Ương, cụ thể là lịch trực chuyên môn và phòng khám. Mục tiêu chính của bài toán là xếp lịch trực cho các cán bộ vào các bộ phận sao cho thời gian trực của các cán bộ tương đương nhau vì điều này ảnh hưởng trực tiếp đến quyền lợi cán bộ (nhiệm vụ và tiền trực).

Đóng góp chính của bài báo này bao gồm: Phân tích và xây dựng mô hình bài toán lập lịch công tác bệnh viện, sau đó thiết kế một giải thuật di truyền cho bài toán này. Chúng tôi đã sử dụng biểu diễn số nguyên, các toán tử lai ghép, đột biến và lựa chọn. Thực hiện phép tiến hóa qua nhiều thế hệ để chọn ra phương án phù hợp nhất. Kết quả thu được trên bộ dữ liệu thử nghiệm cho cho thấy các lịch tìm được đều thỏa mãn các ràng buộc của bài toán và đạt kết quả tốt về các giá trị hàm mục tiêu. Kết quả này cũng được kiểm chứng thông qua so sánh với giải thuật leo đồi.

Phần còn lại của bài báo được tổ chức như sau: phần 2- tổng quan về giải thuật di truyền, phần 3– bài toán lập lịch công tác tại Bệnh viện Mắt Trung Ương và mô hình toán học. Phần 4- Thiết kế giải thuật di truyền. Phần 5- Kế hoạch chạy thử. Phần cuối– kết luận.

2. Tổng quan về giải thuật di truyền

Giải thuật di truyền (hay giải thuật tiến hóa nói chung) là một trong những phát triển quan trọng của những nhà nghiên cứu về tính toán ứng dụng cuối thế kỷ trước trong việc giải xấp xỉ các bài toán tối ưu toàn cục. Việc khai thác nguyên lí tiến hóa như là một định hướng heuristics đã giúp cho giải thuật di truyền giải quyết hiệu quả các bài toán tối ưu (với các lời giải chấp nhận được) mà không cần sử dụng các điều kiện truyền thống (liên tục hay khả vi) như là điều kiện tiên quyết.

Một trong những đặc tính quan trọng của giải thuật di truyền là làm việc theo quần thể các giải pháp. Việc tìm kiếm bây giờ được thực hiện song song song trên nhiều điểm (multipoints). Tuy nhiên, đây không phải là là thuật toán tìm kiếm đa điểm đơn thuần vì các điểm có tương tác với nhau theo nguyên lí tiến hóa tự nhiên. Trong ngữ cảnh sử dụng giải thuật di truyền, người ta có thể dùng khái niệm “cá thể” tương đương với khái niệm “giải pháp”. Các bước cơ bản của giải thuật di truyền được mô tả như sau:

• Bước 1: t=0; Khởi tạo P(t) = {x1,x2,…,xN}, với N là tổng số lượng cá thể.
• Bước 2: Tính giá trị các hàm mục tiêu cho P(t).
• Bước 3: Tạo bể lai ghép MP = se{P(t)} với se là toán tử lựa chọn.
• Bước 4: Xác định P’(t) = cr{MP}, với cr là toán tử lai ghép.
• Bước 5: Xác định P”(t) = mu{P’(t)}, với mu là toán tử đột biến.
• Bước 6: Tính giá trị các hàm mục tiêu cho P”(t)
• Bước 7: Xác định P(t+1) = P”(t) và đặt t = t+1
• Bước 8: Quay lại Bước 3, nếu điều kiện dừng chưa thỏa mãn.

– Biểu diễn giải pháp: Đây là một trong những công việc quan trọng trong thiết kế giải thuật di truyền, quyết định việc áp dụng các toán tử tiến hóa. Một trong những biểu diễn truyền thống của GA là biểu diễn nhị phân. Với phép biểu diễn này, giải pháp cho một bài toán được biểu diễn như là một vector bit, còn gọi là nhiễm sắc thể. Mỗi nhiễm sắc thể bao gồm nhiều gen, trong đó một gen đại diện cho một tham số thành phần của giải pháp. Một kiểu biểu diễn khác cũng thường dùng là biểu diễn số thực. Với phép biểu diễn này, các toán tử tiến hóa sẽ thực hiện trực tiếp trên các giá trị số thực (genes).

– Lựa chọn: Việc lựa chọn các cá thể được thực hiện khi cần một số cá thể để thực hiện sinh sản ra thế hệ sau. Mỗi cá thể có một giá trị thích nghi (fitness). Giá trị này được dùng để quyết định xem lựa chọn cá thể nào. Một số phương pháp lựa chọn thường dùng bao gồm:

+ Roulette wheel: Dựa trên xác suất (tỷ lệ thuận với giá trị hàm thích nghi) để lựa chọn cá thể.

+ Giao đấu (nhị phân): Chỉ định ngẫu nhiên 2 cá thể, sau đó chọn cá thể tốt hơn trong hai cá thể đó.

– Lai ghép: Toán tử lai ghép được áp dụng nhằm sinh ra các cá thể con mới từ các cá thể cha mẹ, thừa hưởng các đặc tính tốt từ cha mẹ. Trong ngữ cảnh tìm kiếm thì toán tử lai ghép thực hiện tìm kiếm xung quanh khu vực của các giải pháp biểu diễn bởi các cá thể cha mẹ.

– Đột biến: Tương tự như lai ghép, đột biến cũng là toán tử mô phỏng hiện tượng đột biến trong sinh học. Kết quả của đột biến thường sinh ra các cá thể mới khác biệt so với cá thể cha mẹ. Trong ngữ cảnh tìm kiếm, toán tử đột biến nhằm đưa quá trình tìm kiếm ra khỏi khu vực cục bộ địa phương.

3. Lập kế hoạch công tác cho cán bộ tại Bệnh viện Mắt Trung ương (TW)

3.1. Mô tả quy trình lập kế hoạch công tác

Tại Bệnh viện Mắt Trung Ương, hàng tháng Phòng Kế hoạch Tổng hợp (KHTH) phải lập kế hoạch trực dự kiến cho cán bộ; trình Ban Giám đốc duyệt; sau đó triển khai cho các đơn vị thực hiện. Kế hoạch trực dự kiến cho số lượng lớn cán bộ và các bộ phận công tác khác nhau. Các cán bộ có thể tham gia trực khám chữa bệnh theo chuyên môn, trực phòng khám. Một cá nhân có thể tham gia trực các nhiệm vụ sau:

+ Trực chuyên môn: Bệnh viện có nhiều bộ phận chuyên môn. Mỗi ngày, các cán bộ trực phải được phân công theo đúng chuyên môn của mình. Đây là nhiệm vụ chính, ưu tiên hàng đầu của các cán bộ.

+ Trực phòng khám: Bệnh viện có nhiều phòng khám trực thuộc khoa. Nếu cán bộ đã trực chuyên môn thì không xếp trực phòng khám. Tùy từng bộ phận mà cán bộ được xếp phải trực cả ngày hoặc cả tuần.

+ Các bộ phận chuyên môn trực theo ngày: Ban Giám đốc, Đáy mắt, Glocom, Phòng mổ, . . . ; Các bộ phận chuyên môn trực theo tuần: Xquang, Dược, Gây mê, Ngân hàng mắt, Điện nước.

+ Các phòng khám trực theo ngày: Phòng khám giáo sư 1 & 2, tư vấn; Các phòng khám trực theo tuần: Tiểu phẫu, Chấn thương, Nhi 1, Nhi 2, Đáy mắt, … Một số bộ phận chỉ làm việc nửa ngày, do đó trong ngày chỉ cần xếp một cán bộ, thời gian trực tính bằng nửa ngày.

Cán bộ nào đi công tác hoặc nghỉ phép phải báo cho Phòng KHTH để phòng không xếp cán bộ đó trực thời gian này. Nếu lịch trực đã được trình lên và có chữ kí của Giám đốc thì không được phép sửa. Trường hợp cán bộ ốm đau, có việc đột xuất, … không thể trực được, cán bộ thay thế sẽ do Phòng KHTH sắp xếp và ghi vào nhật kí kiểm tra.

Mỗi ngày, một bộ phận chuyên môn hoặc một phòng khám phải có bác sĩ và ít nhất 1 điều dưỡng trực. Trong khi đó, cán bộ không thể thực hiện song song 2 nhiệm vụ, số lượng cán bộ thường xuyên có sự thay đổi: công tác, nghỉ phép, nhân viên mới, cán bộ nghỉ hưu, cán bộ thực tập. Nhiệm vụ là phải tìm ra phép gán cán bộ trực các khoảng thời gian của từng bộ phận theo các nhiệm vụ. Điều kiện lí tưởng là các bộ phận chuyên môn và phòng khám luôn có cán bộ trực, không xếp các cán bộ đang nghỉ phép, công tác phải trực, thời gian trực của các cán bộ tương đương nhau. Tuy nhiên, điều này không phải lúc nào cũng đạt được. Do có cán bộ phải công tác, nghỉ phép, mỗi bộ phận phải yêu cầu cán bộ đủ chuyên môn trực, không dễ dàng thay thế cán bộ từ bộ phận này sang bộ phận khác.

Thứ tự sắp xếp lịch như sau: Lịch trực chuyên môn được xếp trước, sau đó đến lịch trực phòng khám. Một phương án chấp nhận được của bài toán phải thỏa mãn các ràng buộc sau:

Ràng buộc cứng:- Tại mỗi thời điểm, cán bộ không được phép trực nhiều bộ phận (bao gồm: nếu cán bộ đã trực chuyên môn thì không xếp trực phòng khám).- Không xếp trực những cán bộ nghỉ theo chế độ, quy định của nhà nước hoặc của viện: công tác, đau ốm, thai sản, nghỉ phép, …- Mỗi ngày, mỗi bộ phận đều phải có cán bộ trực (bao gồm một bác sĩ và 1 điều dưỡng).- Mỗi cán bộ chỉ được phép làm việc ở một số bộ phận nhất định (ví dụ, phòng khám Giáo sư (GS) chỉ phân công giáo sư trực. Do đó, thời gian trực của phòng khám GS có thể rất lớn, không thể tương đương với các phòng khám khác).

Ràng buộc mềm:- Khoảng cách hai lần trực liên tiếp của một cán bộ càng xa nhau càng tốt.- Tránh xếp cán bộ trực một ngày cố định trong tuần.- Tổng thời gian trực của các cán bộ tương đương nhau, để đảm bảo chế độ và tiền trực đều nhau.

Rõ ràng, bài toán lập lịch có thể chia ra thành 2 lớp bài toán độc lập là lập lịch cho bác sĩ và lập lịch cho điều dưỡng. Trong khuôn khổ bài báo, chúng tôi chỉ mô tả bài toán lập lịch cho bác sĩ.

3.2. Mô hình toán học

Xem bài gốc

4. Thiết kế giải thuật di truyền cho bài toán Lập lịch Bệnh viện Mắt Trung Ương

Xem bài gốc

5. Thực nghiệm

Xem bài gốc

6. Kết luận

Trong bài báo này, chúng tôi đưa ra vấn đề xếp lịch công tác tại Bệnh viện Mắt Trung Ương. Đây vừa là một bài toán lập nhiều kế hoạch công tác có liên quan đến nhau, vừa là bài toán cấp phát tài nguyên. Để giải quyết vấn đề này, chúng tôi đã mô hình hóa toán học bài toán. Từ đó dùng giải thuật di truyền với biểu diễn nhiễm sắc thể số nguyên để xây dựng phần mềm hỗ trợ ra quyết định. Dữ liệu thử nghiệm và kiểm tra lấy trực tiếp Bệnh viện Mắt
Trung Ương.

Tài liệu tham khảo
[1] Burke, E. K., Kingston, J. H., & de Werra, D. (2004d). Applications to timetabling. In J. Gross & J. Yellen (Eds.), The handbook of graph theory (pp. 445–474). London: Chapman Hall/CRC.
[2] E. K. Burke, D. G. Elliman, P. H. Ford, and R. F. Weare, “Examination timetabling in british universities a survey,” in The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference (Lecture Notes in Computer Science 1153), E. Burke and P. Ross, Eds. Berlin, Germany: Springer Verlag, 1996, pp. 76–90.
[3] Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280.
[4] Burke, E. K., Elliman, D. G., & Weare, R. F. (1994). A genetic algorithm for university timetabling. In Proceedings of the AISB workshop on evolutionary computing, University of Leeds, UK, 11–13 April 1994.
[5] Colijn, A. W., & Layfield, C. (1995b). Interactive improvement of examination schedules. In E. K. Burke & P. Ross (Eds.), Proceedings of the 1st international conference on the practice and theory of automated timetabling (pp. 112–121), 30 August–1 September 1995. Edinburgh: Napier University.
[6] Corne, D., Ross, P., & Fang, H. (1994). Evolutionary timetabling: Practice, prospects and work in progress. In P. Prosser (Ed.), Proceedings of UK planning and scheduling SIG workshop.
[7] A. Konar, Computational Intelligence: Principles, Techniques and Applications, Springer, 2005.
[8] Ross, P., Hart, E., & Corne, D. (1998). Some observations about GAbased exam timetabling. In E. K. Burke & M. W. Carter (Eds.), Lecture notes in computer science: Vol. 1408. Practice and theory of automated timetabling II: selected papers from the 2nd international conference (pp. 115–129). Berlin: Springer.
[9] White, G. M., & Xie, B. S. (2001). Examination timetables and tabu search with longer-term memory. In E. K. Burke & W. Erben (Eds.), Lecture notes in computer science: Vol. 2079. Practice and theory of automated timetabling III: selected papers from the 3rd international conference (pp. 85–103). Berlin: Springer.