MỘT HƯỚNG TIẾP CẬN LẬP LỊCH NHÓM TỐI ƯU TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 9 một kênh có thời gian đến không chồng lấp nhau. Hoặc được lập lịch trên hai kênh khác nhau. Từ đồ thị được xây dựng, Giải thuật sẽ tìm tập các clique cực đại bắt đầu từ các cạnh trong đồ thị 𝐺 và thực hiện tính tổng trọng số. Các đỉnh trong clique cực đại có tổng trọng số lớn nhất trong tập các clique được tìm thấy chính là tập các chùm lập lịch trên các kênh ra có tổng chiều dài các chùm lập lịch là lớn nhất. Các tác giả trong [4] đã đề xuất giải thuật GreedyOPT với cách tiếp cận là xây dựng vấn đề lập lịch nhóm các chùm đến dưới dạng vấn đề lập lịch công việc trên các máy đồng nhất. Để làm được điều này GreedyOPT gỡ các chùm đã được lập lịch trước đó trên các kênh ra và sử dụng giải thuật lập lịch LAUC để thực hiện lập lịch lại chúng cùng với các chùm mới đến trong khe thời gian 𝜏. Nếu một chùm không thể lập lịch được, giải thuật sẽ cố gắng thay chùm đó bằng một trong những chùm đã được lập lịch mà có thời điểm kết thúc sau cùng nhất. Mục đích của việc làm này nhằm tìm kiếm cơ hội lập lịch cho chùm đang xem xét, cũng như các chùm đến sau (có thời điểm đến lớn hơn) nhằm giảm lượng dữ liệu (số gói tin chứa trong chùm) bị loại bỏ. Theo một hướng tiếp cận khác các tác giả trong [5] đề xuất giải thuật nhóm BATCHOPT lấy ý tưởng từ giải thuật lập lịch công việc [4], tức là xây dựng vấn đề lập lịch nhóm các chùm đến thành vấn đề lập lịch công việc trên k máy đồng nhất cho cả các chùm đã được lập lịch trước đó nhưng chưa được gửi đi. Giải thuật BATCHOPT tiến hành xây dựng một đồ thị

khoảng vô hướng tương ứng các chùm mới đến và các chùm đã được lập lịch trước đó bị gỡ ra được xây dựng. Tiếp đó giải thuật tìm tất cả các clique cực đại của đồ thị và sắp xếp chúng theo thời điểm đến tăng dần. Một đồ thị luồng sau đó được tạo ra dựa trên các clique cực đại đã được sắp xếp, trong đó mỗi cung được đặc trưng bởi các tham số: chi phí, khả năng thông qua và trọng số (độ dài chùm). Cuối cùng BATCHOPT tìm luồng có chi phí tối thiểu rồi loại bỏ các cung của nó. Trong [13] các tác giả đã để xuất giải thuật lập lịch nhóm tối ưu OPT-GS với ý tưởng của giải thuật là mô hình hoá bài toán lập lịch nhóm trên đa kênh sang bài toán tìm tập các đường đi trên đơn đồ thị khoảng có hướng có trọng số. Để thực hiện việc này, Đầu tiên từ tập các chùm đến yêu cầu lập lịch, giải thuật sẽ xây dựng đồ thị tương ứng. Ở đây mỗi chùm 𝑏𝑖 tương ứng mỗi đỉnh 𝑖 và trọng số của đỉnh chính là độ dài của chùm đó. Có một cung đi từ đỉnh 𝑖 đến đỉnh 𝑗 khi và chỉ khi: thời điểm kết thúc của chùm 𝑏𝑖 nhỏ hơn chùm 𝑏𝑗, và thời gian đến của hai chùm này không chồng lấp nhau. Và không tồn tại một chùm khác xen giữa 2 chùm đó mà thời gian đến của 3 chùm ko chồng lấp nhau. Từ cách xây dựng đồ thị như vậy một đường đi từ một đỉnh không có bậc vào đến 1 đỉnh ko có bậc ra, thì tập các đỉnh trên đường đi chính là tập các chùm có thể lập lịch cùng nhau trên kênh ra đó. Từ tập các đường đi được tìm thấy. Giải thuật thực hiện hợp m được đi trên m kênh và tính tổng trọng số các đỉnh. Kết quả của giải thuật, lập lịch cho các chùm tương ứng các đỉnh trong tập có tổng trọng số lớn nhất.