Một số phương pháp tiếp cận cho bài toán lập lịch cá nhân - NCS. Trang Hồng Sơn

Đề tài nghiên cứu: Một số phương pháp tiếp cận cho bài toán lập lịch cá nhân
Chuyên ngành: Khoa Học Máy Tính
Mã số chuyên ngành: 62.48.01.01
Họ và tên NCS: Trang Hồng Sơn
Tập thể hướng dẫn: PGS. TS. Trần Văn Lăng, PGS. TS. Huỳnh Tường Nguyên
Cơ sở đào tạo: Trường Đại học Bách Khoa – ĐHQG TP. HCM
1. Tóm tắt luận án 
Mục tiêu của việc lập lịch công việc cá nhân là mong muốn sắp xếp các công việc cần xử lý vào những khung thời gian làm việc trống có sẵn của bản thân sao cho hiệu quả nhất. Các ứng dụng quản lý công việc cá nhân hiện tại như Microsoft To-Do, Google Tasks, Apple Reminders, Evernote, nTask, Todoist, ... chỉ cung cấp môi trường trực quan giúp mọi người tự sắp xếp các công việc của mình một cách thủ công, và chúng ta thường rất vất vả vì điều đó. Một khó khăn nữa là đôi khi các công việc này đòi hỏi thời gian xử lý rất lớn nên khó để có thể tìm kiếm và sắp xếp các công việc này vào các khung thời gian làm việc phù hợp. Tuy nhiên khác với máy móc là các công việc của con người thường có thể chia nhỏ thành nhiều phần để có thể linh động sắp xếp chúng vào các khung thời gian làm việc khác nhau. Có một thực tế là nếu các công việc được chia quá nhỏ thì việc xử lý lại không có hiệu quả như mong đợi vì các công việc này đã bị phân mảnh quá nhiều và chúng ta phải tốn thời gian cho việc khởi động lại của từng công việc nhỏ. Vì vậy cần phải xem xét đến ràng buộc “các công việc không được chia nhỏ hơn một ngưỡng xác định” để việc xử lý công việc được hiệu quả hơn, và ràng buộc này lại thường không được đề cập đến trong các bài toán lập lịch hiện nay. Cho nên luận án này tập trung giải quyết bài toán lập lịch công việc cá nhân với hai ràng buộc đó là các công việc có thể chia nhỏ nhưng không được nhỏ hơn một ngưỡng xác định và các công việc chỉ được sắp xếp vào những khung thời gian làm việc.
Với chỉ một trong hai ràng buộc này thì bài toán có thể xác định được lời giải tối ưu một cách dễ dàng. Chẳng hạn nếu chỉ xem xét ràng buộc là “các công việc có thể chia nhỏ nhưng không được nhỏ hơn một ngưỡng xác định” thì lời giải tối ưu đạt được bằng cách chia nhỏ hết tất cả các công việc bằng với ngưỡng chặn dưới xác định này, sau đó lần lượt sắp xếp các công việc đã chia nhỏ này lên trục thời gian. Ngược lại nếu chỉ xem xét ràng buộc là “các công việc có thể chia nhỏ và được sắp xếp vào những khung thời gian làm việc” thì lời giải tối ưu đạt được bằng cách chia nhỏ hết tất cả các công việc với đơn vị thời gian là 1, sau đó lần lượt sắp xếp các công việc đã chia nhỏ này vào những khung thời gian làm việc. Tuy nhiên nếu xem xét cả hai ràng buộc cùng một lúc thì bài toán này trở thành bài toán thuộc lớp strongly NP-hard.
Bài toán lập lịch công việc cá nhân này có thể áp dụng trên một người (personal scheduling problem) hoặc trên một nhóm nhiều người (teamwork scheduling problem). Đối với từng bài toán lập lịch cụ thể, luận án đã trình bày các giải pháp và hướng tiếp cận để giải quyết bài toán bao gồm: (1) đặc tả bài toán thông qua phát biểu mô tả bài toán, trình bày các ký hiệu sử dụng trong bài toán, cũng như đưa ra ví dụ minh hoạ để có thể hiểu rõ bài toán, ..., (2) các phương pháp tiếp cận để giải quyết bài toán bao gồm phân tích độ khó của bài toán, xem xét một số trường hợp đặc biệt, đưa ra một số tính chất trong cấu trúc của một lời giải tối ưu, đề xuất phương pháp chính xác dựa trên mô hình MILP và các phương pháp xấp xỉ như heuristic, metaheuristic, matheuristic, ..., và (3) kết quả thực nghiệm để đánh giá các phương pháp đề xuất trên cả hai bộ dữ liệu đầu vào có kích thước nhỏ và lớn, để từ đó đề xuất lựa chọn phương pháp hiệu quả đối với từng loại dữ liệu đầu vào khác nhau.
2. Những kết quả mới của luận án 
Những đóng góp chính của luận án bao gồm:
C1. Xem xét và giải quyết những vấn đề tồn đọng của bài toán lập lịch công việc cá nhân (bài toán PSP) từ các nghiên cứu trước đây.
C2. Mở rộng nghiên cứu giải quyết các bài toán lập lịch công việc cá nhân đặc thù có một số ràng buộc thường được sử dụng trong thực tế như mỗi công việc đều có thời gian chuẩn bị khác nhau (bài toán PSP+setup-time), mỗi công việc đều có thời điểm bắt buộc phải hoàn thành khác nhau (bài toán PSP+deadline), và bài toán lập lịch công việc cá nhân cho một nhóm nhiều người có các khung thời gian làm việc khác nhau (bài toán TWSP).
C3. Đề xuất sơ đồ tổng quát 7 bước tiếp cận để giải quyết lớp các bài toán lập lịch công việc cá nhân bao gồm: (1) phân tích độ khó của bài toán, (2) xem xét một số trường hợp đặc biệt, (3) đưa ra một số tính chất của lời giải tối ưu, (4) xác định miền nghiệm của bài toán, (5) xây dựng mô hình MILP, (6) sử dụng phương pháp chính xác với MILP solver để xác định lời giải tối ưu cho bài toán, (7) sử dụng các phương pháp xấp xỉ dạng heuristic/metaheuristic/matheuristic để xác định lời giải khả thi cho bài toán.
C4. Trên cơ sở xem xét bài toán lập lịch công việc cá nhân như là một bài toán có thời gian là tài nguyên đặc biệt cần được cấp phát cho các công việc, đề xuất một số heuristics đặc thù thừa kế các giải thuật cổ điển, và một số metaheuristics thường dùng trong công nghiệp, qua đó xác định lời giải khả thi có chất lượng tốt trong giới hạn thời gian chấp nhận được (dưới 10 phút).
C5. Đề xuất hướng tiếp cận matheuristics bằng cách kết hợp giải thuật (meta)heuristic cùng với phương pháp chính xác sử dụng MILP solver nhằm xác định lời giải khả thi có chất lượng tốt nhất có thể.
3. Các ứng dụng/ khả năng ứng dụng trong thực tiễn hay những vấn đề còn bỏ ngỏ cần tiếp tục nghiên cứu
Từ các nghiên cứu và đóng góp được trình bày trong luận án này cho bài toán lập lịch công việc cá nhân, một số vấn đề có thể được xem xét và nghiên cứu trong tương lai, cụ thể là:
• Nghiên cứu các đặc tính khác của bài toán để áp dụng các phương pháp mô hình hóa khác, đặc biệt là có thể áp dụng các kỹ thuật trong việc tìm kiếm nghiệm tối ưu trong không gian tìm kiếm.
• Nghiên cứu áp dụng các kỹ thuật nâng cao xác định cận dưới LB như lagrangian relaxation, column generation, ... với mong muốn đề xuất cận dưới LB tốt hơn nữa.
• Thử nghiệm cài đặt thêm các metaheuristics thuộc nhóm tối ưu hoá bầy đàn như particle swarm optimization, ant colonies optimization, bee colony, ...
• Nghiên cứu áp dụng các giải thuật khác như nhóm giải thuật xấp xỉ cho bài toán lập lịch thuộc lớp strongly NP-hard (polynomial-time approximation scheme) có thể đo đạc khoảng cách với lời giải tối ưu bằng lý thuyết như PTAS, EPTAS, FPTAS, QPTAS, ..., hoặc nhóm các giải thuật ứng dụng xác suất ngẫu nhiên (randomized algorithm) như Las Vegas algorithm, Monte Carlo algorithm, ...
• Thay đổi chiến lược chia tập các jobs ban đầu của giải thuật matheuristic E4SSJ, hoặc xem xét có thể kết hợp với phương pháp machine learning (gọi là learnheuristic), ... để có thể xác định lời giải tốt hơn nữa.
• Khảo sát thêm việc phân loại dữ liệu đầu vào nhằm gợi ý giải thuật hiệu quả cụ thể đối với từng nhóm dữ liệu có những đặc điểm, đặc trưng khác nhau.