## Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của công nghệ điện toán đám mây và nhu cầu sử dụng hiệu quả tài nguyên máy tính ảo trong giáo dục và nghiên cứu, việc tối ưu lập lịch cho mạng máy tính ảo trở thành một vấn đề cấp thiết. Theo ước tính, các trường đại học và tổ chức nghiên cứu hiện đang sử dụng hàng trăm máy ảo để phục vụ giảng dạy và nghiên cứu, đòi hỏi một hệ thống quản lý tài nguyên hiệu quả nhằm giảm chi phí vận hành và tăng hiệu suất sử dụng. Luận văn tập trung nghiên cứu bài toán lập lịch đa mục tiêu cho mạng máy tính ảo, trong đó các công việc có thời gian thực thi cố định và các máy ảo có cấu hình đồng nhất. Mục tiêu chính là đề xuất các mô hình toán học MILP và các giải thuật heuristic nhằm tối ưu hóa việc phân bổ tài nguyên, đồng thời xây dựng đường cong Pareto cho các mục tiêu đa dạng như giảm tổng số máy vật lý sử dụng và chi phí hoạt động. Phạm vi nghiên cứu tập trung vào dữ liệu thực tế từ phòng thí nghiệm ảo của trường Đại học Bách Khoa TP.HCM trong khoảng thời gian 2 năm học (4 học kỳ). Nghiên cứu có ý nghĩa quan trọng trong việc nâng cao hiệu quả quản lý tài nguyên công nghệ thông tin, giảm chi phí vận hành và hỗ trợ ra quyết định cho các nhà quản lý hệ thống.

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

### Khung lý thuyết áp dụng

- **Lập lịch tối ưu (Scheduling Theory):** Nghiên cứu các phương pháp phân bổ tài nguyên cho các công việc sao cho thỏa mãn các ràng buộc về thời gian và tài nguyên, đồng thời tối ưu hóa các mục tiêu như thời gian hoàn thành, chi phí, hoặc hiệu suất sử dụng.
- **Tối ưu đa mục tiêu (Multi-objective Optimization):** Áp dụng lý thuyết tối ưu đa mục tiêu để cân bằng các mục tiêu cạnh tranh như giảm tổng số máy vật lý sử dụng và chi phí hoạt động, sử dụng các khái niệm tối ưu Pareto và các phương pháp hỗ trợ ra quyết định đa mục tiêu.
- **Mô hình MILP (Mixed Integer Linear Programming):** Xây dựng các mô hình toán học MILP để mô tả bài toán lập lịch, bao gồm các biến nhị phân và ràng buộc tuyến tính, nhằm tìm lời giải tối ưu bằng các solver chuyên dụng.
- **Giải thuật heuristic và meta-heuristic:** Đề xuất các giải thuật gần đúng như giải thuật tham lam (Greedy), giải thuật di truyền (Genetic Algorithm) để xử lý bài toán có độ phức tạp cao, giúp tìm lời giải khả thi trong thời gian hợp lý.
- **Đồ thị công việc (Job Graph):** Sử dụng đồ thị có hướng để biểu diễn mối quan hệ thời gian giữa các công việc, hỗ trợ phân hoạch bài toán thành các tập con độc lập nhằm giảm không gian tìm kiếm.

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

- **Nguồn dữ liệu:** Dữ liệu thực nghiệm được thu thập từ thời khóa biểu các phòng thí nghiệm ảo của khoa Khoa học và Kỹ thuật máy tính, trường Đại học Bách Khoa TP.HCM, bao gồm thông tin về thời gian bắt đầu, thời gian thực thi, số lượng máy ảo yêu cầu cho từng công việc trong 2 năm học (4 học kỳ).
- **Phương pháp phân tích:** 
  - Xây dựng các mô hình MILP cho bài toán lập lịch đa mục tiêu.
  - Phát triển và triển khai các giải thuật heuristic như VLAB_Greedy, giải thuật di truyền và VLAB_Allocation.
  - Thực hiện các thí nghiệm so sánh hiệu quả các mô hình và giải thuật trên dữ liệu thực tế.
  - Phân tích kết quả bằng các chỉ số như tổng số máy vật lý sử dụng, chi phí vận hành và thời gian thực thi.
  - Vẽ đường cong Pareto để minh họa các điểm tối ưu thỏa hiệp giữa các mục tiêu.
- **Timeline nghiên cứu:** Nghiên cứu được thực hiện trong khoảng thời gian từ tháng 7/2012 đến tháng 7/2013, bao gồm giai đoạn thu thập dữ liệu, xây dựng mô hình, phát triển giải thuật, thực nghiệm và phân tích kết quả.

## Kết quả nghiên cứu và thảo luận

### Những phát hiện chính

