Tổng quan luận án

Luận án tiến sĩ toán học với đề tài "Một số bài toán tối ưu trong lý thuyết xếp hàng và ứng dụng" được nghiên cứu sinh Phan Thị Loan thực hiện dưới sự hướng dẫn khoa học của TS. Hồ Đăng Phúc, bảo vệ tại Viện Khoa học và Công nghệ Quân sự thuộc Bộ Quốc phòng vào năm 2015, thuộc chuyên ngành Lý thuyết xác suất và thống kê toán học (mã số: 62 46 01 06).

Tính cấp thiết và khoảng trống nghiên cứu

Trong thực tiễn kỹ thuật và đời sống, các hệ thống phục vụ luôn đối mặt với hiện tượng các đối tượng có nhu cầu phục vụ xuất hiện ngẫu nhiên và mang tính đám đông. Các ví dụ điển hình bao gồm:

  • Khách hàng đến giao dịch tại ngân hàng hoặc thanh toán tại quầy siêu thị.
  • Bệnh nhân đến khám chữa bệnh tại các phòng khám, bệnh viện.
  • Các cuộc gọi liên lạc chuyển đến tổng đài viễn thông.
  • Các gói dữ liệu và luồng yêu cầu công việc (jobs) truyền tải qua các nút (servers/routers) trên mạng máy tính và mạng viễn thông.

Khi các yêu cầu xuất hiện ngẫu nhiên, hệ thống có thể đáp ứng phục vụ hoặc từ chối, gây ra hiện tượng mất mát nếu hệ thống bị quá tải hoặc năng lực phục vụ vượt quá ngưỡng giới hạn. Các mô hình giải tích cổ điển (như dòng vào Poisson đơn thuần) không còn đáp ứng đầy đủ tính chất đa dạng của mạng viễn thông và mạng máy tính hiện đại, nơi mà dòng yêu cầu có tính chất "Phi Markov", quá trình lưu chuyển dữ liệu diễn ra trên nhiều tầng giao thức (Internet, Application, User) và mỗi công việc bao gồm nhiều công đoạn phức tạp. Do đó, việc xây dựng các mô hình toán học giải quyết bài toán tối ưu hóa mạng hàng đợi, đặc biệt là bài toán cực đại hóa tiện ích mạng (Network Utility Maximization - NUM), bài toán phân chia dòng yêu cầu vào mạng và bài toán luồng cực đại, trở thành một nhu cầu cấp thiết.

Mục tiêu nghiên cứu

  1. Hệ thống hóa các cơ sở toán học về lý thuyết xác suất, quá trình ngẫu nhiên, giải thuật quy hoạch nguyên tuyến tính và lý thuyết đồ thị phục vụ cho phân tích mạng hàng đợi.
  2. Xây dựng và chứng minh sự tồn tại nghiệm cho các bài toán phân chia tối ưu dòng yêu cầu vào mạng hàng đợi $J$ nút (gồm bài toán phân chia dạng 1 và bài toán phân chia dạng 2).
  3. Vận dụng công cụ quy hoạch nguyên, thuật toán Gomory và phương pháp luồng cực đại Ford-Fulkerson nhằm tìm phương án phân bổ tải tối ưu, giảm thiểu độ dài hàng đợi cực đại kỳ vọng tại các nút.
  4. Ứng dụng các kết quả lý thuyết vào mô hình hóa bài toán trung tâm thương mại/phục vụ dựa trên cơ chế ưu tiên dòng vào và bài toán định tuyến trong mạng hướng thông tin (Information-Centric Network - ICN).

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Hệ thống mạng hàng đợi phục vụ $M/M/m$, mạng hàng đợi tổng quát $A/B/m/N$, các mô hình dòng yêu cầu, cơ chế phân chia dòng tải, bài toán luồng mạng và cấu trúc mạng hướng thông tin ICN.
  • Phạm vi nghiên cứu:
    • Về mặt lý thuyết: Tập trung vào không gian trạng thái rời rạc và liên tục, xích Markov, các phân phối xác suất (Poisson, phân phối mũ, Erlang), định luật Little, tính chất PASTA, bài toán quy hoạch nguyên tuyến tính và thuật toán cắt Gomory 1.
    • Về mặt ứng dụng: Đánh giá hiệu năng và phân bổ lưu lượng trên mô hình mạng hàng đợi của trung tâm phục vụ và mạng ICN thông qua công cụ mô phỏng OMNeT++.

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

