Khối song song (AND)
Thời gian lấy max, chi phí lấy tổng.
Khối song song là chỗ thời gian và chi phí tách nhau ra. Nhầm chỗ này là nhầm toàn bộ bài toán.
Công thức
Với k nhánh chạy đồng thời; Tj và Cj là thời gian và chi phí của toàn bộ nhánh thứ j (bản thân nhánh có thể chứa nhiều bước, thậm chí chứa khối song song con).
Vì sao thời gian lấy max còn chi phí lấy tổng
Ba bộ phận cùng làm việc trong 20, 45 và 10 phút. Đồng hồ chỉ chạy một lần cho cả ba — bạn chờ đúng 45 phút. Nhưng bảng lương thì trả cho cả ba, và hoá đơn thì cộng lại. Thời gian là tài nguyên dùng chung được; tiền thì không.
Công thức giả định các nhánh thật sự chạy song song, tức có đủ người/máy làm cùng lúc. Nếu ba nhánh đều do một người làm lần lượt thì đó là chuỗi tuần tự đội lốt song song — hãy vẽ lại thành tuần tự, nếu không thời gian sẽ bị tính thiếu.
Ví dụ
Nhánh 1: Soạn hàng (60 phút / 180.000) → Đóng gói (25 phút / 70.000)
Nhánh 2: Lập chứng từ vận chuyển (20 phút / 50.000)
Thời gian từng nhánh:
Áp dụng (2) và (3):
Nhánh chứng từ có nhanh thêm 15 phút cũng không đổi được gì: nó không nằm trên đường găng.
Cách công cụ tìm ranh giới khối
Khối song song bắt đầu ở cổng rẽ và kết thúc ở cổng gộp — bước gần nhất mà mọi nhánh đều đi qua. Sau khi xác định được ranh giới, cả khối được thu gọn thành một node tổng hợp mang thời gian max và chi phí tổng, rồi phần còn lại của đồ thị được giải như bình thường.
synthetic = f"__par__{block.split}"
graph.time[synthetic] = graph.time[block.split] + max(branch_times) # (2)
graph.cost[synthetic] = graph.cost[block.split] + sum(branch_costs) # (3)
# Mọi luồng đang trỏ vào cổng rẽ nay trỏ vào node tổng hợp
for source, targets in graph.transitions.items():
if block.split in targets:
targets[synthetic] = targets.pop(block.split)
graph.transitions[synthetic] = {block.join: 1.0}Khối lồng khối được xử lý bằng cách thu gọn từ trong ra ngoài — xem Ghép các khối lồng nhau.