- **Bài toán lập lịch cho mạng máy tính ảo thuộc lớp NP-Complete:** Qua chứng minh suy giảm từ bài toán PARTITION, bài toán quyết định trong nghiên cứu được xác định là NP-đầy đủ, cho thấy tính phức tạp cao và khó tìm lời giải tối ưu trong thời gian đa thức.
- **Hiệu quả của các mô hình MILP:** Các mô hình MILP được đề xuất có khả năng mô tả chính xác bài toán, tuy nhiên giới hạn về số lượng công việc và thời gian tính toán khi sử dụng solver Gurobi, đặc biệt với số lượng công việc lớn.
- **Giải thuật heuristic đạt hiệu quả cao:** Giải thuật VLAB_Greedy và giải thuật di truyền cho phép tìm lời giải khả thi với độ chính xác cao, giảm đáng kể thời gian tính toán so với mô hình MILP. Ví dụ, với số lượng công việc lớn hơn 6, giải thuật di truyền kết hợp VLAB_Greedy cho kết quả tốt hơn so với duyệt toàn bộ hoán vị.
- **Ứng dụng đồ thị công việc giúp phân hoạch bài toán:** Việc xây dựng đồ thị công việc và tìm các tập con rời nhau giúp giảm không gian tìm kiếm, tăng hiệu quả giải thuật VLAB_Allocation trong việc phân bổ tài nguyên.
- **Đường cong Pareto minh họa các điểm tối ưu thỏa hiệp:** Việc vẽ đường cong Pareto cho hai mục tiêu chính (tổng số máy vật lý sử dụng và chi phí hoạt động) dựa trên dữ liệu thực tế từ 4 học kỳ giúp nhà quản lý lựa chọn phương án phù hợp với điều kiện cụ thể.

### Thảo luận kết quả

Nguyên nhân của tính phức tạp NP-Complete xuất phát từ việc bài toán yêu cầu phân bổ đồng thời nhiều tài nguyên (máy ảo) cho các công việc có thời gian thực thi cố định và ràng buộc liên tục, làm tăng không gian tìm kiếm. So sánh với các nghiên cứu trước đây về lập lịch đa mục tiêu, luận văn đã mở rộng ứng dụng vào môi trường mạng máy tính ảo với đặc thù đồng nhất máy ảo và thời gian cố định, phù hợp với thực tế phòng thí nghiệm ảo tại các trường đại học.

Các mô hình MILP tuy chính xác nhưng không khả thi với quy mô lớn, do đó giải thuật heuristic và meta-heuristic được ưu tiên sử dụng. Kết quả thực nghiệm cho thấy giải thuật di truyền kết hợp với VLAB_Greedy có thể tìm lời giải gần tối ưu trong thời gian hợp lý, phù hợp với yêu cầu vận hành thực tế.

Việc sử dụng đồ thị công việc để phân hoạch bài toán là một điểm sáng trong nghiên cứu, giúp giảm đáng kể độ phức tạp và tăng hiệu quả giải thuật. Đường cong Pareto cung cấp công cụ trực quan cho nhà quản lý trong việc ra quyết định đa mục tiêu, thể hiện rõ sự đánh đổi giữa chi phí và hiệu suất sử dụng tài nguyên.

Dữ liệu kết quả có thể được trình bày qua biểu đồ so sánh hiệu quả các giải thuật theo các chỉ số mục tiêu, bảng thống kê thời gian thực thi và chi phí, cũng như biểu đồ đường cong Pareto minh họa các điểm tối ưu thỏa hiệp.

## Đề xuất và khuyến nghị

- **Áp dụng giải thuật heuristic trong quản lý thực tế:** Khuyến nghị các tổ chức giáo dục và nghiên cứu sử dụng giải thuật VLAB_Greedy kết hợp giải thuật di truyền để tối ưu lập lịch mạng máy tính ảo, nhằm giảm chi phí vận hành và tăng hiệu quả sử dụng tài nguyên trong vòng 6-12 tháng tới.
- **Phát triển phần mềm quản lý tài nguyên dựa trên mô hình MILP và heuristic:** Đề xuất xây dựng hệ thống phần mềm tích hợp các mô hình và giải thuật đã nghiên cứu, hỗ trợ tự động lập lịch và ra quyết định đa mục tiêu, với mục tiêu triển khai thử nghiệm trong 1 năm.
- **Mở rộng nghiên cứu cho các môi trường máy ảo không đồng nhất:** Khuyến khích nghiên cứu tiếp theo tập trung vào các trường hợp máy ảo có cấu hình khác nhau và thời gian thực thi biến đổi, nhằm nâng cao tính ứng dụng trong thực tế.
- **Tăng cường đào tạo và phổ biến kiến thức về lập lịch đa mục tiêu:** Đề xuất tổ chức các khóa đào tạo, hội thảo cho cán bộ quản lý và kỹ thuật viên CNTT về các phương pháp tối ưu đa mục tiêu và giải thuật heuristic, giúp nâng cao năng lực quản lý tài nguyên.
- **Xây dựng cơ sở dữ liệu và thu thập dữ liệu thực tế liên tục:** Khuyến nghị duy trì và cập nhật dữ liệu về công việc và tài nguyên sử dụng để cải tiến mô hình và giải thuật, đảm bảo tính chính xác và hiệu quả trong dài hạn.

