Skip to main content
 首页 » 编程设计

python之如何为任务优先级建模

2025年05月04日10powertoolsteam

我正在尝试模拟一堆属于同一个通用项目的任务。
任务具有持续时间和优先级(由必须在当前任务之前完成的任务列表表示)。

例如:

      /--->A --->B\ 
Start ---->C------->End 
      \--->D---->E/ 

也就是说任务A、C、D可以同时执行,但是任务B应该在任务A之后执行,任务E应该在任务D之后执行。

我写了这段代码:

#!/usr/bin/python2.7 
# -*- coding: utf-8 -*- 
import simpy 
 
 
class Task(object): 
    """  
        Has an id i.e.: 'E', 
        duration i.e.: 5 
        a list with Task that precede the current 
    """ 
    def __init__(self, idTask, duration, env, previousTasks=None): 
        self.idTask = idTask 
        self.duration = duration 
        self.env = envs 
        self.completed = env.event() 
        self.action = env.process(self.run()) 
        if previousTasks is None: 
            self.previousTasks = [] 
        else: 
            self.previousTasks = previousTasks 
 
    def run(self): 
        while self.can_execute() and not self.completed.triggered: 
            print "Starting task %s at time %s" % (self.idTask, self.env.now) 
            yield self.env.timeout(self.duration) 
            print "Completed task %s in time %s" % (self.idTask, self.env.now) 
            self.completed.succeed(True) 
 
    def can_execute(self): 
        result = True 
        for task in self.previousTasks: 
            if not task.completed.triggered: 
                result = False 
                break 
        return result 
 
if __name__ == "__main__": 
    env = simpy.Environment() 
    taskA = Task('A', 4, env) 
    taskB = Task('B', 5, env, [taskA]) 
    env.run(until=20) 

Task 对象中的 Completed 属性,用于了解当前任务是否已完成或已完成。 (我尝试用一​​个 bool 值来做,但没有不同的结果。)

taskB 将 taskA 作为先行任务。这意味着 taskB 应该在 taskA 完成之前开始,但这是我运行它时的输出:

% python tasks.py 
Starting task A at time 0 
Completed task A at time 4 
% 

我不明白为什么 taskB 不能运行。

-------------------------------------------- ------------------------------

已解决

我使用了“start_delayed”方法,该方法在 Simpy 的 simpy.util 模块中可用。根据当前任务是否有之前的任务要执行,每个任务的“ Action ”是简单过程还是延迟过程。
每个任务的延迟是在 add_precedences 和 estimate_delays 中计算的,但必须将先前任务的持续时间与当前任务的先前任务相加。
这是最终代码:

#!/usr/bin/python2.7 
# -*- coding: utf-8 -*- 
import simpy 
from simpy.util import start_delayed 
 
delays = {} 
completed = [] 
 
 
class Task(object): 
    """ Has an id i.e.: 'E', 
        duration i.e.: 5 
        a list with Task that precede the current 
    """ 
    def __init__(self, id, duration, env, previousTasks=None): 
        self.id = id 
        self.duration = duration 
        self.env = env 
        if previousTasks is None: 
            self.previousTasks = [] 
        else: 
            self.previousTasks = previousTasks 
        self.action = None 
 
    def run(self): 
        while True: 
            if delays[self.id] == self.env.now: 
                print "Start task: %s at time: %s" % (self.id, self.env.now) 
                yield self.env.timeout(self.duration) 
                completed.append(self.id) 
                print "Finish task: %s at time: %s" % (self.id, self.env.now) 
            else: 
                if self.id in completed: 
                    self.env.exit() 
 
 
def add_precedences(prevTask, durations): 
    if len(prevTask) == 0: 
        return 0 
    else: 
        durations.extend(map(lambda x: x.duration, prevTask)) 
        for prev in prevTask: 
            add_precedences(prev.previousTasks, durations) 
        return sum(durations) 
 
 
def estimate_delays(tasks): 
    result = {} 
    for task in tasks: 
        durations = [] 
        total = (add_precedences(task.previousTasks, durations)) 
        result.update({task.id: total}) 
    return result 
 
 
def set_action(tasks): 
    for task in tasks: 
        if delays[task.id] > 0: 
            task.action = start_delayed(task.env, task.run(), delays[task.id]) 
        else: 
            task.action = env.process(task.run()) 
 
if __name__ == '__main__': 
    env = simpy.Environment() 
    taskA = Task('A', 4, env) 
    taskB = Task('B', 5, env, previousTasks=[taskA]) 
    taskC = Task('C', 2, env, previousTasks=[taskB]) 
    tasks = [taskA, taskB, taskC] 
    delays.update(estimate_delays(tasks)) 
    set_action(tasks) 
    env.run(until=20) 

在这种情况下,项目有 3 个任务('A'、'B'、'C'),这是树:

Start --->A--->B--->C--->End  

B 必须在时间开始:4(因为那是 A 的持续时间)。而 C,必须在时间开始:9(因为那是 B+A 的持续时间)。
为了知道哪个任务已经完成,我创建了一个列表,每个任务都添加了自己的 ID。如果它自己的 ID 在该列表中,则每个任务都会从环境中删除。

请您参考如下方法:

我应该这样做作为评论,但我没有这样做的声誉。不过,我认为这可能有助于解决您的问题。

我不熟悉 simpy 但您可能会混淆 triggered 和 processed 这不允许任务 B 执行;检查此链接:http://simpy.readthedocs.org/en/latest/api_reference/simpy.events.html#module-simpy.events