Tổng quan về luận án

Bài toán lập lịch điều độ sản xuất (Scheduling Problem), đặc biệt là bài toán lập lịch Job Shop (Job Shop Scheduling Problem - JSP), là một trong những bài toán tối ưu hóa tổ hợp kinh điển và phức tạp nhất thuộc lĩnh vực Vận trù học (Operations Research) và Khoa học máy tính kể từ thập niên 1950. Luận án tiến sĩ của tác giả Nguyễn Hữu Mùi với đề tài "Thuật toán và các bài toán lịch biểu" (chuyên ngành Khoa học máy tính, mã số 62 48 01 01, bảo vệ tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội dưới sự hướng dẫn của PGS. TS Hoàng Xuân Huấn và PGS. TSKH Vũ Đình Hoà) đã giải quyết triệt để các rào cản tính toán cốt lõi của JSP thông qua việc phát triển khung thuật toán di truyền lai thế hệ mới kết hợp kỹ thuật song song hóa và chứng minh tính hội tụ bằng lý thuyết giải tích ngẫu nhiên.

Khoảng trống nghiên cứu (Research Gap) trung tâm được luận án định vị xuất phát từ thực tiễn: với một bài toán JSP quy mô $n$ công việc ($J_i$) và $m$ máy ($M_j$), không gian tìm kiếm khả dĩ bùng nổ ở mức $(n!)^m$ trạng thái. Các phương pháp giải chính xác như Quy hoạch nguyên tuyến tính hỗn hợp (Mixed Integer Linear Programming - MIP) của Manne (1960), Nới lỏng Lagrangian (Lagrangian Relaxation - LR) của Fisher (1973), hay Nhánh cận (Branch and Bound - BB) của Carlier & Pinson (1989) đều đối mặt với sự bùng nổ thời gian tính toán theo hàm số mũ khi kích thước bài toán mở rộng. Ngược lại, các phương pháp siêu phỏng sinh học kinh điển như Thuật toán di truyền (Genetic Algorithm - GA) dạng nhị phân nguyên bản của Holland (1975) lại liên tục tạo ra các cá thể con vi phạm ràng buộc thứ tự công nghệ (infeasible schedules), đòi hỏi cơ chế sửa sai (repair mechanism) phức tạp và thiếu cơ sở toán học chứng minh sự hội tụ về nghiệm tối ưu toàn cục.

Luận án thiết lập hệ thống 3 câu hỏi nghiên cứu (Research Questions - RQ) và 3 giả thuyết tương ứng (Hypotheses - H):

  • RQ1: Làm thế nào để loại bỏ hoàn toàn các nghiệm không hợp lệ trong quá trình tiến hóa của thuật toán di truyền đối với bài toán Flow Shop hoán vị (PFSP), Flow Shop tổng quát (FSP) và Job Shop tổng quát (JSP)?
  • H1: Một cấu trúc mã hóa số tự nhiên trực tiếp (Natural Number Direct Encoding) ánh xạ chính xác các thao tác ($O_{ij}$) sẽ duy trì tính khả thi cấu trúc $100%$ qua mọi phép lai ghép và đột biến.
  • RQ2: Sự kết hợp giữa thuật toán di truyền với quy tắc ưu tiên sinh lịch biểu tích cực của Giffler & Thompson (GT) và tìm kiếm cục bộ sẽ cải thiện thời gian hoàn thành tổng thể (Makespan - $C_{\max}$) ở mức độ nào so với các tiếp cận heuristic đơn lẻ?
  • H2: Thuật toán di truyền lai mới (Novel Hybrid Genetic Algorithm - NHGA) tích hợp toán tử trao đổi chéo đa cha mẹ dựa trên GT sẽ hội tụ nhanh hơn về vùng nghiệm tối ưu cục bộ chất lượng cao.
  • RQ3: Có thể chứng minh một cách chặt chẽ về mặt toán học rằng thuật toán di truyền lai với cơ chế lưu trữ cá thể tinh hoa (Elitism) sẽ hội tụ tiệm cận về nghiệm tối ưu toàn cục hay không?
  • H3: Bằng cách mô hình hóa thuật toán di truyền dưới dạng một xích Markov Ergodic đồng nhất, xác suất quần thể chứa nghiệm tối ưu toàn cục tiến tới $1$ khi số thế hệ tiến ra vô cùng.

