Tổng quan luận án
Luận án tiến sĩ "Một số phương pháp tiếp cận cho bài toán lập lịch cá nhân" của nghiên cứu sinh Trang Hồng Sơn, chuyên ngành Khoa học máy tính (Mã số: 62480101), được thực hiện tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh dưới sự hướng dẫn của PGS. Huỳnh Tường Nguyên và PGS. Trần Văn Lăng.
Tính cấp thiết và khoảng trống nghiên cứu
Trong thực tế và công việc hàng ngày, việc sắp xếp khối lượng công việc vào các khoảng thời gian trống đóng vai trò quan trọng trong quản lý năng suất cá nhân và tập thể. Các ứng dụng quản trị tác vụ hiện nay như Microsoft To-Do, Google Tasks, Apple Reminders, Evernote, nTask, Todoist chủ yếu cung cấp giao diện trực quan hỗ trợ người dùng thao tác thủ công mà chưa hỗ trợ cơ chế tự động chia nhỏ công việc để tối ưu hóa việc phân bổ vào các khung thời gian trống. Khác với các hệ thống máy móc sản xuất, công việc của con người có thể phân chia linh hoạt thành nhiều phần nhỏ để bố trí vào các khung thời gian làm việc khác nhau. Tuy nhiên, nếu công việc bị chia quá nhỏ, sự phân mảnh sẽ làm phát sinh chi phí thời gian cho việc tái khởi động từng phần việc, làm giảm hiệu quả xử lý tổng thể. Do đó, việc thiết lập ràng buộc "công việc không được chia nhỏ hơn một ngưỡng xác định" ($split_{min}$ hay bounded-splitting) kết hợp với ràng buộc "chỉ sắp xếp công việc vào các khung thời gian làm việc có sẵn" ($available-windows$) là yêu cầu thực tiễn. Khi xét riêng lẻ từng ràng buộc, bài toán có thể tìm được lời giải tối ưu trong thời gian đa thức; nhưng khi kết hợp đồng thời cả hai ràng buộc, bài toán trở thành bài toán thuộc lớp NP-khó mạnh ($strongly\ NP-hard$).
Mục tiêu nghiên cứu
Luận án xác định 3 mục tiêu nghiên cứu cụ thể:
- O1: Nghiên cứu và đề xuất một số phương pháp tiếp cận để giải quyết bài toán lập lịch công việc cá nhân trên các bộ dữ liệu đầu vào có kích thước nhỏ và lớn, qua đó đề xuất lựa chọn phương pháp hiệu quả đối với từng loại dữ liệu đầu vào khác nhau.
- O2: Nghiên cứu giải quyết các bài toán lập lịch công việc cá nhân đặc thù có một số ràng buộc thường được sử dụng trong thực tế.
- O3: Nghiên cứu ứng dụng mở rộng bài toán lập lịch công việc cá nhân trên một nhóm nhiều người.
Câu hỏi nghiên cứu
Để hiện thực hóa các mục tiêu trên, luận án đặt ra 4 câu hỏi nghiên cứu cốt lõi:
- Cần có một khung tổng quát gồm những bước nào để giải quyết các bài toán lập lịch liên quan đến hai ràng buộc $split_{min}$ và $available-windows$?
- Những phương pháp tiếp cận nào có thể giải quyết bài toán một cách hiệu quả với dữ liệu đầu vào có kích thước lớn (quy mô hàng trăm đến hàng ngàn công việc)?
- Làm thế nào để mở rộng mô hình cho các bài toán đặc thù chứa thêm các ràng buộc thực tế như thời gian chuẩn bị ($setup-time$) hay hạn chót hoàn thành ($deadline$)?
- Mô hình và phương pháp giải quyết bài toán lập lịch cá nhân có thể mở rộng và áp dụng cho bài toán lập lịch làm việc nhóm ($teamwork\ scheduling$) của nhiều người như thế nào?
Đối tượng và phạm vi nghiên cứu
- Đối tượng nghiên cứu: Các phương pháp tiếp cận (chính xác, heuristic, metaheuristic, matheuristic) để giải quyết bài toán lập lịch công việc.
- Phạm vi nghiên cứu: Bài toán lập lịch công việc của từng cá nhân (mô hình một máy) và mở rộng cho bài toán lập lịch công việc của một nhóm người (mô hình nhiều máy song song), tập trung vào hàm mục tiêu tối thiểu hóa thời điểm hoàn thành tất cả các công việc ($C_{max}$).
Tổng quan tài liệu và vị trí của luận án
Các hướng nghiên cứu lập lịch trước đây
Luận án điểm lại hệ thống các hướng nghiên cứu lập lịch trong y văn:
- Lập lịch cấp phát tác vụ ($task\ allocation\ scheduling$): Nghiên cứu của Max Witteman và cộng sự (2020) về phân bổ bảo dưỡng máy bay thông qua bài toán đóng gói thùng có kích thước thay đổi ($time-constrained\ variable-sized\ bin\ packing$); Hussein M. và cộng sự (2020) giải quyết phân bổ tác vụ IoT dựa trên bài toán tập bao phủ ($set\ cover$); Xinye Chen và cộng sự (2020) về phân bổ nhiệm vụ trong hệ thống đa robot phân tán; Schwarzrock và cộng sự (2018) và Amorim và cộng sự (2020) ứng dụng thuật toán bầy đàn và bài toán phân công tổng quát ($GAP$) cho phương tiện bay không người lái (UAV).
- Lập lịch ràng buộc nguồn lực ($resource-constrained\ scheduling$): Các công trình giải quyết bài toán lập lịch dự án ràng buộc nguồn lực ($RCPSP$) của Chen Zhi (2019) với 17 quy tắc ưu tiên; Longqing Cui (2020) với tìm kiếm lân cận; HaoJie Chen (2019) với giải thuật di truyền; Humyun Fuad Rahman (2020) với giải thuật memetic; Balouka và Cohen (2021) với phương pháp phân tách Benders; Karam M. và cộng sự (2020) với học tăng cường. Tại Việt Nam, có nghiên cứu xếp thời khóa biểu đại học bằng metaheuristic của Phan và cộng sự (2014) và xếp phòng ký túc xá bằng mô phỏng luyện kim cải tiến của Lê (2018).
- Lập lịch công việc ($job\ scheduling$): Các khảo sát kinh điển về môi trường máy $general\ shop$ (open shop, flow shop, job shop, mixed shop) của Brucker (2007) và các nghiên cứu [32]–[49]. Các sách tổng quan của Leung (2004), Vincent & Billaut (2006), Robert & Vivien (2009), Schwindt & Zimmermann (2015), Pinedo (2016), Blazewicz và cộng sự (1991, 2019) ghi nhận các ràng buộc phổ biến như $precedence$, $preemption$, $batching$, $lot-sizing$, song chưa bao hàm ràng buộc $bounded-splitting$ ($split_{min}$) kết hợp với khung thời gian rảnh.
- Lập lịch với khung cửa sổ thời gian ($time-windows$) và bảo trì định kỳ ($periodic\ maintenance$): Nghiên cứu của Yang Zhang và cộng sự (2020) cho hệ thống sản phẩm - dịch vụ (PSS) sử dụng thuật toán chèn thời gian rảnh kết hợp NEH; nghiên cứu [51] cho máy song song giống hệt; Ting Wang và cộng sự (2020) với mô hình phân vùng tập hợp và thuật toán nhánh và giá ($branch\ and\ price$); Vitor Nesello và cộng sự (2018) với mô hình chỉ mục cung thời gian ($arc-time-indexed$).
Vị trí và các công trình tiền đề trực tiếp
Bài toán lập lịch công việc cá nhân trực tiếp liên quan đến ba công bố:
- Công trình [16] (2010): Lần đầu tiên giới thiệu bài toán lập lịch cá nhân với hai ràng buộc $available-windows$ và $split_{min}$, ký hiệu $1|r_i; d_i; prec; noatw; splitmin_i|\sum w_i U_i$, kết hợp xử lý ngôn ngữ tự nhiên để trích xuất tác vụ và giải thuật di truyền (GA) để tìm lời giải khả thi.
- Công trình [17] (2013): Mô hình hóa bài toán $1|splittable; split_{min}; available-windows|C_{max}$, chứng minh bài toán thuộc lớp NP-khó mạnh thông qua việc thu giảm đa thức từ bài toán 3-Partition ($3-Partition \le_p PSP$), công bố 5 tính chất của lời giải tối ưu và đề xuất 3 giải thuật heuristic dựa trên quy tắc LPT.
- Công trình [18] (2013): Đề xuất mô hình Quy hoạch tuyến tính nguyên hỗn hợp (MILP) cho bài toán $1|splittable; split_{min}; available-windows|C_{max}$, sử dụng các công cụ giải MILP solver (COIN-OR CBC, GLPK, GUROBI) cho các mẫu dữ liệu kích thước nhỏ và bổ sung 1 tính chất của lời giải tối ưu.
Khoảng trống nghiên cứu được lựa chọn giải quyết
Các nghiên cứu trước chỉ dừng lại ở việc đặt bài toán, chứng minh độ phức tạp và áp dụng mô hình MILP giải các bài toán cỡ nhỏ. Luận án lựa chọn giải quyết các khoảng trống còn tồn tại:
- Xây dựng một quy trình khung tổng quát gồm các bước tuần tự từ phân tích lý thuyết đến thực nghiệm để giải quyết bài toán lập lịch có hai ràng buộc $split_{min}$ và $available-windows$.
- Đề xuất các cấu trúc giải thuật nâng cao (heuristic mở rộng, metaheuristic, matheuristic) nhằm xử lý hiệu quả các bộ dữ liệu quy mô lớn (hàng trăm đến hàng ngàn công việc) trong thời gian tính toán chấp nhận được.
- Mở rộng mô hình lý thuyết và giải thuật cho các bài toán đặc thù thực tế: bổ sung thời gian chuẩn bị ($setup-time$), thời hạn bắt buộc ($deadline$) và mở rộng từ cá nhân sang lập lịch nhóm ($teamwork\ scheduling$).
Cơ sở lý thuyết và phương pháp nghiên cứu
Cơ sở lý thuyết và ký hiệu chuẩn
Luận án sử dụng ký hiệu chuẩn ba tham số $\alpha|\beta|\gamma$ của Graham và Brucker (2007) để biểu diễn các bài toán lập lịch:
- $\alpha$: Môi trường máy ($\alpha_1 = 1$ là máy đơn, $\alpha_1 = P$ là nhiều máy song song giống hệt nhau; $\alpha_2 = k$ là số lượng máy).
- $\beta$: Các ràng buộc và đặc điểm của công việc ($splittable$, $split_{min}$, $available-windows$, $setup-time$, $deadline$, $prec$, $pmtn$, $batch$).
- $\gamma$: Tiêu chí tối ưu ($C_{max}$, $L_{max}$, $T_{max}$, $\sum C_i$, $\sum T_i$, $\sum U_i$, $\sum w_i C_i$, $\sum w_i U_i$, $\sum w_i T_i$).
Hệ thống lý thuyết độ phức tạp tính toán được áp dụng theo định nghĩa của Cook (1971), Leeuwen (1990), Garey & Johnson (1979) để phân lớp bài toán vào các lớp P, NP, NP-đầy đủ, NP-khó, NP-đầy đủ mạnh và NP-khó mạnh.
Ký hiệu toán học của mô hình
Luận án chuẩn hóa tập ký hiệu toán học sử dụng xuyên suốt:
| Ký hiệu |
Ý nghĩa bản chất |
Phạm vi sử dụng |
| $J = {J_1, \dots, J_n}$ |
Tập hợp gồm $n$ công việc cần lập lịch |
Toàn bộ luận án |
| $p_i$ |
Thời gian xử lý ($processing-time$) của công việc $J_i$ |
Toàn bộ luận án |
| $rj_i$ |
Thời gian xử lý còn lại ($remaining\ processing\ time$) của công việc $J_i$ |
Chương 3, 4 |
| $st_i$ |
Thời gian chuẩn bị ($setup-time$) của công việc $J_i$ |
Chương 4 |
| $d_i$ |
Thời điểm bắt buộc phải hoàn thành ($deadline$) của công việc $J_i$ |
Chương 4 |
| $C_i$ |
Thời điểm hoàn thành của công việc $J_i$ |
Chương 3, 4 |
| $C_{max}$ |
Thời điểm hoàn thành tất cả các công việc ($\max(C_i)$) |
Chương 3, 4 |
| $C_{max}^*$ |
Giá trị tối ưu nhỏ nhất của $C_{max}$ |
Chương 3, 4 |
| $W = {W_1, \dots, W_m}$ |
Tập hợp gồm $m$ khung thời gian làm việc rảnh |
Chương 3, 4 |
| $w_t$ |
Kích thước độ dài của khung thời gian $W_t$ |
Chương 3 |
| $rw_t$ |
Kích thước còn lại của khung thời gian $W_t$ |
Chương 3 |
| $b_t$ |
Cột mốc thời điểm bắt đầu của khung thời gian $W_t$ |
Chương 3 |
| $M = {M_1, \dots, M_k}$ |
Tập hợp $k$ máy (thành viên) trong bài toán lập lịch nhóm |
Chương 4 |
| $x_{i,t} \in {0, 1}$ |
Biến quyết định nhị phân: công việc $J_i$ có được gán vào khung $W_t$ hay không |
Chương 3, 4 |
| $y_{i,t} \in \mathbb{N}$ |
Biến nguyên: thời lượng thực thi của công việc $J_i$ trong khung $W_t$ |
Chương 3, 4 |
| $s_{i,t}, c_{i,t} \in \mathbb{N}$ |
Biến nguyên: thời điểm bắt đầu và thời điểm hoàn thành của $J_i$ trong khung $W_t$ |
Chương 3, 4 |
Phương pháp nghiên cứu
Luận án áp dụng phương pháp nghiên cứu định lượng kết hợp mô hình hóa toán học và thực nghiệm tính toán:
- Quy trình tiếp cận tổng quát 7 bước:
- Bước 1: Xác định tính NP-đầy đủ / NP-khó của bài toán thông qua quy giảm đa thức.
- Bước 2: Khảo sát các trường hợp đặc biệt.
- Bước 3: Chứng minh các định lý về tính chất cấu trúc của một lời giải tối ưu.
- Bước 4: Xác định miền đánh giá nghiệm (chặn dưới GLB và chặn trên LUB).
- Bước 5: Xây dựng các mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP).
- Bước 6: Sử dụng phương pháp chính xác với bộ giải CPLEX solver để giải quyết các bài toán kích thước nhỏ.
- Bước 7: Thiết kế và cài đặt các phương pháp xấp xỉ (heuristic, metaheuristic, matheuristic) cho các bài toán kích thước lớn.
- Kỹ thuật xấp xỉ và tối ưu hóa:
- Quy tắc ưu tiên và Heuristic xây dựng: FCFS (First Come First Serve), SPT (Shortest Processing Time), LPT (Longest Processing Time), EDD (Earliest Due Date), EDL (Earliest Deadline), STR (Slack Time Remaining), CR (Critical Ratio), cùng các giải thuật ASGN, ASPT, ALPT, AEDL, thuật toán dựa trên luồng cực đại (BMF) và thuật toán ghép cặp kết hợp gán (MAAS).
- Metaheuristics: Genetic Algorithm (GA), Tabu Search (TABU), Simulated Annealing (SA), Basic Hill Climbing (BHC), Stochastic Hill Climbing (SHC), Random Restart Hill Climbing (RRHC).
- Matheuristics: Đề xuất giải thuật lai E4SSJ (Exact for SubSet-Jobs) kết hợp metaheuristic phân rã bài toán con và giải chính xác bằng solver MILP.
- Bộ dữ liệu thực nghiệm:
- Tập dữ liệu DS1: Các bộ dữ liệu kích thước nhỏ phục vụ đối chuẩn giữa giải pháp chính xác (CPLEX solver) và các phương pháp xấp xỉ.
- Tập dữ liệu DS2: Các bộ dữ liệu kích thước lớn phục vụ đánh giá tính mở rộng, chất lượng nghiệm và thời gian hội tụ của các giải thuật heuristic, metaheuristic và matheuristic.
Nội dung chính theo từng chương
Chương 1: Giới thiệu về đề tài luận án
Chương 1 trình bày bối cảnh chung của bài toán lập lịch trong khoa học máy tính, sản xuất và quản lý dự án. Tác giả dẫn các số liệu thống kê thực tế về sử dụng thời gian từ Cục Thống kê Lao động Hoa Kỳ (BLS), Atlassian và RescueTime để làm nổi bật sự lãng phí thời gian và áp lực công việc hàng ngày của mỗi cá nhân (theo David Allen, một cá nhân thường đối mặt từ 50 đến 150 nhiệm vụ). Chương này phân tích hạn chế của các ứng dụng quản lý tác vụ hiện nay, nêu rõ động cơ nghiên cứu về bài toán lập lịch cá nhân với hai ràng buộc $split_{min}$ và $available-windows$, xác định mục tiêu O1, O2, O3, đối tượng, phạm vi nghiên cứu, cấu trúc nội dung và các bước triển khai của luận án.
Chương 2: Tổng quan về bài toán lập lịch công việc
Chương 2 cung cấp hệ thống cơ sở lý thuyết nền tảng về lý thuyết lập lịch và độ phức tạp thuật toán:
- Khảo sát các hướng nghiên cứu lập lịch (cấp phát tác vụ, ràng buộc nguồn lực, lập lịch công việc, lập lịch có khung thời gian).
- Trình bày mô hình toán học chuẩn của bài toán lập lịch, định nghĩa các tham số $p_i, r_i, st_i, d_i, w_i, C_i, L_i, T_i, U_i$, cấu trúc ký hiệu $\alpha|\beta|\gamma$ và chứng minh mối quan hệ chuyển đổi giữa các hàm mục tiêu minimax và minisum khi các thông số $d_i=0$, $w_i=1$, hoặc mức trễ $k=0$.
- Phân loại bài toán quyết định và bài toán tối ưu, phân tích quan hệ giữa các lớp độ phức tạp P, NP, NP-đầy đủ, NP-khó, NP-đầy đủ mạnh (định nghĩa theo Cook, Leeuwen, Garey & Johnson) cùng sơ đồ quan hệ 6 bài toán NP-đầy đủ kinh điển.
- Phân tích các phương pháp giải quyết bài toán tối ưu: phương pháp chính xác (Quy hoạch toán học LP, ILP, BLP, MILP; Phương pháp nhát cắt Gomory; Phương pháp nhánh cận Land & Doig / Little) và phương pháp xấp xỉ (Heuristic, Metaheuristic đơn giải pháp S-metaheuristics và quần thể P-metaheuristics, Matheuristic phân rã và cải tiến).
Mô hình MILP cho bài toán lập lịch song song P||Cmax (Bài toán 4 trong Chương 2):
Hàm mục tiêu:
min(Cmax)
Các ràng buộc:
\sum_{j=1}^m x_{i,j} = 1, \forall i = 1, ..., n
\sum_{i=1}^n x_{i,j} * p_i \le Cmax, \forall j = 1, ..., m
x_{i,j} \in {0, 1}, Cmax \in N
Chương 3: Bài toán lập lịch công việc cá nhân cơ bản
Chương 3 đi sâu giải quyết bài toán lập lịch công việc cá nhân cơ bản ($Personal\ Scheduling\ Problem$ - PSP), ký hiệu $1|splittable; split_{min}; available-windows|C_{max}$:
- Đặc tả bài toán: Phát biểu hình thức việc phân bổ $n$ công việc $J$ vào $m$ khung thời gian $W$. Mỗi công việc có thể chia thành nhiều phần việc con ($sub-jobs$) nhưng mỗi phần việc con phải có thời lượng xử lý $\ge split_{min}$. Mỗi khung $W_t$ có độ dài $w_t$ và điểm bắt đầu $b_t$.
- Chứng minh độ phức tạp: Tác giả phân tích tính NP-khó mạnh của bài toán thông qua quy giảm đa thức từ bài toán 3-Partition.
- Tính chất cấu trúc của lời giải tối ưu: Thiết lập các tính chất nhằm thu hẹp không gian tìm kiếm, bao gồm:
- Tính chất về thứ tự các công việc trong cùng một khung thời gian mà không làm thay đổi giá trị $C_{max}$.
- Tính chất gộp hai phần việc con của cùng một công việc trong một khung thời gian.
- Tính chất dời thời gian rảnh rỗi ($idle-time$) về cuối khung thời gian.
- Tính chất giới hạn số lượng nhát cắt tối đa của một công việc $J_i$ trên các khung thời gian.
- Tính chất hoán vị các công việc có cùng kích thước xử lý.
- Miền đánh giá nghiệm: Xác định cận dưới lớn nhất (GLB) và cận trên nhỏ nhất (LUB) của $C_{max}$.
- Mô hình toán học: Xây dựng và so sánh hai mô hình MILP (MILP 1 và MILP 2) với các biến quyết định $x_{i,t}, y_{i,t}, s_{i,t}, c_{i,t}$.
- Các giải thuật xấp xỉ đề xuất:
- Giải thuật Heuristic: ASGN (dựa trên FCFS), ALPT (dựa trên LPT), BMF (dựa trên luồng cực đại), MAAS (kết hợp Matching và Assignment).
- Giải thuật Metaheuristic: Genetic Algorithm (GA) với cơ chế mã hóa nhiễm sắc thể đặc thù cho việc gán và cắt công việc; Tabu Search (TABU) với cấu trúc danh sách cấm và hàm lân cận tối ưu; Simulated Annealing (SA).
- Giải thuật Matheuristic: E4SSJ (Exact for SubSet-Jobs) phân rã tập công việc thành các tập con và gọi solver giải chính xác từng bài toán con.
- Thực nghiệm và đánh giá:
- Đánh giá trên tập DS1: Solver CPLEX tìm được nghiệm tối ưu trên các mẫu kích thước nhỏ; E4SSJ cho kết quả bám sát nghiệm tối ưu với thời gian tính toán thấp hơn nhiều lần.
- Đánh giá trên tập DS2: Với dữ liệu lớn, CPLEX không thể tìm ra nghiệm trong thời gian cho phép; các giải thuật metaheuristic (GA, TABU) và matheuristic (E4SSJ) duy trì chất lượng nghiệm vượt trội so với các heuristic đơn giản (ASGN, ALPT).
Chương 4: Một số bài toán lập lịch công việc cá nhân đặc thù
Chương 4 mở rộng bài toán cơ bản sang các biến thể thực tế:
- Bài toán có ràng buộc thời gian chuẩn bị ($PSP+setup-time$): Mỗi công việc $J_i$ yêu cầu một thời gian chuẩn bị $st_i$ trước khi thực hiện. Luận án chứng minh quy giảm $PSP \le_p PSP+setup-time$, xây dựng mô hình MILP mở rộng, điều chỉnh các thuật toán heuristic (ASGN, ASPT) và metaheuristic tương ứng, đánh giá thực nghiệm trên DS1 và DS2.
- Bài toán có ràng buộc hạn chót ($PSP+deadline$): Mỗi công việc $J_i$ có một mốc thời gian bắt buộc hoàn thành $d_i$. Luận án chứng minh quy giảm $PSP \le_p PSP+deadline$, xây dựng các ràng buộc kiểm soát tính khả thi của lịch trình ($C_i \le d_i$), đề xuất thuật toán AEDL (Assignment based on Earliest Deadline), các phương pháp leo đồi cải tiến (Basic Hill Climbing, Stochastic Hill Climbing, Random Restart Hill Climbing) và đánh giá tỷ lệ mẫu tìm được nghiệm khả thi trên DS1, DS2.
- Bài toán lập lịch công việc nhóm ($Teamwork\ Scheduling\ Problem$ - TWSP/TWPSP): Mở rộng không gian bài toán từ một cá nhân sang một nhóm gồm $k$ người ($M_1, \dots, M_k$), mỗi người có tập khung thời gian làm việc riêng biệt $W_j = {W_1^j, \dots, W_{m_j}^j}$. Luận án thiết lập mô hình MILP trên hệ nhiều máy song song, xây dựng các giải thuật phân công công việc (ASGN, ALPT, ASPT cho môi trường nhóm) và đánh giá nghiệm thực nghiệm so sánh với solver.
Chương 5: Kết luận
Chương 5 tổng kết toàn bộ các kết quả đạt được của luận án, đánh giá mức độ hoàn thành so với các mục tiêu ban đầu O1, O2, O3, hệ thống hóa các đóng góp khoa học chính và chỉ ra các vấn đề mở cho các nghiên cứu tiếp theo.
Kết quả và những đóng góp mới
Đóng góp về mặt lý luận khoa học
- Quy trình khung tổng quát: Xây dựng khung quy trình chuẩn hóa gồm 7 bước tiếp cận có hệ thống để giải quyết lớp bài toán lập lịch kết hợp hai ràng buộc $split_{min}$ và $available-windows$.
- Chứng minh độ phức tạp: Khẳng định và mở rộng các chứng minh về tính NP-khó mạnh của bài toán lập lịch cá nhân cơ bản và các biến thể đặc thù ($PSP+setup-time$, $PSP+deadline$, $TWSP$) thông qua kỹ thuật quy giảm đa thức từ bài toán 3-Partition và PSP.
- Hệ thống hóa các tính chất tối ưu: Phát hiện và chứng minh các tính chất cấu trúc của lời giải tối ưu (thứ tự công việc, gộp phần việc con, dời thời gian rảnh, giới hạn nhát cắt), tạo tiền đề lý thuyết để rút giảm không gian tìm kiếm cho các thuật toán metaheuristic và matheuristic.
- Mô hình hóa toán học: Xây dựng hoàn chỉnh các mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) cho bài toán cơ bản, bài toán có $setup-time$, bài toán có $deadline$ và bài toán lập lịch nhóm nhiều máy.
Đóng góp về mặt thực tiễn và ứng dụng
- Thiết kế hệ giải thuật đa dạng: Xây dựng hệ thống giải thuật hoàn chỉnh bao gồm các heuristic xây dựng (ASGN, ASPT, ALPT, AEDL, BMF, MAAS), các metaheuristic tối ưu hóa (GA, TABU, SA, Hill Climbing) và giải thuật matheuristic lai E4SSJ.
- Giải pháp xử lý dữ liệu lớn: Giải thuật matheuristic E4SSJ và các metaheuristic đề xuất cho phép xử lý hiệu quả các bộ dữ liệu lớn (tập DS2) mà các solver thương mại như CPLEX không thể xử lý trong thời gian thực tế.
- Đánh giá thực nghiệm toàn diện: Cung cấp bộ kết quả đối chuẩn thực nghiệm chi tiết trên hai tập dữ liệu DS1 và DS2, đưa ra bảng so sánh định lượng về thời gian thực thi và chất lượng hàm mục tiêu $C_{max}$.
Kiến nghị và giải pháp đề xuất
- Đối với bài toán quy mô nhỏ: Khuyến nghị sử dụng mô hình MILP với CPLEX solver để đạt nghiệm tối ưu tuyệt đối.
- Đối với bài toán quy mô lớn trong ứng dụng thực tế: Khuyến nghị sử dụng phương pháp matheuristic E4SSJ hoặc metaheuristic TABU/GA để cân bằng giữa chất lượng nghiệm và thời gian phản hồi.
- Tích hợp các thuật toán đề xuất vào nhân xử lý của các hệ thống quản lý tác vụ cá nhân và phần mềm điều phối công việc nhóm trong doanh nghiệp.
Hạn chế và hướng nghiên cứu tiếp
Hạn chế của luận án
- Các mô hình trong luận án chủ yếu khảo sát trong môi trường lập lịch tiền định ($deterministic\ scheduling$), trong đó các thông số về thời gian xử lý, khung thời gian rảnh, thời điểm deadline và setup-time đều được giả định là biết trước một cách chính xác.
- Các ràng buộc đặc thù ($setup-time$, $deadline$) trong Chương 4 được xem xét độc lập trong từng bài toán riêng lẻ mà chưa được tích hợp đồng thời trong một mô hình tổng quát duy nhất.
- Mô hình làm việc nhóm ($TWSP$) mới dừng lại ở việc phân bổ công việc độc lập trên các máy song song, chưa xét đến sự phụ thuộc phức tạp về thứ tự thực thi công việc giữa các thành viên ($precedence\ constraints$).
Hướng nghiên cứu tiếp
- Nghiên cứu bài toán lập lịch cá nhân trong môi trường động ($dynamic\ scheduling$) và ngẫu nhiên ($stochastic\ scheduling$), nơi các công việc mới hoặc các khung thời gian rảnh có thể xuất hiện bất ngờ theo thời gian thực.
- Tích hợp đồng thời nhiều ràng buộc thực tế trong cùng một bài toán thống nhất: $1|splittable; split_{min}; available-windows; setup-time; deadline; prec|C_{max}$.
- Mở rộng bài toán lập lịch nhóm có xét đến mối quan hệ xã hội, mức độ ưu tiên, kỹ năng chuyên môn khác nhau của từng thành viên và các mối quan hệ ràng buộc thứ tự công việc giữa các cá nhân trong nhóm.
Giá trị tham khảo
Luận án cung cấp tài liệu tham khảo cho các đối tượng và lĩnh vực sau:
- Nghiên cứu sinh, học viên cao học và giảng viên: Chuyên ngành Khoa học máy tính, Toán tin ứng dụng, Vận trù học ($Operations\ Research$) và Kỹ thuật công nghiệp. Tài liệu có giá trị tham khảo về kỹ thuật chứng minh độ phức tạp thuật toán, phương pháp xây dựng mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP), và kỹ thuật thiết kế thuật toán matheuristic.
- Kỹ sư phần mềm và nhà phát triển ứng dụng: Các nhóm kỹ sư phát triển phần mềm quản lý công việc (Task Management, To-Do applications), hệ thống quản lý dự án, hệ thống điều độ nhân sự (Workforce Management) và các nền tảng ERP.
- Phần đáng tham khảo nhất:
- Sơ đồ 7 bước tiếp cận bài toán lập lịch tại Chương 3.
- Các định lý về tính chất của lời giải tối ưu và cấu trúc giải thuật E4SSJ tại Chương 3.
- Kỹ thuật mở rộng mô hình cho bài toán đa máy ($TWSP$) tại Chương 4.
Câu hỏi thường gặp
1. Hai ràng buộc cốt lõi được đặt ra cho bài toán lập lịch công việc cá nhân trong luận án là gì?
Hai ràng buộc cốt lõi là:
- Ràng buộc ngưỡng chia nhỏ công việc ($bounded-splitting$ hay $split_{min}$): Công việc có thể được chia nhỏ thành nhiều phần việc con nhưng kích thước mỗi phần việc con không được nhỏ hơn một giá trị ngưỡng xác định để tránh lãng phí thời gian tái khởi động.
- Ràng buộc khung thời gian làm việc ($available-windows$): Công việc chỉ được phép sắp xếp vào các khoảng thời gian làm việc rảnh có sẵn của cá nhân.
2. Tại sao bài toán lập lịch cá nhân trở thành NP-khó mạnh khi kết hợp cả hai ràng buộc?
Khi chỉ có ràng buộc $split_{min}$, nghiệm tối ưu đạt được bằng cách chia nhỏ toàn bộ công việc bằng đúng ngưỡng $split_{min}$ rồi gán tuần tự lên trục thời gian. Khi chỉ có ràng buộc $available-windows$, nghiệm tối ưu đạt được bằng cách chia nhỏ công việc về đơn vị thời gian bằng 1 rồi gán vào các khung. Tuy nhiên, khi kết hợp cả hai ràng buộc, việc vừa phải chọn kích thước chia hợp lệ ($\ge split_{min}$), vừa phải khớp vừa vặn vào các khung thời gian có kích thước cố định làm phát sinh bài toán tổ hợp tương đương với bài toán 3-Partition, đưa bài toán về lớp NP-khó mạnh ($strongly\ NP-hard$).
3. Phương pháp matheuristic E4SSJ đề xuất trong luận án hoạt động theo nguyên tắc nào?
E4SSJ ($Exact\ for\ SubSet-Jobs$) là phương pháp tiếp cận lai giữa thuật toán heuristic/metaheuristic và quy hoạch toán học. Thay vì giải bài toán nguyên vẹn bằng solver (gặp bùng nổ tổ hợp khi dữ liệu lớn), E4SSJ chia bài toán lớn thành các tập con công việc nhỏ hơn ($subsets$), sau đó áp dụng mô hình toán học MILP và sử dụng solver (như CPLEX) để giải chính xác và tối ưu cục bộ cho từng bài toán con này.
4. Luận án đã mở rộng mô hình cơ bản cho những bài toán đặc thù nào trong Chương 4?
Luận án mở rộng cho 3 bài toán:
- $PSP+setup-time$: Bổ sung thời gian chuẩn bị $st_i$ trước khi thực hiện công việc.
- $PSP+deadline$: Bổ sung thời hạn hoàn thành bắt buộc $d_i$ cho từng công việc.
- $TWSP$ / $TWPSP$ ($Teamwork\ Scheduling\ Problem$): Mở rộng từ một người (máy đơn) sang một nhóm $k$ người (nhiều máy song song), trong đó mỗi người có các khung thời gian rảnh rỗi độc lập.
5. Những quy tắc lập lịch ưu tiên nào được sử dụng trong các thuật toán heuristic của luận án?
Luận án áp dụng các quy tắc lập lịch ưu tiên kinh điển: FCFS (First Come First Serve - đến trước phục vụ trước), SPT (Shortest Processing Time - thời gian xử lý ngắn nhất), LPT (Longest Processing Time - thời gian xử lý dài nhất), EDD (Earliest Due Date - ngày đến hạn sớm nhất), EDL (Earliest Deadline - hạn chót sớm nhất), STR (Slack Time Remaining - thời gian dư thừa còn lại ít nhất), và CR (Critical Ratio - tỷ số tới hạn).
Kết luận
Luận án tiến sĩ của tác giả Trang Hồng Sơn đã giải quyết có hệ thống bài toán lập lịch công việc cá nhân dưới hai ràng buộc đồng thời là chia nhỏ công việc có chặn dưới ($split_{min}$) và gán vào các khung thời gian làm việc rảnh ($available-windows$). Thông qua việc chứng minh tính NP-khó mạnh, phân tích các tính chất cấu trúc của lời giải tối ưu và xây dựng mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP), tác giả đã đề xuất khung giải pháp toàn diện kết hợp giữa solver chính xác cho dữ liệu nhỏ và các giải thuật heuristic, metaheuristic, matheuristic (E4SSJ) cho dữ liệu lớn. Các kết quả nghiên cứu cũng được mở rộng thành công cho các bài toán đặc thù chứa ràng buộc thời gian chuẩn bị ($setup-time$), hạn chót bắt buộc ($deadline$) và bài toán lập lịch phối hợp nhóm ($TWSP$). Luận án đóng góp cả về mặt lý thuyết tối ưu hóa tổ hợp lẫn cơ sở thuật toán thực tiễn cho việc phát triển các ứng dụng quản lý thời gian và lập lịch công việc tự động.
