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 14 𝑓 là một luồng trên mạng 𝐺 thì luồng cực đại 𝑓∗ cần tìm được định nghĩa bởi công thức bên dưới. 𝑓∗ = 𝑓 𝑎𝑟𝑔𝑚𝑎𝑥 ∑ ∑ (𝑒𝑖 − 𝑠𝑖)𝑓𝑖,𝑗 𝑏𝑖∈𝐿𝑗 𝑚 𝑗=1 (1) trong đó 𝐿𝑗 = {𝑏𝑖 |𝑓𝑖,𝑗 = 1} là tập các đỉnh 𝑏𝑖 có luồng đến 𝑤𝑗 bằng 1; chú ý, 𝐿𝑗 có thể bằng rỗng trong quá trình tìm luồng cực đại. Hình 5. Mạng G cùng với các giá trị luồng và khả năng thông qua ban đầu của nó Chi tiết giải thuật như sau: Function 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝐺𝑟𝑎𝑝ℎ(𝐼, 𝑊); Input: - Tập 𝑛 chùm cần lập lịch 𝐼 = {𝑏1, 𝑏2, … , 𝑏𝑛}, trong đó mỗi 𝑏𝑖 = (𝑠𝑖, 𝑒𝑖) với 𝑠𝑖 và 𝑒𝑖 lần lượt là thời điểm đến và kết thúc của chùm i; - Tập 𝑊 kênh dữ liệu ra 𝑊 = {𝑤1, 𝑤2, … , 𝑤𝑚}; Output: 𝑮 = (𝑽, 𝑬) Process Khởi tạo đỉnh phát 𝑆 và đỉnh thu 𝑇 ; 𝐸 = ∅; foreach 𝑏𝑖 ∈ 𝐼 do Tạo đỉnh 𝑏𝑖, 𝑉 = 𝑉 ∪ {𝑏𝑖}; Tạo cung từ đỉnh 𝑆 đến đỉnh 𝑏𝑖, 𝐸 = 𝐸 ∪ {(𝑆, 𝑏𝑖)}, 𝑐𝑆,𝑖 = 1; deg−(𝑤𝑗 ) = 0; foreach 𝑤𝑗 ∈ 𝑊 do Tạo đỉnh 𝑤𝑗 , 𝑉 = 𝑉 ∪ {𝑤𝑗 };