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

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 8 Channel with Void Filling) được gọi để tìm kênh khả dụng lập lịch lần lượt cho các chùm theo thứ tự này; nếu việc lập lịch không thành công, chùm tranh chấp bị loại bỏ. Tương tự như SSF, giải thuật LIF sắp xếp thứ tự không tăng về độ dài của các chùm đến. Sau đó giải thuật LAUC-VF được gọi tìm kênh khả dụng để lập lịch lần lượt cho các chùm đã được sắp xếp theo thứ tự trên; nếu việc lập lịch không thành công, chùm tranh chấp bị loại bỏ. Trong giải thuật SLV, đầu tiên một đồ thị khoảng G được xây dựng và các chùm đến được sắp xếp theo thứ tự không tăng của bậc các đỉnh tương ứng. Dựa trên kết quả sau khi sắp xếp, các chùm tương ứng với đỉnh trong đồ thị được phân phối lên kênh khả dụng đầu tiên trong số 𝑚 kênh ra bằng cách sử dụng giải thuật LAUC-VF. Tiến trình lập lịch được lặp đi lặp lại đối với mỗi chùm lên từng kênh ra hoặc bị loại bỏ (nếu không lập lịch được) cho đến khi không còn đỉnh nào trong danh sách. Tương tự SLV, giải thuật MCF cũng dựa trên đồ thị khoảng được xây dựng với 𝑚 kênh để lập lịch cho 𝑛 chùm đến. Ý tưởng của MCF là: đầu tiên sẽ tìm tất cả các clique cực đại có kích thước lớn hơn m và tập chứa các clique này là 𝐶 = {𝐶1, 𝐶2, . . . , 𝐶𝑚}; với mỗi clique cực đại có thời điểm đến sớm nhất 𝐶𝑖 ∈ 𝐶, MCF lần lượt loại bỏ các đỉnh có thời điểm kết thúc nhỏ nhất cho đến khi kích thước của 𝐶𝑖 bằng hoặc nhỏ hơn 𝑚. Việc loại bỏ các đỉnh rõ ràng sẽ làm thay đổi đến các clique cực đại khác trong C, nên giải thuật MCF lặp lại việc xác định tập C và thực hiện loại bỏ một số

đỉnh của clique cực đại có kích thước lớn hơn m. Giải thuật MCF sẽ dừng khi không còn clique cực đại nào có kích thước lớn hơn 𝑚. Kết quả của giải thuật MCF là danh sách các đỉnh 𝐿 = {𝑏1, 𝑏2, . . . , 𝑏𝑖} mà bậc của chúng không lớn hơn 𝑚 − 1, được nối với danh sách các chùm bị loại bỏ trong các clique có kích thước lớn hơn 𝑚, ký hiệu là 𝑆 = {𝑏𝑖 +1, 𝑏𝑖 +2, . . . , 𝑏𝑛}. Kết quả là 𝐼0 = 𝐿 ∪ 𝑆. Các chùm tương ứng với các đỉnh trong 𝐼0 sau đó lần lượt được phân phối lên m kênh ra theo giải thuật LAUC-VF hoặc bị loại bỏ nếu không lập lịch được cho đến khi không còn đỉnh nào trong danh sách. Một hướng tiếp cận khác của các tác giả trong [10] đã đề xuất giải thuật lập lịch nhóm LGS-MC đây là một mở rộng từ giải thuật lập lịch nhóm trên đơn kênh LGS của nhóm tác giả trong [11] với ý tưởng sắp xếp các kênh theo giá trị LAUT (Latest Available Unscheduled Time), nhằm mục đích với kênh có giá trị LAUT nhỏ nhất là kênh có thể lập lịch được các chùm có tổng độ dài là lớn nhất. Trên mỗi kênh thực hiện gọi giải thuật LGS để lập lịch cho tập các chùm trên kênh đó. Giải thuật dừng lại khi số chùm được lập lịch hết, hoặc lập lịch hết trên m kênh. Đối với giải thuật LGS-MC có độ phức tạp giải thuật thấp (𝑂(𝑛 × 𝑙𝑜𝑔2(𝑛)).), tuy nhiên chỉ tối ưu lập lịch trên từng kênh một nên không có kết quả tối ưu toàn cục. Các tác giả trong [17] đã đề xuất giải thuật MWC-GS. Ý tưởng giải thuật MWC-GS 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 clique cực đại có tổng trọng số

lớn nhất trên đơn đồ thị khoảng có trọng số. Bước đầu tiên của giải thuật là xây dựng đơn đồ thị khoảng có trọng số tương ứng khả năng lập lịch của các chùm trên các kênh. Trong đó mỗi đỉnh tương ứng một chùm lập lịch được trên một kênh thứ 𝑘 và trọng số trên các đỉnh chiều dài của chùm đó; Có một cạnh nối giữa hai đỉnh, khi và chỉ khi: Hai chùm được lập lịch trên cùng