Phạm vi thực nghiệm của luận án bao phủ hệ thống dữ liệu kiểm chuẩn quốc tế khắt khe bao gồm bộ dữ liệu của Lawrence (LA01 đến LA40) và bộ bài toán kinh điển của Muth & Thompson (mt06 $6\times 6$, mt10 $10\times 10$, mt20 $20\times 5$).

Literature Review và Positioning

Tổng quan y văn trong luận án phân loại toàn diện tiến trình phát triển của các phương pháp giải quyết JSP thành hai nhánh tiếp cận chính:

Trong nhánh tiếp cận chính xác, Manne (1960) đã đặt nền móng với mô hình Quy hoạch tuyến tính nguyên hỗn hợp (MIP), sử dụng các biến nhị phân để biểu diễn ràng buộc không chồng chéo trên các máy. Tuy nhiên, Fisher (1973) và Della Croce et al. (1995) đã chỉ ra rằng khi $n, m \ge 10$, số lượng ràng buộc bất đẳng thức tăng phi mã khiến ma trận tính toán vượt ngưỡng bộ nhớ thực tế. Carlier và Pinson (1989) tạo nên bước đột phá khi giải thành công bài toán $10\times 10$ (mt10) sau hơn 20 năm tồn tại bằng thuật toán Nhánh cận (Branch and Bound). Tuy nhiên, Glover và Greenberg (1989) khẳng định rằng các thuật toán nhánh cận thuần túy không thể mở rộng cho các bài toán công nghiệp quy mô lớn do chi phí duyệt cây không gian trạng thái quá lớn.

Trong nhánh tiếp cận gần đúng (Approximation and Meta-heuristics), cuộc tranh luận học thuật diễn ra gay gắt giữa hai trường phái:

  1. Trường phái Heuristic cấu trúc: Nổi bật với quy tắc lập lịch sinh lịch tích cực của Giffler và Thompson (1960) và phương pháp Heuristic Dời nút cổ chai (Shifting Bottleneck - SB) của Adams, Balas và Zawack (1988), sau đó được Applegate và Cook (1991) cải tiến. Trường phái này xử lý bài toán nhanh nhưng dễ bị mắc kẹt tại cực trị cục bộ do tính chất tìm kiếm tham lam (greedy nature).
  2. Trường phái Tối ưu hóa ngẫu nhiên (Stochastic Metaheuristics): Bao gồm Giải thuật Luyện kim mô phỏng (Simulated Annealing - SA) của Van Laarhoven et al. (1992), Thuật toán Tìm kiếm Tabu (Tabu Search - TS) của Glover (1989), Laguna et al. (1991), và Hệ bầy kiến (Ant System - AS) của Colorni et al. (1994). Mặc dù các thuật toán này có khả năng thoát cực trị cục bộ, chúng lại phụ thuộc rất lớn vào việc tinh chỉnh tham số và cấu trúc lân cận $N(x)$.

Đối với Thuật toán di truyền, Nakano và Yamada (1991) đã tiên phong áp dụng GA vào JSP nhưng thừa nhận rằng toán tử đột biến và trao đổi chéo nhị phân cổ điển (Holland, 1975; Goldberg, 1989) phá vỡ các khối gen cấu trúc (building blocks), khiến tỷ lệ cá thể hợp lệ rơi xuống dưới $15%$. Ulder et al. (1991) đề xuất mô hình Genetic Local Search (GLS) để khắc phục điểm yếu này. Luận án của Nguyễn Hữu Mùi định vị chính xác tại giao điểm này: kế thừa ưu thế khám phá toàn cục của GA, tích hợp cơ chế bảo toàn tính hợp lệ cấu trúc bằng mã hóa số tự nhiên, khai thác năng lực sinh lịch tích cực của thuật toán GT, và thiết lập cầu nối toán học với lý thuyết xích Markov của Rudolph (1994).

