Tổng quan luận án

Luận án tiến sĩ của tác giả Nguyen Huynh Tuong, được bảo vệ ngày 17 tháng 6 năm 2009 tại Trường Đào tạo Sau đại học Sức khỏe, Khoa học và Công nghệ thuộc Đại học François-Rabelais de Tours (Cộng hòa Pháp), chuyên ngành Khoa học Máy tính (Informatique), nghiên cứu chuyên sâu về lĩnh vực tối ưu hóa tổ hợp và lý thuyết điều độ lập lịch (scheduling theory). Nghiên cứu được thực hiện tại Phòng thí nghiệm Tin học (Laboratoire d’Informatique - EA 2101), nhóm nghiên cứu Điều độ và Điều hành (Ordonnancement et Conduite), dưới sự hướng dẫn của Phó Giáo sư Ameur Soukhal và Giáo sư Jean-Charles Billaut.

Tính cấp thiết của luận án xuất phát từ sự chuyển dịch trong quản lý chuỗi cung ứng và tổ chức sản xuất công nghiệp hiện đại. Việc áp dụng triết lý sản xuất tinh gọn (Lean Manufacturing) và mô hình Vừa đúng lúc (Just-In-Time - JIT / Juste-à-temps - JàT) đặt ra yêu cầu triệt tiêu các dạng lãng phí (Muda), đặc biệt là lãng phí do sản xuất thừa và tồn kho trung gian. Trong bối cảnh này, các mô hình điều độ truyền thống dựa trên các tiêu chí chính quy đơn thuần (như thời gian hoàn thành cực đại $C_{\max}$, độ trễ lớn nhất $L_{\max}$, hay thời gian lưu chuyển) không còn đáp ứng đầy đủ yêu cầu quản lý thực tế. Hệ thống sản xuất đòi hỏi việc hoàn thành công việc phải càng gần thời hạn giao hàng (due date / date de fin souhaitée) càng tốt, nhằm hạn chế đồng thời cả chi phí lưu kho khi hoàn thành sớm và chi phí phạt cùng rủi ro mất khách hàng khi giao trễ. Bên cạnh đó, sự cạnh tranh tài nguyên giữa các nhóm công việc phục vụ các phân khúc khách hàng hoặc các tác nhân khác nhau đặt ra bài toán điều độ công việc giao thoa (interfering jobs / multi-agent scheduling), nơi mỗi nhóm công việc chịu sự ràng buộc bởi các tiêu chuẩn đánh giá riêng biệt.

Luận án tập trung giải quyết hai khoảng trống nghiên cứu trọng tâm:

  1. Thiếu hụt các thuật toán chính xác có hiệu năng tính toán cao và các lược đồ xấp xỉ đa thức có bảo đảm sai số cho các bài toán điều độ JIT tối thiểu hóa chi phí sớm/trễ trên mô hình máy song song có thời hạn chung (cố định hoặc có thể kiểm soát/đàm phán).
  2. Sự phức tạp trong việc xác định đường biên nghiệm không bị trội (non-dominated solutions / Pareto front) cho lớp bài toán điều độ đa mục tiêu với các tập công việc giao thoa, nơi một tiêu chí được tối ưu hóa trên toàn bộ tập công việc trong khi tiêu chí khác chỉ áp dụng trên một tập con nhất định.

Mục tiêu và các giả thuyết/nhiệm vụ nghiên cứu chính của luận án được xác định gồm:

  • Mục tiêu 1: Phân tích độ phức tạp tính toán và xây dựng các thuật toán quy hoạch động (dynamic programming) chính xác mới cho bài toán tối thiểu hóa tổng độ trễ có trọng số ($\sum w_i T_i$) trên hệ thống máy song song giống hệt ($P_m$) và máy đồng nhất ($Q_m$) với thời hạn chung.
  • Mục tiêu 2: Phát triển các thuật toán đa thức chính xác và các lược đồ xấp xỉ thời gian đa thức (PTAS / FPTAS) cho bài toán tối thiểu hóa đồng thời chi phí sớm và trễ ($\sum (\alpha_i E_i + \beta_i T_i)$) trong các điều kiện thời hạn cho trước hoặc thời hạn kiểm soát được ($\sum (\alpha_i E_i + \beta_i T_i + \gamma d)$).
  • Mục tiêu 3: Thiết lập bức tranh phân loại độ phức tạp (đa thức, NP-khó thông thường, NP-khó nghĩa mạnh) cho các biến thể của bài toán điều độ công việc giao thoa trên một máy đơn và hệ thống máy song song dưới ba phương pháp tiếp cận đa mục tiêu: $\epsilon$-ràng buộc ($\epsilon$-constraint), kết hợp tuyến tính (linear combination), và quy hoạch mục tiêu (goal programming).

