Schedule vector ops on heterogeneous cores

You are optimizing a “vectored computation” on a heterogeneous (non-SMP) CPU with asymmetric cores.

Hardware model

There are two core types:

• D-cores : can execute division operations only.
• MD-cores : can execute multiplication and division , and may have different per-op costs.

Each core runs one operation at a time; operations assigned to the same core run sequentially.

Workload

You are given a vector of independent operations (order doesn’t matter):

• ops[i] ∈ {'M', 'D'} meaning multiply or divide.

And performance parameters:

• D-core: time_D_on_Dcore
• MD-core: time_D_on_MDcore , time_M_on_MDcore

Task

Design and implement a function that produces a near-optimal schedule to minimize the total completion time (makespan):

def schedule_ops(ops: list[str], num_d: int, num_md: int,
                 tD_d: int, tD_md: int, tM_md: int) -> tuple[int, list[int]]:
    """
    Returns:
      - estimated minimal makespan (time units)
      - an assignment array where assignment[i] is the core index chosen for ops[i]
        (e.g., cores 0..num_d-1 are D-cores, num_d..num_d+num_md-1 are MD-cores)
    """

Requirements

• Must never assign an M op to a D-core.
• Should handle large inputs (e.g., up to 1e5 operations).
• The goal is not perfect optimality (the exact optimum may be expensive); aim for a good heuristic with clear reasoning.

Edge cases

• num_d=0 or num_md=0
• All ops are the same type
• Very imbalanced costs (e.g., MD-core divides much slower than D-core)