Luận án điểm lại lịch sử hình thành và phát triển của lý thuyết xếp hàng (Queueing Theory) và lý thuyết mạng hàng đợi (Queueing Network):

  • Giai đoạn khởi đầu: Công trình năm 1907 của Johannsen với tiêu đề "Waiting time and Number of Calls" được ghi nhận là một trong những nghiên cứu đầu tiên về lý thuyết xếp hàng. Tiếp đó, các công trình của A. K. Erlang, tiêu biểu là bài báo "The Theory of Probabilities and Telephone Conversations", đã đặt nền móng toán học cho việc ứng dụng quá trình Poisson trong việc mô tả lưu lượng điện thoại. Năm 1960, A. Erlang tiếp tục phát triển bài toán tối ưu trong công trình "On the Rational Determination of the Number of Circuits".
  • Giai đoạn mở rộng giải tích: Hàng loạt nhà toán học đã tham gia nghiên cứu và phát triển lý thuyết hàng đợi và quá trình ngẫu nhiên như Crommelin, Jensen, Feller, Kolmogorov, Pollaczek, David, Duda, Gromoll, Ghodsi, Jarschel, Hande, Hitchcock, Horst, Jain, Barry Nelson, Koopmans, Frank Kelly, Kumar, Wang Zikun...
  • Giai đoạn mạng hàng đợi đa lớp (Multi-class) và tối ưu hóa tiện ích: Khi mạng truyền thông phát triển, Frank Kelly và sau này là các tác giả như Yung Yi, Mung Chiang (2008) đã phát triển mô hình cực đại hóa tiện ích mạng NUM (Network Utility Maximization).
  • Vị trí của luận án: Kế thừa khung lý thuyết của bài toán NUM và mạng hàng đợi cổ điển, luận án định vị trọng tâm vào việc thiết lập các mô hình toán học giải quyết bài toán phân chia tối ưu dòng yêu cầu ngẫu nhiên vào mạng gồm $J$ nút phục vụ song song có năng lực hữu hạn, kết hợp giải thuật quy hoạch nguyên Gomory và thuật toán luồng mạng Ford-Fulkerson để ứng dụng vào hệ thống phân tán và mạng ICN.

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

Cơ sở lý thuyết và các khái niệm sử dụng

