工厂双工序机器人生产n件产品的最小时间算法求解

问题描述 #

工厂生产设备需完成两道工序：工序A由A类机器人执行，工序B由B类机器人执行，所有机器人的执行时间可能不同。需求：编写算法计算生产n件产品所需的最短时间。

已知条件：

• A类机器人的执行时间列表
• B类机器人的执行时间列表
• 需生产的产品数量

示例 #

输入：

6      # 需生产的设备数量
3      # A类机器人数量
1 3 2  # A类机器人的执行时间列表
2      # B类机器人数量
3 2    # B类机器人的执行时间列表

输出：9

尝试的代码及问题 #

本人尝试编写了三种Python代码，但准确率均较低：

1. 第一种代码（准确率35%）：

import math

n = int(input())
An = int(input())
A = [int(num) for num in input().split()]
A.sort()
Bn = int(input())
B = [int(num) for num in input().split()]
B.sort()


a = 0
for i in A:
    a += 1/i
a = n/a


b = 0
for i in B:
    b += 1/i
b = n/b

c = min(min(A), min(B))

ans = math.ceil(max(a, b)) + c
print(ans)

问题：仅通过平均产能估算时间，完全忽略了产品必须先完成工序A再进行工序B的调度逻辑，结果不符合实际生产流程。

2. 第二种采用二分查找的代码（准确率20%）：

import math
def num(m, A, B):
    a = 0
    for i in A:
        a += m // i

    b = 0
    for i in B:
        b += m // i
    return min(a, b)

n = int(input())
An = int(input())
A = [int(num) for num in input().split()]
Bn = int(input())
B = [int(num) for num in input().split()]




l = 0
r = max((max(A)*n), (max(B)*n)) + min(min(A),min(B))




while l < r:
    m = (r + l) // 2
    k = num(m, A, B)                    #m // x + m // y
    if k < n - 1:
        l = m + 1
    else:
        r = m

print(l+max(A))

问题：判断逻辑错误，仅计算A、B两类机器人在时间m内的总产能最小值，未考虑每件产品必须先完成A工序再进入B工序的顺序要求，无法正确反映实际生产的时间限制。

3. 第三种代码（准确率10%）：

A = []
A.sort()
B = []
B.sort()
n = 

a = []
time = 0
while len(a) < n:
    time += 1
    for i in range(len(A)):
        if time%A[i]==0:
            a.append((time, i))
            if len(a) >= n:
                break


b = []
time = A[0]
while len(b) < n:
    time += 1
    for i in range(len(B)):
        if time%B[i]==0:
            b.append((time, i))
            if len(b) >= n:
                break
b = b[::-1]
#print(b)
c = []
for i in range(len(a)):
    c.append(a[i][0]+b[i][0])

print(max(c))

问题：代码存在语法错误（n =未赋值），且错误地将A工序完成的第i件产品与B工序完成的第i件产品强制配对，忽略了机器人的并行调度能力，导致计算结果严重偏离实际。

正确算法实现方案 #

核心思路 #

1. 生成A工序完成时间列表：使用最小堆模拟A类机器人的并行工作，收集前n件产品完成A工序的时间（按完成顺序升序排列）。
2. 二分查找最短时间：通过二分查找尝试不同的总时间T，判断在该时间内能否将所有完成A工序的产品通过B类机器人处理完毕。判断时使用贪心算法+最小堆，将每个产品分配给当前最早可用的B类机器人，确保所有产品的B工序完成时间不超过T。

代码实现 #

import heapq

def generate_a_times(n, A):
    # 生成前n件产品完成A工序的时间列表（升序）
    heap = []
    for a in A:
        heapq.heappush(heap, (a, a))  # (当前完成时间, 机器人执行时间)
    a_times = []
    for _ in range(n):
        finish, a = heapq.heappop(heap)
        a_times.append(finish)
        heapq.heappush(heap, (finish + a, a))
    return a_times

def is_possible(T, a_times, B):
    # 判断在时间T内能否完成所有n件产品的B工序
    heap = []
    for b in B:
        heapq.heappush(heap, (0, b))  # (机器人下一次可用时间, 机器人执行时间)
    for time in a_times:
        available, b = heapq.heappop(heap)
        finish = max(time, available) + b
        if finish > T:
            return False
        heapq.heappush(heap, (finish, b))
    return True

def main():
    n = int(input())
    An = int(input())
    A = list(map(int, input().split()))
    Bn = int(input())
    B = list(map(int, input().split()))
    
    a_times = generate_a_times(n, A)
    
    # 设置二分查找的上下界
    left = 0
    right = a_times[-1] + max(B) * n  # 上界：最后一件A完成时间 + n件最长B工序时间
    
    answer = right
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid, a_times, B):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    print(answer)

if __name__ == "__main__":
    main()

代码说明 #

• generate_a_times函数：利用最小堆实时获取A类机器人中最早完成任务的时间，生成前n件产品完成A工序的时间序列，确保序列按升序排列。
• is_possible函数：通过最小堆维护B类机器人的可用时间，贪心分配每个产品给最早可用的B机器人，计算每件产品的B工序完成时间，判断是否全部不超过T。
• 二分查找：通过不断缩小范围，找到满足条件的最小T，即为生产n件产品的最短时间。

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