Đối tượng nghiên cứu của luận án là các công việc độc lập (không có quan hệ thứ tự trước sau, không ngắt quãng - non-preemptive) cần được xử lý trên một máy đơn hoặc hệ sinh thái các máy song song (máy song song giống hệt $P_m$ và máy song song đồng nhất $Q_m$). Phạm vi phân tích tập trung vào các mô hình thời hạn chung (common due date $d_i = d$ hoặc tập hữu hạn các mốc thời hạn $d_i \in D$) và các lớp bài toán lập lịch đa mục tiêu với công việc giao thoa.

Tổng quan tài liệu và vị trí của luận án

Luận án thực hiện hệ thống hóa tài liệu chuyên khảo về lý thuyết điều độ và tối ưu hóa tổ hợp từ các công trình kinh điển của Carlier và Chrétienne (1988), Leung (2004), Pinedo (2008), Brucker (2007), Blazewicz và cộng sự (2007), T'Kindt và Billaut (2006).

Đối với bài toán điều độ Just-In-Time và tối thiểu hóa độ trễ, tác giả điểm lại các mốc nghiên cứu:

  • Lawler và Moore (1969) đã đề xuất một thuật toán quy hoạch động giả đa thức độ phức tạp $O(n^2 d)$ cho bài toán một máy với một mốc thời hạn chung $1|d_i=d|\sum w_i T_i$. Tuy nhiên, tác giả luận án chỉ ra rằng việc mở rộng mô hình này sang hệ thống nhiều máy song song không diễn ra trực tiếp như các giả định trước đó trong y văn mà cần một cấu trúc trạng thái và phương trình truy hồi hoàn toàn mới.
  • Yuan (1992) chứng minh bài toán $1|d_i=d|\sum w_i T_i$ là NP-khó. Bài toán tổng quát $1|d_i|\sum w_i T_i$ được Lenstra, Rinnooy Kan và Brucker (1977) chứng minh là NP-khó theo nghĩa mạnh.
  • Lenstra (1977) chứng minh trường hợp các công việc có thời gian thực hiện bằng nhau ($p_i = p$) có thể đưa về bài toán gán (assignment problem) giải được trong thời gian đa thức $O(n^3)$.
  • Arkin và Roundy (1991), Cheng và cộng sự (1999) phân tích các mô hình thời hạn phụ thuộc thời gian gia công như mô hình thời gian chờ bằng nhau (SLK: $d_i = p_i + q$) hay mô hình gia công cộng chờ (PPW: $d_i = \alpha p_i + q, w_i = k p_i$), chứng minh tính NP-khó khi $0 < \alpha < 1$ và chỉ ra tính giải được đa thức theo quy tắc LPT (khi $\alpha \le 0$) hoặc SPT (khi $\alpha \ge 1$).
  • Về tính xấp xỉ của hàm mục tiêu trễ hạn: Lawler (1982) đề xuất FPTAS độ phức tạp $O(n^7/\epsilon)$ cho bài toán $1|d_i|\sum T_i$, sau đó được cải tiến bởi Kovalyov (1995) thành $O(n^6 \log n + n^6/\epsilon)$ và Koulamas (1996) thành $O(n^5 \log n + n^5/\epsilon)$. Kellerer và Strusewich (2003) thiết lập FPTAS $O(n^6 \log W / \epsilon^3)$ cho bài toán $1|d_i=d|\sum w_i T_i$. Kolliopoulos và Steiner (2006, 2007) nghiên cứu FPTAS cho họ thời hạn cố định và trường hợp mục tiêu dịch chuyển $\sum w_i (T_i + d)$. Ngược lại, trên hệ thống máy song song $P_m|d_i=d|\sum w_i T_i$, Kovalyov và Werner (2002) chứng minh không tồn tại thuật toán xấp xỉ đa thức trừ phi $P = NP$.
  • Về mô hình gán thời hạn kiểm soát được: Luận án kế thừa bảng phân loại của Gordon, Proth và Chu (2002) gồm các mô hình CON (Constant flow allowance: $d_i = d$), SLK ($d_i = r_i + p_i + q$), TWK (Total Work: $d_i = r_i + k \cdot p_i$), PPW ($d_i = r_i + k \cdot p_i + q$), NOP (Number of Operations: $d_i = r_i + k \cdot n_i$), và các tiếp cận ngẫu nhiên RDM / JIQ / JIS qua mô phỏng.
  • Về điều độ công việc giao thoa và đa tác nhân: Khái niệm được định hình qua các công trình nền tảng của Agnetis và cộng sự (2004), Perez, Soukhal và Billaut (2005).