Luận án dựa trên nền tảng của lý thuyết xác suất, quá trình ngẫu nhiên, tối ưu hóa rời rạc và lý thuyết đồ thị:

  1. Không gian xác suất và biến ngẫu nhiên: Không gian xác suất cơ bản $(\Omega, \mathcal{A}, P)$ và không gian đo $(\mathbb{R}, \mathcal{B})$ với $\sigma$-đại số Borel $\mathcal{B}$ trên đường thẳng thực $\mathbb{R}$. Các đặc trưng số gồm kỳ vọng toán học $E\xi = \int_{\mathbb{R}} x dF(x)$ và phương sai $Var\xi = D\xi$.
  2. Các phân phối xác suất chuyên biệt:
    • Phân phối Poisson: $P(\xi = n) = \frac{\lambda^n}{n!} e^{-\lambda}$ với $E\xi = Var\xi = \lambda$.
    • Phân phối Mũ (Exponential): Hàm mật độ $f(x) = \lambda e^{-\lambda x}$ ($x \ge 0$), kỳ vọng $E\xi = \frac{1}{\lambda}$, phương sai $Var\xi = \frac{1}{\lambda^2}$.
    • Phân phối Erlang ($Er_k(\lambda)$): Tổng của $k$ biến ngẫu nhiên độc lập cùng phân phối mũ tham số $\lambda$, có hàm mật độ $f(x) = \frac{\lambda^k x^{k-1}}{(k-1)!} e^{-\lambda x}$ ($x > 0$), kỳ vọng $E\xi = \frac{k}{\lambda}$.
  3. Quá trình ngẫu nhiên và Xích Markov: Khái niệm ánh xạ $X(\theta, \omega)$ với $\theta \in \Theta \subset \mathbb{R}$. Quá trình Poisson có số gia độc lập. Xích Markov thời gian rời rạc và liên tục với không gian trạng thái $E$, xác suất chuyển trạng thái $P(s, i, t, j) = P[X_t = j \mid X_s = i]$.
  4. Mô hình mạng hàng đợi Kendall $A/B/m/N$:
    • $A$: Quy luật phân phối của khoảng thời gian giữa hai yêu cầu đến kế tiếp.
    • $B$: Quy luật phân phối thời gian phục vụ.
    • $m$: Số kênh/trạm phục vụ song song.
    • $N$: Dung lượng tối đa của hệ thống (khi $N = \infty$ viết tắt là $A/B/m$).
    • Ký hiệu $M$ biểu thị quá trình Markov (phân phối mũ), $G$ biểu thị phân phối tổng quát bất kỳ.
  5. Định luật Little và Tính chất PASTA:
    • Luật Little (1954): $E(N) = \lambda E(T)$, thiết lập mối liên hệ giữa số yêu cầu trung bình trong hệ thống $E(N)$, cường độ dòng vào $\lambda$ và thời gian lưu trú trung bình $E(T)$.
    • Tính chất PASTA (Poisson Arrivals See Time Averages): Dòng đến Poisson nhận định trạng thái hệ thống đồng nhất với phân bố theo thời gian thực của hệ thống.
  6. Lý thuyết Quy hoạch tuyến tính và Quy hoạch nguyên:
    • Dạng chuẩn và dạng chính tắc của bài toán quy hoạch tuyến tính.
    • Bài toán quy hoạch nguyên (Integer Programming - IP), bài toán quy hoạch nguyên 0-1, quy hoạch nguyên hoàn toàn và quy hoạch nguyên bộ phận.
    • Phương pháp cắt Gomory (Gomory Cut), phương pháp nhánh cận (Land-Doig), phương pháp Monte-Carlo.
  7. Lý thuyết đồ thị và luồng trên mạng: Đồ thị $G=(V, E)$, bài toán tìm đường đi ngắn nhất, bài toán luồng cực đại (Maximum Flow Problem) và thuật toán Ford-Fulkerson (1962).

Bảng ký hiệu và thuật ngữ chuyên ngành trong luận án

Ký hiệu / Thuật ngữ Ý nghĩa trong luận án
$\mathbb{R}^+$ Tập hợp các số thực không âm $[0, +\infty)$
$\mathbb{N}^+$ Tập hợp các số tự nhiên
$E$ Không gian trạng thái của quá trình ngẫu nhiên
$Th(N)$ Thông lượng của mạng phục vụ
$q(i, j)$ Cường độ chuyển trạng thái từ $i$ sang $j$
$p_{ij}$ / $\rho_{ij}$ Xác suất chuyển trạng thái
$D$ Tập nghiệm chấp nhận được của bài toán tối ưu
$Var$ / $D\xi$ Phương sai của biến ngẫu nhiên
$f: D \to \mathbb{R}$ Hàm mục tiêu
$FCFS$ Nguyên tắc đến trước phục vụ trước (First-Come, First-Served)
$\lambda_i$ / $\mu_i$ Cường độ sinh dòng yêu cầu / Cường độ phục vụ tại nút $i$
$(LP)$ Bài toán quy hoạch tuyến tính (Linear Programming)
$(PT)$ Bài toán vận tải
$(DT)$ Bài toán đối ngẫu
$IP$ Bài toán quy hoạch nguyên (Integer Programming)
$NDO$ Đối tượng dữ liệu có gán tên (Named Data Object)
$ICN$ Mạng hướng thông tin (Information-Centric Network)
$\pi_w$ Xác suất một công việc phải chờ đợi (xác suất chậm trễ)
$E(L_q)$ Độ dài hàng đợi trung bình
$E(W)$ Thời gian chờ đợi trung bình trong hàng đợi

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

  • Phương pháp giải tích và tối ưu hóa giải tích: Sử dụng các phương trình cân bằng xác suất cục bộ/toàn cục để xác định phân bố dừng của mạng hàng đợi; thiết lập các bài toán tối ưu hóa rời rạc dưới dạng bài toán Min-Max.
  • Phương pháp thuật toán: Ứng dụng thuật toán cắt Gomory 1 kết hợp bảng đơn từ điển (Simplex) để giải bài toán quy hoạch nguyên hoàn toàn; triển khai thuật toán Ford-Fulkerson tìm luồng cực đại.
  • Phương pháp mô phỏng số: Thiết lập và đánh giá thực nghiệm mô hình mạng hướng thông tin ICN trên phần mềm mô phỏng mạng OMNeT++.

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

