CHƯƠNG 1 GIỚI THIỆU VỀ ĐỀ TÀI LUẬN ÁN Chương này giới thiệu chung về đề tài luận án, cũng như là động cơ, mục tiêu, phạm vi và đối tượng nghiên cứu. Ngoài ra những nội dung công việc trong luận án cũng được liệt kê, trình bày sơ lược ở cuối chương này, qua đó định hướng người đọc nắm được luồng thực hiện các tiếp cận thách thức được đặt ra trong bài toán nghiên cứu.1 Giới thiệu chung Trong thế giới thực cũng như hoạt động thường ngày có rất nhiều vấn đề liên quan đến việc lập lịch (scheduling). Chẳng hạn, lập lịch để lập thời khóa biểu cho một trường học, lập lịch để thu xếp cũng như lập kế hoạch cho một tổ chức, lập lịch để khai thác tài nguyên của một hệ thống sao cho tối ưu,. Khi đề cập đến hoạt động của chiếc máy tính hay một mạng các máy tính, lập lịch là một phương pháp tiếp cận để phân phối nguồn tài nguyên máy tính như băng thông, bộ nhớ, bộ xử lý, cho các quy trình, luồng dữ liệu và ứng dụng khác nhau sao cho tối ưu theo một hoặc nhiều tiêu chí nào đó, ví dụ như là lập lịch để cân bằng tải trên hệ thống và đảm bảo phân phối tài nguyên đồng đều, từ đó đưa ra mức độ ưu tiên theo các quy tắc đã đặt ra.
Những vấn đề này bảo đảm một hệ thống máy tính có thể phục vụ tất cả các yêu cầu và đạt được chất lượng dịch vụ nhất định. Trong quản lý dự án, lập lịch là lập một danh sách các hoạt động, cũng như các công việc được giao và các mốc thời gian quan trọng trong một dự án. Khi đó một lịch trình bao gồm ngày bắt đầu và ngày kết thúc, thời lượng và các nguồn lực được chỉ định cho mỗi hoạt động. Việc lập lịch dự án hiệu quả là một yếu tố quan trọng của việc quản lý thời gian.
Việc định nghĩa một bài toán lập lịch (mà kết quả đầu tiên về lập lịch có thể tham khảo trong công bố của Johnson1 ) đã được nhiều tác giả phát biểu khác nhau trong nhiều nghiên cứu mà có thể liệt kê một số phát biểu điển hình như lập lịch là liên quan đến việc phân bổ các nguồn lực khan hiếm cho các hoạt động với mục tiêu tối ưu hóa một hoặc nhiều độ đo hiệu quả sử dụng tài nguyên [1], lập lịch là một quá trình ra quyết định liên quan đến việc phân bổ nguồn lực giới hạn hoặc máy móc theo thời gian để thực hiện một tập hợp các công việc hoặc nhiệm vụ, trong 1 S. Johnson, “Optimal two- and three-stage production schedules with setup times included,” Naval Re- search Logistics Quarterly, vol. 1 đó một hoặc một số mục tiêu phải được tối ưu hóa và đáp ứng một tập hợp các ràng buộc nào đó [2], lập lịch là một quá trình ra quyết định được sử dụng thường xuyên trong nhiều ngành công nghiệp sản xuất và dịch vụ, nó liên quan đến việc phân bổ nguồn lực cho các nhiệm vụ trong khoảng thời gian nhất định, với mục đích là tối ưu hóa một hoặc nhiều mục tiêu nào đó [3], lập lịch là bài toán phân bổ nguồn lực theo thời gian để thực hiện một tập hợp các nhiệm vụ, trong đó các vấn đề tính toán và sản xuất là quan trọng nhất [4]. Đối với các bài toán lập lịch hiện nay, các nhà nghiên cứu thường xem xét các bài toán lập lịch cho một loại tài nguyên cụ thể như lập lịch cấp phát các tác vụ (task allocation scheduling) là bài toán cấp phát các tác vụ cho một tập các máy thực thi với chi phí tổng thể tối thiểu, bài toán này thường được áp dụng để thiết kế các hệ thống máy tính phân tán và cả trong sản xuất tự động [5], lập lịch ràng buộc nguồn lực (resource constrained scheduling) là bài toán bao gồm các hoạt động phải được lên kế hoạch tùy thuộc vào sự ưu tiên và các ràng buộc về nguồn lực sao cho hiệu quả theo các tiêu chí xác định [6], lập lịch công việc (job scheduling) là bài toán xác định thứ tự xử lý của các công việc trên các máy trong các khoảng thời gian nhất định với mỗi máy chỉ có thể xử lý một công việc tại một thời điểm [7],.
Trong đó, lập lịch công việc là một hướng có rất nhiều nghiên cứu và đóng vai trò quan trọng trong việc giúp mọi người lập kế hoạch sử dụng tất cả các nguồn lực của họ một cách hiệu quả và tối ưu nhất có thể, do đó nó được sử dụng trong nhiều ngành sản xuất và dịch vụ. Lập lịch công việc cũng rất cần thiết trong cuộc sống cá nhân (personal job scheduling), không chỉ giúp các cá nhân xử lý nhiều công việc phức tạp mà còn giảm căng thẳng. Trong thời đại công nghệ hiện nay, mọi người phải đối phó với hàng trăm công việc, email và nhiều vấn đề phức tạp cần giải quyết từng ngày. Theo David Allen [8], một chuyên gia về cải thiện năng suất công việc, hầu hết chúng ta luôn có khoảng 50 đến 150 nhiệm vụ lớn nhỏ cần phải được xử lý ở bất cứ thời điểm nào.
Bên cạnh đó, mỗi công việc sẽ có nhiều thuộc tính và ràng buộc khác nhau như là thời điểm bắt đầu, thời hạn phải hoàn thành, thời gian xử lý thích hợp để thực hiện công việc hiệu quả hơn,. Và để thành công, chúng ta cần có khả năng quyết định nhanh chóng những công việc quan trọng nhất cần làm là gì và những công việc nào ít quan trọng hơn có thể được dời lại phía sau. Thời gian là tài nguyên quý giá nhất mà mọi người không thể mua, và thật không may chúng ta thường lãng phí hoặc sử dụng nó một cách không hiệu quả. Một vài số liệu thống kê thú vị liên quan tới thời gian mà chúng ta đang trải qua trong cuộc sống hằng ngày như sau: • Thời gian làm việc: nhân viên toàn thời gian làm việc trung bình 8.5 giờ mỗi ngày trong 2 tuần và 5.53 giờ mỗi ngày vào một ngày cuối tuần (theo thống kê của BLS2 ); nhân viên có trung bình 56 lần gián đoạn công việc và tốn trung bình 2 giờ mỗi ngày để phục hồi sau khi mất tập trung (theo thống kê của Atlassian3 ).
• Thời gian giải trí: xem tivi là hình thức giải trí được yêu thích nhất tốn 2.81 giờ mỗi ngày; giao tiếp với bạn bè tốn trung bình 0.64 giờ mỗi ngày; thể dục thể thao tốn trung bình 0.31 giờ mỗi ngày; những người từ 15 đến 24 tuổi chơi game tốn khoảng 1 giờ mỗi ngày (theo thống kê của BLS). • Thời gian sử dụng điện thoại: trung bình là 3 giờ 15 phút mỗi ngày và hầu hết mọi người kiểm tra điện thoại trung bình 58 lần mỗi ngày (theo thống kê của RescueTime4 ). Kỹ năng quản lý thời gian và công việc tốt sẽ giúp con người làm việc hiệu quả hơn, quản lý được những rủi ro có thể xảy ra và có thể cân bằng được giữa công việc cá nhân và những công việc khác. Theo Kukreja5 thì việc tạo ra một lịch trình trước khi bắt đầu một ngày là một trong 10 cách thiết thực để cải thiện kỹ năng quản lý thời gian, và theo Kukhnavets6 thì chia nhỏ công việc cũng là một trong những gợi ý để cải thiện kỹ năng quản lý công việc.
Để tạo ra một lịch trình chúng ta có thể sử dụng 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,. Mặc dù các ứng dụng này ngày càng trở nên thông minh hơn và đều có những đặc điểm thế mạnh riêng nhưng nó 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, mà không thể tự động chia nhỏ các công việc để tối ưu hóa việc thực thi các công việc này trong các khung thời gian trống có sẵn của từng người. Một vấn đề nữa là với rất nhiều công việc và những ràng buộc phải được thỏa mãn, đặc biệt hơn cả là vì sự thay đổi liên tục trong cuộc sống thực, mọi người sẽ rất vất vả và tốn thời gian khi liên tục phải tự sắp xếp lại các công việc đã được sắp xếp của mình mỗi khi các công việc 2 BLS, 24% of employed persons do some work at home on days they work in 2019, 2020. Available: https://www.release/pdf/atus.
3 Atlassian, You waste a lot of time at work, 2020. Available: https://www.com/time-wasting- at-work-infographic (visited on 07/21/2020). 4 RescueTime, Screen time stats 2019: Here’s how much you use your phone during the workday, 2019. Available: https://blog.com/screen-time-stats-2018 (visited on 03/21/2019).
Kukreja, 10 practical ways to improve time management skills, 2020. Available: https://www.org/articles/productivity/10-ways-improve-your-time-management-skills. Kukhnavets, What are the benefits of a personal task manager? 2019. Available: https://hygger.io/ blog/benefits-personal-task-manager (visited on 01/22/2019).
3 bị thay đổi. Do đó bài toán lập lịch công việc cá nhân có thể tự động phân chia các công việc nhỏ hơn trong những khung thời gian làm việc là rất quan trọng để áp dụng cho các ứng dụng quản lý công việc cá nhân. Đối với một tổ chức hoặc một nhóm người cùng làm việc, vấn đề lập lịch cũng được đặt ra sao cho hoạt động phối hợp trong nhóm và mỗi thành viên được hiệu quả. Việc lập lịch riêng cho mỗi thành viên hay còn gọi là lập lịch cá nhân là một bài toán quan trọng và cơ bản cho việc lập lịch cho cả tập thể nhóm (teamwork job scheduling).
Trong phạm vi nghiên cứu, luận án tập trung chủ yếu vào bài toán lập lịch công việc của một cá nhân, xem xét các phương pháp tiếp cận như là những nghiên cứu cơ bản để có thể làm nền tảng cho các bài toán lập lịch công việc đặc thù khác và cho bài toán lập lịch công việc trong một tập thể hoặc một nhóm người có quan hệ xã hội.2 Động cơ nghiên cứu Đối với việc lập lịch công việc cá nhân, bài toán sẽ có hai đặc điểm chính. Thứ nhất, mỗi người đều có những khung thời gian làm việc (available-windows) khác nhau, có thể linh động sắp xếp những công việc của họ vào đấy. Thứ hai, mỗi người có thể muốn chia một công việc lớn thành nhiều công việc nhỏ để dễ dàng sắp xếp vào các khung làm việc của mình, nhưng nếu các công việc được chia quá nhỏ thì lại không thể hiệu quả khi không đủ thời gian để xử lý, vì vậy cần phải có thêm ràng buộc là các công việc không được chia nhỏ hơn một ngưỡng xác định (bounded-splitting) để 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 (xem trình bày tại Bảng 1.