Tổng quan về luận án

Trong bối cảnh toàn cầu hóa chuỗi cung ứng và sự chuyển dịch phương thức sản xuất từ mô hình "đẩy" (push system) sang mô hình "kéo" (pull system), bài toán lập lịch sản xuất đóng vai trò then chốt trong việc tối ưu hóa tài nguyên và nâng cao năng lực cạnh tranh doanh nghiệp. Luận án tiến sĩ chuyên ngành Khoa học Máy tính (Informatique) với tiêu đề "Complexité et algorithmes pour l’ordonnancement multicritère de travaux indépendants : problèmes juste-à-temps et travaux interférants" (Độ phức tạp và thuật toán cho bài toán lập lịch đa mục tiêu các tác vụ độc lập: Các bài toán Đúng-Thời-Điểm và tác vụ can thiệp) được thực hiện bởi nghiên cứu sinh Nguyen Huynh Tuong tại Phòng thí nghiệm Khoa học Máy tính (Laboratoire d’Informatique - EA 2101), Đại học François-Rabelais de Tours (Pháp), dưới sự hướng dẫn khoa học của PGS. Ameur Soukhal và GS. Jean-Charles Billaut, bảo vệ thành công ngày 17 tháng 6 năm 2009 trước hội đồng giám khảo quốc tế gồm các chuyên gia đầu ngành như GS. Philippe Baptiste (CNRS/École Polytechnique), GS. Philippe Chrétienne (Université Pierre et Marie Curie - Paris VI), GS. Alessandro Agnetis (Università di Siena), GS. Jacques Carlier (Université de Technologie de Compiègne) và GS. Emmanuel Néron.

Nghiên cứu tập trung giải quyết khoảng trống học thuật (research gap) cốt lõi trong lý thuyết lập lịch tổ hợp (combinatorial scheduling theory): tính phi chính quy (non-regular criteria) của hàm mục tiêu trong hệ thống Đúng-Thời-Điểm (Just-in-Time - JIT / Juste-à-temps) và cấu trúc cạnh tranh tài nguyên đa tác tử bất đối xứng (interfering jobs / multi-agent scheduling). Các mô hình cổ điển thường chỉ tối ưu hóa các tiêu chuẩn chính quy như Cực tiểu hóa thời gian hoàn thành cực đại ($C_{\max}$ - makespan) hay Trễ hạn lớn nhất ($L_{\max}$). Tuy nhiên, thực tiễn sản xuất tinh gọn (Lean manufacturing) đòi hỏi loại bỏ triệt để lãng phí (Muda) từ cả hai phía: giao hàng trễ (phạt trễ hạn) và giao hàng sớm (phát sinh chi phí tồn kho, bảo quản).

Khung câu hỏi nghiên cứu và giả thuyết được định hình xuyên suốt hai phần chính:

  1. Câu hỏi nghiên cứu 1 (RQ1): Trong bài toán lập lịch JIT với hạn định chung ($d_i = d$), làm thế nào để xây dựng các thuật toán quy hoạch động (Dynamic Programming) và lược đồ xấp xỉ đa thức (PTAS/FPTAS) hiệu quả cho hệ thống một máy ($1$) và nhiều máy song song đồng nhất ($Pm$) hoặc tỷ lệ ($Qm$)?
  2. Câu hỏi nghiên cứu 2 (RQ2): Đối với các tác vụ có thời gian thực thi bằng nhau ($p_i = p$) hoặc tùy ý, việc kiểm soát hạn định (controllable due dates: CON, SLK, TWK, PPW) tương tác như thế nào với cấu trúc nghiệm dạng chữ V (V-shape property) để đạt nghiệm tối ưu toàn cục?
  3. Câu hỏi nghiên cứu 3 (RQ3): Khi các tập tác vụ độc lập can thiệp lẫn nhau ($N_1 \subset N$), ranh giới độ phức tạp tính toán giữa các lớp bài toán giải được trong thời gian đa thức ($P$), $NP$-khó theo nghĩa thông thường (NP-hard in the ordinary sense) và $NP$-khó theo nghĩa mạnh (strongly NP-hard) được phân định ra sao dưới các tiếp cận $\varepsilon$-ràng buộc ($\varepsilon$-constraint), tổ hợp tuyến tính (linear combination) và quy hoạch mục tiêu (goal programming)?

Giả thuyết nghiên cứu:

  • H1: Tồn tại thuật toán quy hoạch động với độ phức tạp giả đa thức giải chính xác bài toán cực tiểu hóa tổng độ trễ có trọng số $\sum w_i T_i$ trên $m$ máy song song khi có hạn định chung hoặc họ hạn định rời rạc.
  • H2: Cấu trúc hình học của ma trận chi phí gán (assignment cost matrix) cho phép chuyển đổi bài toán JIT với thời gian xử lý bằng nhau ($p_i = p$) về bài toán phân công cổ điển (Linear Assignment Problem) giải được trong thời gian đa thức $O(n^3)$.
  • H3: Tiếp cận $\varepsilon$-ràng buộc trên bài toán tác vụ can thiệp thiết lập được các mặt biên Pareto tối ưu thông qua các thuật toán đa thức hoặc giả đa thức khi một trong các hàm mục tiêu là chính quy.

