Tổng quan về luận án

Trong kỷ nguyên chuyển đổi số và kinh tế tri thức, con người phải đối mặt với khối lượng công việc ngày càng gia tăng cùng tính chất đa nhiệm phức tạp. Theo các khảo sát thực nghiệm được trích dẫn trong công trình nghiên cứu, chuyên gia năng suất David Allen chỉ ra rằng mỗi cá nhân thường xuyên phải xử lý từ 50 đến 150 nhiệm vụ lớn nhỏ tại bất kỳ thời điểm nào; số liệu từ Cục Thống kê Lao động Hoa Kỳ (BLS) cho thấy người lao động làm việc trung bình 8,5 giờ mỗi ngày trong tuần và 5,53 giờ vào ngày cuối tuần; trong khi thống kê từ Atlassian ghi nhận nhân viên trải qua trung bình 56 lần gián đoạn công việc mỗi ngày và tiêu tốn khoảng 2 giờ chỉ để tái tập trung và phục hồi trạng thái làm việc sau phân tâm. Mặc dù thị trường hiện nay có nhiều ứng dụng quản lý tác vụ cá nhân phổ biến như Microsoft To-Do, Google Tasks, Apple Reminders, Evernote, nTask hay Todoist, các hệ thống này hoàn toàn chỉ đóng vai trò cung cấp môi trường trực quan giúp người dùng tự thao tác sắp xếp thủ công. Chúng thiếu vắng cơ chế toán học tự động hóa để phân rã và điều phối lịch trình một cách tối ưu vào các khoảng thời gian trống khả dụng của từng cá nhân.

Khoảng trống học thuật cốt lõi (research gap) nằm ở chỗ: các lý thuyết lập lịch kinh điển trong công nghiệp và khoa học máy tính—từ các công trình nền tảng của Leung (2004), Brucker (2007), Pinedo (2016) đến Blazewicz và cộng sự (2019)—chủ yếu tập trung giải quyết bài toán lập lịch trên máy móc (machine scheduling) hoặc quản lý dự án công nghiệp với các ràng buộc truyền thống như quan hệ thứ tự ưu tiên (precedence relations), gián đoạn vô điều kiện (preemption), gom lô (batching) và xác định kích thước lô (lot-sizing). Ngược lại, đối với hoạt động của con người, công việc có thể chia nhỏ linh hoạt nhưng không thể phân mảnh tùy tiện. Việc chia nhỏ công việc xuống dưới một ngưỡng thời gian tối thiểu ($split_{min}$) sẽ gây ra chi phí khởi động lại (restart time / setup penalty) và làm sụt giảm nghiêm trọng hiệu suất lao động. Khi kết hợp đồng thời hai ràng buộc: (1) công việc có thể chia nhỏ nhưng bị chặn dưới bởi một ngưỡng xác định ($split_{min}$), và (2) công việc chỉ được bố trí vào các khung thời gian làm việc rời rạc có sẵn ($available-windows$), bài toán chuyển đổi đột ngột từ lớp bài toán giải được trong thời gian đa thức sang lớp bài toán NP-khó mạnh ($strongly\text{ }NP-hard$).

Luận án tiến sĩ chuyên ngành Khoa học máy tính (Mã số: 62480101) của tác giả Trang Hồng Sơn, dưới sự hướng dẫn khoa học của PGS. Huỳnh Tường Nguyên và PGS. Trần Văn Lăng tại Trường Đại học Bách khoa – Đại học Quốc gia TP. Hồ Chí Minh (2022), mang tên: "Một số phương pháp tiếp cận cho bài toán lập lịch công việc cá nhân" (Approaches for Personal Scheduling Problem). Nghiên cứu này thiết lập các câu hỏi nghiên cứu ($RQ$) và giả thuyết khoa học ($H$) cụ thể:

  • $RQ_1$: Cấu trúc toán học và độ phức tạp tính toán lý thuyết của bài toán lập lịch công việc cá nhân dưới sự tương tác của hai ràng buộc $split_{min}$ và $available-windows$ là gì?
  • $RQ_2$: Tồn tại những tính chất cấu trúc đặc thù nào của một lời giải tối ưu giúp thu hẹp không gian tìm kiếm tổ hợp?
  • $RQ_3$: Làm thế nào để thiết kế các thuật toán chính xác dựa trên Quy hoạch tuyến tính nguyên hỗn hợp (MILP) và các thuật toán xấp xỉ lai (Matheuristics, Metaheuristics) nhằm tìm kiếm lời giải tối ưu hoặc cận tối ưu cho các tập dữ liệu thực nghiệm quy mô lớn trong thời gian thực thi chấp nhận được?
  • $RQ_4$: Khung phương pháp tiếp cận tổng quát có thể mở rộng như thế nào cho các bài toán đặc thù chứa ràng buộc thời gian chuẩn bị ($setup-time$), thời điểm bắt buộc hoàn thành ($deadline$) và bài toán lập lịch công việc nhóm ($TWSP$)?