Đó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 ba đóng góp nền tảng cho lý thuyết tiến hóa và tối ưu hóa tổ hợp:

  1. Mở rộng định lý Schemata (Schema Theorem) sang miền biểu diễn số tự nhiên: Khắc phục hạn chế của lý thuyết chuỗi nhị phân kinh điển (Holland, 1975; Goldberg, 1989), luận án thiết lập nguyên lý duy trì lược đồ bậc cao cho các hoán vị thao tác không gian đa chiều, chứng minh rằng toán tử di truyền được thiết kế đặc thù không phá vỡ tính liên tục của chuỗi công nghệ.
  2. Thiết lập mô hình hội tụ tiệm cận dựa trên Xích Markov Ergodic: Luận án chứng minh rằng quá trình chuyển dịch trạng thái quần thể của thuật toán di truyền lai với toán tử duy trì cá thể tinh hoa (Elitism) tạo thành một xích Markov đồng nhất. Không gian trạng thái được chứng minh là có tính chất xích không thể phân rã (irreducible) và không tuần hoàn (aperiodic). Xác suất để thuật toán tìm thấy và lưu giữ nghiệm tối ưu toàn cục $x^*$ thỏa mãn điều kiện tiệm cận:

$$\lim_{t \to \infty} P(X_t \cap S^* \neq \emptyset) = 1$$

  1. Chuyển dịch hệ hình biểu diễn bài toán JSP: Thay vì tách rời không gian biểu diễn (Representation Space) và không gian lịch biểu thực thi (Schedule Space), luận án thiết lập mối quan hệ ánh xạ song ánh $1-1$ giữa cá thể mã hóa số tự nhiên và tập lịch biểu tích cực (Active Schedules).

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

Khung phân tích của luận án tích hợp đồng thời ba cấu phần lý thuyết:

  • Lý thuyết Lập lịch tích cực (Active Schedule Theory): Dựa trên định lý của Giffler và Thompson (1960), chứng minh rằng không gian các lịch biểu tích cực luôn chứa ít nhất một lịch biểu tối ưu toàn cục về Makespan. Việc thu hẹp không gian tìm kiếm từ $(n!)^m$ về tập con các lịch biểu tích cực làm giảm kích thước bài toán đi hàng triệu lần.
  • Toán tử di truyền lai đa cá thể cha mẹ: Đề xuất cơ chế lai ghép 3 cá thể cha mẹ kết hợp với thuật toán giải mã GT, đảm bảo mọi cá thể con sinh ra đều tự động thỏa mãn $100%$ các ràng buộc công nghệ mà không cần thêm bất kỳ bước sửa sai (repair mechanism) nào.
  • Điều kiện biên xác định: Nghiên cứu xác lập rõ ràng các giả định biên bao gồm: thời gian xử lý $p_{ij}$ là tiền định (deterministic), không xét hiện tượng máy hỏng ngẫu nhiên (machine breakdowns), xử lý liên tục không ngắt quãng (non-preemptive), và mỗi máy chỉ xử lý tối đa một thao tác tại một thời điểm.

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

Thiết kế nghiên cứu

Luận án theo đuổi thế giới quan bản thể luận khách quan (Realism) và phương pháp luận thực chứng tính toán (Computational Positivism). Thiết kế nghiên cứu tuân thủ mô hình thực nghiệm lặp 4 bước:

Cỡ mẫu thử nghiệm bao gồm toàn bộ các bộ dữ liệu chuẩn mực được công nhận rộng rãi trong cộng đồng Vận trù học quốc tế: 40 bài toán Lawrence (LA01 - LA40) với kích thước từ $10\times 5$ đến $30\times 10$, và 3 bài toán thử thách của Muth & Thompson (mt06 $6\times 6$, mt10 $10\times 10$, mt20 $20\times 5$).

Quy trình nghiên cứu rigorous

Quy trình giải bài toán Job Shop bằng thuật toán di truyền lai tuần tự (NHGA) và song song (PHGA) được thiết kế theo các giao thức tính toán chuẩn xác:

Quy trình thực thi cụ thể bao gồm:

  1. Cấu trúc mã hóa số tự nhiên: Mỗi thao tác $O_{ij}$ được biểu diễn bằng một số nguyên $k \in {1, 2, \dots, n \times m}$. Thứ tự xuất hiện của số hiệu công việc trong chuỗi cá thể đại diện cho thứ tự ưu tiên của thao tác tương ứng của công việc đó.
  2. Toán tử lai ghép cải tiến: Luận án phát triển cơ chế lai ghép trên 3 cá thể cha mẹ ($P_1, P_2, P_3$). Toán tử này duyệt qua cấu trúc xung đột tài nguyên và sử dụng thuật toán GT để chọn thao tác có thời gian hoàn thành sớm nhất từ một trong ba cha mẹ, loại bỏ hoàn toàn khả năng sinh ra chu kỳ khóa chết (deadlock).
  3. Mô hình song song hóa Master - Slave (PHGA): Tiến trình Master chịu trách nhiệm quản lý quần thể chính, phân phối các khối tính toán và điều phối cá thể di cư. Các tiến trình Slave thực thi song song các toán tử di truyền, tính toán hàm thích nghi $eval(v_i) = 1 / C_{\max}(v_i)$ và tìm kiếm cục bộ trên các tập con của quần thể.

Data và phân tích

Dữ liệu được thu thập qua hàng nghìn lượt chạy thử nghiệm lặp lại để loại trừ yếu tố ngẫu nhiên. Môi trường tính toán được cài đặt bằng ngôn ngữ C/C++, thực thi trên hệ thống máy chủ đa nhân tại Trung tâm Khoa học Tính toán – Trường Đại học Sư phạm Hà Nội.

Độ tin cậy và tính hợp lệ của thuật toán được lượng hóa qua hai chỉ số thống kê then chốt:

  • Sai số tương đối phần trăm (Percentage Relative Error - RE): $$RE = \frac{C_{\max} - C^}{C^} \times 100%$$ (trong đó $C_{\max}$ là giá trị Makespan tìm được, $C^$ là giá trị tối ưu toàn cục đã biết).*
  • Hệ số tăng tốc tính toán (Speedup Factor - $S_p$): $$S_p = \frac{T_1}{T_p}$$ (trong đó $T_1$ là thời gian thực thi tuần tự, $T_p$ là thời gian thực thi song song với $p$ bộ xử lý).

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

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

  1. Hiệu năng tìm kiếm nghiệm tối ưu vượt trội trên các bài toán kiểm chuẩn chuẩn mực: Thuật toán NHGA đạt độ chính xác $100%$ ($RE = 0.00%$) trên toàn bộ các bài toán kích thước nhỏ và trung bình của bộ kiểm chuẩn Lawrence (từ LA01 đến LA15), tìm thấy giá trị tối ưu Makespan tuyệt đối trong thời gian dưới $2.5$ giây.
  2. Hóa giải rào cản tính toán trên bộ bài toán Muth & Thompson: Đối với bài toán mt06 ($6\times 6$), thuật toán đạt Makespan tối ưu $C_{\max} = 55$ ngay ở thế hệ thứ $12$. Đối với bài toán mt10 ($10\times 10$) – một bài toán từng làm đau đầu giới toán học suốt 3 thập kỷ, thuật toán NHGA đạt Makespan $C_{\max} = 930$ với độ lệch chuẩn cực tiểu qua 30 lần chạy độc lập. Với bài toán mt20 ($20\times 5$), thuật toán đạt $C_{\max} = 1165$.
  3. Hiệu ứng tăng tốc gần như tuyến tính của thuật toán song song PHGA: Khi triển khai trên kiến trúc phân tán Master-Slave, thuật toán PHGA giảm thời gian chạy máy xuống từ $3.8$ đến $7.2$ lần so với thuật toán tuần tự NHGA trên cùng một bộ tham số kích thước quần thể ($N = 100$), xác suất lai ghép ($p_c = 0.85$) và xác suất đột biến ($p_m = 0.08$), trong khi chất lượng nghiệm tối ưu hoàn toàn đồng nhất.
  4. Xác thực toán học cho tính hội tụ: Bằng việc tính toán ma trận xác suất chuyển tiếp giữa các trạng thái $P_{ij}$, luận án chứng minh rằng ma trận chuyển trạng thái của thuật toán di truyền có cơ chế Elitism có dạng ma trận khối tam giác trên:

$$P = \begin{pmatrix} C & 0 \ R & T \end{pmatrix}$$

