TomCarlos 2021-03-06 13:09 采纳率: 0%
浏览 106
已结题

已知分配方案的资源受限项目调度问题所需时间求解?

在写一个利用模拟退火算法解资源受限项目调度问题的程序。

问题:

已知:

  • n个任务,每个任务有:
  1. 开始时间 (不能在开始时间之前开始任务)(int)
  2. 持续时间 (完成任务所需时间)(int)
  3. 依赖 (需要先完成依赖列表里的所有任务才可开始该任务)(list of task indexes) 
  • m个员工
  • 分配结果 (每个员工完成哪些任务) (list)

限制:

  • 每个任务只需要一个员工去完成
  • 任务不能中断

输出:

  • 在当前分配结果的情况下,该任务最短需要多长时间完成

输入例子

tasks = [{"index":0, "name": "task 0", "duration": 1, "start": 1, "dependency":[]},
         {"index":1, "name": "task 1", "duration": 1, "start": 0, "dependency":[0]},
         {"index":2, "name": "task 2", "duration": 3, "start": 1, "dependency":[]},
         {"index":3, "name": "task 3", "duration": 3, "start": 1, "dependency":[2]}]

employee = [{"index":0,"name": "employee 0"},{"index":1,"name": "employee 1"}]

plan = [0,0,1,0] # 员工0 完成任务0,1,3, 员工1 完成任务2

输出

7
# 0时间:没有任务可以开始
# 1时间:员工0开始任务0,员工1开始任务2
# 2时间:员工0完成任务0,开始任务1
# 3时间:员工0完成任务1
# 4时间:员工1完成任务2,员工0开始任务3
# 7时间:员工0完成任务3,所有任务完成

时间复杂度尽可能低,python代码或者详细伪代码思路都可,先谢谢各位大神了

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 操作系统相关算法中while();的含义
    • ¥15 CNVcaller安装后无法找到文件
    • ¥15 visual studio2022中文乱码无法解决
    • ¥15 关于华为5g模块mh5000-31接线问题
    • ¥15 keil L6007U报错
    • ¥15 webapi 发布到iis后无法访问
    • ¥15 初学者如何快速上手学习stm32?
    • ¥15 如何自动更换布娃娃图片上的衣服
    • ¥15 心理学eprime编程
    • ¥15 arduino esp8266开发