Tương ứng với các câu hỏi trên, các giả thuyết nghiên cứu bao gồm:

  • $H_1$: Sự kết hợp giữa ngưỡng phân rã chặn dưới $split_{min}$ và khung thời gian làm việc $available-windows$ khiến bài toán trở thành NP-khó mạnh thông qua phép thu giảm đa thức từ bài toán phân hoạch 3 phần tử ($3-Partition$).
  • $H_2$: Việc khai thác các tính chất dồn dịch thời gian rảnh rỗi ($idle-time$) và gộp các công việc con ($sub-jobs$) cho phép xác định miền chặn dưới lớn nhất ($GLB$) và chặn trên nhỏ nhất ($LUB$) chặt chẽ.
  • $H_3$: Thuật toán lai Matheuristics kết hợp giữa siêu phỏng đoán heuristic/metaheuristic và bộ giải tối ưu cục bộ MILP solver sẽ vượt trội hơn các thuật toán Metaheuristic thuần túy (như GA, TABU, SA) về độ chính xác và tính hội tụ trên tập dữ liệu kích thước lớn.
  • $H_4$: Mô hình mở rộng cho môi trường đa máy phân tán giải quyết thành công bài toán phối hợp lịch trình nhóm đa thành viên mà vẫn bảo đảm tối thiểu hóa thời điểm hoàn thành tối đa ($C_{max}$).

Khung lý thuyết của luận án được xây dựng dựa trên sự giao thoa giữa Lý thuyết độ phức tạp tính toán (Computational Complexity Theory của Cook, 1971; Garey & Johnson, 1979), Lý thuyết Lập lịch tất định (Deterministic Scheduling Theory theo ký hiệu ba tham số $\alpha|\beta|\gamma$ của Graham và cộng sự, 1979), và Lý thuyết Quy hoạch toán học (Mathematical Programming theo Wolsey, 1998). Về mặt phạm vi, luận án nghiên cứu chuyên sâu bài toán lập lịch cá nhân đơn máy và nhóm cộng tác đa máy, kiểm chứng định lượng trên hai bộ dữ liệu chuẩn: bộ dữ liệu mẫu nhỏ DS1 (từ 10 đến 50 công việc) đối chiếu trực tiếp với nghiệm tối ưu tuyệt đối của CPLEX Solver, và bộ dữ liệu mẫu lớn DS2 (hàng trăm đến hàng ngàn công việc) nhằm đo lường khả năng mở rộng quy mô giải thuật.

Literature Review và Positioning

Nghiên cứu lập lịch công việc là một nhánh học thuật lâu đời khởi nguồn từ công trình tiên phong của Johnson (1954) về lịch trình sản xuất tối ưu. Qua nhiều thập kỷ phát triển, các hệ thống phân loại lý thuyết đã được chuẩn hóa bởi các nhà khoa học hàng đầu:

  1. Dòng nghiên cứu lý thuyết lập lịch hệ thống và máy móc kinh điển: Graham và cộng sự (1979), Leung (2004), Brucker (2007), Pinedo (2016), Blazewicz và cộng sự (2019) đã hệ thống hóa toàn diện các bài toán trên môi trường máy đơn ($1$), máy song song ($P, Q, R$) và các phân xưởng phức hợp ($Open\text{ }Shop, Flow\text{ }Shop, Job\text{ }Shop, Mixed\text{ }Shop$). Các ràng buộc công việc truyền thống được phân tích sâu sắc bao gồm quan hệ thứ tự ($prec$), tính gián đoạn ($pmtn$), gom nhóm ($batching$), và kích thước lô sản xuất ($lot-sizing$).
  2. Dòng nghiên cứu lập lịch có khung thời gian khả dụng và bảo trì định kỳ: Zhang và cộng sự (2020) đã nghiên cứu bài toán lập lịch hệ thống sản phẩm - dịch vụ (PSS) với khung cửa sổ thời gian ($time-windows$), đề xuất giải thuật chèn thời gian nhàn rỗi ($idle\text{ }time\text{ }insertion$) kết hợp thuật toán thích nghi NEH và Metaheuristics. Ting Wang và cộng sự (2020) khảo sát mô hình máy đơn có bảo trì định kỳ linh hoạt ($periodic\text{ }maintenance$) với thời gian xử lý suy giảm tuyến tính, giải quyết thông qua mô hình phân vùng tập hợp ($set-partitioning$) và giải thuật nhánh và giá ($branch\text{ }and\text{ }price$). Vitor Nesello và cộng sự (2021) đề xuất thuật toán chính xác dựa trên mô hình chỉ mục cung thời gian lặp ($arc-time-indexed\text{ }models$) cho bài toán lập lịch máy đơn có bảo trì và thời gian thiết lập phụ thuộc trình tự trên 420 bộ dữ liệu chuẩn.
  3. Dòng nghiên cứu phân bổ tác vụ trong các hệ thống thông minh: Max Witteman và cộng sự (2021) mô hình hóa bài toán bảo dưỡng đội bay 45 máy bay dưới dạng đóng gói thùng có kích thước thay đổi ($time-constrained\text{ }variable-sized\text{ }bin\text{ }packing$) sử dụng heuristic $worst-fit\text{ }decreasing$. Hussein M. và cộng sự (2020) tiếp cận bài toán phân bổ tác vụ IoT dựa trên mở rộng bài toán tập bao phủ ($set\text{ }cover$). Xinye Chen và cộng sự (2020), Schwarzrock và cộng sự (2018), Amorim và cộng sự (2020) nghiên cứu phân bổ tác vụ trong mạng lưới robot phân tán và phương tiện bay không người lái (UAV) bằng giải thuật bầy đàn kết hợp phân công tổng quát ($Swarm-GAP$).