Nghiên cứu sử dụng khung lý thuyết tối ưu hóa tổ hợp phân loại theo ký hiệu 3 trường của Graham ($\alpha|\beta|\gamma$), lý thuyết độ phức tạp tính toán của Garey & Johnson (1978), lý thuyết xấp xỉ đa thức của Woeginger (2000), và mở rộng lý thuyết lập lịch đa tác tử của Agnetis et al. (2004). Về quy mô, công trình phân tích toán học toàn diện trên tập $n$ tác vụ tùy ý, xây dựng các cấu trúc dữ liệu và thuật toán được chứng minh độ phức tạp chặt chẽ từ $O(n \log n)$, $O(n^3)$ đến các FPTAS đạt độ chính xác sai số tương đối $\varepsilon > 0$.

Literature Review và Positioning

Lý thuyết lập lịch Đúng-Thời-Điểm (JIT) bắt nguồn từ hệ thống sản xuất Toyota do Taiichi Ohno khởi xướng nhằm triệt tiêu lãng phí. Trong luận án, tác giả trích dẫn nhận định sâu sắc của Sourd [199]: "l’idée de base est d’éviter toute production anticipée de produits intermédiaires ou finaux, ce qui signifie que le producteur se contente de produire la quantité strictement nécessaire, au moment voulu, pour satisfaire la demande de chaque client. Ainsi, c’est la date à laquelle le client demande à être livré qui fixe la date de livraison du produit mais, le JàT va même plus loin : toutes les dates de toutes les opérations de la fabrication du produit livré sont également fixées de manière à ce qu’il n’y ait pas de temps mort dans la chaîne de fabrication." Quan điểm này củng cố triết lý của Sensei Yoshida trong Lean Training Newsletter [225]: “être lean c’est arrêter de surproduire”, coi sản xuất thừa là nguyên nhân cốt lõi dẫn đến lãng phí vốn và diện tích lưu kho.

Trong dòng nghiên cứu về hàm mục tiêu sớm/trễ (Early/Tardy - $E/T$), Kanet [129] đặt nền móng cho bài toán $1|d_i = d, \text{unrestrictive}|\sum (E_i + T_i)$ với thuật toán $O(n^2)$, chứng minh nghiệm tối ưu luôn tuân theo quy tắc dạng chữ V (V-shape): các tác vụ hoàn thành sớm xếp theo thứ tự thời gian xử lý giảm dần (LPT - Longest Processing Time First), và các tác vụ trễ hạn xếp theo thứ tự thời gian xử lý tăng dần (SPT - Shortest Processing Time First). Hall, Kubiak và Sethi [85], cùng với Emmons [61], đã mở rộng tính chất V-shape cho các mô hình tổng quát. Tuy nhiên, bài toán với trọng số bất kỳ $1|d_i = d|\sum (\alpha_i E_i + \beta_i T_i)$ đã được Hall, Kubiak và Sethi [87] chứng minh là $NP$-khó theo nghĩa thông thường.

                  ┌──────────────────────────────────────────────────────────┐
                  │                 Lập lịch Đa Mục tiêu                     │
                  └─────────────┬──────────────────────────────┬─────────────┘
                                │                              │
                                ▼                              ▼
    ┌───────────────────────────────────────┐  ┌─────────────────────────────────────────┐
    │  Tiêu chuẩn JIT (Phi chính quy)       │  │  Tác vụ can thiệp (Interfering jobs)    │
    │  - Hàm phạt Sớm/Trễ: α_i E_i + β_i T_i │  │  - Đa tác tử cạnh tranh: N_1 ⊂ N        │
    │  - Hạn định: d cố định / kiểm soát    │  │  - Tiếp cận: ε-contrainte, Goal Prog.   │
    │  - Tính chất hình học: V-shape        │  │  - Tối ưu Pareto, phân tích P vs NP-hard│
    └───────────────────┬───────────────────┘  └────────────────────┬────────────────────┘
                        │                                           │
                        ▼                                           ▼
    ┌───────────────────────────────────────┐  ┌─────────────────────────────────────────┐
    │  Thuật toán Quy hoạch động & PTAS/FPTAS│  │  Thuật toán Đa thức & Quy hoạch động    │
    │  - Phân tích ranh giới Lawler & Moore │  │  - Phân loại độ phức tạp chặt chẽ       │
    │  - Cắt tỉa không gian trạng thái      │  │  - Ma trận chi phí gán (Assignment)     │
    └───────────────────────────────────────┘  └─────────────────────────────────────────┘

Về bài toán cực tiểu hóa tổng độ trễ có trọng số $\sum w_i T_i$, Lawler và Moore [150] đã đề xuất thuật toán quy hoạch động kinh điển với độ phức tạp $O(n^2 d)$ cho bài toán một máy $1|d_i=d|\sum w_i T_i$. Tuy nhiên, luận án của Nguyen Huynh Tuong chỉ ra một lỗ hổng quan trọng: việc mở rộng trực tiếp công thức quy hoạch động của Lawler & Moore sang môi trường nhiều máy song song ($Pm$) không hề hiển nhiên và tiềm ẩn sai số về cấu trúc truy hồi nếu không xác định đúng trạng thái hoàn thành của từng máy. Đối với bài toán tổng quát $1|d_i|\sum w_i T_i$, Lenstra, Rinnooy Kan và Brucker [154] đã chứng minh tính chất $NP$-khó theo nghĩa mạnh.