Vị trí của luận án được xác lập thông qua việc giải quyết các bài toán chưa có lời giải tối ưu hoặc chưa có cấu trúc thuật toán chặt chẽ trong y văn: xây dựng thuật toán quy hoạch động chính xác giải quyết triệt để bài toán trễ hạn trên hệ thống máy song song giống hệt ($P_m$) và máy đồng nhất ($Q_m$), thiết lập các lược đồ xấp xỉ PTAS cho bài toán sớm/trễ tổng quát trên hệ thống máy song song, và mở rộng toàn diện lý thuyết điều độ công việc giao thoa từ một máy sang hệ thống máy song song.

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án vận dụng hệ thống lý thuyết và phương pháp nghiên cứu định lượng chặt chẽ trong khoa học máy tính lý thuyết và tối ưu hóa toán học:

  1. Khung ký hiệu điều độ chuẩn: Sử dụng ký hiệu ba trường $\alpha | \beta | \gamma$ của Graham và cộng sự:

    • Trường $\alpha$: Môi trường máy ($1$: máy đơn; $P_m$: $m$ máy song song giống hệt; $Q_m$: $m$ máy song song đồng nhất với tốc độ gia công $s_j$).
    • Trường $\beta$: Đặc tính công việc và thông số thời hạn ($d_i = d$: thời hạn chung; $d_i \in D, |D|=k$: họ $k$ thời hạn; unrestrictive / non-restrictive: thời hạn không hạn chế; restrictive: thời hạn hạn chế; $d_i \text{ unknown}$: thời hạn kiểm soát được; $p_i = p$: thời gian xử lý đồng nhất).
    • Trường $\gamma$: Hàm mục tiêu cần tối ưu hóa ($\sum w_i T_i$, $\sum (\alpha_i E_i + \beta_i T_i)$, $\sum (\alpha_i E_i + \beta_i T_i + \gamma d)$, hoặc các cặp mục tiêu đa tiêu chí $F_\ell(f_1, f_2)$).

  2. Mô hình hóa chi phí sớm/trễ và tiêu chí không chính quy (Non-regular Criteria):

    • Độ sớm (Earliness): $E_i = \max(0, d_i - C_i)$ (theo thời điểm kết thúc). Các biến thể: tính theo thời điểm phát hành (promptitude) $E_i^r = \max(0, r_i - s_i)$, tính theo thời điểm bắt đầu trong mô hình xưởng chuyền (flowshop) $E_i^s = \max(0, d_i^s - s_{(1,i)})$.
    • Độ trễ (Tardiness): $T_i = \max(0, C_i - d_i)$.
    • Hàm chi phí tuyến tính liên tục tổng quát: $F_i(E_i, T_i) = \sum (\alpha_i E_i + \beta_i T_i)$, được chia thành 4 trường hợp trọng số: đơn vị (unitaire: $\alpha_i = \beta_i = w$), đồng nhất (identique: $\alpha_i = \alpha, \beta_i = \beta$), đối xứng (symétrique: $\alpha_i = \beta_i = w_i$), và bất kỳ (quelconque: $\alpha_i, \beta_i$).
    • Do tính chất không chính quy, việc chèn các khoảng thời gian chết (temps mort / idle time) giữa các công việc có thể làm giảm tổng chi phí, dẫn đến bài toán xác định thời điểm bắt đầu tối ưu (optimal timing problem). Nghiệm tối ưu có cấu trúc hình chữ V (V-shape structure), trong đó các công việc hoàn thành trước $d$ tuân theo quy tắc LPT (Longest Processing Time First) và các công việc trễ hạn tuân theo quy tắc SPT (Shortest Processing Time First).

  3. Lý thuyết độ phức tạp và xấp xỉ thuật toán:

    • Đánh giá bài toán trong lớp các bài toán tối ưu hóa tổ hợp $NPO$.
    • Xác định sai số tương đối: $\text{Err}(I, A) = \frac{|f^(I) - f(A(I))|}{\max{f^(I), f(A(I))}}$ và tỷ số hiệu năng $R(I, A) = \min\left{\frac{f(A(I))}{f^(I)}, \frac{f^(I)}{f(A(I))}\right}$.
    • Phân loại xấp xỉ: Lớp $APX$ (thuật toán có bảo đảm sai số $1+\epsilon$), Lớp $PTAS$ (lược đồ xấp xỉ thời gian đa thức với độ phức tạp $q_\epsilon(|I|)$), và Lớp $FPTAS$ (lược đồ xấp xỉ thời gian hoàn toàn đa thức với độ phức tạp $q(|I|, 1/\epsilon)$).
    • Hai kỹ thuật chuyển đổi quy hoạch động thành lược đồ xấp xỉ: Làm tròn dữ liệu đầu vào (rounding-the-input-data) và thu gọn không gian trạng thái (trimming-the-state-space).

  4. Phương pháp tiếp cận bài toán đa mục tiêu:

    • Phương pháp $\epsilon$-ràng buộc: Tối ưu hóa một tiêu chí chính trên tập $N$ đồng thời giới hạn tiêu chí thứ hai trên tập con $N_1$ trong một ngưỡng $\epsilon$.
    • Phương pháp tổ hợp tuyến tính: Tối ưu hóa hàm mục tiêu trọng số $\lambda f_1(N) + (1-\lambda) f_2(N_1)$.
    • Quy hoạch mục tiêu (Goal Programming): Tối thiểu hóa độ lệch so với các mức mục tiêu đã xác định trước.