Trong bức tranh tổng quan đó, các cuộc tranh luận học thuật nổi bật tập trung vào hai quan điểm đối lập:

  • Tranh luận 1 (Tính gián đoạn công việc): Quan điểm lập lịch máy tính truyền thống (Horn, 1974; Brucker, 2007) cho phép chia cắt tác vụ vô hạn với đơn vị thời gian tối thiểu bằng 1 để tối ưu hóa việc lấp đầy tài nguyên. Ngược lại, quan điểm công thái học và quản trị hành vi con người (David Allen, 2015; Kukhnavets, 2019) khẳng định sự phân mảnh quá mức làm triệt tiêu năng suất do chi phí chuyển đổi ngữ cảnh ($context-switching\text{ }cost$).
  • Tranh luận 2 (Phương pháp giải quyết bài toán NP-khó): Một trường phái ưu tiên phát triển mô hình quy hoạch toán học chính xác (Wolsey, 1998; Balouka & Cohen, 2021 với phương pháp phân tách Benders) nhằm bảo đảm tính tối ưu tuyệt đối. Trường phái thứ hai nhấn mạnh việc áp dụng các thuật giải xấp xỉ, tìm kiếm cục bộ và tiến hóa bầy đàn (Rahman et al., 2020; Chen Zhi et al., 2020) để đáp ứng thời gian thực thi nhanh trong các ứng dụng thực tế.

Về nguồn gốc trực tiếp của bài toán lập lịch cá nhân (Personal Scheduling Problem - PSP):

  • Năm 2010, bài toán được khởi xướng lần đầu bởi nhóm nghiên cứu quốc tế trong công trình [16] với 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 và giải thuật di truyền (GA) để tìm kiếm lời giải khả thi.
  • Năm 2013, công trình [17] đã hình thức hóa bài toán dưới dạng $1|splittable; split_{min}; available-windows|C_{max}$, thực hiện chứng minh bài toán thuộc lớp NP-khó mạnh thông qua thu giảm đa thức từ bài toán $3-Partition$, chỉ ra 5 tính chất của lời giải tối ưu và đề xuất 3 giải thuật heuristic xây dựng trên quy tắc LPT.
  • Cùng năm 2013, công trình [18] bổ sung thêm một tính chất của lời giải tối ưu, xây dựng mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) đầu tiên và giải nghiệm bằng các bộ giải thương mại như COIN-OR CBC, GLPK và GUROBI trên tập dữ liệu kích thước nhỏ.

Luận án của NCS. Trang Hồng Sơn định vị chính xác vào khoảng trống nghiên cứu còn bỏ ngỏ của các công trình đi trước: phát triển một khung phương pháp luận toàn diện, giải quyết trọn vẹn bài toán từ việc phân tích độ phức tạp, chứng minh bổ sung các tính chất không gian nghiệm, xây dựng công thức toán học tối ưu, phát triển thuật toán lai Matheuristics đột phá có khả năng xử lý các bộ dữ liệu lớn vượt ngưỡng tính toán của các MILP solver truyền thống, đồng thời mở rộng mô hình sang các bài toán có ràng buộc thực tế ($setup-time$, $deadline$) và môi trường cộng tác nhóm ($TWSP$).

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án mang lại những đóng góp nền tảng cho lý thuyết tối ưu hóa tổ hợp và lý thuyết lập lịch hiện đại:

  1. Mở rộng hệ thống phân loại ba tham số của Graham (1979): Luận án chính thức bổ sung hai tham số đặc trưng cho hành vi tác vụ con người vào trường $\beta$, cụ thể là ràng buộc phân rã có chặn dưới ($split_{min}$) và ràng buộc khung thời gian rời rạc ($available-windows$), xác lập ký hiệu chuẩn tắc: $$1|splittable; split_{min}; available-windows|C_{max}$$
  2. Chứng minh toán học về sự chuyển pha độ phức tạp tính toán: Luận án chứng minh một cách tường minh rằng nếu chỉ xét riêng lẻ ràng buộc $split_{min}$, bài toán tìm được nghiệm tối ưu dễ dàng bằng cách chia nhỏ tất cả công việc bằng ngưỡng chặn dưới rồi sắp xếp tuần tự theo trục thời gian. Nếu chỉ xét riêng lẻ ràng buộc $available-windows$, bài toán đạt nghiệm tối ưu bằng cách chia nhỏ công việc thành các đơn vị thời gian $1$. Tuy nhiên, khi kết hợp đồng thời cả hai ràng buộc, bài toán lập tức trở thành NP-khó mạnh. Luận án tái khẳng định và mở rộng cấu trúc chứng minh thông qua phép thu giảm đa thức từ bài toán phân hoạch 3 tập hợp ($3-Partition \le_p PSP$).
  3. 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 (Structural Properties):
    • Tính chất hoán vị: Thứ tự thực thi của các công việc hoặc công việc con bên trong cùng một khung thời gian làm việc không làm thay đổi giá trị hàm mục tiêu $C_{max}$.
    • Tính chất hợp nhất công việc con: Hai công việc con ($sub-jobs$) thuộc cùng một công việc gốc $J_i$ nếu được gán vào cùng một khung thời gian $W_t$ thì luôn có thể gộp lại thành một công việc duy nhất mà không làm phương hại đến tính khả thi của lịch trình.
    • Tính chất dồn dịch thời gian nhàn rỗi: Mọi khoảng thời gian rảnh rỗi ($idle-time$) bên trong một khung thời gian luôn có thể được dồn dịch liên tục về phía cuối của khung thời gian đó.
    • Tính chất giới hạn phân cắt: Số lượng công việc con tối đa được cắt ra từ một công việc $J_i$ có thời gian xử lý $p_i$ với ngưỡng chặn dưới $split_{min}$ bị chặn trên nghiêm ngặt bởi $\lfloor p_i / split_{min} \rfloor$.
  4. Mô hình hóa lý thuyết và xác lập miền nghiệm: Thiết lập công thức xác định chặn dưới lớn nhất ($GLB - Greatest\text{ }Lower\text{ }Bound$) và chặn trên nhỏ nhất ($LUB - Least\text{ }Upper\text{ }Bound$), tạo nền tảng giới hạn không gian tìm kiếm cho các giải thuật phân nhánh và giải thuật xấp xỉ.

