วางแผนการบูรณาการ

ตัวอย่างที่ 1 เรียงลำดับงานและหาเส้นทางวิกฤต

tasks = {   # งาน: (ชั่วโมง, งานที่ต้องเสร็จก่อน)
    "power distribution": (3, []),
    "flight controller": (2, ["power distribution"]),
    "RC receiver": (1, ["flight controller"]),
    "GNSS + compass": (2, ["flight controller"]),
    "telemetry radio": (1, ["flight controller"]),
    "ESCs + motors": (3, ["power distribution", "flight controller"]),
    "companion computer": (3, ["power distribution", "flight controller"]),
    "camera trigger": (2, ["companion computer", "flight controller"]),
}

indeg = {t: len(p) for t, (_, p) in tasks.items()}
order, ready = [], [t for t, d in indeg.items() if d == 0]
while ready:
    t = ready.pop(0)
    order.append(t)
    for u, (_, pred) in tasks.items():
        if t in pred:
            indeg[u] -= 1
            if indeg[u] == 0:
                ready.append(u)
assert len(order) == len(tasks), "dependency cycle"

finish, prev = {}, {}
for t in order:
    d, pred = tasks[t]
    start = max((finish[p] for p in pred), default=0)
    prev[t] = max(pred, key=lambda p: finish[p]) if pred else None
    finish[t] = start + d
end = max(finish, key=finish.get)
path, t = [], end
while t:
    path.append(t)
    t = prev[t]
print("order:", " -> ".join(order))
print(f"total effort {sum(d for d, _ in tasks.values())} h, earliest finish with parallel work {finish[end]} h")
print("critical path:", " -> ".join(reversed(path)))

order: power distribution -> flight controller -> RC receiver -> GNSS + compass -> telemetry radio -> ESCs + motors -> companion computer -> camera trigger
total effort 17 h, earliest finish with parallel work 10 h
critical path: power distribution -> flight controller -> companion computer -> camera trigger

ถ้ามีคนเดียวต้องใช้เวลารวมทั้งหมด แต่ถ้ามีสองถึงสามคน งานบนเส้นทางวิกฤตคือสิ่งที่ต้องเฝ้าดู งานอื่นเลื่อนได้โดยไม่ทำให้ทั้งโครงงานช้า และโปรแกรมจะแจ้งทันทีถ้ากราฟวนกลับ ซึ่งแปลว่าลำดับที่เขียนไว้ขัดแย้งกันเอง

ตัวอย่างที่ 2 ตรวจการจัดสรรพอร์ตและ I2C

PORTS = {"SERIAL1": {"name": "TELEM1", "flow": True}, "SERIAL2": {"name": "TELEM2", "flow": True},
         "SERIAL3": {"name": "GPS1", "flow": False}, "SERIAL5": {"name": "TELEM3", "flow": True}}
PROTO = {2: "MAVLink2", 5: "GPS"}
plan = [   # อุปกรณ์, พอร์ต, SERIALn_PROTOCOL, SERIALn_BAUD, ต้องการ flow control
    ("telemetry radio", "SERIAL1", 2, 57, False),
    ("companion computer", "SERIAL3", 2, 921, True),
    ("GNSS", "SERIAL3", 5, 115, False),
    ("ground display radio", "SERIAL5", 2, 57, False),
]
i2c = {"external bus": [("GNSS module compass", 0x0E), ("add-on compass", 0x0E), ("barometer", 0x77)]}

used, issues = {}, []
for dev, port, proto, baud, need_flow in plan:
    if port in used:
        issues.append(f"{port} used by both {used[port]} and {dev}")
    used[port] = dev
    if need_flow and not PORTS[port]["flow"]:
        issues.append(f"{dev} needs flow control but {port} ({PORTS[port]['name']}) has none")
    print(f"{port:<8}{PORTS[port]['name']:<7} {dev:<21} {PROTO[proto]:<9} baud code {baud}")
for bus, devs in i2c.items():
    seen = {}
    for dev, addr in devs:
        if addr in seen:
            issues.append(f"I2C {bus}: {dev} and {seen[addr]} both at 0x{addr:02X}")
        seen[addr] = dev
print("issues:", *issues, sep="\n  ")
free = [p for p in PORTS if p not in used]
print("free ports:", free)

SERIAL1 TELEM1  telemetry radio       MAVLink2  baud code 57
SERIAL3 GPS1    companion computer    MAVLink2  baud code 921
SERIAL3 GPS1    GNSS                  GPS       baud code 115
SERIAL5 TELEM3  ground display radio  MAVLink2  baud code 57
issues:
  companion computer needs flow control but SERIAL3 (GPS1) has none
  SERIAL3 used by both companion computer and GNSS
  I2C external bus: add-on compass and GNSS module compass both at 0x0E
free ports: ['SERIAL2']

แผนนี้มีสามปัญหาที่พบได้บ่อยจริง: ต่อคอมพิวเตอร์บนลำไว้ที่พอร์ต GPS ซึ่งชนกับ GNSS และไม่มี flow control และใส่เข็มทิศรุ่นเดียวกันสองตัวบนบัสเดียวกัน วิธีแก้คือย้ายคอมพิวเตอร์บนลำไป SERIAL2 ซึ่งยังว่างและมี flow control และเลือกเข็มทิศเสริมที่ตั้งที่อยู่ต่างกันได้ หรือต่อไว้บนบัสอื่น