graph - 在 2 台并行机器上调度任务
问题描述
给定一个 DAG,找到在 2 台并行机器上运行函数的顺序的最佳方法是什么?
每台机器一次可以运行一个任务,并且一个任务在其依赖项完成执行之前不能运行。我知道如何为 n 个任务和 n 台机器做到这一点,但对于 2 台机器有点迷失。任何帮助从哪里开始?
解决方案
您可以使用 CP 技术和 CP Solver。这是在 Python 中使用 CP-Optimizer 的示例:
# 1. PROBLEM DATA (EXAMPLE)
n = 20
DURATION = [ 108, 90, 67, 286, 107, 65, 468, 444, 126, 50, 143, 450, 275, 125, 143, 215, 85, 45, 204, 488 ]
DAG = [ [0,5], [1,6], [2,4], [3,7], [3,8], [4,10], [5,9], [6,11], [7,13], [8,12],[9,14], [10,15], [12,16], [14,17], [15,18], [16,19] ]
N = range(n)
# 2. MODELING THE PROBLEM WITH CP-OPTIMIZER
from docplex.cp.model import *
m = CpoModel()
task = [interval_var(size=DURATION[i]) for i in N ] # Decision variables: tasks
usedMachines = sum([pulse(task[i],1) for i in N]) # Cumul function: number of tasks executing over time
m.add(minimize(max(end_of(task[i]) for i in N))) # Objective: minimize schedule makespan
m.add([end_before_start(task[i],task[j]) for [i,j] in DAG]) # Constraints: precedence between tasks
m.add(usedMachines <= 2) # Constraints: maximal number of machines
# 3. SOLVING THE PROBLEM
sol = model.solve()
# 4. DISPLAY SOLUTION
import docplex.cp.utils_visu as visu
for i in range(n):
visu.interval(sol.get_var_solution(task[i]), i, str(i))
visu.show()
这个小问题实例的最佳解决方案示例,具有 1992 年的最佳制造时间(解决时间小于 0.01 秒,包括最优性证明):
推荐阅读
- javascript - Apps 脚本:时间戳未正确复制
- java - 如何在 ClickListerner 上为网格布局编码
- angular - *ngTemplateOutlet 指令的实际场景是什么?
- javascript - 使用 JavaScript 或 jQuery 切换 CSS 根变量?
- c# - 如何使用 asp.net 从本地文件夹中删除数据列表中的图像 - 错误(system.io.directorynotfoundexception 找不到路径的一部分)
- python - 有没有办法区分功能?
- javascript - Javascript 滚动条 Var 无法正常工作
- python - Python:我有一个值,但无法让它显示回文本字段
- powerbi - 无法使用 RestApi 获取 power bi 中的数据集列表?
- c++ - 为什么我只能在 C++ 中使用可变长度数组分配小于 10 mb 的空间?