Ghép các khối lồng nhau
Thu gọn từ trong ra ngoài rồi giải một lần.
Sáu công thức trước xử lý từng cấu trúc riêng lẻ. Trang này nói cách chúng được ghép lại để tính một quy trình thật, nơi song song lồng trong loại trừ, loại trừ lồng trong vòng lặp.
Thuật toán hai bước
- Thu gọn mọi khối song song, từ trong ra ngoài. Mỗi khối biến thành một node tổng hợp mang max thời gian và ∑ chi phí của các nhánh. Sau bước này đồ thị chỉ còn rẽ nhánh loại trừ và vòng lặp.
- Giải chuỗi Markov trên đồ thị còn lại bằng công thức (5), thu được số lần ghé thăm kỳ vọng của mọi bước.
Công thức tổng
Vẻ đẹp của cách làm này: sau khi có vector n, thời gian và chi phí chỉ là hai phép nhân vô hướng trên cùng một vector. Mọi cấu trúc phức tạp đã được nuốt gọn vào nv.
Vì sao phải thu gọn từ trong ra ngoài
Một khối song song có thể chứa khối song song khác. Muốn biết thời gian của nhánh ngoài, phải biết thời gian của khối trong trước. Công cụ xếp hạng các khối theo độ sâu lồng nhau và xử lý khối sâu nhất trước.
Khối ngoài có hai nhánh. Nhánh trên lại là một khối song song con gồm X (30 phút) và Y (15 phút), sau đó tới Z (5 phút). Nhánh dưới là W (12 phút).
Bước 1 — thu gọn khối trong:
Bước 2 — nhánh trên giờ là chuỗi tuần tự 30 + 5 = 35; áp dụng (2) cho khối ngoài:
Chi phí thì cộng tất cả bốn bước, không bỏ bước nào.
Ví dụ đầy đủ: quy trình P2P
Quy trình mẫu P2P — Mua hàng đến thanh toán có đủ: chuỗi tuần tự, cổng loại trừ theo hạn mức, khối song song chờ hàng và hoá đơn, và vòng rework đối chiếu chứng từ.
| Thành phần | Công thức | Đóng góp |
|---|---|---|
| Lập phiếu (PR) | (1) | 30,00 |
| Duyệt: 75%×45 + 25%×180 | (4) | 78,75 |
| Tạo PO + gửi NCC | (1) | 35,00 |
| max(nhận hàng 120, hoá đơn 20) | (2) | 120,00 |
| Đối chiếu × 1,2821 | (5) | 44,87 |
| Xử lý sai lệch × 0,2821 | (5) | 25,38 |
| Thanh toán | (1) | 40,00 |
| E[T] | 374,00 phút | |
Đúng bằng con số công cụ hiển thị: 6 giờ 14 phút. Bạn có thể mở quy trình mẫu này và tự đối chiếu từng dòng.
Ở bước thu gọn, công cụ dùng max(E[nhánh]) thay cho E[max(nhánh)]. Với nhánh có thời lượng cố định, hai giá trị bằng nhau. Với nhánh chứa yếu tố ngẫu nhiên, max(E[·]) ≤ E[max(·)] nên kết quả giải tích là cận dưới. Đó chính là lý do có thêm tab Mô phỏng.