Khung phân tích độc đáo

Luận án xây dựng khung phân tích tích hợp ba trụ cột: Lý thuyết Độ phức tạp $\rightarrow$ Mô hình Toán học Chính xác (MILP) $\rightarrow$ Thuật toán Xấp xỉ Cải tiến và Lai ghép (Heuristic/Metaheuristic/Matheuristic).

Mô hình Quy hoạch Tuyến tính Nguyên Hỗn hợp (MILP) cơ sở cho bài toán lập lịch cá nhân được thiết lập với tập hợp $n$ công việc $J = {J_1, J_2, \dots, J_n}$, mỗi công việc có thời gian xử lý $p_i$, và tập hợp $m$ khung thời gian làm việc $W = {W_1, W_2, \dots, W_m}$, mỗi khung có kích thước $w_t$ bắt đầu tại mốc thời gian $b_t$.

Các biến quyết định chính:

  • $x_{i,t} \in {0, 1}$: nhận giá trị $1$ nếu công việc $J_i$ được phân công vào khung thời gian $W_t$, ngược lại nhận $0$.
  • $y_{i,t} \in \mathbb{N}$: thời lượng thực thi của công việc $J_i$ bên trong khung thời gian $W_t$.
  • $s_{i,t} \in \mathbb{N}$: thời điểm bắt đầu của công việc $J_i$ trong khung $W_t$.
  • $c_{i,t} \in \mathbb{N}$: thời điểm hoàn thành của công việc $J_i$ trong khung $W_t$.
  • $C_{max} \in \mathbb{N}$: thời điểm hoàn thành của toàn bộ tất cả các công việc.

Hàm mục tiêu: $$\min C_{max}$$

Hệ thống ràng buộc cốt lõi: $$\sum_{t=1}^{m} y_{i,t} = p_i, \quad \forall i = 1, \dots, n \quad \text{(Bảo toàn tổng thời gian xử lý công việc)}$$ $$\sum_{i=1}^{n} y_{i,t} \le w_t, \quad \forall t = 1, \dots, m \quad \text{(Không vượt quá dung lượng khung thời gian)}$$ $$y_{i,t} \ge split_{min} \cdot x_{i,t}, \quad \forall i = 1, \dots, n; \forall t = 1, \dots, m \quad \text{(Ràng buộc ngưỡng phân chia tối thiểu)}$$ $$y_{i,t} \le p_i \cdot x_{i,t}, \quad \forall i = 1, \dots, n; \forall t = 1, \dots, m \quad \text{(Ràng buộc kích hoạt biến nhị phân)}$$ $$C_{max} \ge c_{i,t}, \quad \forall i = 1, \dots, n; \forall t = 1, \dots, m \quad \text{(Xác định Makespan)}$$

Khung phân tích này thiết lập điều kiện biên chặt chẽ: tổng năng lực các khung thời gian phải thỏa mãn $\sum_{t=1}^m w_t \ge \sum_{i=1}^n p_i$, và mỗi khung thời gian khả dụng $w_t$ phải có kích thước tối thiểu lớn hơn hoặc bằng $split_{min}$ để tránh tạo ra các biến không khả thi vô nghiệm.

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

Thiết kế nghiên cứu

