MỞ ĐẦU Chương 2 Co sở lý thuyết Luận văn tôt nghiệp Trang 5/67 Nguyễn Quyết Thắng — 10070940 2.1 Bài toán lập lịch 2.1 Tổng quan Lập lịch theo nghĩa rộng là một quá trình hỗ trợ quyết định cách cấp phát tài nguyên để xử lý một tập các tác vụ/công việc sao cho thỏa mãn một số ràng buộc cho sẵn, đồng thời tối ưu hóa mục tiêu dé ra. Nó đóng một vai trò quan trọng trong việc giúp đỡ con người lập kế hoạch sử dụng nguồn tài nguyên hợp lý và có hiệu quả nhất. Và do vậy, nó thường được áp dụng trong các hệ thống quản lý sản xuất công nghiệp và dịch vụ. Từ những năm 1950, các bài toán về hỗ trợ ra quyết định đã được đào sâu và liên tục cải tiến song hành cùng với ngành khoa học quản lý tại các nước phát triển trên thế giới do nhu cầu thực tiễn của nó ngày càng tăng.
Các bài toán nghiên cứu học thuật ngày càng được mở rộng và sát với thực tế. Trong số những bài toán tối ưu hóa tổ hợp ứng dụng thực tiễn vào thời điểm này, đa phần thường liên quan đến bài toán lập lịch trong thế giới công nghiệp và dùng để quản lý/ tối ưu việc sử dụng các nguồn tài nguyên rất hạn chế. Tuy nhiên, các kết quả đạt được cũng được áp dụng rất nhiều trong các lĩnh vực khác như về giáo dục, viễn thông, giao thông vận tải, hàng không, sinh tin học, tài chính,. Nhờ vào sự tiễn bộ và hỗ trợ của máy tính, các bài toán và thuật toán trong lập lịch ngày càng đa dạng, gần gũi với thực tế, và thực sự thu hút các nhà nghiên cứu quan tâm đến giải quyết những bài toán có tính thách thức cao.
Sự phát triển trong các nghiên cứu và ứng dụng liên quan đến lập lịch có thể được phân loại sơ bộ như sau: e Dựa theo định dang dữ liệu đầu vào: — Dữ liệu được biết trước, và không thay đối — Dữ liệu được biết trước và thay đổi phụ thuộc vào thời gian thực hiện — Dữ liệu không được biết trước, chỉ được biết đến khi gần đến thời điểm thực thi (online scheduling) e Dựa theo mục tiêu tối ưu cần đạt được: — Tối ưu đơn mục tiêu: đã được giải quyết và cải tiến thông qua nhiều phương pháp khác nhau [14], — Tối ưu đa mục tiêu: Hoogeveen và T kindt [21] đã tổng kết các bài toán nghiên cứu và ứng dụng liên quan; đặc biệt trong số các bài toán tối ưu đa mục tiêu, nhóm bài toán "lập lịch vừa đúng hạn” (Just-In-Time Scheduling) đã thu hút các nhà nghiên cứu nhiều nhất trong những năm cuối thế kỷ 20 và cả cho đến hiện nay, — Tối ưu đa mục tiêu theo hướng cân bằng các lợi ích cục bộ: Agnetis dé xuất vào năm 1999, các bài toán liên quan sau đó được đào sâu trong và đã thu hút nhiều nghiên cứu gia khác. CƠ SỞ LÝ THUYẾT Luận văn tôt nghiệp Trang 6/67 Nguyễn Quyết Thắng — 10070940 — Tối ưu đa mục tiêu theo hướng tính toán cân bang đan xen: mục đích là để xác định một kế hoạch để giúp các nhà sản xuất ra quyết định một cách tối ưu hóa chung cho toàn bộ các công việc và đồng thời thỏa mãn một số tiêu chuẩn quy định chỉ cho một tập hợp con của công việc (ví dụ như là theo yêu cầu của một vài khách hàng đặc biệt) [13]. e Dựa theo các thuật toán và các phương pháp tiếp cận, chúng có thể được phân nhỏ thành một số loại như sau: — Do độ khó của bài toán: Brucker [14] xây dựng một bảng tổng kết độ khó của các bài toán lập lịch đã được nghiên cứu; ngoài ra một vài công trình nổi bật khác cũng có thể tham khảo thêm, như là các công trình của Timkovsky về việc so sánh độ khó giữa các nhóm bài toán lập lịch, hoặc có thể tham khảo bài toán lập lịch đầu tiên được chứng minh bởi Johnson, hoặc một vài kết quả khác [1], - Xác định cận biên P 4 NP (maximal polynomial solvable): một số nghiên cứu quan tâm đến cận giới hạn trong các bài toán lập lịch [14] [12] — Phương pháp tính chính xác: quy hoạch nguyên [11], quy hoạch động [19], phương pháp tính cận và nhánh [20] [5], — Các giải thuật gần đúng dựa trên phương pháp tính chính xác: thuật giải gần đúng cho quy hoạch phi tuyến tinh (linear programming); xây dựng chuỗi giải thuật gần đúng có đảm bảo chắc chắn được chất lượng của giải pháp tìm thấy (approximation scheme [6]); thuật giải gần đúng dựa trên cây quyết định (branch and cut, branch and price, search tree based approaches [5], recovering beam search [11], relaxation, hiệu chỉnh cấu hình của solver giải hiệu qua các bài toán quy hoạch tuyến tính,. — Các thuật toán tiễn hóa: thuật giải di truyền [16], tìm kiếm lân cận, meta-heuristic [22], thuật giải lai (hybird) [11],.
e Dựa theo các công cụ lập lịch ứng dụng: từ những năm 1957, biểu đồ GANTT, biểu đồ PERT, CPM, một số công cụ tối ưu đã được thương mại hóa hoặc tích hợp vào các sản phẩm thương mại. Và cho đến hiện nay, có lẽ hầu hết các thuật toán cơ bản đều được nhúng vào trong các dòng sản phẩm hỗ trợ quản lý doanh nghiệp (ERP — enterprise resource planning) 2.2 Bài toán lập lich Gia sử có m máy M;(j = 1,.,m) phải thực hiện n công việc J;(¡ = 1,. Một ldp lich là việc cắp phát một hoặc nhiều khoảng thời gian trên một hoặc nhiêu máy cho mỗi công việc. Các lập lịch có thể duoc biểu diễn bằng giản đồ Gantt như ở Hình 2.
Giản đồ Gantt có thể biểu diễn theo cách nhìn ở góc độ từng máy (Hình 2.1(a)) hay 6 góc độ từng công việc (Hình 2. CƠ SỞ LÝ THUYẾT Luận văn tôt nghiệp Trang 7/67 Nguyễn Quyết Thắng — 10070940 (a) M,| ‘1 J3 J4| J2 J4 M› J3 J2 J4 Ji J3 > Ji Mì M› J MỊ M J2 M› Mì M› J4 My |M, M, > Hình 2.1: Giản đồ Gantt nhìn dưới góc độ máy và góc độ công việc. Bài toán lập lịch là bài toán di tim một lập lịch thỏa mãn một số ràng buộc và mục tiêu nào đó. Các ràng buộc có thể là ràng buộc về các thuộc tính của công việc hay là ràng buộc về môi trường làm việc và khả năng của máy.
Mục tiêu cần thỏa mãn ví dụ như là cực tiểu thời gian hoàn thành các công việc, công việc hoàn thành không được quá sớm cũng không qua trễ, cực tiểu thời gian trễ so với thời gian hoàn thành dự kiến. hoặc là sự kết hợp của nhiều mục tiêu khác nhau. Một số khái niệm liên quan về lập lịch: e Mot lập lịch khả di: là một lập lịch sao cho: — Không có 2 khoảng thời gian nào trùng lắp nhau trên cùng một máy. — Không có 2 khoảng thời gian nào trùng lắp được cấp phát cho cùng 1 công việc.
— Thỏa mãn một số đặc điểm của van dé đặc trưng. e Mot lập lịch tối ưu là một lập lịch cực tiểu một mục tiêu tối ưu mong muốn. Một sô khái niệm liên quan dén công việc e Một công việc J; gồm có nj; tác vụ Ó¡,. Nếu nj = 1, công việc J; chỉ có một tác vụ duy nhat.
Ta dong nhat O;; với J;. e Tương ứng với mỗi tác vụ O;; có một thời gian xử lý cần thiết là p;;. Tương tự, nêu nj = | ta đồng nhất Pij VỚI Pj. e Tương ứng với mỗi tác vụ O;; có một tập các may ,; C {M1,., Mm} mà có khả năng xử lý được tác vụ đó.
— Nếu như tất cả yj; đều là các tập hợp chỉ có một phan tử (một máy), ta có trường hợp các máy chuyên dụng (dedicated machine), nghĩa là mỗi tác vụ chỉ có thể được thực hiện trên một máy chuyên dụng đó mà thôi. CƠ SỞ LÝ THUYẾT Luận văn tôt nghiệp Trang 8/67 Nguyễn Quyết Thắng — 10070940 — Nếu như tất cả ;; đều là các tập hợp tất cả các máy {M1,.,Mm}, ta có trường hợp các máy song song (parallel), nghĩa là bất kỳ tác vụ nào cũng có thể được thực thi trên bất kỳ máy nào. — Trường hợp tổng quát trong sản xuất, các máy có thể được trang bị với nhiều công cụ khác nhau. Điều này có nghĩa là một tác vụ chỉ có thể được thực hiện được trên máy nào mà được trang bị công cụ thích hợp.
Ở đây, ta gọi là trường hợp các may đa chức nang (multi-purpose machine - MPM). — Trong toàn bộ chu kỳ xử lý, tác vụ O;; trong thực tế cũng có thể sử dung cùng lúc tat cả các máy trong tập py; j. Các bài toán dạng này gọi là các bài toán lập lịch tác vụ đa xử lý (multiprocessor task scheduling problems). e release date r;: đây là thời điểm mà sau đó tác vu đầu tiên của công việc J; được phép thực thi.
e Ham chi phí ƒ;(z): Hàm số đo mức chi phí của việc hoàn thành công việc J; tại thời điểm ứ. e Thời gian hoàn thành dự kiến (due date) d;: là thời điểm mà công việc tương ứng J; được mong đợi hoàn thành. Ở đây ta phân biệt due date với deadline là thời điểm mà công việc nhất định phải hoàn thành trước nó, không thể thay đổi được. e Trọng số w;: La phần đóng góp của một biến số.
Ví dụ w;C; nghĩa là C; được xem xét tính toán với trọng sô wj. Để đặc tả cũng như phân loại một bài toán lập lịch, ta sử dụng ký hiệu gồm 3 trường: ol Bly VỚI: e a: đặc tả môi trường máy e B: đặc tả các đặc trưng của công việc. e Y: đặc tả mục tiêu tối ưu. Ví dụ một số bài toán lập lịch: Pl|prec: pi = l|Cmax l|r; pmtn|Lnax J3 |P¡j = 1Gnax CHƯƠNG 2.
CƠ SỞ LY THUYET Luận văn tôt nghiệp Trang 9/67 Nguyễn Quyết Thắng — 10070940 2.3 Môi trường may Môi trường máy trong bài toán lập lịch œ được đặc tả bởi một chuỗi 2 thông số: O = QQ) Các giá tri có thể có của œ là 0,P,O,R, PMPM,OMPM,G,X,O,J,F. Ký hiệu ø có ý nghĩa là rỗng. e Nếu ơi c {2,P,Q,R,PMPM,OQMPM} , mỗi công việc J; chỉ bao gồm một tác vụ duy nhất. Nếu @ = 2, mỗi công việc phải được thực thi trên một máy chuyên dụng cho nó.
Nếu a, € {P,Q,R} , chúng ta có các máy song song, nghĩa là mỗi công việc có thể được xử lý trên bất kỳ máy nào trong tập M1,. Nếu ơi = P, ta có các máy đồng nhất song song. Xét thời gian xử lý p;; của công việc J; trên máy M;, vì các máy là đồng nhất song song ta có p;; = p; cho tat cả các máy.