Luận án định vị nghiên cứu thông qua việc so sánh đối sánh trực tiếp với hai công trình quốc tế mang tính bước ngoặt:

  1. Nghiên cứu của Kellerer và Strusevich [133]: Phát triển một FPTAS có độ phức tạp $O(n^6 \log W / \varepsilon^3)$ cho bài toán $1|d_i = d|\sum w_i T_i$ (với $W = \sum w_i$). Luận án của Nguyen Huynh Tuong đi xa hơn khi thiết lập cấu trúc quy hoạch động chặt chẽ cho hệ thống máy song song $Pm$ và $Qm$, mở ra đường hướng xấp xỉ hoàn chỉnh khi có họ hạn định rời rạc ($|D| = l$).
  2. Nghiên cứu của Kovalyov và Werner [141]: Chứng minh rằng bài toán trên máy song song $Pm|d_i = d|\sum T_i$ không thuộc lớp $APX$ (tức không tồn tại thuật toán xấp xỉ với tỷ số hằng số trừ phi $P=NP$), đồng thời đề xuất lược đồ xấp xỉ thỏa mãn $(X^\sharp - X^) \le \varepsilon(X^ + d)$. Luận án của Nguyen Huynh Tuong bổ khuyết và hoàn thiện bức tranh lý thuyết này bằng cách đưa ra các thuật toán xấp xỉ đa thức PTAS cho bài toán tổng chi phí sớm trễ $\sum (\alpha_i E_i + \beta_i T_i)$ trên một máy và $m$ máy song song đồng nhất.

Song song đó, trong mảng nghiên cứu tác vụ can thiệp (interfering jobs), luận án kế thừa và mở rộng công trình tiên phong của Agnetis, Mirchandani, Pacciarelli và Pacifici [121, 2004] về lập lịch đa tác tử (multi-agent scheduling). Điểm đột phá của luận án là khảo sát các mô hình bất đối xứng: hàm mục tiêu thứ nhất được tính trên toàn bộ tập tác vụ $N$, trong khi hàm mục tiêu thứ hai chỉ tác động trên tập con $N_1 \subset N$, phản ánh chính xác bài toán thực tế của các doanh nghiệp khi phải thỏa mãn chỉ số hiệu năng chung của nhà máy đồng thời đáp ứng các cam kết dịch vụ (SLA) khắt khe cho một nhóm khách hàng chiến lược.

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

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

Luận án tạo ra những bước tiến lý thuyết cơ bản trong tối ưu hóa tổ hợp và lý thuyết thuật toán:

  1. Hoàn thiện và sửa đổi cấu trúc quy hoạch động Lawler & Moore: Luận án chứng minh rằng công thức truy hồi kinh điển của Lawler và Moore [150] không thể áp dụng trực tiếp cho hệ thống máy song song $Pm|d_i=d|\sum w_i T_i$. Tác giả thiết lập một hàm đệ quy mới dựa trên không gian trạng thái đa chiều, theo dõi chính xác thời điểm rảnh rỗi của từng máy và phân loại rõ ràng vị trí tác vụ rơi vào vùng hoàn thành sớm ($C_i \le d$), vùng trễ hoàn toàn ($S_i \ge d$), hay tác vụ vắt ngang hạn định ("straddling job" với $S_i < d < C_i$).
  2. Thiết lập tính chất V-shape mở rộng: Chứng minh tính tối ưu của cấu trúc sắp xếp LPT-SPT cho các biến thể hạn định kiểm soát được (controllable due dates: SLK, TWK, PPW) trên máy đơn và máy song song, làm rõ điều kiện biên của các hệ số phạt $(\alpha, \beta, \gamma)$.
  3. Phân loại độ phức tạp toàn diện cho bài toán tác vụ can thiệp: Luận án hoàn thiện bản đồ độ phức tạp (Complexity Landscape) cho các bài toán trên một máy và máy song song khi kết hợp các hàm mục tiêu $\sum C_j(N)$, $\sum w_j C_j(N)$, $C_{\max}(N)$, $L_{\max}(N)$ với các hàm tương ứng trên tập con $N_1$, xác lập ranh giới phân định rõ ràng giữa lớp $P$, $NP$-khó thông thường và $NP$-khó theo nghĩa mạnh.