Điều này đảm bảo rằng một khi quần thể đã bước vào tập trạng thái chứa nghiệm tối ưu toàn cục $C$, nó sẽ không bao giờ rời khỏi tập này, chứng minh tính hấp thu vững chắc (absorbing states) của nghiệm tối ưu.

Implications đa chiều

  • Về mặt lý thuyết: Thiết lập mô hình phân tích xích Markov chuẩn tắc làm công cụ mẫu mực để chứng minh tính hội tụ cho các thuật toán siêu phỏng sinh học (Meta-heuristics) lai khác như PSO, ACO, ABC khi áp dụng vào các bài toán NP-hard.
  • Về mặt phương pháp luận: Cung cấp phương thức mã hóa số tự nhiên kèm toán tử lai đa cha mẹ bảo toàn tính hợp lệ cấu trúc, mở ra hướng đi mới trong việc xử lý các bài toán tối ưu có ràng buộc thứ tự phức tạp (Precedence-Constrained Combinatorial Optimization).
  • Về mặt ứng dụng thực tiễn: Cung cấp lõi thuật toán điều độ cho các hệ thống sản xuất tích hợp máy tính (Computer Integrated Manufacturing - CIM), hệ thống sản xuất linh hoạt (Flexible Manufacturing Systems - FMS) và lập lịch luồng công việc trong tính toán đám mây (Cloud Workflow Scheduling).
  • Về mặt chính sách và công nghiệp: Hỗ trợ quá trình chuyển đổi số trong các doanh nghiệp sản xuất công nghiệp tại Việt Nam, tối ưu hóa công suất máy móc, giảm thiểu thời gian chờ (idle time) và tiết kiệm chi phí vận hành từ $12-18%$.

Limitations và Future Research

Mặc dù đạt được những đột phá học thuật xuất sắc, luận án thẳng thắn thừa nhận các giới hạn nghiên cứu (Boundary Conditions):

  1. Mô hình lập lịch tĩnh và tiền định (Deterministic & Static Scheduling): Luận án tập trung vào bài toán với các tham số thời gian $p_{ij}$ cố định, chưa mô hình hóa các biến động ngẫu nhiên theo thời gian thực như máy hỏng đột xuất, hủy đơn hàng, hoặc thời gian gia công dao động (stochastic processing times).
  2. Mục tiêu đơn biến (Single-Objective Optimization): Nghiên cứu tập trung tối ưu hóa chỉ số Makespan ($C_{\max}$). Trong thực tế điều độ sản xuất hiện đại, các doanh nghiệp thường đối mặt với bài toán đa mục tiêu (Multi-Objective) bao gồm tổng độ trễ trễ hạn (Total Tardiness), chi phí năng lượng tiêu thụ (Energy Consumption) và độ cân bằng tải giữa các máy (Workload Balance).
  3. Điểm nghẽn truyền thông trong kiến trúc Master - Slave: Khi số lượng nút xử lý song song mở rộng vượt quá một ngưỡng nhất định, chi phí truyền thông (communication overhead) giữa tiến trình Master và các tiến trình Slave có xu hướng triệt tiêu một phần hiệu quả tăng tốc tính toán.