Chương 1: Một số kiến thức liên quan

Chương 1 đóng vai trò hệ thống hóa toàn bộ các công cụ toán học nền tảng được sử dụng xuyên suốt trong các chương nghiên cứu tiếp theo của luận án. Nội dung chương bao gồm:

  • Trình bày các khái niệm không gian xác suất, đại lượng ngẫu nhiên rời rạc và liên tục, hàm mật độ xác suất, hàm phân phối, kỳ vọng toán học và phương sai.
  • Khảo sát chi tiết ba lớp biến ngẫu nhiên cơ bản trong lý thuyết xếp hàng: biến ngẫu nhiên phân phối Poisson, phân phối mũ và phân phối Erlang $Er_k(\lambda)$, nêu rõ các tính chất đại số và giải tích của chúng.
  • Trình bày định nghĩa quá trình ngẫu nhiên $X(t, \omega)$, phân loại theo tham số thời gian rời rạc và liên tục; định nghĩa quá trình Poisson và tính chất số gia độc lập.
  • Phân tích xích Markov, không gian trạng thái, ma trận xác suất chuyển và xác suất chuyển trạng thái $P(s, i, t, j)$.
  • Thiết lập bài toán quy hoạch tuyến tính tổng quát: $$\min (\max) f(x) = \langle c, x \rangle = \sum_{j=1}^n c_j x_j \quad \text{với } x_j \ge 0$$
  • Giới thiệu bài toán quy hoạch nguyên tuyến tính tổng quát với không gian biến số $x \in D_x \subset \mathbb{Z}^p$, $y \in D_y \subset \mathbb{R}^q$, phân biệt bài toán quy hoạch nguyên 0-1, bài toán nguyên hoàn toàn ($q=0$) và bài toán nguyên bộ phận ($q>0$). Trình bày nguyên lý các phương pháp giải như phương pháp Gomory, phương pháp nhánh cận (Branch and Bound - Land and Doig) và phương pháp Monte-Carlo.
  • Khái quát lý thuyết đồ thị bắt nguồn từ bài toán 7 cây cầu Königsberg của Leonhard Euler (thế kỷ XVIII), định nghĩa cấu trúc đồ thị $G=(V, E)$ và bài toán tìm đường đi ngắn nhất giữa hai đỉnh ứng dụng trong mạng thông tin và tối ưu hóa vận tải.

Chương 2: Mạng hàng đợi M/M/m và một số bài toán trong mạng hàng đợi

