Muốn chia ca trực theo nguyện vọng cho công bằng, có ba cách làm đã được kiểm chứng: chọn lần lượt theo kiểu rắn bò (thứ tự đảo chiều sau mỗi lượt), đấu điểm (mỗi người có cùng số điểm để "đặt" vào ca mình muốn) và tối ưu tổng mức không hài lòng bằng thuật toán Hungary. Cách thứ ba tìm được phương án mà tổng thứ hạng nguyện vọng của cả nhóm nhỏ nhất, tính tay được với nhóm nhỏ. Dù chọn cách nào, những ca ai cũng ngại (đêm giao thừa, mùng Một Tết) nên được luân phiên qua các năm thay vì để thuật toán quyết một lần.
Bài toán: ai cũng có ý muốn, ca nào cũng phải có người
Một khoa có bốn bác sĩ trẻ cần chia bốn ca trực Tết: đêm 30, mùng 1, mùng 2, mùng 3, mỗi người một ca. Ai cũng muốn được ở nhà đêm giao thừa và sáng mùng Một, nhưng mức độ khác nhau: người quê xa muốn trực sớm để kịp về, người có con nhỏ muốn né mùng 1. Trưởng khoa có thể chỉ định, nhưng sẽ có người thấy mình bị thiệt mà không biết vì sao. Cách tốt hơn là thu nguyện vọng và dùng một quy tắc minh bạch.
Bài này bàn chuyện ai nhận ca nào khi đã có danh sách ca. Chuyện xếp lịch sao cho những người không được trùng ca không bị xếp cùng nhau là một bài toán khác (tô màu đồ thị), còn chia việc nhà hay việc nhóm thì có những phương pháp riêng.
Cách 1: chọn lần lượt kiểu rắn bò
Bốc thăm thứ tự, rồi lần lượt chọn ca. Khi mỗi người nhận nhiều ca (chẳng hạn 3 người chia 6 ca trực cuối tuần trong quý), dùng thứ tự đảo chiều: lượt 1 theo thứ tự A, B, C; lượt 2 theo C, B, A; lượt 3 lại A, B, C. Người chọn sau ở lượt này được chọn trước ở lượt sau, bù lại thiệt thòi.
| Lượt | Thứ tự chọn | Lượt chọn thứ |
|---|---|---|
| 1 | A, B, C | A: 1, B: 2, C: 3 |
| 2 | C, B, A | C: 4, B: 5, A: 6 |
Tổng "vị trí chọn" của mỗi người: A có 1 + 6 = 7, B có 2 + 5 = 7, C có 3 + 4 = 7. Bằng nhau tuyệt đối. Ưu điểm lớn của cách này là ai cũng hiểu, làm được trong năm phút ở phòng giao ban. Nhược điểm: khi chỉ có một lượt (mỗi người một ca), người bốc số cuối nhận ca còn lại, có khi là ca tệ nhất với chính mình trong khi một người khác lại không ngại ca đó lắm. Cách chọn lần lượt không nhìn thấy cường độ ưa ghét của từng người.
Cách 2: tối ưu tổng thứ hạng bằng thuật toán Hungary
Mỗi người xếp hạng bốn ca từ 1 (muốn nhất) đến 4 (ngại nhất). Mục tiêu: tìm cách giao ca sao cho tổng thứ hạng của cả nhóm nhỏ nhất. Bốn người thì có 4! = 24 cách, thử hết được; mười người đã là hơn ba triệu cách. Thuật toán Hungary, do Harold Kuhn công bố năm 1955 và đặt tên để ghi công hai nhà toán học Hungary là Dénes Kőnig và Jenő Egerváry, giải bài toán này rất nhanh mà không phải thử hết.
Bảng nguyện vọng
| Đêm 30 | Mùng 1 | Mùng 2 | Mùng 3 | |
|---|---|---|---|---|
| Bình | 4 | 3 | 1 | 2 |
| Cúc | 3 | 4 | 2 | 1 |
| Duy | 1 | 4 | 3 | 2 |
| Én | 2 | 4 | 3 | 1 |
Duy quê xa, muốn trực đêm 30 để mùng 1 về quê. Ba người còn lại đều xếp mùng 1 cuối hoặc gần cuối.
Bước 1: trừ theo hàng
Mỗi hàng trừ đi số nhỏ nhất của hàng đó (ở đây đều là 1). Ý nghĩa: ta chỉ quan tâm mỗi người "thiệt thêm" bao nhiêu so với ca tốt nhất của họ.
| Đêm 30 | Mùng 1 | Mùng 2 | Mùng 3 | |
|---|---|---|---|---|
| Bình | 3 | 2 | 0 | 1 |
| Cúc | 2 | 3 | 1 | 0 |
| Duy | 0 | 3 | 2 | 1 |
| Én | 1 | 3 | 2 | 0 |
Bước 2: trừ theo cột
Cột nào chưa có số 0 thì trừ đi số nhỏ nhất của cột. Chỉ cột mùng 1 cần trừ, nhỏ nhất là 2: cột này thành 0, 1, 1, 1.
| Đêm 30 | Mùng 1 | Mùng 2 | Mùng 3 | |
|---|---|---|---|---|
| Bình | 3 | 0 | 0 | 1 |
| Cúc | 2 | 1 | 1 | 0 |
| Duy | 0 | 1 | 2 | 1 |
| Én | 1 | 1 | 2 | 0 |
Bước 3: thử giao ca vào các ô 0
Cần bốn ô 0 không chung hàng, không chung cột. Cúc và Én đều chỉ có ô 0 ở mùng 3: không đủ. Kiểm bằng cách kẻ ít đường nhất che hết các số 0: hàng Bình, cột đêm 30, cột mùng 3, tổng 3 đường. Ít hơn 4 đường nghĩa là chưa giao được.
Bước 4: điều chỉnh
Trong các ô chưa bị che, số nhỏ nhất là 1. Trừ 1 ở mọi ô chưa bị che, cộng 1 ở những ô bị che hai lần (giao của hàng Bình với cột đêm 30 và cột mùng 3):
| Đêm 30 | Mùng 1 | Mùng 2 | Mùng 3 | |
|---|---|---|---|---|
| Bình | 4 | 0 | 0 | 2 |
| Cúc | 2 | 0 | 0 | 0 |
| Duy | 0 | 0 | 1 | 1 |
| Én | 1 | 0 | 1 | 0 |
Giờ chọn được bốn ô 0 độc lập. Duy nhận đêm 30, Én nhận mùng 3, còn Bình và Cúc chia mùng 1 và mùng 2. Có hai cách:
| Phương án | Bình | Cúc | Duy | Én | Tổng thứ hạng |
|---|---|---|---|---|---|
| I | mùng 2 (hạng 1) | mùng 1 (hạng 4) | đêm 30 (hạng 1) | mùng 3 (hạng 1) | 7 |
| II | mùng 1 (hạng 3) | mùng 2 (hạng 2) | đêm 30 (hạng 1) | mùng 3 (hạng 1) | 7 |
Tổng nhỏ nhất là 7 (thử cả 24 cách sẽ thấy không cách nào dưới 7, và còn một phương án thứ ba cũng bằng 7: Bình mùng 2, Cúc mùng 3, Én mùng 1). Kiểm nhanh: tổng các số đã trừ ở bước 1, 2, 4 là 4 + 2 + 1 = 7, đúng bằng tổng thứ hạng tối ưu. Đây là một mẹo kiểm tra hay của thuật toán.
Khi máy hoà, người phải quyết
Thuật toán chỉ nói: ai đó trong Bình, Cúc, Én phải nhận mùng 1, và mọi phương án tối ưu đều tốn tổng 7. Phương án I làm Cúc nhận ca tệ nhất của mình; phương án II chia đều hơn (không ai phải nhận hạng 4). Nếu tiêu chí là "người thiệt nhất thiệt ít nhất có thể", phương án II tốt hơn. Đây là chỗ con số tổng che giấu cảm nhận công bằng. Cách xử lý thường dùng:
- Phạt nặng hạng cuối: thay vì 1, 2, 3, 4, dùng thang 1, 2, 4, 8. Hạng cuối trở nên "đắt" và thuật toán tự tránh dồn ca tệ nhất cho một người.
- Sổ nợ ca: ai năm ngoái trực mùng 1 thì năm nay được đánh dấu, chi phí nhận mùng 1 của họ tăng thêm. Qua vài năm, ca tệ đi vòng quanh cả khoa.
Cách 3: đấu điểm
Mỗi người nhận cùng một số điểm, chẳng hạn 100, và phân điểm vào các ca theo mức mình muốn né (hoặc muốn nhận). Người rất ghét mùng 1 có thể dồn 70 điểm để né; người chỉ hơi ngại thì đặt 30. Hệ thống ưu tiên người đặt nhiều điểm hơn. Khác với xếp hạng, đấu điểm cho phép thể hiện cường độ: "tôi ghét mùng 1 gấp đôi anh".
Nhược điểm: đấu điểm mời gọi chiến thuật. Nếu ai cũng đoán người khác sẽ dồn điểm né mùng 1, bạn có thể tiết kiệm điểm ở mùng 1 và dồn sang ca khác. Các trường kinh doanh dùng đấu điểm để chia lớp học phần từ lâu và gặp đúng vấn đề này. Năm 2013, trường Wharton (Đại học Pennsylvania) chuyển sang hệ thống Course Match dựa trên công trình của Eric Budish, kết hợp ngân sách điểm ngang nhau với một cơ chế giá nội bộ để giảm chiến thuật mà vẫn giữ được cường độ ưa thích. Với một khoa vài người, phiên bản đơn giản là cho đấu điểm một lần, công bố kết quả, rồi luân phiên ca tệ qua các năm.
So sánh ba cách
| Cách | Dễ hiểu | Thấy cường độ ưa ghét | Chống chiến thuật | Hợp khi |
|---|---|---|---|---|
| Chọn lần lượt kiểu rắn bò | Rất dễ | Không | Khá: lượt cuối chọn thật lòng là tốt nhất, lượt đầu có thể tính chọn trước ca dễ bị tranh | Mỗi người nhận nhiều ca |
| Thuật toán Hungary trên thứ hạng | Cần giải thích | Một phần (qua thang điểm) | Không hoàn toàn: có thể khai hạng sai để né | Nhóm cần tổng hài lòng cao, có người điều phối tin cậy |
| Đấu điểm | Dễ | Có | Kém nếu chỉ chạy một lần | Có nhiều ca khác hẳn nhau về mức nặng nhẹ |
Một lưu ý về chống chiến thuật của thuật toán Hungary: vì nó tối thiểu tổng, một người có thể khai phóng đại mức ghét một ca để đẩy ca đó sang người khác. Trong nhóm nhỏ quen nhau, việc này ít xảy ra và dễ bị nhận ra; trong hệ thống lớn ẩn danh thì nên kết hợp với luân phiên hoặc giới hạn kiểu "mỗi người chỉ được đánh hạng 4 cho đúng một ca".
Góc nhìn hôm nay: quy trình gợi ý cho một khoa, một ca kíp
- Lập danh sách ca và công bố luật trước: cách thu nguyện vọng, thang điểm, cách xử lý hoà, sổ nợ ca.
- Mỗi người xếp hạng (hoặc phân điểm) riêng, nộp kín.
- Chạy thuật toán (bảng tính có công cụ giải bài toán giao việc; nhóm dưới mười người làm tay được), xem các phương án hoà nếu có.
- Chọn phương án hoà theo tiêu chí đã công bố, ghi sổ nợ ca cho năm sau.
- Cho phép đổi ca tự nguyện sau khi có lịch, miễn hai bên đồng ý và báo người điều phối.
Lịch trực cũng phải tuân thủ quy định về thời giờ làm việc, nghỉ ngơi của Bộ luật Lao động 2019 và quy chế riêng của ngành; thuật toán chỉ chọn trong số những phương án hợp lệ. Người muốn đọc thêm có thể tìm bài gốc "The Hungarian Method for the Assignment Problem" của Harold Kuhn (1955) và các tài liệu về "nurse rostering", bài toán xếp ca điều dưỡng được nghiên cứu nhiều trong vận trù học.
Câu hỏi thường gặp
Chia ca trực theo nguyện vọng thế nào cho công bằng?
Có ba cách phổ biến: bốc thăm rồi chọn lần lượt theo kiểu rắn bò, tối ưu tổng thứ hạng nguyện vọng bằng thuật toán Hungary, hoặc cho mỗi người cùng số điểm để đấu vào ca. Những ca ai cũng ngại như đêm giao thừa nên luân phiên qua các năm bằng sổ nợ ca.
Thuật toán Hungary là gì?
Là thuật toán giải bài toán giao việc: giao n việc cho n người sao cho tổng chi phí hoặc tổng mức không hài lòng nhỏ nhất. Harold Kuhn công bố năm 1955 và đặt tên để ghi công hai nhà toán học Hungary Kőnig và Egerváry. Các bước chính là trừ theo hàng, trừ theo cột, kẻ đường che số 0 và điều chỉnh.
Chọn lần lượt kiểu rắn bò là gì?
Là cách chọn mà thứ tự đảo chiều sau mỗi lượt: A, B, C rồi C, B, A. Người chọn cuối lượt này được chọn đầu lượt sau, nên tổng vị trí chọn của mọi người bằng nhau khi số lượt chẵn.
Ai phải trực mùng 1 Tết khi không ai muốn?
Thuật toán chỉ cho biết các phương án ít thiệt hại nhất cho cả nhóm, thường có nhiều phương án hoà nhau. Nên chọn theo tiêu chí công bố trước, chẳng hạn người chưa trực mùng 1 lâu nhất, và ghi sổ để năm sau luân phiên.
Đấu điểm chia ca có nhược điểm gì?
Đấu điểm cho thấy ai ghét ca nào nhiều hơn, nhưng dễ bị chiến thuật: người ta đoán người khác đặt bao nhiêu điểm rồi đặt theo đó thay vì theo ý thật. Chạy lặp lại nhiều kỳ và luân phiên ca nặng giúp giảm vấn đề này.