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 12 S b1 b3 b6 w1 b5 b2 b4 Luồng Khả năng thông qua FS,bi=0 CS,bi=1 w2 T Fbi,wj=0 Cbi,wj=1 Fw1,T=0 Cw1,T=6 Fw2,T=0 Cw1,T=5 Luồng Khả năng thông qua Hình 3. Mạng 𝐺 = (𝑉, 𝐸) được xây dựng từ tập 6 chùm đến lập lịch và 2 kênh ra; trong đó, đỉnh 𝑏𝑖 tương ứng với chùm đến thừ i, đỉnh 𝑤𝑖 tương tương với kênh thứ 𝑖, và 𝑠, 𝑡 là hai đỉnh ảo được thêm vào cho chức năng đỉnh phát và đỉnh thu Bước 2: Tìm luồng cực đại trên mạng 𝐺. Các bước thực hiện như thể hiện ở Hình 4 a, b, c và kết quả tìm được đường tăng luồng lớn nhất 𝐿 = 𝐿1 ∪ 𝐿2; Bước 3: Lập lịch các chùm trong tập 𝐿 = 𝐿1 ∪ 𝐿2; Giải thuật lập lịch được mô tả như sau: Giải thuật MF_GS (Maximum Flow Group Scheduling) Đầu vào: - Tập 𝑛 chùm cần lập lịch 𝐼 = {𝑏1, 𝑏2, … , 𝑏𝑛 }, trong đó mỗi 𝑏𝑖 = (𝑠𝑖, 𝑒𝑖) với 𝑠𝑖 biểu diễn thời điểm đến và 𝑒𝑖 biểu diễn thời điểm kết thúc của chùm 𝑖 (𝑖 = 1,2, … 𝑛); - Tập 𝑊 kênh dữ liệu ra 𝑊 = {𝑤1, 𝑤2, … , 𝑤𝑚}; Đầu ra: - 𝐼′ (𝐼′ ⊆ 𝐼) là tập các chùm được lập lịch trên các kênh ra sao cho tổng độ dài các chùm trong tập 𝐼’ là lớn nhất. Giải pháp: Bước 1: Xây dựng mạng 𝐺 = (𝑉, 𝐸); 𝐺(𝑉, 𝐸) = 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝐺𝑟𝑎𝑝ℎ(𝐼, 𝑊) Bước 2: Tìm đường tăng luồng từ đỉnh phát 𝑠 đến đỉnh thu 𝑡; 𝐿 = 𝐹𝑀𝐹_𝑂𝑃𝑇(𝐺) Bước 3: Lập lịch các chùm trong tập 𝐿; 𝐼’ = 𝑠𝑐ℎ𝑒𝑑𝑢𝑙𝑒𝐵𝑢𝑟𝑠𝑡𝑠𝑓𝑟𝑜𝑚𝑀𝑊𝐶(𝐿) Bước 4: Kết thúc;