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

Lập lịch công việc là một vấn đề quan trọng trong quản lý sản xuất và khoa học máy tính, nhằm tối ưu hóa việc sử dụng tài nguyên như máy móc và thời gian. Luận văn tập trung nghiên cứu bài toán lập lịch công việc có chu kỳ và không có chu kỳ trong môi trường máy đơn, một bài toán phức tạp với nhiều ứng dụng thực tiễn trong sản xuất công nghiệp, ví dụ như dây chuyền sản xuất đồ gỗ nội thất. Mục tiêu nghiên cứu là tối ưu hóa hai tiêu chí chính: thời gian hoàn thành (makespan) và tổng độ trễ (total tardiness) của các công việc không có chu kỳ, đồng thời đảm bảo các công việc có chu kỳ được thực hiện đúng hạn.

Phạm vi nghiên cứu được thực hiện tại Trường Đại học Bách Khoa, Đại học Quốc gia TP. Hồ Chí Minh trong năm 2013, với dữ liệu mô phỏng và thực nghiệm trên các bộ dữ liệu có kích thước từ 10 đến 10,000 công việc không có chu kỳ, chu kỳ công việc cố định ở mức 100 đơn vị thời gian. Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện hiệu quả lập lịch, giảm thời gian hoàn thành và độ trễ, góp phần nâng cao năng suất và chất lượng quản lý sản xuất.

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

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

- **Lý thuyết lập lịch (Scheduling Theory):** Nghiên cứu các thuật toán và mô hình để phân bổ tài nguyên cho các công việc nhằm tối ưu hóa các tiêu chí như makespan, tổng độ trễ.
- **Bài toán NP-Hard:** Luận văn chứng minh bài toán lập lịch công việc có chu kỳ và không có chu kỳ thuộc lớp NP-Hard, cho thấy tính phức tạp và khó khăn trong việc tìm lời giải tối ưu.
- **Giải thuật heuristic:** Áp dụng các giải thuật heuristic như LPT (Longest Processing Time) và EDF (Earliest Deadline First) cải tiến để giải quyết bài toán trong thời gian hợp lý.
- **Giải thuật di truyền (Genetic Algorithm):** Sử dụng giải thuật tiến hóa để nâng cao chất lượng lời giải, kết hợp với các heuristic nhằm cân bằng giữa hiệu quả và thời gian tính toán.

Các khái niệm chính bao gồm: makespan (thời gian hoàn thành lớn nhất), tổng độ trễ (tổng thời gian trễ so với deadline), công việc có chu kỳ (periodic job), công việc không có chu kỳ (aperiodic job), heuristic, và thuật toán tiến hóa.

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

- **Nguồn dữ liệu:** Dữ liệu mô phỏng gồm các bộ công việc có chu kỳ và không có chu kỳ với các thông số thời gian xử lý và deadline được tạo ngẫu nhiên theo các kịch bản khác nhau.
- **Phương pháp phân tích:** 
  - Chứng minh tính NP-Hard của bài toán qua việc rút gọn từ các bài toán phân hoạch đã biết.
  - Thiết kế và triển khai các giải thuật heuristic cải tiến dựa trên LPT và EDF.
  - Áp dụng giải thuật di truyền kết hợp với các heuristic để cải thiện kết quả.
  - Thực hiện các thí nghiệm trên phần cứng CPU Intel Core i5, 2.53GHz, RAM 3GB để đánh giá hiệu suất.
- **Timeline nghiên cứu:** 
  - Giai đoạn 1 (01/2013 - 06/2013): Nghiên cứu lý thuyết, chứng minh NP-Hard.
  - Giai đoạn 2 (07/2013 - 09/2013): Phát triển giải thuật heuristic và di truyền.
  - Giai đoạn 3 (10/2013 - 11/2013): Thực nghiệm và đánh giá.
  - Giai đoạn 4 (12/2013): Hoàn thiện luận văn và bảo vệ.

## 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 thuộc lớp NP-Hard:** Luận văn chứng minh bài toán tối ưu makespan và tổng độ trễ trong môi trường máy đơn với công việc có chu kỳ và không có chu kỳ là NP-Hard, khẳng định tính khó của bài toán.
- **Hiệu quả của các giải thuật LPT heuristic:** Các giải thuật LPT_HEU1, LPT_HEU2, LPT_HEU3 cải tiến so với LPT cổ điển đã giảm makespan trung bình từ 3% đến 5%, với LPT_HEU3 cho kết quả tốt nhất (makespan giảm khoảng 5% so với LPT truyền thống).
- **Giải thuật di truyền kết hợp LPT heuristic:** Khi chạy trong 30-90 giây với quần thể 5,000-10,000 cá thể, giải thuật di truyền cải thiện makespan thêm từ 2% đến 4% so với các heuristic đơn lẻ, tuy nhiên hiệu quả giảm dần khi số lượng công việc không có chu kỳ tăng.
- **Hiệu quả của giải thuật EDF heuristic:** Giải thuật EDF_HEU giảm tổng độ trễ trung bình khoảng 19% so với EDF cổ điển, đặc biệt hiệu quả khi số lượng công việc không có chu kỳ lớn.
- **Giải thuật di truyền kết hợp EDF heuristic:** Tương tự như LPT, giải thuật di truyền kết hợp với EDF_HEU cải thiện tổng độ trễ thêm từ 5% đến 10% trong thời gian chạy 30-90 giây.

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