$$\begin{aligned} \text{Mô hình SLK:} \quad & d_i = p_i + q \ \text{Mô hình TWK:} \quad & d_i = k \cdot p_i \ \text{Mô hình PPW:} \quad & d_i = k \cdot p_i + q \ \text{Mô hình NOP:} \quad & d_i = k \cdot n_i \end{aligned}$$

                ┌─────────────────────────────────────────────────────────────┐
                │          Cấu trúc tối ưu nghiệm chữ V (V-Shape)             │
                └──────────────────────────────┬──────────────────────────────┘
                                               │
                                               ▼
                         ┌──────────────────────────────────────────┐
                         │   Hạn định chung d (Common Due Date)     │
                         └───────┬──────────────────────────┬───────┘
                                 │                          │
                 Vùng Sớm (Early Jobs)                      Vùng Trễ (Tardy Jobs)
                 C_i ≤ d                                    C_i > d
                 ┌───────────────┐                          ┌───────────────┐
                 │  Quy tắc LPT  │                          │  Quy tắc SPT  │
                 │  p_1 ≥ p_2... │                          │  p_k ≤ p_k+1..│
                 └───────────────┘                          └───────────────┘

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

Khung phân tích của luận án tích hợp liên ngành ba trụ cột lý thuyết: Lý thuyết Lập lịch cổ điển, Lý thuyết Tối ưu hóa Đa mục tiêu (MCDA), và Lý thuyết Xấp xỉ Thuật toán (Approximation Theory).

Phương pháp tiếp cận giải tích mới dựa trên việc chuyển đổi không gian bài toán:

  • Kỹ thuật ma trận chi phí gán (Assignment Cost Matrix Reformulation): Đối với các tác vụ có thời gian thực thi đồng nhất ($p_i = p$), hàm mục tiêu sớm/trễ $\sum (\alpha_i E_i + \beta_i T_i)$ được tuyến tính hóa thành bài toán phân công vị trí tối ưu trên trục thời gian. Chi phí gán tác vụ $J_i$ vào vị trí $j$ trên máy $k$ được biểu diễn giải tích tường minh, cho phép giải quyết chính xác bằng thuật toán Hungary trong thời gian $O(n^3)$.
  • Kỹ thuật xử lý tiêu chuẩn phi chính quy (Non-regular criteria & Optimal timing): Khắc phục hiện tượng nghiệm tối ưu xuất hiện khoảng thời gian chết (temps morts / idle times) có chủ đích giữa các tác vụ để ghìm thời gian hoàn thành sát với hạn định mong muốn $d$.
  • Kỹ thuật rút gọn không gian trạng thái (Trimming the state space) & Làm tròn dữ liệu (Rounding the input data): Chuyển đổi các thuật toán quy hoạch động giả đa thức thành các lược đồ xấp xỉ PTAS và FPTAS, kiểm soát chặt chẽ sai số tương đối $\varepsilon$ trong giới hạn tính toán đa thức.

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

Thiết kế nghiên cứu

Nghiên cứu được xây dựng trên nền tảng triết học toán học thực chứng (positivism / formal mathematical proof) và chuẩn mực thuật toán suy luận diễn dịch nghiêm ngặt:

┌──────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                   Quy trình Thiết kế Nghiên cứu                                   │
└──────────────────────────────────────────────────────────────────────────────────────────────────┘
  [Mô hình hóa Toán học] ──► [Phân tích Độ phức tạp] ──► [Thiết kế Thuật toán] ──► [Đánh giá Xấp xỉ]
  - Ký hiệu Graham 3 trường    - Quy dẫn Đa thức (Reductions) - Quy hoạch động (ProgDyn) - Chứng minh Bound:
  - Hàm mục tiêu JIT/Interfer. - 3-PARTITION, SUBSET-SUM      - Matrix Assignment         f(A(I)) ≤ (1+ε)f*(I)
  - Biến quyết định d, S_i, C_i - Phân loại P vs NP-hard      - Thuật toán Tham lam       - Phân tích Time/Space
  • Mô hình hóa toán học: Biểu diễn các bài toán lập lịch dưới dạng tối ưu hóa tổ hợp rời rạc với các ràng buộc tài nguyên $m$ máy song song ($1, Pm, Qm$).
  • Phân tầng thiết kế đa cấp (Multi-level design): Khảo sát từ trường hợp cơ sở đơn giản (1 máy, thời gian xử lý bằng nhau $p_i = p$, hạn định cho trước) đến các trường hợp tổng quát phức tạp (nhiều máy song song tỷ lệ $Qm$, thời gian xử lý tùy ý $p_i$, hạn định kiểm soát được, đa tác tử can thiệp).
  • Ranh giới bài toán (Boundary conditions): Giả định các tác vụ hoàn toàn độc lập, không có thời gian thiết lập phụ thuộc chuỗi (sequence-dependent setup times), không cho phép ngắt quãng (non-preemptive scheduling), và năng lực xử lý của các máy là tiền định (deterministic).

Quy trình nghiên cứu rigorous

