GIỚI THIỆU
Giới thiệu đề tài
Công việc xếp lịch trực cho y tá là một nhiệm vụ phức tạp và tốn thời gian, nhưng hiện tại vẫn chủ yếu được thực hiện thủ công tại Việt Nam Do đó, việc nghiên cứu và phát triển các giải pháp tự động hóa cho vấn đề này là vô cùng cần thiết.
Bài toán xếp lịch trực cho y tá đã được nghiên cứu và phát triển từ những năm 1980, với nhiều thành công nhất định qua các giai đoạn Mặc dù đã có nhiều sản phẩm được áp dụng tại các bệnh viện trên thế giới, nhưng vẫn chưa có giải pháp nào hoàn hảo cho tất cả các tình huống Đặc điểm riêng biệt của bài toán này khiến nó trở thành một lĩnh vực nghiên cứu tiềm năng cho nhiều nhà khoa học.
Từ những năm 1980, kỹ thuật tìm kiếm cục bộ (Local Search) đã thu hút sự chú ý lớn nhờ khả năng giải quyết các bài toán phức tạp Một ứng dụng tiêu biểu của phương pháp này là bài toán xếp lịch, trong đó bài toán phân công trực cho y tá nổi bật như một ví dụ điển hình.
Tác giả nghiên cứu giải thuật tìm kiếm cục bộ với kỹ thuật Tu chỉnh lặp có trọng số (Weighted Iterative Repair) Mặc dù kỹ thuật này đã được nghiên cứu và thành công từ lâu, nhưng vẫn còn nhiều điều mới mẻ khi áp dụng cho bài toán thỏa mãn ràng buộc quá mức, như trong bài toán phân công trực y tá.
Bài toán xếp lịch trực y tá
Công việc xếp lịch trực y tá thường tốn nhiều thời gian và công sức, dẫn đến kết quả không tối ưu Do đó, nhiều quốc gia tiên tiến hiện nay đã áp dụng mô hình hóa và giải pháp máy tính để cải thiện quy trình này.
Bài toán thường được phân chia thành 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 lệ bắt buộc phải tuân thủ, trong khi ràng buộc mềm là các yêu cầu hay mong muốn từ phía các y tá, không bắt buộc phải đáp ứng hoàn toàn và được sử dụng để tối ưu hóa bài toán.
Bài toán xếp lịch trực y tá không chỉ tuân theo quy định của luật lao động mà còn có những đặc trưng riêng biệt Do đó, việc lựa chọn một mô hình tiêu biểu để đại diện cho bài toán này là rất cần thiết Tác giả đã chọn Bệnh viện Nhi Đồng I và Bệnh viện Chợ Rẫy, hai cơ sở y tế lớn tại thành phố, với mô hình phân công trực y tá phổ biến ở Việt Nam.
Bài toán được xây dựng dựa trên mô hình trực ba ca bốn kíp cho các khoa lớn với khối lượng công việc lớn Trong khi đó, những khoa nhỏ với nhu cầu y tá ít và thời gian trực không cần quá chặt chẽ thường áp dụng mô hình hai ca trực.
Mô hình trực ba ca:
- Ca Sáng: từ 7 giờ sáng đến 3 giờ chiều
- Ca Chiều: từ 3 giờ chiều đến 9 giờ tối
- Ca Đêm: từ 9 giờ tối đến 7 giờ sáng ngày hôm sau
Bài toán xếp lịch trực cho y tá được coi là một thách thức lớn do quy mô và độ phức tạp của các ràng buộc Với số lượng ràng buộc rất lớn, mục tiêu chính của bài toán là tìm ra giải pháp đáp ứng tất cả các ràng buộc cứng (ký hiệu C) và giảm thiểu số vi phạm các ràng buộc mềm (ký hiệu M).
1.2.2 Các ràng buộc của bài toán
• Quy định của luật lao động: (C)
- Thời gian nghỉ phép một năm là 12 ngày
- Thời gian nghỉ giữa các ca trực ít nhất phải là 2 ca
Ví dụ: nếu một y tá làm ca tối hôm nay thì không thể phân vào ca trực sáng hay chiều hôm sau
• Quy định của bệnh viện: bao gồm một số nhóm chính sau:
- Ràng buộc nhân công (C): bao gồm số lượng y tá tối đa và tối thiểu trong mỗi ca trực
Ví dụ: Số y tá cần cho ca trực sáng tối thiểu là 4 và tối đa là 5
- Ràng buộc giờ làm việc (C):
Ví dụ: Một y tá phải làm việc từ 20 đến 23 ca trong giai đoạn 30 ngày
- Ràng buộc về sự phân bố ca:
Ví dụ: Khoảng cách giữa hai ca trực liên tục là 3 ca (M)
Sau một ca trực đêm phải là một ngày nghỉ (C)
• Yêu cầu của y tá: Đây là những mong muốn của chính các y tá cho lịch trực của họ Các yêu cầu này được phân làm 4 loại sau:
- Ưu tiên 1: những yêu cầu không quan trọng (M)
- Ưu tiên 2: những yêu cầu bình thường (M)
- Ưu tiên 3: những yêu cầu quan trọng không bắt buộc (M)
- Loại bắt buộc: những nguyện vọng cấp thiết hoặc đã hoạch định từ trước rất lâu cần phải được giải quyết (C)
- Số ca trực thêm hoặc số ca trực nợ phải được tính (C)
- Số ngày nghỉ phép chưa được sử dụng phải được phân bổ cho phù hợp (M)
Bài toán xếp lịch trực cho y tá được đánh giá rất phức tạp, xét theo hai cách nhìn sau:
Mô hình trực ba ca cho phép tìm kiếm trong không gian lớn, với 4 giá trị biểu diễn ca trực của mỗi y tá trong một ngày Điều này dẫn đến khoảng 4^4.720 lựa chọn cho lịch trực của 24 y tá trong 30 ngày.
Trong môi trường làm việc hiện nay, có rất nhiều ràng buộc cần phải thỏa mãn, bao gồm ràng buộc về nhân công, giờ làm việc và sự phân bố ca Bên cạnh đó, còn tồn tại những ràng buộc phát sinh từ mong muốn của người lao động như y tá và bác sĩ, điều này tạo ra áp lực cho việc quản lý và tổ chức công việc hiệu quả.
Dựa theo những tiêu chí trên, bài toán xếp lịch trực y tá được xếp vào nhóm bài toán
NP-hard và có số ràng buộc quá mức (over-constrained)
Luận văn được tổ chức thành 6 chương:
1 Chương thứ nhất giới thiệu về đề tài
2 Chương thứ hai giới thiệu các phương pháp giải quyết bài toán xếp lịch trực y tá và 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ố
3 Chương thứ ba trình bày phương hướng ứng dụng kỹ thuật 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á, đồng thời đề xuất phương án giải quyết cho các ràng buộc đa biến và kết hợp một số heuristic để tăng độ hiệu quả của giải thuật
4 Chương thứ tư trình bày thiết kế thư viện cho giải thuật Tu chỉnh lặp có trọng số và mô hình ứng dụng xếp lịch trực y tá
5 Chương thứ năm trình bày các phương án chạy thử nghiệm chương trình, các kết quả thử nghiệm, sau đó tiến hành nhận xét và phân tích các kết quả đó
6 Chương cuối cùng kết luận lại những kết quả đã đạt được trong luận văn đồng thời đề xuất hướng nghiên cứu mở rộng cho đề tài sau này.
CÁC NGHIÊN CỨU LIÊN QUAN
Các nghiên cứu liên quan đến bài toán xếp lịch trực y tá
Bài toán phân công trực y tá đã được quan tâm nghiên cứu phát triển từ những năm
Kể từ năm 1970, ngành công nghiệp đã trải qua nhiều giai đoạn phát triển và đạt được những thành công đáng kể, với nhiều sản phẩm được áp dụng trong các bệnh viện trên toàn thế giới Qua quá trình phát triển, có hai xu hướng lớn trong việc giải quyết bài toán, đó là phương pháp quy hoạch toán học và lập trình ràng buộc.
2.1.1 Qui hoạch toán học ( Mathematical Programming )
Vào thập niên 1970, sự phát triển mạnh mẽ của phần cứng máy tính đã dẫn đến sự ra đời của lập trình toán học, một xu hướng lập trình mới Phương pháp này nổi bật với khả năng giải quyết hiệu quả các bài toán tối ưu, đánh dấu một bước ngoặt quan trọng trong việc tìm kiếm lời giải tối ưu cho các bài toán xếp lịch.
Phương pháp lập trình toán học cho bài toán xếp lịch trực y tá được phân thành ba loại chính dựa trên kỹ thuật tính toán, bao gồm quy hoạch tuyến tính, quy hoạch nguyên và quy hoạch mục tiêu.
• Qui hoạch tuyến tính ( Linear Programming )
Quy hoạch tuyến tính là phương pháp tìm kiếm giải pháp tối ưu cho các hàm mục tiêu trong khi vẫn đảm bảo các ràng buộc Mặc dù nghiệm của quy hoạch tuyến tính thường không nguyên, nhưng trong bài toán xếp lịch trực y tá yêu cầu nghiệm phải là nguyên, phương pháp này vẫn có thể áp dụng hiệu quả cho một số bài toán xếp lịch nhân viên.
Năm 1973, Rothstein áp dụng quy hoạch tuyến tính để xếp lịch cho nhân viên nhà bếp của bệnh viện, nhưng không áp dụng cho việc xếp lịch trực y tá Ông dựa vào số ngày nghỉ để tối đa hóa khoảng cách giữa hai ngày nghỉ liên tiếp trong tuần làm việc 5 ngày Mặc dù bài toán được lập trình theo quy hoạch tuyến tính với lời giải nguyên, phương pháp này chỉ giải quyết được một số ít bài toán và không thể mở rộng cho việc xếp lịch trực y tá thực tế.
• Qui hoạch nguyên ( Integer Programming )
Quy hoạch nguyên được thiết kế để tìm ra các lời giải có giá trị nguyên cho bài toán quy hoạch tuyến tính, nhưng chi phí tính toán của nó rất cao Điều này khiến cho việc xử lý các mô hình có số lượng biến lớn trở nên phức tạp Do đó, không tồn tại một phương pháp quy hoạch nguyên chuẩn cho bài toán xếp lịch trực y tá Thay vào đó, các nhà nghiên cứu đã tập trung phát triển các nguyên lý quy hoạch nguyên đặc biệt để đáp ứng các yêu cầu của bài toán này.
Quy hoạch đa chọn lọc ( Multiple Choice Programming )
Warner (1976) áp dụng nguyên lý quy hoạch đa chọn lọc để giải quyết bài toán xếp lịch trực y tá tại bệnh viện của trường đại học Michigan Phương pháp này tìm kiếm sự kết hợp tối ưu từ các lời giải khả thi, kết hợp các lịch trực cho đến khi đạt được giải pháp tốt nhất cho nhân viên cuối cùng Ở bước tiếp theo, nguyên lý này tính toán lịch trực tối ưu dựa trên mức độ yêu thích của y tá Trong cả hai bước, quy hoạch đa chọn lọc sử dụng phương pháp quy hoạch tuyến tính để tìm ra lời giải ban đầu, sau đó tiến hành tìm kiếm lời giải nguyên tốt nhất.
Y tá 1: Các lịch trực khả thi
Y tá 2: Các lịch trực khả thi
Y tá 25: Các lịch trực khả thi
Lịch trực tốt nhất cho Y tá 1
Lịch trực tốt nhất cho Y tá 2
Lịch trực tốt nhất cho Y tá 25
Hình 2-1: Ví dụ một bảng phân công trực cho 25 y tá
Warner giả định rằng mỗi y tá chỉ có từ 10 đến 20 lịch trực trong một bảng phân công hai tuần, nhưng thực tế con số này cao hơn nhiều Do đó, phương pháp của Warner chỉ phù hợp với các bài toán xếp lịch trực y tá có mô hình nhỏ và đơn giản.
• Qui hoạch mục tiêu ( Goal Programming )
Quy hoạch mục tiêu là một dạng đặc biệt của quy hoạch nguyên, cho phép tồn tại nhiều mục tiêu đồng thời, có thể là cực đại, cực tiểu hoặc theo thứ tự ưu tiên nhất định Phương pháp này, còn được gọi là quy hoạch đa mục tiêu, nổi bật với khả năng điều chỉnh mức độ quan trọng giữa các mục tiêu dựa trên sở thích của người sử dụng Tuy nhiên, sự linh hoạt này đi kèm với chi phí tính toán phức tạp cho hàm mục tiêu.
Vào thập niên 1980, các nghiên cứu về bài toán xếp lịch trực y tá thường thiếu tính linh hoạt, với các mô hình được xây dựng dựa trên một tập hợp các mục tiêu cố định mà mỗi tác giả đề xuất.
Vào năm 1988, Ozharahan và Bailey đã phát triển phương pháp lập kế hoạch mục tiêu cho bài toán xếp lịch trực y tá, đóng vai trò quan trọng trong hệ thống hỗ trợ quyết định linh hoạt Nghiên cứu này khác biệt so với các nghiên cứu trước đó khi xác định thời gian ca trực từ 8 đến 10 giờ Dù đạt được một số thành công nhất định, nghiên cứu chỉ áp dụng cho bảng phân công trong một tuần.
Phương pháp lập trình toán học chủ yếu được áp dụng để giải quyết các mô hình bài toán phân công nhỏ và đơn giản Dù các nhà nghiên cứu đã cố gắng mở rộng mô hình bằng cách nới lỏng các ràng buộc, nhưng vẫn tồn tại nhiều hạn chế trong việc áp dụng lập trình toán học cho bài toán xếp lịch trực y tá thực tế.
2.1.2 Lập trình ràng buộc ( Constraint Programming )
Ràng buộc là một đặc tính phổ quát trong cuộc sống, xuất hiện trong mọi khía cạnh Vấn đề quan trọng là làm thế nào để nhận dạng và mô hình hóa ràng buộc này Từ những năm 70, cùng với sự phát triển của trí tuệ nhân tạo, nghiên cứu về ràng buộc đã dẫn đến sự ra đời của một mô hình lập trình mới, đó là lập trình ràng buộc.
Nhiều nhà nghiên cứu đã nhận thấy ưu điểm của phương pháp lập trình ràng buộc và bắt đầu áp dụng nó cho bài toán xếp lịch trực y tá Một trong những nghiên cứu tiêu biểu là của Abdennadhdr và Schlenker, được thực hiện cho bệnh viện ở Munich vào năm 1999.
[26], Andy Hon Wai Chun (xây dựng cho bệnh viện Authority ở Hồng Kông - 2000) [1],
• Dùng lập trình logic có ràng buộc
Hệ thống INTERDIP, được phát triển bởi Abdennadhdr và Schlenker vào năm 1999, nhằm mục đích xếp lịch trực cho y tá tại bệnh viện Munich, Đức Hệ thống này sử dụng ngôn ngữ lập trình IF/Prolog để giải quyết bài toán, trong đó các mối quan hệ được mô tả thông qua các luật vị từ (predicate).
Các nghiên cứu liên quan đến kỹ thuật tu chỉnh lặp
Các giải thuật tìm kiếm được phân loại thành hai nhóm chính: giải thuật hồi quy và giải thuật tìm kiếm cục bộ Trong đó, Kỹ thuật Tu chỉnh lặp có trọng số là một giải thuật cải tiến thuộc nhóm tìm kiếm cục bộ.
Các giải thuật tìm kiếm cục bộ bắt đầu bằng việc khởi tạo một lời giải ban đầu, có thể được tạo ra thông qua nhiều phương pháp như sử dụng giải thuật khác, gán ngẫu nhiên hoặc áp dụng các heuristic Sau đó, giải thuật sẽ tìm kiếm lời giải lân cận tốt hơn và quy trình này được lặp lại cho đến khi đạt được số lần lặp đã xác định Trong mỗi lần lặp, giải thuật chỉ khảo sát một phần của lời giải trước và nỗ lực cải tiến nó Tuy nhiên, một vấn đề phổ biến của các giải thuật này là khả năng bị mắc kẹt trong các cực tiểu địa phương.
Khi giải thuật rơi vào trạng thái "kẹt" ở mức tối ưu cục bộ, nó không thể tìm thấy lời giải lân cận tốt hơn Để vượt qua tình trạng này, nhiều kỹ thuật đã được đề xuất, bao gồm việc khởi động lại giải thuật từ một lời giải khác (GSAT của Selman et al., 1992), chọn ngẫu nhiên một lời giải lân cận không tốt hơn (kỹ thuật Mô phỏng luyện kim - Simulated Annealing - của Abramson, 1992), và lựa chọn lời giải tốt nhất mà không trùng lặp với những lời giải trước đó (Tabu của Glover, 1989).
Tu chỉnh lặp có trọng số là một phương pháp hiệu quả để giải quyết vấn đề tối ưu hóa khi gặp phải trạng thái tối thiểu cục bộ Bằng cách tăng trọng số của các ràng buộc vi phạm, thuật toán điều chỉnh giá trị chi phí của lời giải hiện tại, giúp tìm ra lời giải lân cận có thể chấp nhận được.
Việc áp dụng giải thuật vào bài toán giải hệ ràng buộc và bài toán ràng buộc quá mức không giống nhau, do đó, giải thuật này thường được phân chia thành hai nhóm: nhóm giải thuật dành cho bài toán thỏa mãn ràng buộc và nhóm giải thuật cho bài toán ràng buộc quá mức.
2.2.1 Tu chỉnh lặp có trọng số cho bài toán thoả mãn ràng buộc
Nhóm giải thuật này đã được phát triển từ sớm và đạt nhiều thành công nổi bật, với một số ví dụ tiêu biểu như Breakout (Morris, 1993), GENET (Tsang và Wang, 1992; Devenport và Tsang, 1994), Guided Local Search (Voudouris và Tsang, 1996), Discrete Lagrangian (Wu và Wah, 1999), và Weight GSAT (Selman, 1992).
Dưới đây sẽ trình bày hai giải thuật tiêu biểu nhất trong nhóm kỹ thuật Tu chỉnh lặp có trọng số cho các bài toán thoả mãn ràng buộc
Nhóm nghiên cứu từ Đại học Essex đã phát triển mô hình mạng GENET, kết hợp kỹ thuật Tu chỉnh lặp có trọng số với min-conflicts heuristic Vào năm 1991-1992, Tsang và Wang đã chứng minh thành công của GENET trong việc giải quyết các bài toán hệ ràng buộc song biến.
Năm 1994, A Davenport và Tsang đã cải tiến thuật toán GENET để giải quyết các bài toán hệ ràng buộc ngoài song biến Đồng thời, GENET cũng được nghiên cứu mở rộng để áp dụng cho các bài toán tối ưu hóa.
Bài toán thoả mãn ràng buộc có thể được mô hình hoá bởi mạng GENET như sau:
Mỗi nốt trong mô hình đại diện cho giá trị của một biến, và tất cả các nốt của biến đó tạo thành một nhóm (cluster) Nhóm này hình thành miền trị cho biến, với mỗi nốt có hai trạng thái: bật và tắt (on/off) Trong mỗi nhóm, chỉ có một nốt duy nhất ở trạng thái bật, tương ứng với giá trị hiện tại được chọn cho biến.
Mô hình ràng buộc tạo ra liên kết giữa các nốt, trong đó hai nốt thuộc hai nhóm khác nhau sẽ được kết nối bằng một liên kết cấm nếu chúng tương ứng với hai giá trị bị cấm Mỗi liên kết cấm được gán một trọng số âm, với giá trị khởi đầu của tất cả các liên kết cấm là -1.
Mỗi nốt trong nhóm sẽ được đánh giá thông qua hàm tính năng lượng sau:
Trong bài viết này, chúng ta định nghĩa các khái niệm quan trọng trong lý thuyết đồ thị: "adjacent(x,y)" là tập hợp các nốt y kề với nốt x, "wx,y" là trọng số của liên kết cấm giữa hai nốt x và y, và "sy" là trạng thái của nốt y, với giá trị 1 khi nốt y đang bật và 0 khi nốt y không hoạt động.
Sau khi đánh giá, mỗi nốt sẽ có giá trị năng lượng E tương ứng Trong mỗi nhóm, nốt có năng lượng E lớn nhất sẽ được bật, trong khi các nốt còn lại sẽ ở trạng thái tắt Điều này cho thấy GENET đánh giá tất cả các giá trị có thể của biến thông qua hàm E và chọn giá trị biến ít gây xung đột nhất với các biến khác.
Khi khảo sát các giá trị của biến, có thể phát hiện nhiều nốt có cùng năng lượng E lớn nhất Tình huống này có thể xảy ra trong hai trường hợp khác nhau.
- Nếu một trong những nốt này đã ở trạng thái bật thì giữ nguyên trạng thái của noát (tình huoáng 1)
- Nếu không có nốt nào trong những nốt này ở trạng thái bật thì bật ngẫu nhiên một nốt (tình huống 2)
Sau nhiều lần lặp, mạng có thể đạt trạng thái hội tụ, trong đó không có nốt bật nào có E nhỏ hơn các nốt khác trong cùng nhóm GENET sẽ kiểm tra xem trạng thái này có phải là giải pháp cho bài toán hay không Nếu tất cả các nốt bật đều có E=0, thì đây chính là giải pháp; ngược lại, mạng đang ở trạng thái tối thiểu cục bộ Khi đó, trọng số của các liên kết sẽ được tính lại theo công thức: \( w'_{ij} = w_{ij} - s_j \times s_i \).
Trọng số của các liên kết sẽ giảm cho đến khi giải thuật vượt qua trạng thái tối thiểu cục bộ, đánh dấu quá trình "học hỏi" của GENET Để minh họa cho kỹ thuật GENET, chúng ta sẽ khảo sát một bài toán cụ thể.
Cho 5 biến A, B, C, D, E có cùng miền trị { }1,2,3 Tìm các giá trị của biến thoả:
- Tổng của các biến A+B, B+C, C+D, D+E là chẳn
Hình 2-2: Ví dụ một bài toán thoả mãn ràng buộc có 5 biến A, B, C, D, E
Sau đây, bài toán trên sẽ được mô hình hoá theo GENET (hình 2-3) Mỗi biến A, B,
Hướng nghiên cứu của luận văn
Mục tiêu của luận văn là nghiên cứu ứng dụng kỹ thuật Tu chỉnh lặp có trọng số vào bài toán ràng buộc quá mức, cụ thể là bài toán xếp lịch trực y tá Để đánh giá hiệu quả của giải thuật, tác giả sẽ tiến hành so sánh với giải thuật tìm kiếm Tabu được trình bày trong luận văn cao học của Bùi Văn Quang (2004).
Ngoài ra, khi đánh giá hai giải thuật, tác giả sẽ dựa vào các tiêu chí sau: (xem chương
- Khả năng tìm thấy lời giải khả thi
- Chất lượng của lời giải
- Thời gian thực thi của giải thuật
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)
Kỹ thuật Iterative Repair kết hợp giữa tìm kiếm cục bộ và đánh giá trọng số của các ràng buộc, trong đó mỗi ràng buộc được gán một trọng số phản ánh độ ưu tiên cần được thoả mãn Thuật toán sẽ tìm kiếm lời giải lân cận tốt hơn từ lời giải ban đầu, và chất lượng của lời giải được đánh giá thông qua hàm tính chi phí.
) ( cost s ci constra penalty ci s weight ci
In this context, "cost" refers to the total weight of the constraints, while "weight" denotes the significance of a specific constraint Additionally, "penalty" is the function used to calculate the degree of violation associated with a constraint.
Trong mỗi lần lặp, giải thuật đánh giá hàm chi phí và chấp nhận lời giải mới nếu nó tốt hơn lời giải hiện tại Quá trình này giúp giải thuật dần cải thiện từ lời giải thô ban đầu, tạo ra những lời giải tốt hơn qua từng lần lặp.
Khi gặp phải trạng thái tối thiểu cục bộ, giải thuật sẽ điều chỉnh trọng số của các ràng buộc vi phạm, làm thay đổi giá trị chi phí của giải pháp hiện tại cho đến khi một giải pháp lân cận trở nên chấp nhận được Trong quá trình cải tiến giải pháp, giải thuật "học hỏi" dần thông qua việc điều chỉnh trọng số của các ràng buộc, giúp các ràng buộc khó được thỏa mãn trước tiên.
Ví dụ minh hoạ phương pháp thoát khỏi trạng thái tối thiểu cục bộ của giải thuật Tu chỉnh lặp có trọng số:
Xem xét bài toán tô màu đồ thị có số ràng buộc quá mức sau [12]:
Các nốt a, b, c, d đại diện cho các biến cần tô màu, với miền trị là {đỏ, xanh} Các cung cab, cac, cbc, cbd và ccd biểu thị các ràng buộc a≠b, a≠c, b≠c, b≠d và c≠d Mỗi ràng buộc vi phạm sẽ bị phạt bằng cách tăng thêm một giá trị chi phí w vào mức tối thiểu cục bộ.
Hình 3.1(a) cho thấy trạng thái tối thiểu cục bộ với chi phí là 2w Thuật toán sẽ tăng trọng số của các ràng buộc vi phạm, dẫn đến chi phí giải pháp tăng lên 4w, giúp tìm ra lời giải lân cận có chi phí thấp hơn Hình 3.1(b) minh họa một lời giải mới khi giá trị biến d chuyển từ đỏ sang xanh, với chi phí là 3w Tiếp theo, thuật toán chuyển giá trị biến b từ xanh sang đỏ, sau hai lần chuyển, chi phí của lời giải giảm xuống còn w, tối ưu hơn so với lời giải ban đầu (hình 3.1c).
(a) tối thiểu cục bộ, chi phí 2w
(b) sau khi taêng trọng số, chi phí 3w
(c) lời giải sau cùng, chi phí w
Hình 3-1: Ví dụ bài toán tô màu đồ thị có số ràng buộc quá mức
3.1.1 Mối quan hệ giữa lượng thông tin, chi phí và số lần lặp
Giải thuật Tu chỉnh lặp có trọng số hoạt động dựa trên việc sử dụng thông tin từ các lần lặp trước để cải thiện hiệu quả tìm kiếm lời giải mới Việc này mang lại những kết quả đáng kể, nhưng cũng đi kèm với chi phí nhất định Nếu không có các heuristic mạnh mẽ, việc sử dụng quá nhiều thông tin có thể dẫn đến hiệu suất giảm, gây tác dụng ngược trong quá trình giải quyết bài toán.
Một câu hỏi quan trọng là cách sử dụng thông tin một cách hiệu quả Hình vẽ minh họa mối quan hệ giữa lượng thông tin, chi phí cho mỗi lần lặp và số lần chỉnh sửa trong thuật toán.
Hình 3-2: Mối quan hệ giữa lượng thông tin, chi phí và số lần lặp
Lượng thông tin trong hệ thống tỉ lệ nghịch với số lần lặp và tỉ lệ thuận với chi phí Hệ thống sử dụng ít thông tin có thể cần nhiều lần lặp hơn để đạt giải pháp, nhưng mỗi lần lặp sẽ tốn ít chi phí hơn Mục tiêu lý tưởng là tìm ra điểm cân bằng giữa lượng thông tin và tổng chi phí cho bài toán.
Sau nhiều thử nghiệm, các nhà nghiên cứu nhận thấy có hai yếu tố chính ảnh hưởng đến lượng thông tin và chi phí tính toán [21,22]
• Độ sâu của giải thuật: là độ nhìn trước (look-ahead) trong một lần tu chỉnh
Chiến lược với độ sâu 0 chỉ xem xét kết quả hiện tại, trong khi chiến lược với độ sâu 1 phân tích trạng thái kết quả sau khi thực hiện các điều chỉnh Một ví dụ điển hình cho chiến lược này là heuristic min-conflicts, phương pháp này sẽ đánh giá các xung đột tối thiểu để tìm ra giải pháp tối ưu.
Chi phí tính toán cho một lần lặp
Lượng thông tin và khả năng tu chỉnh được chọn lựa sao cho ít gây xung đột nhất Chiến lược với độ sâu 2 xem xét các khả năng tu chỉnh liên quan sau khi thực hiện tu chỉnh hiện tại Một số hệ thống áp dụng độ sâu thay đổi, vì việc điều chỉnh giá trị một biến có thể ảnh hưởng đến các biến khác, do đó cần thay đổi thêm nhiều biến khác để duy trì các ràng buộc trước Trong trường hợp này, độ sâu của hệ thống có thể thay đổi tùy theo tình huống.
Tiêu chuẩn đánh giá là công cụ quan trọng để đo lường chất lượng của các khả năng tu chỉnh Sau khi xác định tập hợp các khả năng, mỗi khả năng sẽ được đánh giá và chỉ một khả năng tốt nhất sẽ được chọn Một tiêu chuẩn đánh giá lý tưởng cần phải đo lường chính xác chất lượng kết quả, đảm bảo cả hai yếu tố: đạt được mục tiêu của bài toán và đáp ứng các ràng buộc đã đặt ra.
Có thể chia làm hai loại chiến lược thường được sử dụng:
- Less-informed heuristic: chiến lược sử dụng lượng thông tin ít, có độ sâu 0
Một số tiêu chuẩn thường sử dụng trong chiến lược này như: fitness, temporal dependents, distance of move [23], …
The more-informed heuristic, also known as the look-ahead heuristic, is a strategy that utilizes a large amount of information to make decisions A well-known example of this type of heuristic is the min-conflicts heuristic.
Việc áp dụng các heuristic rất linh hoạt, cho phép sử dụng nhiều chiến lược đồng thời để đánh giá hiệu quả Chẳng hạn, có thể kết hợp ba tiêu chí đánh giá như fitness, temporal dependents và distance of move, hoặc áp dụng nhiều độ sâu trong các thuật toán khác nhau.
PEBL (Plausible Explanation-based Learning) [21]
Nhiều thử nghiệm đã chỉ ra rằng không có chiến lược nào phù hợp hoàn toàn cho mọi bài toán Chẳng hạn, kỹ thuật nhìn trước tỏ ra đặc biệt hiệu quả đối với các bài toán nhỏ và khó, nhưng lại không mang lại kết quả tốt khi áp dụng cho những vấn đề lớn.
Tóm lại, lượng thông tin ảnh hưởng rất lớn đến chi phí tính toán của giải thuật
Ứ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á
TOÁN XẾP LỊCH TRỰC Y TÁ
3.2.1 Mô hình hoá bài toán
Bài toán xếp lịch trực y tá được mô tả như một hệ ràng buộc:
Giả sử cần xếp lịch cho N y tá trong M ngày Bài toán sẽ bao gồm các tập sau:
• Tập các biến V, mỗi biến vij đại diện cho ngày làm việc thứ j của y tá i:
• Tập các miền giá trị D, mỗi biến vij có một miền giá trị Dij tương ứng:
Theo yêu cầu của bài toán, các biến đều thuộc cùng miền giá trị, bao gồm các ca trực trong ngày: ca sáng, ca chiều, ca tối và ca ra trực (nghỉ).
D = {0, 1, 2, 3}, trong đó 0, 1, 2, 3 lần lượt đại diện cho các ca sáng, chiều, tối và nghỉ
3.2.2 Lựa chọn độ sâu cho giải thuật
Tác giả lựa chọn chiến lược độ sâu 1, dựa trên ý tưởng của heuristic chọn trị ít gây xung đột nhất (min-conflicts heuristic) [20,28]
Heuristic chọn trị ít gây xung đột nhất (min-conflicts heuristic)
Cho tập các biến, tập những ràng buộc song biến Hai biến được coi là xung đột (conflict) nếu giá trị của chúng vi phạm ràng buộc
Phương pháp này bao gồm việc chọn một biến đang vi phạm ràng buộc và tìm kiếm trong không gian các phép gán khả thi, đồng thời ưu tiên lựa chọn phương án gây ra ít tranh chấp nhất.
Trong phần này, tác giả không hoàn toàn tuân theo phương pháp chọn trị truyền thống, mà thay vào đó, lựa chọn phép gán dựa trên điểm đánh giá của lời giải Điểm đánh giá này thường phản ánh lời giải ít xung đột nhất Mặc dù tiêu chí lựa chọn có sự khác biệt, nhưng thuật toán vẫn đảm bảo độ nhìn trước là 1.
3.2.3 Lựa chọn tiêu chuẩn đánh giá
Bài toán ràng buộc quá mức có:
• Tập các trọng số của ràng buộc cứng:
• Tập các trọng số của ràng buộc mềm:
• Tập trạng thái của ràng buộc cứng:
CH = {chi}, với 0 ≤ i ≤ K-1, trong đó chi=1 nếu ràng buộc i thoả mãn, ngược lại chi=0 nếu vi phạm
• Tập trạng thái của ràng buộc mềm:
CS = {csi}, với 0 ≤ i ≤ V-1, trong đó csi=1 nếu ràng buộc i thoả mãn, ngược lại csi=0 nếu vi phạm
Cho số lần lặp lại ràng buộc cứng là n Hàm đánh giá lời giải được xây dựng như sau:
K i i ch ws cs wh n ores WeightedSc
Chất lượng lời giải được đánh giá qua giá trị điểm, khiến giải thuật tìm kiếm hướng tới những lời giải có điểm cao hơn Tuy điều này giúp tiếp cận lời giải tối ưu, nhưng giải thuật có thể bỏ lỡ do giá trị trọng số của các ràng buộc hiện tại làm cho những lời giải khác trở nên hấp dẫn hơn Do đó, giải thuật cần thêm một hàm đánh giá để phát hiện lời giải tối ưu.
V i i i cs iws SostScores với iwsi là trọng số ban đầu của các ràng buộc mềm
Hàm SoftScores xác định giá trị mục tiêu thực nhằm tìm ra lời giải tối ưu nhất Nó dựa trên điểm đánh giá ban đầu của các ràng buộc mềm.
Cách thức đánh giá lời giải đóng vai trò quan trọng trong việc nâng cao hiệu quả thực thi chương trình Vì vậy, việc lựa chọn phương pháp đánh giá cần được thực hiện một cách cẩn thận và có hệ thống.
Giải thuật chỉ khảo sát một phần của lời giải trong mỗi lần lặp, thay vì đánh giá toàn bộ giá trị mục tiêu Tác giả chỉ xem xét lời giải mới tại vùng khảo sát và tính độ sai biệt giá trị mục tiêu so với lời giải hiện tại Nếu độ sai biệt lớn hơn không, lời giải mới sẽ được chấp nhận và điểm ghi được sẽ bằng điểm của lời giải cũ cộng với độ sai biệt Phương pháp này được áp dụng trong cả hai trường hợp tính điểm, giúp tăng hiệu suất của giải thuật một cách rõ rệt.
Procedure Tính_độ_sai_biệt_so_với_lời_giải_hiện_tại (v, m,
For (mỗi ràng buộc ci mà có biến v tham gia)
If (giá trị mới m của biến v làm thay đổi trạng thái của ràng buộc) then
If (trạng thái mới của ràng buộc ci là thoả mãn) then
If (ci là ràng buộc cứng) then
If (ci là ràng buộc cứng) then
DecOfWeightedScores←DecOfWeightedScores - n×ci.weight Else
Hình 3-5: Giải thuật tính độ sai biệt giá trị mục tiêu so với lời giải hiện tại khi chọn giá trị m cho bieán v
3.2.4 Giải thuật Tu chỉnh lặp có trọng số ( Weighted Iterative Repair –
Sau đây là giải thuật Tu chỉnh lặp có trọng số hoàn chỉnh cho bài toán xếp lịch trực y tá (hình 3-6):
CurrentState←khởi tạo trạng thái hiện tại cho biến
While (BestSoftScores > DesiredScores và StuckCounter < MaxStuck) do
If (CurrentState không phải là trạng thái tối thiểu cục bộ) then
For (mỗi biến vi liên quan ít nhất một ràng buộc vi phạm) For (moói di chuyeồn mj trong mieàn trũ cuỷa vi)
Tính_độ_sai_biệt_so_với_lời_giải_hiện_tại
If (CurrentState khả thi và BestSoftScores < CurrentSoftScores) then
Tăng_trọng_số_ràng_buộc_vi_phạm
Hình 3-6: Giải thuật Tu chỉnh lặp có trọng số (WIR)
Một trong những thách thức lớn khi áp dụng giải thuật vào bài toán phân công trực y tá là khả năng không đáp ứng được các ràng buộc đa biến Giải thuật thường chỉ xem xét một biến tại mỗi lần điều chỉnh, dẫn đến việc chọn giá trị mới chỉ khi nó cải thiện giải pháp Tuy nhiên, việc thay đổi một biến có thể không đủ để thỏa mãn các ràng buộc đa biến, ngay cả khi chúng có trọng số lớn Điều này khiến giải thuật dễ bị mắc kẹt trong các ràng buộc mềm và chỉ đạt tối ưu cục bộ, mà không thể chuyển sang các vùng giải pháp khác Để khắc phục vấn đề này, cần có các phương pháp mới nhằm xử lý hiệu quả các ràng buộc đa biến.
Trong bài viết này, tác giả đề xuất một phương pháp mới để đánh giá ràng buộc đa biến với nhiều mức độ vi phạm, thay vì chỉ xem xét hai trạng thái thoả mãn hoặc vi phạm như thông thường Mỗi biến trong ràng buộc sẽ tham gia vào quá trình làm cho ràng buộc được thoả mãn, với trọng số w v cho từng biến Trọng số của ràng buộc được tính bằng tổng trọng số của các biến tham gia Mỗi biến có ba trạng thái tương ứng với các giá trị trọng số – wv, 0, và +wv, trong đó điểm mới là cho phép biến nhận trọng số âm, điều này sẽ được giải thích khi đi vào chi tiết ràng buộc cụ thể.
Trong bài toán phân công trực y tá có hai loại ràng buộc cứng đa biến:
- Ràng buộc về nhân lực trong một ngày: số y tá tối thiểu và tối đa trong một ca trực
- Ràng buộc số ngày làm việc hợp lệ trong một giai đoạn xếp lịch: số ngày làm việc tối thiểu và tối đa trong thời gian xếp lịch
Ràng buộc về nhân lực:
Trong một ngày có ba loại ca trực: ca sáng, ca trưa, ca tối (không kể ca ra nghỉ) Vì thế ràng buộc này sẽ có 6 thông số:
- Số y tá tối thiểu / tối đa cho ca sáng
- Số y tá tối thiểu / tối đa cho ca chiều
- Số y tá tối thiểu / tối đa cho ca tối
Trọng số của ràng buộc sẽ được phân chia đồng đều cho ba ca: sáng, chiều và tối Nếu mỗi nhóm có đủ số lượng y tá theo yêu cầu, toàn bộ ràng buộc sẽ nhận 1/3 trọng số của nhóm đó Nếu không đủ, trọng số của nhóm sẽ được tính toán theo cách khác.
YCTB YT if YT YCTB
DL: độ lệch so với số y tá yêu cầu trung bình
YT: số lượng y tá hiện có cho một loại ca trực
YCTB: số y tá yêu cầu trung bình cho một loại ca trực
Khi có sự thay đổi số lượng y tá trong ca trực, trọng số của ràng buộc sẽ tăng lên tương ứng với trọng số của biến đại diện cho ca trực đó, giúp cải thiện điểm của lời giải Giải thuật sẽ tiếp tục điều chỉnh từng biến trong ràng buộc đa biến cho đến khi đạt được sự thoả mãn cần thiết.
Việc cho phép biến nhận giá trị trọng số âm là hữu ích khi số y tá hiện có vượt quá hai lần số y tá yêu cầu trung bình Trị âm này dẫn đến độ lệch DL âm, khiến trọng số WG của ràng buộc cũng trở nên âm, do đó, điểm của lời giải bị giảm Theo nguyên tắc tu chỉnh, thuật toán sẽ cố gắng điều chỉnh số y tá trong ca trực về giá trị trung bình để tìm ra lời giải tốt hơn.
Phương pháp này nâng cao tính định hướng của các biến trong ràng buộc đa biến, giúp việc chọn trị trở nên hiệu quả hơn Nhờ vào cách tiếp cận này, vấn đề ràng buộc đa biến đã được giải quyết một cách toàn diện.
Số y tá tối thiểu cho ca sáng là 3 và tối đa là 5, với tổng trọng số yêu cầu nhân lực là 120 Ràng buộc này được chia thành ba nhóm, do đó trọng số cho ca sáng sẽ là 120/3 Số y tá cần trung bình cho ca sáng là 4, và mỗi biến tham gia vào ràng buộc nhóm ca sáng sẽ có trọng số là 40/4.
Xét một số trường hợp sau: so sánh giữa các số y tá hiện tại là 6, 7 và 9
So sánh giữa hai giá trị 6 và 7, nếu số y tá hiện tại là 7 thì độ lệch DL là 2 và trọng số WG×2 Do đó, trường hợp 6 y tá cho ca trực sáng sẽ có trọng số lớn hơn trường hợp 7 y tá Điều này hợp lý vì với 7 y tá, cần phải thay đổi giá trị của hai biến, trong khi với 6 y tá chỉ cần thay đổi một biến.