Chương 2 là chương lý thuyết trọng tâm của luận án, tập trung giải quyết các bài toán tối ưu phân chia dòng tải và bài toán luồng cực đại trong mạng hàng đợi $M/M/m$:

  • Phân tích mô hình hàng đợi $M/M/m$: Khảo sát hệ thống có dòng vào Poisson cường độ $\lambda$, thời gian phục vụ phân phối mũ cường độ $\mu$, gồm $m$ trạm phục vụ giống nhau. Thiết lập hệ phương trình cân bằng xác suất trạng thái, xác định biểu thức xác suất chậm trễ $\pi_w$.
  • Độ dài hàng đợi và thời gian lưu trú: Rút ra công thức tính độ dài hàng đợi trung bình: $$E(L_q) = \sum_{n=0}^\infty n \rho_{m+n} = \frac{\pi_w \rho}{1-\rho}$$ và thời gian chờ trung bình: $$E(W) = \frac{\pi_w}{m\mu (1-\rho)}$$ cùng phân phối thời gian chờ đợi $P(W > t) = \sum_{n=0}^\infty P\left(\sum_{k=0}^{n+1} D_k > t\right) \rho_{m+n}$.
  • Khung bài toán cực đại hóa tiện ích mạng (NUM): Phân tích bài toán tối ưu hóa hàm tiện ích tổng thể $f(x) = \sum_{i=1}^J U_i(x_i)$ trên mạng gồm $J$ nút với vector trạng thái $x = (x_1, \dots, x_J)$.
  • Xây dựng bài toán quy hoạch nguyên và thuật toán Gomory 1:
    • Trình bày chi tiết thuật toán Gomory 1 áp dụng cho bài toán nguyên hoàn toàn ($n_1 = n$).
    • Biểu diễn hàm mục tiêu và các biến cơ sở qua tập biến phi cơ sở $N_k$: $$x_i = x_{i0}^{(k)} - \sum_{j \in N_k} x_{ij}^{(k)} x_j$$
    • Xây dựng phương trình siêu phẳng cắt Gomory từ dòng có thành phần tự do không nguyên nhỏ nhất nhằm loại bỏ nghiệm không nguyên mà không làm mất nghiệm nguyên của bài toán.
  • Xây dựng và giải hai bài toán phân chia tối ưu dòng yêu cầu vào mạng:
    • Bài toán phân chia dạng 1: Dòng gồm $n_A$ yêu cầu từ bên ngoài phân bổ vào mạng $J$ nút. Tìm ma trận phân bổ $[x_{ij}]{n_A \times J}$ thỏa mãn: $$\max \sum{i=1}^{n_A} \sum_{j=1}^J \alpha_{ij} x_{ij}$$ với các ràng buộc: $$\sum_{j=1}^J x_{ij} \le 1, \quad x_{ij} \in {0, 1}, \quad \min \max_{j=1,\dots,J} E(l_j)$$ Luận án đưa ra Giả thiết (I): dòng yêu cầu ngoài bị chặn tại mọi thời điểm ($n_A \le C$). Dưới Giả thiết (I), luận án chứng minh tập phương án nguyên là hữu hạn và khác rỗng, từ đó chứng minh sự tồn tại lời giải tối ưu cho bài toán dạng 1.
    • Bài toán phân chia dạng 2: Trường hợp mọi yêu cầu đều có thể tiếp nhận xử lý tại bất kỳ nút nào trong mạng. Tìm vector $(x_1, x_2, \dots, x_J)$ thỏa mãn: $$\sum_{j=1}^J x_j = n_A, \quad x_j \in \mathbb{N}, \quad x_j \ge 0, \quad \min \max_{j=1,\dots,J} E(l_j)$$ Luận án chứng minh sự tồn tại lời giải tối ưu cho bài toán dạng 2 khi thỏa mãn Giả thiết (I) và tập phương án nguyên khác rỗng.
  • Bài toán luồng cực đại trên mạng: Khảo sát bài toán luồng trên mạng $G=(V, E)$, liên hệ với bài toán vận tải trong quy hoạch tuyến tính và trình bày thuật toán Ford-Fulkerson (1962) để tìm luồng cực đại giữa nút phát và nút thu.

Chương 3: Một số bài toán thực tế về mạng phục vụ

Chương 3 trình bày việc áp dụng các mô hình lý thuyết đã phát triển vào các bài toán kỹ thuật và quản lý thực tế:

  • Tối ưu hóa mạng phục vụ trong Trung tâm phục vụ / Trung tâm thương mại: Xây dựng mô hình phân chia luồng khách hàng và yêu cầu phục vụ dựa trên cơ chế phân loại dòng vào và cơ chế ưu tiên phục vụ, tối ưu hóa các tham số phục vụ để giảm thiểu thời gian chờ đợi của khách hàng.
  • Tối ưu hóa mạng phục vụ trong Mạng hướng thông tin (ICN):
    • Ứng dụng kỹ thuật tìm mảng và phân bổ dữ liệu có đặt tên (Named Data Objects - NDO).
    • Khảo sát cơ chế quản lý bảng tiền tố tên (Name Prefix Table), bảng định tuyến (Routing Table) và chiến lược tìm đường (Routing).
    • Phân tích hiệu năng dòng yêu cầu và dung lượng hàng đợi tại các router trong mạng ICN thông qua mô phỏng trên phần mềm OMNeT++.
    • Bảng số liệu thực nghiệm: Bảng 3.1 thống kê danh mục dữ liệu tại một số router; Bảng 3.2 khảo sát hiệu năng mạng ICN với nhiều router trên nền tảng OMNeT++.
  • Ứng dụng khai phá dữ liệu trong môi trường phân tán: Tích hợp mô hình hàng đợi để dự báo xu hướng dòng dữ liệu lớn, hỗ trợ các hệ thống hỗ trợ ra quyết định (Decision Support Systems - DSSs).

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