Các hướng nghiên cứu tiếp nối trong tương lai được xác lập rõ ràng:

  • Tích hợp logic mờ (Fuzzy Logic) và lý thuyết xác suất để giải quyết bài toán Job Shop ngẫu nhiên/mờ (Fuzzy/Stochastic JSP).
  • Phát triển thuật toán di truyền đa mục tiêu (Multi-Objective Evolutionary Algorithms - MOEA như NSGA-II, MOEA/D) cho bài toán lập lịch xanh (Green Scheduling).
  • Nâng cấp kiến trúc tính toán song song từ mô hình Master-Slave sang mô hình Đảo quần thể bất đồng bộ (Asynchronous Island Model) kết hợp tính toán trên GPU (CUDA programming).

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

  • Tác động học thuật sâu rộng: Luận án là công trình tiên phong tại Việt Nam giải quyết trọn vẹn cả ba khía cạnh của bài toán JSP: cải tiến cấu trúc thuật toán, thực thi tính toán song song hiệu năng cao, và chứng minh toán học giải tích ngẫu nhiên. Công trình được ứng dụng làm tài liệu giảng dạy chuyên đề sau đại học tại Đại học Quốc gia Hà Nội và Trường Đại học Sư phạm Hà Nội.
  • Hiện đại hóa sản xuất công nghiệp: Mô hình thuật toán của luận án có khả năng tích hợp trực tiếp vào các hệ thống điều hành sản xuất công nghiệp (Manufacturing Execution Systems - MES) và hoạch định nguồn lực doanh nghiệp (Enterprise Resource Planning - ERP) như SAP, Oracle MES, hỗ trợ các nhà máy dệt may, cơ khí chế tạo và đóng gói tự động hóa.
  • Tiêu chuẩn kiểm chuẩn thuật toán: Hệ thống hóa các bộ kiểm chuẩn chuẩn mực (Benchmark Instances) giúp các nhóm nghiên cứu trong nước có bộ công cụ đối sánh chuẩn quốc tế.

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

  1. Nghiên cứu sinh và Học viên cao học chuyên ngành Khoa học máy tính & Vận trù học: Kế thừa khung lý thuyết chứng minh xích Markov Ergodic để phát triển luận án về các thuật toán tối ưu hóa bầy đàn và tiến hóa mới.
  2. Giảng viên và Nhà nghiên cứu cao cấp: Nguồn tư liệu học thuật mẫu mực về cấu trúc thiết kế thuật toán lai và tối ưu hóa song song cho các chương trình đào tạo sau đại học.
  3. Kỹ sư R&D phần mềm công nghiệp: Tiếp cận mã nguồn và giải thuật tối ưu hóa lịch biểu thực tế để tích hợp vào các giải pháp phần mềm Quản lý sản xuất thông minh (Smart Factory / Industry 4.0).
  4. Nhà quản lý vận hành sản xuất: Áp dụng phương pháp luận phân phối tải và sinh lịch biểu tích cực để loại bỏ lãng phí thời gian máy chờ và nâng cao năng suất tổng thể của dây chuyền.

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

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

Đóng góp độc đáo nhất là việc xây dựng thành công chứng minh toán học giải tích về sự hội tụ tiệm cận của thuật toán di truyền lai tuần tự về tập nghiệm tối ưu toàn cục dựa trên lý thuyết Xích Markov Ergodic. Bằng cách thiết lập ma trận xác suất chuyển trạng thái $P$ và chứng minh tính chất không thể phân rã, không tuần hoàn kết hợp với toán tử bảo tồn cá thể tinh hoa (Elitist selection), luận án đã vượt qua hạn chế "hộp đen thực nghiệm" của các nghiên cứu meta-heuristic trước đây, đưa ra khẳng định toán học vững chắc rằng: $\lim_{t \to \infty} P(X_t \cap S^* \neq \emptyset) = 1$.

2. Sự đổi mới về phương pháp luận của luận án vượt trội hơn các công trình quốc tế cùng thời như thế nào?

So với công trình GA nhị phân của Nakano & Yamada (1991) vốn gặp bế tắc vì tỷ lệ sinh cá thể không hợp lệ cao, và công trình GLS của Ulder et al. (1991) chỉ sử dụng tìm kiếm cục bộ đơn giản, luận án đã đổi mới toàn diện với ba trụ cột:

  • Áp dụng Mã hóa số tự nhiên trực tiếp theo chuỗi thao tác.
  • Tích hợp Toán tử lai ghép 3 cha mẹ dựa trên thuật toán Giffler & Thompson (GT) để $100%$ cá thể con sinh ra đều là lịch biểu tích cực (Active Schedule).
  • Triển khai Mô hình song song hóa Master - Slave giảm triệt để độ phức tạp thời gian tính toán thực tế mà không làm suy giảm chất lượng nghiệm.

3. Phát hiện thực nghiệm nào gây bất ngờ và có ý nghĩa tính toán lớn nhất trong luận án?

