MỞ ĐẦU 2 có thể có để hoàn thành sản phẩm. Để đáp ứng nhu cầu thị trường thì nhà máy trên phải tạo ra được một số sản phẩm trong một thời gian nhất định nào đó (deadline). Do đó, việc tạo ra sản phẩm hàng ngày sẽ mang tính chất chu kì và do vậy công việc tạo ra sản phẩm này được gọi là công việc có chu kỳ. Ví dụ: sau 15h làm việc thì phải tạo ra một sản phẩm.
Giả sử tại thời điểm t nào đó, có một người khách đến đặt hàng. Đơn hàng bao gồm một số công việc, trong đó các công việc có thể có deadline giống hoặc khác nhau. Các công việc này vì vậy được gọi là các công việc không có chu kỳ. Yêu cầu đặt ra của bài toán: cần lập lịch làm việc để hoàn thành được sản phẩm đáp ứng nhu cầu thị trường (có chu kỳ) đồng thời hoàn thành yêu cầu khách hàng (không có chu kỳ).
Luận văn này sẽ tập trung giải quyết bài toán trên. Các kết quả cần đạt được bao gồm lập mô hình toán học cho bài toán và dé xuất các giải thuật heuristic để giải bài toán. Mục tiêu đặt ra bao gdm 2 mục tiêu riêng rẽ. Thứ nhất là tối thiểu hóa Cax(N) - thời gian hoàn thành hay là makespan của tập công việc không có chu kỳ.
Tương ứng với lý thuyết lập lịch bài toán này được ký hiệu là 1|periodic job(c,p), aperiodic job set(N)|Cmax(N). Mục tiêu thứ 2 là tối thiểu hóa 17; - tổng độ trễ của các công việc trong tập công việc không có chu kỳ. Tương ứng với lý thuyết lập lịch bài toán này được ký hiệu là 1|periodic job(c, p), aperiodic job set(N)|}` Tj.3 Cau trúc luận văn Phần còn lại của luận văn này được tổ chức như sau: e Chương 2 trình bày lý thuyết về lập lịch và trong trường hợp của luận văn là lập lịch trong môi trường máy đơn. e Chương 3 chứng minh bài toán là NP-Hard cho việc lập lịch mục tiêu thời gian hoàn thành cũng như là NP-Hard cho việc lập lịch mục tiêu tổng độ trễ.
e Chương 4 trình bày các giải thuật heuristic để giải quyết bài toán. e Chương 5 trình bày các kết quả thực nghiệm của việc ứng dụng các giải thuật heuristic. e Cuối cùng là phần kết luận, các hướng phát triển của luận văn, phụ lục và danh mục tài liệu tham khảo. Chương 2 Lý thuyết 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 đề ra.
Nó đóng một vai trò quan trong 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ụ. Trong ngành khoa hoc máy tính, lập lịch là phương pháp mà các thread (tuyến trình), process (quá trình) hay luông đữ liệu (data flow) được truy cập vào tài nguyên hệ thống (ví dụ như thời gian xử lý, băng thông liên lạc). Điều này thường được thực hiện dé cân bang tải hệ thống một cách có hiệu quả hay để đạt được một mục tiêu chất lượng hay dịch vụ.
Sự cần thiết cho một thuật toán lập lịch xuất phát từ yêu cầu cho hầu hết các hệ thống hiện nay để thực hiện đa nhiệm (thực hiện nhiều hơn một quá trình tại một thời điểm — multitasking) và ghép kênh (truyền nhiều luông đông thời — multiplexing) (Theo wikipedia).2 Định nghĩa bài toán lập lịch Giả sử rằng với m máy M;(j = 1,.,m) phải xử lý n công việc J;(¡ = 1,. Một lịch biểu cho mỗi công việc là một sự phân công công việc đó trong một hay nhiều khoảng thời gian trên một hoặc nhiều máy. Các lịch biểu có thể được biểu diễn bằng biểu đồ Gantt như trong hình 2. Biểu đồ Gantt có thể được định hướng theo máy (hình 2.
la) hay định hướng theo công việc (hình 2. LÝ THUYẾT LẬP LỊCH 4 Wi J4 J3 J2 J M2 J3 J2 J1 Ms J2 dJ1 (a) t ‹h Ma M2 M1 + Ma M2 Mạ Bs) M2 M1 oq M1 0) ‘ Hình 2. e Mot lịch biểu được gọi là khả thi néu không có máy nào được phân công xử lý cùng một lúc nhiều công việc. Ngoài ra lịch biểu còn phải thỏa mãn một số ràng buộc của bài toán.
e Mot lịch biểu được gọi là tối ưu nếu nó khả thi và đạt cực tiểu theo một tiểu chuẩn tối ưu đã cho.3 Dw liệu của một công việc Công việc J; trải qua n; công đoạn Oj, Ở;a, Ở¿a, - - - , Oin, tương ứng với mỗi công đoạn O; là một thời gian xử lý p;;. Nếu công việc J; chỉ gồm có một công đoạn (n; = 1) thì chúng ta đồng nhất J; với O;; và thời gian thực hiện là p;. Thời điểm mà kể từ đó công đoạn đầu tiên của công việc J; sẵn sàng để được xử lý gọi là thoi điển sẵn sàng (release date) của công việc J; và được ký hiệu là 7;. Thời điểm quy định một công việc phải hoàn tất được gọi là thoi điểm đến han (due date) của một công việc ký hiệu dj.
Tương ứng với mỗi công đoạn O;; là một tập máy g;; C {M1,Mo,.,Mm}, trong đó công đoạn Oj; có thể được xử lý trên bất kỳ máy nào trong ¿;;. Thông thường ¿;; chỉ có một phan tử hoặc bằng với tập tất cả các máy. Khi ¿;; có một phan tử ta có các máy chuyên dụng (dedicated machines). khi yi; bằng với tập tat cả các máy thi ta có các mdy song song (parallel machines).
Dé làm mềm dẻo van đề lập lịch trong sản xuất thông thường các máy được trang bị những dụng cụ khác nhau, điều này có nghĩa là một công đoạn có thể được xử lý trên bất kỳ máy nào miễn là máy đó được trang bị những dụng cụ thích hợp. Những bài toán lập lịch thuộc dang này gọi la bài toán lập lịch với các may da năng (multipurpose machines). Ngoài ra cũng có trường hợp tat cả các máy trong tập uj; được sử dụng đồng thời trong suốt quá trình xử lý của công đoạn. Những bài toán lập lịch thuộc dạng này được gọi là bai toán lập lịch với những công việc da xu lý (multiprocessor task scheduling problems).
LÝ THUYẾT LẬP LỊCH 5 Dé đo lường mức độ hoàn thành của một công việc J; tại thời điểm ¢ ta dùng một hàm tri giá ƒ#(7). Trong đó thời điểm tới hạn đ;, trọng số w; có thể được dùng trong định nghĩa của hàm ƒ;(?). Trường hợp tổng quát, các giá tri pj, pij, r¡, di, wi có thể được giả sử là những giá trị nguyên. Các lớp bài toán lập lịch được xác định bởi ba trường phân loại là œ|B|y.
Trong đó œ xác định môi trường máy, B xác định tinh chat của các công việc và y dùng để chỉ định tiêu chuẩn tối ưu.4 Các tính chất đặc trưng của công việc Các tinh chất đặc trưng của công việc được quy định bởi trường B chứa đựng nhiều nhất là 6 thành phan B¡, Ba. Bs và Bo. e Bị chỉ định có hay không khả năng tach một công việc (preemption-job splitting). Việc tách một công việc hay một công đoạn có nghĩa là việc xử lý có thể bị gián đoạn và sẽ tiếp tục vào một thời điểm khác và có thể được xử lý trên một máy khác.
Một công việc hay một công đoạn có thể được chia cắt nhiều lần. Nếu việc tách công việc được cho phép ta ký hiệu By = pmtn. Ngược lại thì B không xuất hiện trong trường ÿ. e › quy định quan hệ thứ tự thực hiện trước sau giữa những công việc.
Quan hệ thứ tự này có thé được biểu diễn bằng một đồ thị có hướng không chu trình G = (V,A), trong đó V = {1,.,n} tương ứng với tập những công việc và (i,k) € A nếu và chỉ néu J; phải được hoàn thành trước khi J, bat đầu được xử lý. Nếu bài toán có ràng buộc quan hệ trước sau giữa những công việc ta đặt Ba = prec. e 63 — rị chi định thoi điểm sẵn sàng dé bắt đầu (release date) thực hiện công việc. Nếu r;—0thì Ba không xuất hiện trong trường ÿ.
e ÿ¿ chỉ định thời gian xử lý công việc hay công đoạn. Nếu By là biểu thức p; = 1(pij = 1) thì mỗi công việc (công đoạn) có thời gian xử lý một đơn vị thời gian. Đôi khi trường Ba chưa thêm một số tính chất với một sự giải thích rõ rang, ví dụ như p; € {1,2}. e Bs — d;¡ chỉ định thoi điểm đến hạn (due date) cho từng công việc J;, nghĩa là công việc J; không thể hoàn thành trễ hơn thời điểm d;.
e Đôi khi trong một vài ứng dụng lập lịch, các công việc phải được lập thành từng 16 (batch). Mỗi lô là tập của những công việc được kết hợp xử lý trên cùng một máy. Thời gian hoàn thành của lô được định nghĩa là thời gian hoàn thành của tất cả các công việc trong lô đó. Mỗi lô có thể có từ 1 đến n công việc.
Tén tại một khoảng thời gian thiết lập (setup time) cho từng 16 để lô đó sẵn sàng được xử lý. Chúng ta giả sử rằng thời gian khởi động cho tất cả các lô là bang nhau. Bài todn chia lô (batching problem) là dạng bài toán nhóm những công việc vào trong các lô và sau đó tiễn hành xếp lịch cho các lô đó. Có 2 dạng bài toán chia lô là p-batching và s-batching.
Đối với bài toán p-batching thời gian xử lý của lô bằng với thời gian xử lý lớn nhất của các công việc trong lô đó, còn với bài toán s-batching thời gian xử lý của lô bằng tổng thời gian xử lý của từng công việc trong lô đó. Bg = p — batching hoặc Bg = s — batching để chỉ định dang bài toán này, ngược lại thì Be không xuất hiện trong trường ÿ. LÝ THUYẾT LẬP LỊCH 6 2.5 Môi trường may Môi trường máy là một trong các yếu tố quan trọng của bài toán lập lịch. Môi trường máy được đặc trưng bằng một chuỗi 2 tham số œ = œ¡0¿.
Trong đó œ¡ có thể nhận một trong các giá trị o, P, Q, R, PMPM, QMPM, G, X, O, J, F để chỉ định dang bài toán va œ¿ để xác định số máy. e Nếu a = o thi mỗi công việc phải được xử lý trên một máy chuyên dụng. e Nếu ơi c {P,Q,R}, ta có các máy là song song, nghĩa là mỗi công việc có thể được xử lý trên một trong số các máy M1, M›,ẢM3,.