Các kết quả thực nghiệm cho thấy việc cải tiến các giải thuật heuristic truyền thống bằng cách áp dụng các chiến lược lựa chọn công việc thích hợp và kết hợp với giải thuật di truyền giúp nâng cao hiệu quả lập lịch đáng kể. Việc giảm makespan và tổng độ trễ góp phần tăng năng suất và giảm chi phí trong sản xuất. So với các nghiên cứu trước đây, luận văn đã mở rộng phạm vi bài toán với sự kết hợp công việc có chu kỳ và không có chu kỳ, đồng thời cung cấp các giải pháp thực tiễn có thể áp dụng trong môi trường máy đơn.

Dữ liệu có thể được trình bày qua các biểu đồ so sánh makespan và tổng độ trễ giữa các giải thuật, cũng như bảng thống kê phần trăm cải thiện theo số lượng công việc không có chu kỳ, giúp minh họa rõ ràng hiệu quả của các phương pháp đề xuất.

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

- **Áp dụng giải thuật LPT_HEU3 và EDF_HEU trong quản lý sản xuất:** Để tối ưu thời gian hoàn thành và giảm độ trễ, các nhà quản lý nên triển khai các giải thuật heuristic cải tiến này trong hệ thống lập lịch sản xuất, đặc biệt trong môi trường máy đơn.
- **Sử dụng giải thuật di truyền kết hợp heuristic:** Đề xuất sử dụng giải thuật di truyền trong các trường hợp cần nâng cao chất lượng lịch biểu, với thời gian chạy tối thiểu 30 giây để đạt hiệu quả tốt, phù hợp cho các hệ thống có khả năng tính toán cao.
- **Phát triển phần mềm hỗ trợ lập lịch:** Khuyến nghị xây dựng phần mềm tích hợp các giải thuật này, cho phép tùy chỉnh tham số như kích thước quần thể, thời gian chạy, để phù hợp với từng môi trường sản xuất cụ thể.
- **Nghiên cứu mở rộng đa mục tiêu:** Khuyến khích nghiên cứu tiếp tục mở rộng bài toán sang tối ưu đa mục tiêu, kết hợp các tiêu chí như độ trễ tối đa, số lượng công việc bị trễ, nhằm đáp ứng đa dạng yêu cầu thực tế.
- **Đào tạo và nâng cao nhận thức:** Tổ chức các khóa đào tạo cho cán bộ kỹ thuật và quản lý về các phương pháp lập lịch hiện đại, giúp áp dụng hiệu quả các giải thuật vào thực tiễn.

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

- **Nhà quản lý sản xuất:** Có thể áp dụng các giải thuật để tối ưu hóa lịch trình sản xuất, giảm chi phí và nâng cao năng suất.
- **Chuyên gia công nghệ thông tin trong lĩnh vực sản xuất:** Sử dụng các thuật toán và mô hình trong phát triển phần mềm quản lý sản xuất.
- **Nghiên cứu sinh và sinh viên ngành Khoa học Máy tính, Quản lý công nghiệp:** Tham khảo để hiểu sâu về bài toán lập lịch phức tạp và các giải pháp heuristic, tiến hóa.
- **Các nhà phát triển giải pháp tự động hóa và tối ưu hóa:** Áp dụng các thuật toán đề xuất để phát triển hệ thống lập lịch thông minh trong các môi trường sản xuất và dịch vụ.

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

1. **Bài toán lập lịch công việc có chu kỳ và không có chu kỳ là gì?**  
Là bài toán phân bổ thời gian thực hiện các công việc định kỳ và không định kỳ trên một máy đơn sao cho tối ưu các tiêu chí như thời gian hoàn thành và tổng độ trễ.

2. **Tại sao bài toán này được xem là NP-Hard?**  
Bởi vì nó có thể được rút gọn từ các bài toán phân hoạch đã được chứng minh là NP-Complete, cho thấy không tồn tại thuật toán đa thức để giải chính xác trong mọi trường hợp.

3. **Giải thuật heuristic LPT và EDF cải tiến có ưu điểm gì?**  
Chúng giúp giảm thời gian hoàn thành và tổng độ trễ so với các giải thuật truyền thống bằng cách lựa chọn công việc phù hợp hơn tại mỗi bước lập lịch.

4. **Giải thuật di truyền được áp dụng như thế nào trong bài toán này?**  
Giải thuật di truyền tiến hóa quần thể các lời giải, kết hợp với các heuristic để tìm kiếm lời giải tốt hơn trong không gian lớn của bài toán.

5. **Thời gian chạy giải thuật di truyền ảnh hưởng thế nào đến kết quả?**  
Thời gian chạy càng lâu giúp tìm ra lời giải tốt hơn nhưng hiệu quả cải thiện giảm dần sau một ngưỡng nhất định, cần cân bằng giữa chất lượng và thời gian tính toán.

## Kết luận

- Luận văn đã chứng minh bài toán lập lịch công việc có chu kỳ và không có chu kỳ trong môi trường máy đơn là NP-Hard, khẳng định tính phức tạp của bài toán.  
- Đã đề xuất và phát triển các giải thuật heuristic cải tiến dựa trên LPT và EDF, cho kết quả thực nghiệm vượt trội so với các giải thuật truyền thống.  
- Áp dụng giải thuật di truyền kết hợp với heuristic giúp nâng cao chất lượng lời giải, cân bằng giữa hiệu quả và thời gian tính toán.  
- Kết quả thực nghiệm với bộ dữ liệu lớn (đến 10,000 công việc) chứng minh tính khả thi và hiệu quả của các giải pháp đề xuất.  
- Đề xuất các hướng nghiên cứu mở rộng đa mục tiêu và phát triển phần mềm hỗ trợ ứng dụng trong thực tế.

**Hành động tiếp theo:** Triển khai các giải thuật vào hệ thống quản lý sản xuất thực tế, đồng thời nghiên cứu mở rộng các bài toán lập lịch phức tạp hơn để đáp ứng nhu cầu đa dạng của ngành công nghiệp hiện đại.