Greedy Makespan算法Python实现问题：测试不通过及索引错误

我用Python实现Greedy Makespan算法时，遇到两个问题：

• 曾出现"列表赋值索引越界"错误，修复后仍测试不通过
• 返回的任务分配结果与报告的完工时间（Makespan）不一致，比如测试1中计算出的完工时间为8，与预期的7不符

算法实现代码 #

greedy_min_make_span(T, m):
  # T is an array of n numbers, m >= 2
  A = [Nil, ... , Nil] # Initialize the assignments to nil (array size n)
  M = [ 0, 0, ...., 0] # initialize the current load of each processor to 0 (array size m)
  for i = 1 to n
    find processor j for which M[j] is the least.
    A[i] = j
    M[j] = M[j] + T[i]
 # Assignment achieves a makespan of max(M[1], .. M[m])
 return A


def greedy_makespan_min(times, m):
    # times is a list of n jobs.
    assert len(times) >= 1
    assert all(elt >= 0 for elt in times)
    assert m >= 2
    n = len(times)
    # please do not reorder the jobs in times or else tests will fail.
    # Return a tuple of two things: 
    #    - Assignment list of n numbers from 0 to m-1
    #    - The makespan of your assignment
    A = n*[0]
    M = m*[0]
    
    i = 1
    for i in range(i, n):
        j = M.index(min(M))
        A[i] = j
        M[j] = M[j] + times[i]
    return (A, M)

工具函数 #

def compute_makespan(times, m, assign):
    times_2 = m*[0]
    
    for i in range(len(times)):
        proc = assign[i]
        time = times[i]
        times_2[proc] = times_2[proc] + time
    return max(times_2)

测试用例 #

def do_test(times, m, expected):
    (a, makespan) = greedy_makespan_min(times,m )
    print('	 Assignment returned: ', a)
    print('	 Claimed makespan: ', makespan)
    assert compute_makespan(times, m, a) == makespan, 'Assignment returned is not consistent with the reported makespan'
    assert makespan == expected, f'Expected makespan should be {expected}, your core returned {makespan}'
    print('Passed')
print('Test 1:')
times = [2, 2, 2, 2, 2, 2, 2, 2, 3] 
m = 3
expected = 7
do_test(times, m, expected)

print('Test 2:')
times = [1]*20 + [5]
m = 5
expected =9
do_test(times, m, expected)

当前测试结果（Test 1） #

• 返回的分配结果：[0, 0, 1, 2, 0, 1, 2, 0, 1]
• 报告的完工时间：[6, 7, 4]
• compute_makespan计算得到的完工时间：8，与预期7不符

错误原因分析与修复 #

1. 循环遗漏第一个任务（索引0） #

原代码循环从i=1开始，跳过了times[0]：第一个任务固定分配给A[0]=0，但未更新对应处理器的负载M[0]，导致负载计算完全错误，分配结果也不符合贪心策略。

2. 返回值错误：应返回max(M)而非M数组 #

原函数返回(A, M)，但测试用例期望第二个返回值是完工时间（即所有处理器的最大负载），这直接导致断言失败。

修复后的代码 #

def greedy_makespan_min(times, m):
    assert len(times) >= 1
    assert all(elt >= 0 for elt in times)
    assert m >= 2
    n = len(times)
    A = n*[0]
    M = m*[0]
    
    # 遍历所有任务，从索引0开始
    for i in range(n):
        j = M.index(min(M))
        A[i] = j
        M[j] += times[i]
    # 返回分配列表和最大负载（完工时间）
    return (A, max(M))

修复效果验证 #

• Test 1：分配结果变为[0,1,2,0,1,2,0,1,2]，各处理器负载为6、6、7，完工时间为7，与预期一致。
• Test 2：20个1分给5个处理器各4个，再将5分给负载最小的处理器，最终负载为9，符合预期。

内容的提问来源于stack exchange，提问作者LeGOATJames23