Nghiên cứu tuân thủ chặt chẽ triết lý thực chứng logic và chủ nghĩa duy thực toán học (Positivism / Mathematical Realism), trong đó mọi khẳng định khoa học đều được chứng minh thông qua giải tích toán học trừu tượng và kiểm chứng thực nghiệm bằng mô phỏng số học.

Thiết kế nghiên cứu đa tầng (Multi-level design) được triển khai qua 3 cấp độ:

  • Cấp độ 1 (Cơ sở): Bài toán lập lịch cá nhân đơn máy cơ bản (PSP).
  • Cấp độ 2 (Đặc thù hóa): Mở rộng bài toán với các ràng buộc thực tế nâng cao gồm thời gian chuẩn bị công việc ($PSP + setup-time$) và hạn chót nghiêm ngặt ($PSP + deadline$).
  • Cấp độ 3 (Cộng tác đa tác tử): Mở rộng bài toán lên không gian nhiều máy biểu diễn bài toán lập lịch nhóm làm việc ($Teamwork\text{ }Scheduling\text{ }Problem - TWSP$).

Quy trình nghiên cứu rigorous

Luận án xây dựng và thực thi quy trình nghiên cứu chuẩn mực gồm 7 bước tuần tự:

  1. Đặc tả toán học: Định nghĩa bài toán, hệ thống hóa ký hiệu, xây dựng các ví dụ minh họa và thiết lập bài toán quyết định tương ứng.
  2. Chứng minh độ phức tạp: Khảo sát các trường hợp suy biến, chứng minh tính quy dẫn đa thức và xác lập vị trí của bài toán trong cấu trúc độ phức tạp ($NP-complete$, $strongly\text{ }NP-hard$).
  3. Khai phá tính chất tối ưu: Phân tích cấu trúc hình học của không gian nghiệm để phát hiện các định lý triệt tiêu lời giải dư thừa.
  4. Xác định biên nghiệm: Thiết lập các thuật toán tính toán chặn dưới $GLB$ và chặn trên $LUB$.
  5. Mô hình hóa toán học: Xây dựng mô hình Quy hoạch Tuyến tính Nguyên Hỗn hợp (MILP) tối ưu hóa biến số.
  6. Phương pháp giải chính xác: Ứng dụng các bộ giải chuyên dụng (CPLEX Optimizer Studio) và thuật toán phân nhánh cắt (Branch-and-Cut, Gomory Cutting Plane).
  7. Phương pháp xấp xỉ và lai ghép: Thiết kế hệ thống thuật toán Heuristic, Metaheuristic và Matheuristic.

Hệ thống thuật toán xấp xỉ được phát triển đa dạng bao gồm:

  • Heuristics kế thừa cổ điển: Thuật toán gán việc dựa trên các quy tắc ưu tiên cổ điển như Đến trước phục vụ trước ($ASGN - FCFS$), Thời gian xử lý ngắn nhất ($ASPT - SPT$), Thời gian xử lý dài nhất ($ALPT - LPT$), Hạn chót sớm nhất ($AEDL - EDL$), và các giải thuật mạng nâng cao như Thuật toán luồng cực đại ($BMF - Max\text{ }Flow$) và Ghép cặp kết hợp ($MAAS - Matching\text{ }and\text{ }Assignment$).
  • Metaheuristics công nghiệp: Tối ưu hóa tìm kiếm lân cận với Giải thuật Leo đồi (BHC, SHC, RRHC), Luyện kim nhân tạo ($Simulated\text{ }Annealing - SA$), Tìm kiếm Tabu ($Tabu\text{ }Search - TABU$) với danh sách cấm linh hoạt, và Giải thuật Di truyền ($Genetic\text{ }Algorithm - GA$) với kỹ thuật mã hóa nhiễm sắc thể đặc thù cho bài toán phân mảnh công việc.
  • Toán tử lân cận chuyên sâu: Đề xuất hai toán tử trích xuất và tái chèn dịch chuyển lùi ($EBSR - Extraction\text{ }and\text{ }Backward\text{ }Shifted\text{ }Re-insertion$) và trích xuất và tái chèn dịch chuyển tiến ($EFSR - Extraction\text{ }and\text{ }Forward\text{ }Shifted\text{ }Re-insertion$) nhằm khai thác tối đa không gian nghiệm cục bộ.
  • Đột phá Matheuristics: Phát triển thuật toán $E4SSJ$ (Exact for SubSet-Jobs), kết hợp sức mạnh phân rã của Heuristic với năng lực tìm nghiệm tối ưu cục bộ của MILP CPLEX Solver trên các tập công việc con được chọn lọc.

Data và phân tích

Các thuật toán được lập trình, đóng gói và thực thi trên môi trường tính toán chuẩn mực. Dữ liệu thực nghiệm được chia thành:

  • Tập dữ liệu mẫu nhỏ (DS1): Gồm các trường hợp từ 10 đến 50 công việc, phân bố đều trong các khung thời gian với các tỷ lệ thời gian xử lý và kích thước khung ngẫu nhiên, cho phép CPLEX giải ra nghiệm tối ưu tuyệt đối để làm mốc chuẩn (ground truth).
  • Tập dữ liệu mẫu lớn (DS2): Gồm các mẫu thử nghiệm có quy mô từ 100 đến hàng ngàn công việc, vượt quá khả năng giải quyết trong thời gian đa thức của các bộ giải MILP thương mại, dùng để kiểm tra độ trễ hội tụ và chất lượng nghiệm xấp xỉ.