Căn cứ theo nội dung văn bản luận án, các kết quả nghiên cứu chính và đóng góp mới bao gồm:

  1. Về mặt lý luận toán học:
    • Phát biểu và thiết lập dạng toán học chặt chẽ cho hai lớp bài toán phân chia tối ưu dòng yêu cầu vào mạng hàng đợi $J$ nút (Bài toán phân chia dạng 1 và Bài toán phân chia dạng 2) kết hợp tiêu chuẩn tối ưu hóa Min-Max đối với độ dài hàng đợi kỳ vọng tại các nút.
    • Chứng minh toán học tường minh về sự tồn tại lời giải tối ưu cho cả hai dạng bài toán phân chia dòng yêu cầu dưới điều kiện dòng vào bị chặn (Giả thiết I).
    • Ứng dụng thành công thuật toán cắt Gomory 1 vào việc tìm nghiệm nguyên chính xác cho bài toán phân chia tải trên mạng hàng đợi.
  2. Về mặt thực tiễn và ứng dụng:
    • Đề xuất mô hình tối ưu hóa hàm mạng phục vụ ứng dụng kỹ thuật tìm mảng cho mạng hướng thông tin (Information-Centric Network - ICN), giải quyết bài toán định tuyến và quản lý bộ nhớ đệm tại các router.
    • Xây dựng mô hình tối ưu dòng phục vụ cho bài toán trung tâm thương mại/trung tâm dịch vụ dựa trên cơ chế dòng vào và thứ tự ưu tiên phục vụ.
    • Triển khai mô phỏng, kiểm chứng các thông số lưu lượng và bảng định tuyến của mạng ICN trên công cụ mô phỏng OMNeT++.

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

  • Hạn chế:
    • Các chứng minh sự tồn tại nghiệm của bài toán phân chia dòng yêu cầu dạng 1 và dạng 2 chỉ khẳng định tính tồn tại mà chưa khẳng định tính duy nhất của lời giải tối ưu.
    • Các mô hình giải tích trong chương 2 chủ yếu xây dựng dựa trên giả thiết dòng Poisson và thời gian phục vụ phân phối mũ ($M/M/m$), chưa mở rộng đầy đủ cho các phân phối tổng quát phức tạp ($G/G/m$).
  • Hướng nghiên cứu tiếp:
    • Mở rộng nghiên cứu điều kiện duy nhất của nghiệm tối ưu cho bài toán phân chia dòng yêu cầu.
    • Nghiên cứu các lớp mạng hàng đợi phi Markov với các phân phối thời gian phục vụ tổng quát trong môi trường mạng phân tán.
    • Tối ưu hóa sâu hơn thuật toán định tuyến và phân loại đối tượng dữ liệu NDO trên các topo mạng ICN quy mô lớn.

Giá trị tham khảo

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

  • Nghiên cứu sinh, học viên cao học chuyên ngành Toán học: Đặc biệt là chuyên ngành Lý thuyết xác suất và thống kê toán học, Vận trù học và Toán ứng dụng, tham khảo phương pháp kết hợp giữa lý thuyết xếp hàng và quy hoạch nguyên rời rạc.
  • Giảng viên, nhà nghiên cứu Công nghệ thông tin và Viễn thông: Tham khảo mô hình toán học giải quyết bài toán phân bổ lưu lượng, cân bằng tải, tối ưu hóa tiện ích mạng (NUM) và kiến trúc mạng hướng thông tin ICN.
  • Kỹ sư thiết kế hệ thống: Ứng dụng các công thức tính toán chỉ số hiệu năng hàng đợi ($E(L_q)$, $E(W)$, $\pi_w$) và mô hình mô phỏng OMNeT++ để tối ưu hóa năng lực trạm phục vụ và cấu hình router.

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