## Đối tượng nên tham khảo luận văn

- **Nhà quản lý CNTT và phòng thí nghiệm ảo:** Giúp họ hiểu rõ các phương pháp tối ưu lập lịch tài nguyên, từ đó áp dụng để giảm chi phí vận hành và nâng cao hiệu quả sử dụng máy ảo.
- **Giảng viên và sinh viên ngành Khoa học Máy tính:** Cung cấp kiến thức chuyên sâu về lập lịch đa mục tiêu, mô hình MILP và giải thuật heuristic, phục vụ nghiên cứu và học tập.
- **Nhà nghiên cứu trong lĩnh vực tối ưu hóa và quản lý tài nguyên:** Tham khảo các mô hình toán học và giải thuật mới, đồng thời áp dụng vào các bài toán tương tự trong các lĩnh vực khác.
- **Các tổ chức phát triển phần mềm quản lý tài nguyên:** Hướng dẫn thiết kế và phát triển các công cụ hỗ trợ lập lịch đa mục tiêu cho mạng máy tính ảo, nâng cao tính cạnh tranh và hiệu quả sản phẩm.

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

1. **Bài toán lập lịch mạng máy tính ảo có đặc điểm gì nổi bật?**  
   Bài toán tập trung vào các công việc có thời gian thực thi cố định và máy ảo đồng nhất, yêu cầu phân bổ máy ảo liên tục cho từng công việc, đồng thời tối ưu đa mục tiêu như giảm số máy vật lý sử dụng và chi phí vận hành.

2. **Tại sao bài toán được xác định là NP-Complete?**  
   Do tính chất phức tạp trong việc phân bổ đồng thời nhiều tài nguyên với các ràng buộc liên tục và không ngắt quãng, bài toán suy giảm từ bài toán PARTITION vốn đã được chứng minh là NP-Complete.

3. **Các mô hình MILP có thể giải quyết bài toán quy mô lớn không?**  
   Mô hình MILP chính xác nhưng bị giới hạn về số lượng công việc và thời gian tính toán, không phù hợp với bài toán quy mô lớn trong thực tế.

4. **Giải thuật heuristic nào được đề xuất và ưu điểm của nó?**  
   Giải thuật VLAB_Greedy kết hợp giải thuật di truyền được đề xuất, giúp tìm lời giải khả thi nhanh chóng với độ chính xác cao, phù hợp với quy mô lớn và dữ liệu thực tế.

5. **Làm thế nào để lựa chọn giải pháp tối ưu trong đa mục tiêu?**  
   Sử dụng đường cong Pareto để minh họa các điểm tối ưu thỏa hiệp giữa các mục tiêu, từ đó nhà quản lý có thể lựa chọn giải pháp phù hợp dựa trên điều kiện và ưu tiên cụ thể.

## Kết luận

- Luận văn đã chứng minh bài toán lập lịch đa mục tiêu cho mạng máy tính ảo thuộc lớp NP-Complete, khẳng định tính phức tạp và thách thức trong việc tìm lời giải tối ưu.  
- Đã đề xuất các mô hình MILP và giải thuật heuristic hiệu quả, trong đó giải thuật di truyền kết hợp VLAB_Greedy cho kết quả khả thi và nhanh chóng trên dữ liệu thực tế.  
- Việc sử dụng đồ thị công việc giúp phân hoạch bài toán, giảm không gian tìm kiếm và tăng hiệu quả giải thuật.  
- Đường cong Pareto được xây dựng giúp hỗ trợ ra quyết định đa mục tiêu, cung cấp công cụ trực quan cho nhà quản lý.  
- Đề xuất các hướng phát triển tiếp theo bao gồm mở rộng mô hình cho máy ảo không đồng nhất và phát triển phần mềm quản lý tài nguyên tích hợp các giải thuật đã nghiên cứu.  

**Hành động tiếp theo:** Áp dụng các giải thuật đề xuất vào hệ thống quản lý phòng thí nghiệm ảo thực tế, đồng thời tiếp tục nghiên cứu mở rộng để nâng cao hiệu quả và tính ứng dụng của bài toán.