Chỉ số đánh giá độ tin cậy bao gồm: Thời gian thực thi tính bằng giây CPU ($CPU\text{ }time$), Sai số tương đối so với nghiệm tối ưu tuyệt đối ($Optimality\text{ }Gap$), và Giá trị hàm mục tiêu Makespan cực tiểu ($C_{max}^*$).

Phát hiện đột phá và implications

Những phát hiện then chốt

  1. Hiệu ứng bùng nổ tổ hợp do tương tác ràng buộc kép: Dữ liệu thực nghiệm khẳng định hiện tượng chuyển pha độ phức tạp tính toán. Khi giải quyết bài toán cơ bản $PSP$ với mô hình MILP trên tập dữ liệu DS1, thời gian giải của bộ giải CPLEX tăng theo hàm số mũ khi số lượng công việc $n$ vượt quá 30, trong khi các thuật toán Heuristic và Metaheuristic duy trì thời gian thực thi dưới $0,5$ giây.
  2. Sự vượt trội của giải thuật Matheuristics ($E4SSJ$): Trên cả hai tập dữ liệu DS1 và DS2, giải thuật $E4SSJ$ tạo ra bước đột phá về chất lượng nghiệm. Thay vì tìm kiếm ngẫu nhiên như GA hay TABU, $E4SSJ$ liên tục tái cơ cấu các tập công việc con ($SubSet-Jobs$) và giải tối ưu cục bộ bằng solver. Kết quả thực nghiệm ghi nhận $E4SSJ$ đạt giá trị $C_{max}$ tiệm cận tuyệt đối với nghiệm tối ưu của MILP Solver trên tập DS1 với thời gian chỉ bằng một phần nhỏ, và vượt trội hoàn toàn so với các thuật toán Heuristic truyền thống ($ASGN, ASPT, ALPT$) trên tập dữ liệu lớn DS2.
  3. Tính nhạy cảm cao của ràng buộc Setup-time và Deadline:
    • Trong bài toán $PSP + setup-time$, thời gian chuẩn bị $st_i$ gây ra hiệu ứng tích lũy lãng phí dung lượng khung thời gian nếu công việc bị phân mảnh thành nhiều công việc con. Do đó, các thuật toán ưu tiên giảm thiểu số lượng vết cắt công việc đạt hiệu quả vượt trội.
    • Trong bài toán $PSP + deadline$, việc áp dụng các giải thuật heuristic thông thường ($ASGN, ASPT$) thường xuyên tạo ra các lời giải không khả thi ($infeasible\text{ }solutions$) do vi phạm thời hạn nghiêm ngặt $d_i$. Giải thuật $AEDL$ kết hợp tìm kiếm lân cận $RRHC$ và toán tử $EBSR/EFSR$ chứng minh khả năng duy trì 100% tính khả thi và đạt độ tối ưu cao.
  4. Hiệu năng cân bằng tải trong bài toán nhóm ($TWSP$): Mở rộng sang mô hình làm việc nhóm đa máy $M = {M_1, \dots, M_k}$, các thuật toán gán việc thích ứng giúp triệt tiêu thời gian nhàn rỗi bất đối xứng giữa các thành viên, hạ thấp giá trị $C_{max}$ toàn cục của nhóm xuống mức tối ưu lý thuyết.

Implications đa chiều

  • Ý nghĩa lý thuyết: Xác lập cơ sở toán học vững chắc cho một phân nhánh mới trong lý thuyết điều độ: Lập lịch hướng người dùng (Human-centric Scheduling Theory), bắc cầu nối giữa tối ưu hóa tổ hợp thuần túy và khoa học năng suất hành vi con người.
  • Ý nghĩa phương pháp luận: Khung tiếp cận 7 bước cùng mô hình lai ghép Matheuristics ($E4SSJ$) cung cấp một phương pháp luận mẫu mực có thể chuyển giao trực tiếp để giải quyết các bài toán tối ưu tổ hợp phức tạp khác trong công nghiệp logistics, quản lý chuỗi cung ứng và điều phối tài nguyên máy tính đám mây.
  • Ý nghĩa thực tiễn công nghệ: Cung cấp thuật toán lõi (Core Optimization Engine) cho các công ty công nghệ phát triển phần mềm năng suất, biến các ứng dụng To-Do thụ động thành các trợ lý quản lý thời gian thông minh tự động điều phối lịch làm việc tối ưu.
  • Ý nghĩa quản trị tổ chức: Giúp các doanh nghiệp tối ưu hóa hoạt động cộng tác nhóm, giảm thiểu xung đột lịch trình, phân bổ đều khối lượng công việc, hạn chế hiện tượng kiệt sức (burnout) và gia tăng hiệu suất làm việc tổng thể.