1. Luận án giải quyết những dạng bài toán phân chia tối ưu dòng yêu cầu nào?

Luận án thiết lập và giải hai dạng bài toán phân chia dòng yêu cầu vào mạng gồm $J$ nút:

  • Dạng 1: Mỗi yêu cầu $i$ chỉ được phân bổ vào tối đa một nút $j$ thông qua biến nhị phân $x_{ij} \in {0, 1}$ nhằm cực đại hóa tổng hệ số $\sum \alpha_{ij} x_{ij}$ đồng thời làm cực tiểu độ dài hàng đợi cực đại kỳ vọng $\min \max_j E(l_j)$.
  • Dạng 2: Tất cả các yêu cầu đều có thể tiếp nhận xử lý tại bất kỳ nút nào trong mạng, phân bổ số lượng yêu cầu $x_j \in \mathbb{N}$ vào nút $j$ sao cho tổng bằng $n_A$ và thỏa mãn điều kiện $\min \max_j E(l_j)$.

2. Điều kiện nào đảm bảo sự tồn tại nghiệm cho các bài toán phân chia dòng yêu cầu trong luận án?

Sự tồn tại nghiệm được đảm bảo nhờ Giả thiết (I): Dòng yêu cầu từ bên ngoài vào mạng tại mọi thời điểm luôn bị chặn trên bởi một hằng số hữu hạn ($n_A \le C$). Khi đó, tập các phương án nguyên là tập hữu hạn và khác rỗng, đảm bảo tồn tại giá trị lớn nhất/nhỏ nhất của hàm mục tiêu.

3. Thuật toán quy hoạch nguyên nào được sử dụng chính trong Chương 2?

Luận án sử dụng Thuật toán Gomory 1 dành cho bài toán quy hoạch nguyên tuyến tính hoàn toàn. Thuật toán bắt đầu bằng việc giải bài toán quy hoạch tuyến tính nới lỏng bằng phương pháp đơn hình đối ngẫu tự điển, sau đó bổ sung liên tiếp các siêu phẳng cắt Gomory từ các hàng có thành phần tự do không nguyên để tiến tới nghiệm nguyên tối ưu sau một số hữu hạn bước lặp.

4. Các kết quả lý thuyết của luận án được công bố tại các diễn đàn khoa học nào?

Công trình nghiên cứu trong luận án đã được công bố qua 05 bài báo khoa học trên các ấn phẩm chuyên ngành:

  • Tạp chí Nghiên cứu Khoa học Kỹ thuật và Công nghệ Quân sự.
  • Tạp chí Ứng dụng Toán học.
  • Kỷ yếu Hội nghị Khoa học và Công nghệ Quốc gia NICS 2014 (do Quỹ NAFOSTED tổ chức).
  • Báo cáo tại Hội nghị Toán ứng dụng toàn quốc lần thứ 3 (2010), các seminar tại Viện Công nghệ Thông tin, Viện Toán học (Viện Hàn lâm Khoa học và Công nghệ Việt Nam) và Viện Khoa học và Công nghệ Quân sự.

Kết luận

Luận án tiến sĩ "Một số bài toán tối ưu trong lý thuyết xếp hàng và ứng dụng" của tác giả Phan Thị Loan đã hệ thống hóa và phát triển các mô hình tối ưu hóa trong mạng hàng đợi $M/M/m$. Tác giả đã thiết lập thành công mô hình toán học và chứng minh sự tồn tại nghiệm cho hai bài toán phân chia tối ưu dòng yêu cầu vào mạng dưới điều kiện dòng vào bị chặn, đồng thời vận dụng giải thuật quy hoạch nguyên Gomory và thuật toán luồng mạng Ford-Fulkerson để giải quyết bài toán cân bằng tải. Các kết quả nghiên cứu đã được kiểm chứng thông qua ứng dụng mô hình hóa mạng phục vụ trung tâm thương mại và mô phỏng mạng hướng thông tin ICN trên phần mềm OMNeT++, đóng góp cơ sở lý thuyết và thực tiễn cho chuyên ngành Lý thuyết xác suất và thống kê toán học.