Quy trình phát triển và kiểm chứng thuật toán tuân thủ các bước chứng minh toán học chuẩn mực:

  1. Chứng minh Độ phức tạp (Complexity Proofs): Sử dụng các kỹ thuật quy dẫn đa thức (polynomial reductions) từ các bài toán $NP$-đầy đủ kinh điển như PARTITION, SUBSET-SUM, và 3-PARTITION để xác định ngưỡng $NP$-khó theo nghĩa thông thường hoặc nghĩa mạnh.
  2. Xây dựng Thuật toán Chính xác (Exact Algorithms):
    • Thiết lập các hệ thức truy hồi quy hoạch động tối ưu (Bellman equations).
    • Chứng minh tính đúng đắn (Correctness) bằng quy nạp toán học.
    • Phân tích độ phức tạp thời gian (Time complexity) và không gian bộ nhớ (Space complexity).
  3. Xây dựng Lược đồ Xấp xỉ (Approximation Schemes):
    • Thiết kế thuật toán xấp xỉ $A$ sao cho với mọi bộ dữ liệu đầu vào $I$ và sai số cho trước $\varepsilon > 0$, giá trị hàm mục tiêu thỏa mãn:

$$\frac{f(A(I)) - f^(I)}{f^(I)} \le \varepsilon \quad \Longleftrightarrow \quad f(A(I)) \le (1 + \varepsilon) f^*(I)$$

Data và phân tích

Do bản chất là một công trình nghiên cứu lý thuyết toán tin và tối ưu hóa tổ hợp, "dữ liệu" trong luận án được cấu thành từ các không gian mẫu dữ liệu toán học trừu tượng (instances), các bộ dữ liệu chuẩn và các ma trận phân tích:

  • Bộ thông số đầu vào: Tập $n$ tác vụ với các vector thời gian gia công $P = (p_1, p_2, \dots, p_n)$, vector trọng số phạt $W = (w_1, w_2, \dots, w_n)$, hệ số phạt sớm/trễ $\alpha = (\alpha_1, \dots, \alpha_n)$, $\beta = (\beta_1, \dots, \beta_n)$, hạn định $d$ hoặc họ hạn định $D = {D_1, D_2, \dots, D_l}$.
  • Kỹ thuật phân tích cấu trúc: Sử dụng đại số ma trận biểu diễn chi phí gán tác vụ (assignment matrix), phân tích hình học các điểm chuyển tiếp thời gian chết trên đồ thị biểu diễn tiến độ gia công.
  • Kiểm tra độ vững (Robustness checks): Kiểm tra tính đóng của các thuật toán quy hoạch động dưới các điều kiện biên cực hạn (ví dụ: hạn định rất lớn - non-restrictive due dates, hạn định chặt chẽ - restrictive due dates, trọng số suy biến về dạng đơn vị $\alpha_i = \beta_i = 1$).

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

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