Limitations và Future Research

Mặc dù đạt được những kết quả đột phá, luận án thẳng thắn chỉ ra các giới hạn nghiên cứu:

  1. Giả định về tính tất định của dữ liệu (Deterministic assumption): Các thông số đầu vào như thời gian xử lý ($p_i$), kích thước khung thời gian ($w_t$), thời gian chuẩn bị ($st_i$) và hạn chót ($d_i$) đều được giả định là các hằng số nguyên biết trước chính xác, chưa phản ánh tính bất định và biến động ngẫu nhiên trong đời sống thực.
  2. Hàm mục tiêu đơn biến: Nghiên cứu hiện tại tập trung chủ yếu vào việc cực tiểu hóa thời điểm hoàn thành tối đa ($C_{max}$), chưa tích hợp các hàm mục tiêu đa chiều như tối thiểu hóa độ trễ có trọng số ($\sum w_i T_i$), tối thiểu hóa số công việc trễ hạn ($\sum U_i$), hay hàm đo lường mức độ thỏa dụng/mức độ hài lòng của cá nhân.
  3. Mô hình lập lịch tĩnh ngoại tuyến (Offline Scheduling): Các thuật toán giải quyết bài toán với giả định toàn bộ tập công việc đã xuất hiện đầy đủ tại thời điểm $t=0$, chưa xét đến kịch bản động thời gian thực khi các công việc khẩn cấp phát sinh ngẫu nhiên trong ngày làm việc.

Chương trình nghiên cứu tương lai (Future Research Agenda) mở ra 4 hướng đi chiến lược:

  • Hướng 1: Phát triển mô hình lập lịch cá nhân thích ứng động thời gian thực (Online / Real-time Dynamic PSP) kết hợp các cơ chế phản xạ tức thời khi có sự thay đổi lịch trình.
  • Hướng 2: Ứng dụng Trí tuệ nhân tạo và Học máy (Machine Learning / Deep Reinforcement Learning) để tự động dự báo thời gian thực hiện công việc ($p_i$) dựa trên thói quen lịch sử và độ tập trung của từng cá nhân.
  • Hướng 3: Mở rộng bài toán sang tối ưu hóa đa mục tiêu Pareto (Multi-objective PSP/TWSP), cân bằng giữa hiệu suất công việc ($Makespan$), mức độ tiêu hao năng lượng thể chất/tinh thần và mức độ ưu tiên công việc.
  • Hướng 4: Tích hợp các ràng buộc phụ thuộc phức tạp trong mô hình nhóm, như quan hệ phụ thuộc công việc chéo giữa các thành viên (cross-member precedence) và chia sẻ kỹ năng chuyên môn trong môi trường làm việc lai (Hybrid Workplace).

Tác động và ảnh hưởng

Luận án tạo ra những giá trị tác động sâu rộng trên nhiều bình diện:

  • Tác động học thuật: Đóng góp một hệ thống chứng minh toán học chuẩn tắc và các bộ dữ liệu thực nghiệm chuẩn (benchmark datasets) cho cộng đồng Khoa học máy tính và Vận trù học quốc tế. Nghiên cứu mở ra tiềm năng trích dẫn cao trong các tạp chí chuyên ngành hàng đầu thế giới (như Computers & Operations Research, European Journal of Operational Research, Applied Soft Computing, Journal of Scheduling).
  • Chuyển đổi công nghiệp phần mềm: Mở đường cho các tập đoàn công nghệ lớn (như Microsoft, Google, Notion, Asana) tích hợp động cơ tối ưu hóa toán học vào các sản phẩm quản lý công việc thế hệ mới, chuyển đổi từ mô hình nhắc việc thụ động sang tự động hóa lập lịch thông minh.
  • Lợi ích kinh tế - xã hội: Giúp người lao động tri thức tiết kiệm từ 1 đến 2 giờ mỗi ngày bị lãng phí do việc phân vân, tự sắp xếp lịch trình thủ công hoặc chuyển đổi ngữ cảnh không hợp lý; góp phần nâng cao năng suất lao động xã hội và cân bằng giữa công việc và cuộc sống (work-life balance).

Đối tượng hưởng lợi

  • Nghiên cứu sinh và Giới học thuật: Tiếp cận một khung phương pháp luận hoàn chỉnh từ chứng minh độ phức tạp lý thuyết đến thiết kế thuật toán lai Matheuristics để áp dụng cho các bài toán tối ưu tổ hợp tương tự.
  • Kỹ sư R&D và Nhà phát triển sản phẩm công nghệ: Sở hữu trực tiếp các cấu trúc dữ liệu, mô hình toán học MILP và mã giả giải thuật tối ưu để lập trình tích hợp vào các hệ thống phần mềm SaaS quản lý năng suất và điều phối nhân sự.
  • Nhà quản lý dự án và Lãnh đạo doanh nghiệp: Có được công cụ toán học hỗ trợ ra quyết định phân bổ nguồn lực và sắp xếp lịch trình làm việc nhóm khoa học, minh bạch và tối ưu hóa năng suất tập thể.
  • Người dùng cá nhân trong xã hội hiện đại: Hưởng lợi từ các công cụ quản trị thời gian tự động, giảm thiểu áp lực quá tải công việc và nâng cao hiệu quả làm việc cá nhân.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo và đột phá nhất của luận án là gì?
