Luận án Tiến sĩ Khoa học máy tính: Phương pháp lập lịch cá nhân - Trang Hồng Sơn

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA TRANG HỒNG SƠN MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN CHO BÀI TOÁN LẬP LỊCH CÁ NHÂN LUẬN ÁN TIẾN SĨ TP. HỒ CHÍ MINH - NĂM 2022 ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA TRANG HỒNG SƠN 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: 62480101 Phản biện độc lập: PGS.

Nguyễn Tuấn Đăng Phản biện độc lập: PGS. Huỳnh Trung Hiếu Phản biện: PGS. Đỗ Thanh Nghị Phản biện: PGS. Nguyễn Đình Thuân Phản biện: PGS.

Lê Hoàng Thái NGƯỜI HƯỚNG DẪN: 1. Huỳnh Tường Nguyên 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 N P -khó mạnh (strongly N P -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 ii 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 họa để 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 xác định tính N P -đầy đủ 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 Mixed-Integer Linear Programming (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. iii ABSTRACT The objective of personal scheduling aims to assign the jobs into available time windows so that jobs can be handled in the most effective way.

Current personal task management applica- tions such as Microsoft To-Do, Google Tasks, Apple Reminders, Evernote, nTask, Todoist,. only provide a visual environment that helps us to manually organize jobs, and we often struggle because of that. Another issue is that sometimes these jobs require a lot of processing time, so it is difficult to determine and assign these jobs into suitable available time windows. However, unlike machines, personal jobs can often be split into a lot of parts so that they can be flexibly assigned in different available time windows.

It is possible that the jobs are split into sub-jobs with “too small size”, the scheduling result is not as effective in many practical situations as expected since these jobs are too fragmented, and it should be spent more time on resuming the sub-jobs. It is necessary, consequently, to consider the constraint that "the jobs cannot be split less than a certain threshold" for a more efficient result, and this constraint is often not addressed in literature scheduling problems. Therefore, this thesis focuses on methodology and several approaches for solving the personal scheduling problem with two constraints that are the jobs that can be split but not less than a certain threshold and jobs are only assigned in available time windows. With only one of these two constraints, the problem can easily determine the optimal so- lution.

For example, if we consider the constraint of "the jobs that can be split but not less than a certain threshold", then the optimal solution is achieved by splitting all jobs equal to this specified threshold and then assigning these sub-jobs into the time axis. Otherwise, when only considering the constraint of "the jobs can be split and assigned in available time windows", the optimal solution is achieved by splitting all jobs into units of time is 1, and then assigning these sub-jobs into available time windows. However, if both constraints are considered at the same time, this problem becomes a strongly N P -hard problem. This personal scheduling problem can be applied to one person (personal scheduling prob- lem) or multiple people (teamwork scheduling problem).

For each specific scheduling problem, the thesis has presented almost necessary approaches related, including (1) specification of the problem through problem statements, presentation of notations used in the problem, as well as iv giving illustrative examples to be able to understand the problem, ., (2) approaches for solving the problem include determining the N P -completeness of the problem, considering some spe- cial cases, giving some properties in the structure of an optimal solution, proposing the exact method based on Mixed-Integer Linear Programming (MILP) model and approximate methods such as heuristic, metaheuristic, matheuristic, ., and (3) the experimental results to evaluate the proposed methods on both input datasets which are small samples and large samples, from which to propose an effective method for selection with different input dataset types. v LỜI CÁM ƠN Tôi xin chân thành cám ơn trường Đại học Bách Khoa, Đại học Quốc Gia Thành phố Hồ Chí Minh, là đơn vị đào tạo đã tạo mọi điều kiện và môi trường nghiên cứu thuận lợi cho tôi thực hiện luận án và trường Đại học Hoa Sen, là đơn vị công tác đã hỗ trợ tôi rất nhiều trong suốt thời gian qua. Em xin được gởi lời tri ân sâu sắc nhất đến thầy Trần Văn Lăng và thầy Huỳnh Tường Nguyên đã tận tình hướng dẫn, định hướng và động viên em trong suốt thời gian học tập, nghiên cứu và thực hiện luận án này. Em xin gởi lời cám ơn tới các thầy cô trong khoa Khoa học và Kỹ thuật Máy tính, và đặc biệt là thầy Trần Văn Hoài, cô Lê Thanh Vân, thầy Nguyễn Đức Dũng, thầy Nguyễn Hồ Mẫn Rạng, thầy Phạm Hoàng Anh đã có những đóng góp quý báu trong những buổi báo cáo chuyên đề và báo cáo học thuật.

Em cũng xin cám ơn thầy Ameur Soukhal đã cho em có cơ hội được học tập, nghiên cứu tại Laboratoire d’Informatique thuộc trường University François-Rabelais of Tours và trải nghiệm cuộc sống trong bốn tháng tuyệt vời ở thành phố thanh bình Tours, cộng hòa Pháp. Tôi cũng xin gởi lời cám ơn tới bạn Nguyễn Văn Huy là cộng sự cùng nhóm nghiên cứu đã hỗ trợ tôi rất nhiều trong các công trình công bố khoa học của nhóm chúng tôi. Cuối cùng con muốn bày tỏ lòng biết ơn sâu sắc nhất đến ba, mẹ, vợ và hai con trai thân yêu luôn là hậu phương vững chắc nhất, là điểm tựa để mỗi ngày tiếp thêm nghị lực giúp con có thể hoàn thành tốt luận án này. Hồ Chí Minh, ngày tháng năm Trang Hồng Sơn vi MỤC LỤC Danh mục hình ảnh ix Danh mục bảng biểu xii Danh mục từ viết tắt xii Danh mục bảng ký hiệu xv Chương 1 Giới thiệu về đề tài luận án 1 1.1 Giới thiệu chung .2 Động cơ nghiên cứu .3 Mục tiêu, phạm vi và đối tượng nghiên cứu .4 Nội dung công việc của luận án .5 Cấu trúc luận án.

7 Chương 2 Tổng quan về bài toán lập lịch công việc 9 2.1 Tình hình nghiên cứu .2 Giới thiệu bài toán lập lịch công việc .3 Các phương pháp giải quyết .4 Kết chương. 44 Chương 3 Bài toán lập lịch công việc cá nhân cơ bản 45 3.1 Đặc tả bài toán .2 Các phương pháp tiếp cận .4 Kết chương. 90 Chương 4 Một số bài toán lập lịch công việc cá nhân đặc thù 92 4.1 Bài toán ràng buộc setup-time .2 Bài toán ràng buộc deadline .3 Bài toán lập lịch công việc nhóm .4 Kết chương. 142 vii Chương 5 Kết luận 144 5.1 Tóm tắt các công việc đã thực hiện .2 Đánh giá kết quả .3 Các đóng góp chính .4 Hướng phát triển.

148 Danh mục công trình đã công bố 150 Tài liệu tham khảo 151 viii DANH MỤC HÌNH ẢNH 2.1 Các hướng nghiên cứu và các ràng buộc liên quan .2 Sơ đồ Gantt theo hướng máy (a) và hướng công việc (b) [10] .3 Mối quan hệ giữa các hàm mục tiêu .4 Một lịch trình khả thi cho bài toán 1 .5 Dữ liệu đầu vào cho bài toán 2 .6 Một lịch trình khả thi cho bài toán 2 .7 Một lịch trình khả thi với 3 − batches cho bài toán 3 .8 Bài toán quyết định .