Luận án công bố 5 nhóm kết quả đột phá mang tính hệ thống cho lý thuyết lập lịch:

  1. Sửa đổi và tổng quát hóa Quy hoạch động Lawler & Moore: Luận án chứng minh công thức quy hoạch động cổ điển $O(n^2 d)$ chỉ đúng cho trường hợp 1 máy. Tác giả phát triển thuật toán quy hoạch động mới giải quyết bài toán trên $m$ máy song song đồng nhất $Pm|d_i=d|\sum w_i T_i$ và mở rộng thành công cho máy song song tỷ lệ tốc độ $Qm|d_i=d|\sum w_i T_i$, đồng thời tổng quát hóa cho trường hợp họ gồm $l$ hạn định rời rạc $Pm|d_i \in D, |D|=l|\sum w_i T_i$.
  2. Giải quyết bài toán JIT với thời gian xử lý bằng nhau trong thời gian đa thức: Chứng minh rằng các bài toán JIT phức tạp gồm $1|p_i=p, d_i=d|\sum (\alpha_i E_i + \beta_i T_i)$, trường hợp 2 hạn định $1|p_i=p, d_i \in {D_1, D_2}|\sum (\alpha_i E_i + \beta_i T_i)$, họ $k$ hạn định $1|p_i=p, d_i \in D, |D|=k|\sum (\alpha_i E_i + \beta_i T_i)$, và máy song song tỷ lệ $Qm|p_i=p, d_i \in D, |D|=k|\sum (\alpha_i E_i + \beta_i T_i)$ đều được quy dẫn tương đương về bài toán phân công tuyến tính và giải chính xác trong thời gian đa thức $O(n^3)$ hoặc $O(mn^3)$.
  3. Thiết lập lược đồ xấp xỉ PTAS cho bài toán E/T tổng quát: Đề xuất thành công lược đồ xấp xỉ đa thức PTAS cho bài toán $1|d_j = d, \text{non-restrictive}|\sum (\alpha_i E_i + \beta_i T_i)$ và mở rộng cho hệ thống $m$ máy song song $Pm|d_j = d, \text{non-restrictive}|\sum (\alpha_i E_i + \beta_i T_i)$, vượt qua rào cản tính toán của bài toán vốn đã được chứng minh là $NP$-khó.
  4. Tối ưu hóa bài toán hạn định kiểm soát được (Controllable Due Dates): Đối với bài toán gán hạn định chung kết hợp chi phí duy trì hạn định $\sum (\alpha_i E_i + \beta_i T_i + \gamma d)$, luận án đưa ra các thuật toán giải chính xác đa thức khi thời gian gia công bằng nhau ($p_i = p$) trên $1, Pm, Qm$, và thuật toán nhánh cận / quy hoạch động cho trường hợp thời gian gia công tùy ý.
  5. Bản đồ phân loại toàn diện cho bài toán tác vụ can thiệp (Interfering Jobs): Xác định độ phức tạp chính xác cho 16 biến thể bài toán lập lịch đa tác tử trên 1 máy và máy song song:
    • Các bài toán giải được trong thời gian đa thức: $1||\varepsilon(\sum C_j(N) / C_{\max}(N_1))$, $1||\varepsilon(\sum C_j(N) / \sum C_j(N_1))$ khi các trọng số bằng nhau.
    • Các bài toán $NP$-khó theo nghĩa thông thường: $1||\varepsilon(\sum w_j C_j(N) / C_{\max}(N_1))$, $1||\varepsilon(C_{\max}(N) / \sum w_j C_j(N_1))$.
    • Các bài toán $NP$-khó theo nghĩa mạnh: $1||\varepsilon(\sum w_j C_j(N) / \sum w'_j C_j(N_1))$ với trọng số bất kỳ.
┌─────────────────────────────────────────────────────────────────────────────────────────────────┐
│              Tóm tắt Phân loại Độ phức tạp cho Bài toán Tác vụ Can thiệp (1 Máy)                 │
├───────────────────────────────────────────┬─────────────────────────────┬───────────────────────┤
│ Hàm Mục tiêu Kép (Toàn thể N / Tập con N1)│ Trọng số / Tham số          │ Phân loại Độ phức tạp │
├───────────────────────────────────────────┼─────────────────────────────┼───────────────────────┤
│ ∑ C_j(N) và C_max(N1)                     │ Đơn vị (w_j = 1)            │ Đa thức - P           │
│ ∑ C_j(N) và ∑ C_j(N1)                     │ Đơn vị (w_j = 1)            │ Đa thức - P           │
│ ∑ w_j C_j(N) và C_max(N1)                 │ Trọng số bất kỳ             │ NP-khó thông thường   │
│ C_max(N) và ∑ w_j C_j(N1)                 │ Trọng số bất kỳ             │ NP-khó thông thường   │
│ ∑ w_j C_j(N) và ∑ w'_j C_j(N1)            │ Trọng số độc lập            │ NP-khó theo nghĩa mạnh│
└───────────────────────────────────────────┴─────────────────────────────┴───────────────────────┘

Implications đa chiều

  • Về mặt Lý thuyết: Công trình tái định nghĩa ranh giới giữa tính khả giải đa thức và tính bất khả giải thuật toán trong lý thuyết lập lịch hiện đại. Việc tích hợp thành công cấu trúc V-shape vào mô hình toán học giải tích cung cấp một công cụ mạnh mẽ để nghiên cứu các hàm mục tiêu phi chính quy phức tạp hơn trong tương lai.
  • Về mặt Phương pháp luận: Cung cấp phương pháp mẫu mực trong việc chuyển hóa thuật toán quy hoạch động thành lược đồ xấp xỉ hoàn toàn đa thức (FPTAS/PTAS) thông qua kỹ thuật làm tròn và cắt tỉa không gian trạng thái. Kỹ thuật này có thể tái sử dụng trực tiếp cho các bài toán tối ưu hóa tổ hợp khác trong logistics và vận tải.
  • Về mặt Thực tiễn Sản xuất: Các thuật toán đề xuất giải quyết triệt để bài toán đồng bộ hóa trong dây chuyền lắp ráp công nghiệp (nơi các linh kiện phải hoàn thành đúng thời điểm ghép nối) và bài toán điều phối đơn hàng trong các trung tâm phân phối thương mại điện tử.
  • Về mặt Quản trị Chuỗi Cung ứng: Cung cấp cơ sở khoa học để các nhà quản lý đàm phán hạn định giao hàng ($d$) với khách hàng thông qua mô hình hạn định kiểm soát được, cân bằng tối ưu giữa chi phí sản xuất, chi phí lưu kho và mức độ hài lòng của đối tác.

Limitations và Future Research

Luận án thẳng thắn thừa nhận các giới hạn học thuật và biên tế nghiên cứu:

  1. Giới hạn môi trường tiền định (Deterministic Assumption): Toàn bộ mô hình toán học giả định thời gian gia công $p_i$, trọng số $w_i$, và hạn định $d$ là các đại lượng xác định hoàn toàn. Trong thực tế xưởng sản xuất, các yếu tố ngẫu nhiên như máy hỏng đột xuất, dao động thời gian gia công, hay thay đổi đơn hàng khẩn cấp chưa được tích hợp vào mô hình ngẫu nhiên (Stochastic scheduling).
  2. Giới hạn về mô hình máy: Nghiên cứu chủ yếu dừng lại ở môi trường 1 máy và các máy song song độc lập ($Pm, Qm$). Các cấu trúc xưởng sản xuất phức tạp hơn như xưởng dòng (Flow-shop), xưởng linh hoạt (Job-shop), hay xưởng mở (Open-shop) với tiêu chuẩn JIT và tác vụ can thiệp chưa được bao quát toàn diện.
  3. Giả định không ngắt quãng (Non-preemption): Các thuật toán được thiết kế dưới điều kiện tác vụ khi đã bắt đầu gia công trên máy thì không thể bị tạm dừng.

Chương trình nghiên cứu tương lai (Future Research Agenda):

  • Mở rộng 1: Phát triển các thuật toán xấp xỉ trực tuyến (Online algorithms) và thuật toán thích ứng mạnh mẽ (Robust scheduling) khi dữ liệu về tác vụ chỉ được tiết lộ dần theo thời gian thực.
  • Mở rộng 2: Khảo sát bài toán JIT và tác vụ can thiệp trên hệ thống Flow-shop đa tầng có tính đến thời gian chuyển đổi và thiết lập phụ thuộc chuỗi gia công (sequence-dependent setup times).
  • Mở rộng 3: Mở rộng lý thuyết tác vụ can thiệp cho trường hợp $K$ tác tử tổng quát ($K \ge 3$) với các cấu trúc ràng buộc tài nguyên phi tuyến tính.
  • Mở rộng 4: Tích hợp trí tuệ nhân tạo và học tăng cường (Reinforcement Learning) để tối ưu hóa không gian tìm kiếm trạng thái trong các thuật toán quy hoạch động quy mô cực lớn.

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

Luận án đã tạo ra những ảnh hưởng sâu rộng trên nhiều bình diện:

  • Tác động Học thuật: Được đánh giá xuất sắc bởi hội đồng chấm luận án gồm các giáo sư hàng đầu châu Âu. Các kết quả nghiên cứu đã được công bố trên các tạp chí quốc tế uy tín và kỷ yếu hội nghị chuyên ngành hàng đầu về Tối ưu hóa tổ hợp và Nghiên cứu vận hành (như Computers & Operations Research, European Journal of Operational Research, Journal of Scheduling). Các công thức quy hoạch động và chứng minh độ phức tạp trong luận án trở thành tài liệu tham khảo nền tảng cho các nghiên cứu tiếp nối về lập lịch đa tác tử.
  • Chuyển dịch Công nghiệp: Cung cấp thuật toán lõi cho các hệ thống phần mềm điều hành sản xuất (MES - Manufacturing Execution Systems) và hệ thống hoạch định tài nguyên doanh nghiệp (ERP), đặc biệt trong các ngành công nghiệp lắp ráp ô tô, sản xuất bán dẫn, và công nghiệp đóng gói thực phẩm tươi sống.
  • Đóng góp Xã hội & Môi trường: Việc tối ưu hóa lịch trình sản xuất Đúng-Thời-Điểm giúp các nhà máy giảm thiểu đáng kể mức tiêu thụ năng lượng của máy móc trong thời gian chờ (idle power consumption), đồng thời cắt giảm lãng phí vật tư do lưu kho quá hạn, đóng góp trực tiếp vào mục tiêu sản xuất xanh và bền vững.

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

┌─────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                   Đối tượng Thụ hưởng Nghiên cứu                                │
├──────────────────────────┬──────────────────────────────────────────────────────────────────────┤
│ Nhóm Đối tượng           │ Lợi ích và Giá trị Chuyển giao Cụ thể                                │
├──────────────────────────┼──────────────────────────────────────────────────────────────────────┤
│ Nghiên cứu sinh &        │ Kế thừa khung lý thuyết phân loại độ phức tạp, phương pháp quy dẫn   │
│ Nhà nghiên cứu OR/CS     │ đa thức và kỹ thuật thiết kế FPTAS/PTAS cho các hàm phi chính quy.   │
├──────────────────────────┼──────────────────────────────────────────────────────────────────────┤
│ Giảng viên & Chuyên gia  │ Giáo trình mẫu mực về ứng dụng Quy hoạch động nâng cao và tối ưu     │
│ Tối ưu hóa Tổ hợp        │ đa mục tiêu trong khoa học máy tính lý thuyết.                       │
├──────────────────────────┼──────────────────────────────────────────────────────────────────────┤
│ Kỹ sư R&D phần mềm       │ Các thuật toán đa thức $O(n^3)$ và lược đồ xấp xỉ sẵn sàng cài đặt   │
│ Quản phối Sản xuất (MES) │ vào các module lập lịch tự động, giải phóng thời gian tính toán.     │
├──────────────────────────┼──────────────────────────────────────────────────────────────────────┤
│ Giám đốc Vận hành &      │ Công cụ định lượng giúp ra quyết định tối ưu hóa hạn định giao hàng, │
│ Quản lý Chuỗi Cung ứng   │ cân bằng chính xác chi phí lưu kho và uy tín giao hàng đúng hẹn.     │
└──────────────────────────┴──────────────────────────────────────────────────────────────────────┘

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

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và mở rộng lý thuyết nào?

Đóng góp độc đáo nhất là việc tái cấu trúc và sửa đổi toàn diện thuật toán quy hoạch động kinh điển của Lawler & Moore (1969). Luận án chứng minh rằng phương trình quy nạp trạng thái của Lawler & Moore không thể suy rộng trực tiếp cho hệ thống máy song song, từ đó thiết lập phương trình đệ quy đa chiều mới cho các bài toán $Pm|d_i=d|\sum w_i T_i$ và $Qm|d_i=d|\sum w_i T_i$. Đồng thời, luận án đã mở rộng lý thuyết lập lịch đa tác tử của Agnetis et al. (2004) sang mô hình tác vụ can thiệp bất đối xứng ($N_1 \subset N$).

2. Đổi mới phương pháp luận của luận án vượt trội hơn các nghiên cứu trước đây ra sao?

So với nghiên cứu của Kellerer & Strusevich [133] (chỉ tập trung vào FPTAS cho 1 máy) và Kovalyov & Werner [141] (chứng minh tính bất khả xấp xỉ trong $APX$ của máy song song), luận án đã:

  • Tuyến tính hóa cấu trúc bài toán JIT với thời gian xử lý bằng nhau về bài toán phân công ma trận giải được trong $O(n^3)$.
  • Phát triển thành công kỹ thuật xấp xỉ PTAS cho bài toán tổng chi phí sớm/trễ $\sum (\alpha_i E_i + \beta_i T_i)$ trên hệ thống $m$ máy song song.
  • Tích hợp đồng thời 3 cách tiếp cận đa mục tiêu ($\varepsilon$-ràng buộc, tổ hợp tuyến tính, quy hoạch mục tiêu) trên cùng một cấu trúc dữ liệu quy hoạch động thống nhất.

3. Phát hiện nào trong luận án gây bất ngờ nhất về mặt toán học?

Phát hiện bất ngờ nhất là tính khả giải đa thức của bài toán họ hạn định rời rạc khi thời gian gia công bằng nhau: bài toán phức tạp $Qm|p_i=p, d_i \in D, |D|=k|\sum (\alpha_i E_i + \beta_i T_i)$ với $k$ hạn định khác nhau và tốc độ máy khác nhau tưởng chừng là $NP$-khó, nhưng lại được quy dẫn chính xác về bài toán phân công tuyến tính $O(mn^3)$ nhờ phát hiện cấu trúc không gian thời gian chết tối ưu có tính chất chu kỳ và đối xứng.

4. Luận án có cung cấp quy trình tái lập thuật toán (Replication Protocol) không?

Có. Toàn bộ các thuật toán trong luận án (như thuật toán WTP2CDD, WTQ2CDD, AssQm1, các thuật toán xấp xỉ PTAS) đều được trình bày chi tiết dưới dạng mã giả (pseudo-code) chuẩn hóa, kèm theo các ví dụ số học minh họa từng bước chạy của ma trận gán, bảng quy hoạch động và chứng minh toán học tường minh về tính hội tụ và chặn sai số.

5. Chương trình nghiên cứu 10 năm được định hình từ luận án như thế nào?

Luận án mở ra lộ trình nghiên cứu dài hạn tập trung vào:

  • Chuyển đổi từ mô hình tiền định sang lập lịch ngẫu nhiên (Stochastic JIT scheduling) và lập lịch trực tuyến (Online interfering jobs).
  • Khám phá các thuật toán tham lam ngẫu nhiên hóa và siêu phỏng đoán (metaheuristics: di truyền, tìm kiếm Tabu, tối ưu bầy đàn) kết hợp quy hoạch động để giải quyết các bài toán công nghiệp quy mô hàng chục nghìn tác vụ.
  • Phát triển lý thuyết trò chơi hợp tác (Cooperative Game Theory) trong lập lịch đa tác tử với cơ chế phân chia chi phí công bằng.

Kết luận

Luận án tiến sĩ của Nguyen Huynh Tuong là một công trình khoa học mẫu mực, xuất sắc và toàn diện trong lĩnh vực Tối ưu hóa Tổ hợp và Khoa học Máy tính lý thuyết.

Năm đóng góp cốt lõi mang tính nền tảng của công trình bao gồm:

  1. Thiết lập lại nền tảng quy hoạch động chính xác cho bài toán cực tiểu hóa tổng độ trễ có trọng số trên máy song song ($Pm, Qm$) với hạn định chung và họ hạn định rời rạc.
  2. Khám phá và chứng minh tính khả giải đa thức $O(n^3)$ cho một họ lớn các bài toán Đúng-Thời-Điểm với thời gian gia công đồng nhất thông qua kỹ thuật ma trận chi phí gán.
  3. Phát triển thành công các lược đồ xấp xỉ đa thức PTAS cho bài toán tối ưu hóa sớm/trễ phi chính quy trên máy đơn và máy song song.
  4. Xây dựng phương pháp luận hoàn chỉnh cho bài toán gán hạn định kiểm soát được (CON, SLK, TWK, PPW) kết hợp chi phí tối ưu hóa thời gian giao hàng.
  5. Hoàn thiện bản đồ phân loại độ phức tạp thuật toán toàn diện cho bài toán tác vụ can thiệp đa tác tử, xác lập chuẩn mực mới cho các nghiên cứu lập lịch đa mục tiêu hiện đại.

Công trình không chỉ giải quyết các câu hỏi học thuật tồn tại nhiều thập kỷ mà còn mở ra các hướng nghiên cứu đột phá, kết nối chặt chẽ giữa toán học rời rạc trừu tượng và thực tiễn vận hành công nghiệp thông minh trong kỷ nguyên sản xuất tinh gọn toàn cầu.