Dữ liệu phân tích trong luận án là dữ liệu toán học hình thức, các ma trận chi phí, không gian trạng thái quy hoạch động và các tập dữ liệu thực nghiệm mô phỏng kiểm chứng hiệu năng biên dưới/biên trên.

Nội dung chính theo từng chương

Phần I: Điều độ vừa đúng lúc với thời hạn chung (Ordonnancement juste-à-temps à date due commune)

Chương 1: Giới thiệu về điều độ vừa đúng lúc (Introduction à l'ordonnancement juste-à-temps)

Chương này đặt nền tảng lý thuyết về hệ thống sản xuất Just-in-Time, nguồn gốc từ hệ thống Kanban tại nhà máy Toyota của Taiichi Ohno, phân tích 4 mức độ phân tích của phương pháp Lean và định nghĩa các dạng lãng phí (sản xuất thừa, hàng lỗi, phương pháp kém hiệu quả, vận chuyển dư thừa). Chương 1 hệ thống hóa các cách đo lường độ sớm, độ trễ, hàm mục tiêu tuyến tính liên tục, các mô hình thời hạn cho trước (hạn chế và không hạn chế), họ thời hạn cố định, và các mô hình gán thời hạn kiểm soát được (CON, SLK, TWK, PPW, NOP, RDM). Đồng thời, chương này thiết lập các định nghĩa hình thức về độ phức tạp tính toán, bảo đảm hiệu năng và cấu trúc các lớp xấp xỉ $APX$, $PTAS$, $FPTAS$.

| Tiêu chí | $d_i = d$ cho trước (không hạn chế) | $d_i = d$ cho trước (hạn chế) | $d_i \in D, |D|=k$ ($k$ cố định) | $d$ kiểm soát được (chưa biết) | | :--- | :--- | :--- | :--- | :--- | | $\sum w_i T_i$ (Chương 2) | - | $1$; $P_m$; $Q_m$ | $P_m$; $Q_m$ | - | | $\sum (\alpha_i E_i + \beta_i T_i)$ (Chương 3) | - | $1$; $P_m$; $Q_m$ | $P_m$; $Q_m$ | - | | $\sum (\alpha_i E_i + \beta_i T_i + \gamma d)$ (Chương 4) | - | - | - | $1$; $P_m$; $Q_m$ |

Chương 2: Độ trễ có trọng số với thời hạn xác định (Retard pondéré avec une date de fin donnée)

Chương 2 tập trung giải quyết bài toán $P_m|d_i \in D, |D|=l|\sum w_i T_i$. Tác giả phân tích chương trình quy hoạch động kinh điển của Lawler và Moore (1969) cho trường hợp một máy với hàm đệ quy: $$f(i, t) = \min { f(i-1, t), f(i-1, t-p_i) + w_i \max(0, t-d) }$$ Luận án chứng minh rằng công thức này không thể mở rộng trực tiếp cho trường hợp đa máy do sự phụ thuộc chéo của các khoảng thời gian gia công trên các máy khác nhau. Từ đó, tác giả xây dựng thuật toán quy hoạch động mới cho bài toán trên hệ thống máy song song giống hệt ($P_m$) và mở rộng cho máy song song đồng nhất ($Q_m$). Thuật toán xử lý hiệu quả các trạng thái công việc sớm ($C_i < d$), công việc trễ hoàn toàn ($S_i > d$), và công việc vắt ngang qua mốc thời hạn (straddling job: $S_i < d \le C_i$). Đồng thời, chương này thảo luận việc mở rộng thuật toán cho trường hợp họ thời hạn $d_i \in D$.

Bài toán Phương pháp & Độ phức tạp Tài liệu tham khảo gốc
$1 p_i = p \sum w_i T_i$
$P_m p_i = p, r_i \sum T_i$
$Q p_i = p \sum w_i T_i$
$1 w_i = k p_i \sum w_i T_i$
$1 d_i = d \sum w_i T_i$
$1 d_i = d \sum w_i T_i$
$P_m d_i = d \sum w_i T_i$

Chương 3: Độ sớm và trễ có trọng số với các thời hạn xác định (Avance et retard pondérés avec dates de fin données)

Chương 3 khảo sát hàm mục tiêu tổng quát $\sum (\alpha_i E_i + \beta_i T_i)$ khi mốc thời hạn được ấn định trước. Tác giả phân tích các trường hợp:

  1. Trường hợp thời gian thực hiện bằng nhau ($p_i = p$):
    • Thiết lập cấu trúc nghiệm tối ưu trên một máy đơn với một mốc thời hạn chung, hai mốc thời hạn và họ mốc thời hạn.
    • Chứng minh các bài toán này có thể chuyển đổi thành bài toán gán ma trận chi phí (assignment matrix) và giải chính xác trong thời gian đa thức $O(n^3)$.
    • Mở rộng thành công mô hình giải thuật đa thức cho hệ thống máy song song đồng nhất $Q_m$ với họ mốc thời hạn.
  2. Trường hợp thời gian thực hiện bất kỳ ($p_i$ tùy ý):
    • Xây dựng lược đồ xấp xỉ thời gian đa thức (PTAS) cho bài toán trên một máy đơn $1|d_i=d|\sum (\alpha_i E_i + \beta_i T_i)$.
    • Phát triển PTAS cho bài toán trên hệ thống $m$ máy song song giống hệt $P_m|d_i=d|\sum (\alpha_i E_i + \beta_i T_i)$, khắc phục rào cản tính toán của bài toán tối ưu hóa sớm/trễ đa máy.

Chương 4: Độ sớm và trễ có trọng số với thời hạn kiểm soát được (Avance et retard pondérés avec dates de fin contrôlables)

Chương 4 khảo sát bài toán khi mốc thời hạn $d$ không cố định mà là một biến quyết định cần xác định đồng thời với thứ tự gia công, với hàm chi phí mở rộng $\sum (\alpha_i E_i + \beta_i T_i + \gamma d)$ ($\gamma$ là hệ số phạt cho việc kéo dài thời hạn chung):

  • Khi thời gian gia công bằng nhau ($p_i = p$): Phát triển các thuật toán giải tích và thuật toán tổ hợp giải chính xác bài toán trên một máy đơn, máy song song giống hệt với họ thời hạn, và máy song song đồng nhất $Q_m|p_i=p, d_i=n p \lambda_m|\sum (\alpha E_i + \beta T_i)$ (thuật toán AssQm1).
  • Khi thời gian gia công bất kỳ: Thiết lập cấu trúc đặt lịch không có thời gian chết nội bộ giữa các công việc hoàn thành trước và sau $d$, đề xuất thuật toán giải quyết trên một máy và hệ thống máy song song. Đánh giá thực nghiệm hiệu năng của nghiệm thông qua so sánh giữa cận dưới (lower bound) và cận trên (upper bound).

Chương 5: Kết luận và triển vọng của phần một (Conclusion et perspectives de la première partie)

Tổng kết các kết quả đạt được về mặt thuật toán và độ phức tạp cho các bài toán JIT một máy và máy song song; khẳng định tính khả thi của các thuật toán quy hoạch động và lược đồ xấp xỉ PTAS/FPTAS đã đề xuất.

Phần II: Điều độ các công việc giao thoa độc lập (Ordonnancement de travaux interférant indépendants)

Chương 6: Giới thiệu về điều độ công việc giao thoa (Introduction à l'ordonnancement des travaux interférants)

Chương này giới thiệu mô hình điều độ đa mục tiêu trên tập công việc giao thoa (interfering jobs / multi-agent scheduling). Đặt vấn đề từ thực tiễn quản lý sản xuất: một phân xưởng phải xử lý toàn bộ tập công việc $N$, nhưng có những nhóm đơn hàng đặc thù $N_1 \subset N$ (thuộc về khách hàng ưu tiên hoặc nhóm dự án có cam kết riêng) đòi hỏi một tiêu chí chất lượng riêng biệt. Tác giả định nghĩa không gian nghiệm không bị trội (Pareto front) và thiết lập ba kỹ thuật tối ưu hóa đa mục tiêu: tiếp cận $\epsilon$-ràng buộc, hàm kết hợp tuyến tính và quy hoạch mục tiêu.

Chương 7: Bài toán điều độ trên một máy đơn (Problème d'ordonnancement à une seule machine)

Khảo sát toàn diện bài toán điều độ công việc giao thoa trên một máy đơn với các cặp hàm mục tiêu kết hợp giữa $\sum C_j(N)$, $\sum w_j C_j(N)$, $C_{\max}(N)$, $L_{\max}(N)$ đối với toàn bộ tập $N$ và $\sum C_j(N_1)$, $\sum w_j C_j(N_1)$, $C_{\max}(N_1)$, $L_{\max}(N_1)$ đối với tập con $N_1$:

  • Nhận diện và chứng minh các trường hợp giải được trong thời gian đa thức (ví dụ các cặp mục tiêu liên quan đến $C_{\max}(N)$ và $L_{\max}(N_1)$ qua các biến thể quy tắc SPT, EDD và kỹ thuật hoán vị cục bộ).
  • Phân loại và chứng minh các bài toán NP-khó theo nghĩa thông thường (NP-difficile au sens ordinaire) và đề xuất các thuật toán quy hoạch động giả đa thức tương ứng.
  • Chứng minh tính NP-khó theo nghĩa mạnh (NP-difficile au sens fort) cho các trường hợp kết hợp phức tạp giữa tổng thời gian hoàn thành có trọng số $\sum w_j C_j(N)$ và độ chậm trễ cực đại $L_{\max}(N_1)$.

Chương 8: Bài toán điều độ trên các máy song song (Problème d'ordonnancement à machines parallèles)

Mở rộng không gian bài toán công việc giao thoa lên môi trường $m$ máy song song. Chương 8 xây dựng cấu trúc quy hoạch động tổng quát (formulation générale de programmation dynamique) và áp dụng cụ thể để tìm nghiệm không bị trội cho các bài toán đa mục tiêu:

  1. Bài toán với cặp mục tiêu $\sum C_j(N_1)$ và $\sum C_j(N)$.
  2. Bài toán với cặp mục tiêu $\sum w_j C_j(N_1)$ và $C_{\max}(N)$.
  3. Bài toán với cặp mục tiêu $\sum w_j C_j(N)$ và $C_{\max}(N_1)$.
  4. Bài toán với cặp mục tiêu $C_{\max}(N)$ và $C_{\max}(N_1)$.

Các thuật toán quy hoạch động được phát triển cho phép tính toán chính xác nghiệm tối ưu Pareto trong thời gian giả đa thức khi số lượng máy $m$ cố định.

Chương 9: Kết luận và triển vọng của phần hai (Conclusion et perspectives de la seconde partie)

Đánh giá toàn diện các kết quả phân loại độ phức tạp và hiệu quả của khung quy hoạch động cho bài toán điều độ công việc giao thoa; mở ra hướng nghiên cứu cho các mô hình xưởng máy phức tạp hơn.

Kết quả và những đóng góp mới

Luận án đã đạt được các đóng góp khoa học mới về mặt lý thuyết và giải thuật trong tối ưu hóa tổ hợp:

  1. Về mặt lý thuyết độ phức tạp:

    • Hoàn thiện bức tranh phân loại độ phức tạp cho các bài toán điều độ Just-in-Time với thời hạn chung, bao gồm các biến thể với thời gian gia công đồng nhất ($p_i = p$) và thời gian gia công bất kỳ, trên máy đơn và hệ thống máy song song ($P_m, Q_m$).
    • Thiết lập bản đồ độ phức tạp chi tiết (đa thức, NP-khó thông thường, NP-khó nghĩa mạnh) cho lớp bài toán điều độ công việc giao thoa (interfering jobs) trên một máy đơn và máy song song với các cặp tiêu chí kết hợp giữa $\sum C_j, \sum w_j C_j, C_{\max}, L_{\max}$.

  2. Về mặt thuật toán và phương pháp giải:

    • Phát hiện giới hạn trong mô hình quy hoạch động của Lawler và Moore (1969) khi áp dụng cho bài toán máy song song; từ đó xây dựng thuật toán quy hoạch động chính xác mới giải bài toán $P_m|d_i \in D, |D|=l|\sum w_i T_i$ và mở rộng cho hệ thống máy đồng nhất $Q_m$.
    • Đề xuất phương pháp mô hình hóa bài toán gán ma trận chi phí độ phức tạp $O(n^3)$ để giải chính xác các bài toán JIT sớm/trễ khi thời gian xử lý bằng nhau trên các cấu hình máy khác nhau.
    • Xây dựng thành công các lược đồ xấp xỉ thời gian đa thức (PTAS) cho bài toán tối thiểu hóa chi phí sớm và trễ có trọng số $\sum (\alpha_i E_i + \beta_i T_i)$ trên máy đơn và hệ thống máy song song giống hệt $P_m$.
    • Phát triển khung thuật toán quy hoạch động tổng quát có khả năng tìm kiếm nghiệm không bị trội (Pareto) cho bài toán điều độ công việc giao thoa đa mục tiêu trên hệ thống máy song song.

Hạn chế và hướng nghiên cứu tiếp

Căn cứ theo nội dung và phạm vi nghiên cứu được tác giả trình bày, các hạn chế và hướng mở rộng bao gồm:

  • Luận án giới hạn không gian khảo sát ở các công việc độc lập, không có quan hệ ràng buộc thứ tự trước sau (precedence constraints), xử lý không ngắt quãng (non-preemptive) và thời điểm sẵn sàng ban đầu đồng nhất ($r_i = 0$ cho hầu hết các mô hình chính).
  • Các thuật toán quy hoạch động và lược đồ xấp xỉ trên hệ thống máy song song phụ thuộc vào giả định số lượng máy $m$ là một hằng số cố định; khi $m$ là một biến đầu vào tùy ý, độ phức tạp tính toán sẽ gia tăng đáng kể.
  • Hướng phát triển tiếp theo được tác giả xác định bao gồm:
    1. Mở rộng bài toán điều độ JIT và công việc giao thoa cho các hệ thống sản xuất phức tạp hơn như xưởng chuyền (flowshop), xưởng mở (open shop) hoặc xưởng gia công theo luồng công việc (job shop).
    2. Tích hợp thời gian chuẩn bị máy phụ thuộc thứ tự (sequence-dependent setup times) và thời điểm phát hành công việc không đồng nhất ($r_i \neq 0$).
    3. Cải tiến bậc đa thức của các lược đồ xấp xỉ PTAS và nghiên cứu khả năng xây dựng FPTAS cho các trường hợp bài toán mở.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên môn cho:

  • Nghiên cứu sinh và nhà nghiên cứu trong các lĩnh vực Nghiên cứu Vận hành (Operations Research), Khoa học Máy tính lý thuyết và Tối ưu hóa Tổ hợp: Cung cấp phương pháp luận chứng minh độ phức tạp, kỹ thuật thiết kế giải thuật quy hoạch động đa chiều và phương pháp xây dựng lược đồ xấp xỉ thuật toán (PTAS/FPTAS).
  • Giảng viên đại học: Sử dụng làm tài liệu giảng dạy chuyên đề cao học và tiến sĩ về Lý thuyết điều độ nâng cao (Advanced Scheduling Theory), Tối ưu hóa đa mục tiêu và Sản xuất tinh gọn.
  • Kỹ sư hệ thống và chuyên gia phân tích công nghiệp: Tham khảo các mô hình toán học và thuật toán gán thời hạn (CON, SLK, TWK, PPW) để thiết kế các mô-đun lập lịch sản xuất tự động trong các hệ thống phần mềm điều hành sản xuất (MES) và hoạch định nguồn lực doanh nghiệp (ERP).

Câu hỏi thường gặp

1. Luận án giải quyết những dạng bài toán điều độ Just-In-Time nào?
Luận án giải quyết hai nhóm bài toán JIT chính: bài toán tối thiểu hóa độ trễ có trọng số ($\sum w_i T_i$) và bài toán tối thiểu hóa đồng thời chi phí sớm và trễ ($\sum (\alpha_i E_i + \beta_i T_i)$ hoặc $\sum (\alpha_i E_i + \beta_i T_i + \gamma d)$), trên cả mô hình một máy đơn và hệ thống máy song song ($P_m, Q_m$), dưới các điều kiện thời hạn cho trước (hạn chế/không hạn chế, một mốc hoặc họ mốc thời hạn) và thời hạn kiểm soát được.

2. Điểm khiếm khuyết trong thuật toán quy hoạch động của Lawler và Moore (1969) được luận án chỉ ra là gì?
Lawler và Moore (1969) đề xuất thuật toán quy hoạch động cho bài toán $1|d_i=d|\sum w_i T_i$ và cho rằng có thể suy rộng trực tiếp sang mô hình đa máy song song. Luận án chỉ ra rằng sự tương tác và phụ thuộc thời gian giữa các công việc được xếp lịch đồng thời trên nhiều máy song song khiến hàm đệ quy của Lawler và Moore không bảo toàn tính tối ưu, từ đó tác giả phải thiết lập một cấu trúc trạng thái và phương trình truy hồi quy hoạch động hoàn toàn mới.

3. Bài toán điều độ công việc giao thoa (interfering jobs) khác gì so với bài toán điều độ đa mục tiêu truyền thống?
Trong điều độ đa mục tiêu truyền thống, tất cả các công việc trong tập $N$ đều đóng góp bình đẳng vào việc tính toán mọi hàm mục tiêu. Trong bài toán công việc giao thoa, một hàm mục tiêu được đánh giá trên toàn bộ tập công việc $N$, trong khi một hoặc nhiều hàm mục tiêu khác chỉ được tính toán riêng trên một tập con các công việc $N_1 \subset N$, phản ánh sự cạnh tranh tài nguyên giữa các nhóm đơn hàng hoặc các tác nhân khác nhau.

4. Khi thời gian xử lý của các công việc bằng nhau ($p_i = p$), bài toán sớm/trễ được giải quyết bằng phương pháp nào?
Tác giả chứng minh rằng khi $p_i = p$, bài toán tối thiểu hóa chi phí sớm/trễ trên một máy hoặc máy song song đồng nhất với họ thời hạn cho trước có thể quy đổi trực tiếp về bài toán gán ma trận chi phí (assignment problem) và giải chính xác trong thời gian đa thức $O(n^3)$.

5. Những phương pháp nào được sử dụng để giải quyết bài toán đa mục tiêu với công việc giao thoa?
Luận án áp dụng ba phương pháp tối ưu hóa đa mục tiêu: tiếp cận $\epsilon$-ràng buộc ($\epsilon$-constraint approach), tổ hợp tuyến tính các tiêu chí (linear combination of criteria) và quy hoạch mục tiêu (goal programming) để tính toán tập nghiệm không bị trội (Pareto front).

Kết luận

Luận án tiến sĩ của Nguyen Huynh Tuong đã giải quyết toàn diện các bài toán tối ưu hóa tổ hợp phức tạp trong lý thuyết điều độ lập lịch, tập trung vào mô hình sản xuất Just-in-Time và hệ thống các tập công việc giao thoa. Công trình đã đóng góp những bước tiến học thuật quan trọng thông qua việc thiết lập các thuật toán quy hoạch động chính xác mới cho hệ thống máy song song, xây dựng các lược đồ xấp xỉ thời gian đa thức (PTAS), và hoàn thiện bản đồ phân loại độ phức tạp tính toán cho bài toán điều độ công việc giao thoa. Đây là tài liệu học thuật có giá trị lý thuyết sâu sắc và định hướng ứng dụng thực tiễn cao cho lĩnh vực nghiên cứu vận hành và tối ưu hóa điều độ công nghiệp.