Phát hiện thực nghiệm ấn tượng nhất là khả năng giải quyết dứt điểm bài toán Muth & Thompson mt10 ($10\times 10$) đạt giá trị Makespan tối ưu $C_{\max} = 930$ với độ lệch chuẩn hội tụ bằng $0$ qua nhiều lần chạy độc lập. Bài toán mt10 nổi tiếng là một thách thức tính toán kéo dài hơn 20 năm (từ 1963 đến 1989 mới được giải chính xác bằng nhánh cận). Việc một thuật toán di truyền lai tìm ra nghiệm tối ưu trong thời gian vài giây trên máy tính cá nhân khẳng định tính hiệu quả tuyệt đối của cấu trúc lai ghép GT.

4. Luận án có cung cấp đầy đủ giao thức để tái lập kết quả thực nghiệm (Replication Protocol) không?

Có. Luận án đặc tả chi tiết toàn bộ các cấu phần thuật toán: cấu trúc mảng dữ liệu mã hóa, công thức tính hàm thích nghi $eval(v_i)$, giả mã (pseudo-code) của thủ tục di truyền tuần tự và song song, quy tắc phân chia luồng Master-Slave, danh mục tham số thực nghiệm cố định ($N, p_c, p_m$, số thế hệ dừng), cùng với ma trận dữ liệu đầu vào chi tiết của từng bài toán kiểm chuẩn (như bảng thời gian gia công $p_{ij}$ và tuần tự công nghệ máy).

5. Chương trình nghị sự nghiên cứu 10 năm tới từ nền tảng của luận án được định hình ra sao?

Nền tảng của luận án mở đường cho 3 trục nghiên cứu trọng điểm:

  • Trục 1 (Dynamic & Uncertain Scheduling): Phát triển các thuật toán tiến hóa thích nghi tự động (Adaptive Evolutionary Algorithms) kết hợp Học tăng cường sâu (Deep Reinforcement Learning) để điều độ sản xuất động khi có biến cố thời gian thực.
  • Trục 2 (High-Performance Computing): Tận dụng kiến trúc tính toán song song hàng loạt trên chip đồ họa (Massively Parallel GPU Computing với CUDA) để giải quyết các bài toán JSP quy mô siêu lớn ($1000 \times 1000$).
  • Trục 3 (Sustainable Manufacturing): Mở rộng khung phân tích sang bài toán tối ưu hóa đa mục tiêu cân bằng giữa Makespan, lượng phát thải carbon và chi phí năng lượng giờ cao điểm.

Kết luận

Luận án tiến sĩ "Thuật toán và các bài toán lịch biểu" của tác giả Nguyễn Hữu Mùi là một công trình khoa học xuất sắc, mẫu mực và toàn diện trong lĩnh vực Khoa học máy tính và Tối ưu hóa tổ hợp. Năm đóng góp then chốt tạo nên giá trị học thuật cốt lõi của luận án bao gồm:

  1. Hệ thống hóa và phân tích sâu sắc các nhánh tiếp cận chính xác, xấp xỉ và siêu phỏng sinh học cho bài toán lập lịch Job Shop tổng quát.
  2. Thiết lập cấu trúc mã hóa số tự nhiên trực tiếp cho bài toán Flow Shop hoán vị (PFSP) và Flow Shop tổng quát (FSP), loại bỏ hoàn toàn các nghiệm không hợp lệ.
  3. Phát triển thành công Thuật toán di truyền lai mới (NHGA) cho JSP tích hợp toán tử lai ghép 3 cha mẹ và quy tắc sinh lịch biểu tích cực Giffler & Thompson (GT).
  4. Thiết kế và cài đặt hoàn chỉnh Thuật toán di truyền lai song song (PHGA) theo mô hình Master-Slave, đạt hiệu năng tăng tốc tính toán vượt trội trên các hệ thống phân tán.
  5. Xây dựng chứng minh toán học giải tích chặt chẽ bằng Xích Markov Ergodic khẳng định tính hội tụ tiệm cận của thuật toán về nghiệm tối ưu toàn cục.

Công trình không chỉ giải quyết trọn vẹn những thách thức tính toán kinh điển của bài toán lập lịch Job Shop mà còn thiết lập một chuẩn mực phương pháp luận mới kết hợp hài hòa giữa mô hình hóa toán học chính xác, thuật toán tiến hóa thông minh và kiến trúc tính toán song song hiệu năng cao, đóng góp thiết thực cho sự phát triển của nền khoa học công nghệ và nền sản xuất thông minh hiện đại.