Đó là việc định danh toán học và chứng minh sự chuyển pha độ phức tạp của bài toán lập lịch dưới sự tương tác của hai ràng buộc $split_{min}$ và $available-windows$. Luận án chứng minh rằng trong khi từng ràng buộc đơn lẻ chỉ tạo ra bài toán giải được trong thời gian đa thức thuộc lớp P, sự kết hợp đồng thời của chúng tạo ra một bài toán thuộc lớp NP-khó mạnh ($1|splittable; split_{min}; available-windows|C_{max}$), từ đó mở rộng hệ thống lý thuyết lập lịch kinh điển của Graham.

2. Đột phá phương pháp luận của giải thuật Matheuristics ($E4SSJ$) so với các nghiên cứu tiền nhiệm quốc tế là gì?
Các công trình trước đây như [17] chỉ dừng lại ở Heuristic LPT đơn giản, còn [18] chỉ áp dụng thuần túy bộ giải MILP solver vốn bị nghẽn tính toán trên dữ liệu lớn. Luận án đã sáng tạo phương pháp lai Matheuristics $E4SSJ$, phân rã không gian nghiệm bằng siêu phỏng đoán thông minh và chỉ chuyển các bài toán con chọn lọc cho solver giải tối ưu, đạt được sự cân bằng hoàn hảo giữa tốc độ tính toán siêu nhanh và chất lượng nghiệm tiệm cận tối ưu tuyệt đối.

3. Phát hiện thực nghiệm nào gây ngạc nhiên nhất trong quá trình nghiên cứu?
Đó là hiện tượng sụt giảm tính khả thi nghiêm trọng của các giải thuật heuristic kinh điển khi bổ sung ràng buộc thời hạn bắt buộc ($deadline$). Trong khi các quy tắc ưu tiên phổ biến như FCFS hay SPT hoàn toàn thất bại và tạo ra các lịch trình vi phạm hạn chót, giải thuật $AEDL$ kết hợp các toán tử dịch chuyển đặc thù ($EBSR/EFSR$) lại tìm ra các cấu trúc sắp xếp hợp lý giải quyết triệt để sự xung đột giữa tính liên tục của công việc và hạn định thời gian.

4. Luận án có cung cấp quy trình tái lập thực nghiệm (Replication Protocol) hoàn chỉnh không?
Hoàn toàn có. Luận án cung cấp đầy đủ công thức toán học tường minh của các mô hình MILP, bảng danh mục biến số và tham số, thuật toán chi tiết dưới dạng mã giả, quy chuẩn sinh dữ liệu mẫu DS1/DS2 và thông số cấu hình của các bộ giải CPLEX, bảo đảm tính minh bạch và khả năng tái lập 100% cho cộng đồng khoa học.

5. Lộ trình nghiên cứu phát triển 10 năm tới được xác lập ra sao?
Lộ trình 10 năm định hướng tiến hóa bài toán từ mô hình tất định ngoại tuyến sang mô hình tối ưu hóa ngẫu nhiên/mờ thời gian thực (Real-time Stochastic Optimization), tích hợp mô hình ngôn ngữ lớn (LLM) và học máy để tự động hiểu ngữ cảnh tác vụ, và mở rộng quy mô giải quyết các bài toán điều phối nhân lực quy mô lớn trên nền tảng điện toán đám mây.

Kết luận

Công trình luận án tiến sĩ của tác giả Trang Hồng Sơn đã giải quyết trọn vẹn và xuất sắc bài toán lập lịch công việc cá nhân thông qua các đóng góp học thuật cốt lõi:

  1. Xác lập vị trí lý thuyết và chứng minh toán học bài toán lập lịch cá nhân với hai ràng buộc $split_{min}$ và $available-windows$ thuộc lớp NP-khó mạnh.
  2. Phát hiện, chứng minh và hệ thống hóa các tính chất cấu trúc của không gian nghiệm tối ưu, thiết lập công thức xác định các biên chặn $GLB$ và $LUB$.
  3. 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ơ sở và các bài toán mở rộng ($setup-time$, $deadline$, $TWSP$).
  4. Sáng tạo giải thuật Matheuristics $E4SSJ$ và hệ thống các thuật toán Heuristics/Metaheuristics cải tiến với các toán tử lân cận chuyên dụng ($EBSR$, $EFSR$), vượt trội hoàn toàn về hiệu năng tính toán.
  5. Thực nghiệm quy mô lớn trên các bộ dữ liệu chuẩn DS1 và DS2, chứng minh tính ưu việt vượt bậc của các giải pháp đề xuất so với các bộ giải thương mại và phương pháp cổ điển.
  6. Mở ra một phân nhánh nghiên cứu khoa học mới giàu tiềm năng ứng dụng: Lập lịch tối ưu hướng con người và nhóm cộng tác hiện đại.