资源约束项目调度

Question

我正在尝试实现一个资源受限项目调度问题的算法。我有几个资源，resource constraints，所有这些都在整数时域。使用我的类ResourceUtilization，我希望确保资源约束不会在任何时候都被违反。我的类的关键元素是具有大小utilization的数组(num_resources, max_makespan)。我将给定资源demands的活动添加到ResourceUtilization，从start_time添加到finish_time。我还需要在某个时候删除这个活动。大多数被调用的方法is_free()检查是否可以将活动添加到时间间隔中。

import numpy as np
cimport numpy as np
import cython

DTYPE = np.int
ctypedef np.int_t DTYPE_t

cdef class ResourceUtilization:
    cdef DTYPE_t[:, :] res_constraints
    cdef DTYPE_t[:, :] utilization
    cdef DTYPE_t max_makespan
    cdef DTYPE_t num_resources

    def __init__(self, np.ndarray[DTYPE_t, ndim=2] res_constraints, DTYPE_t num_resources, DTYPE_t max_makespan):
        self.res_constraints = res_constraints
        self.num_resources = num_resources
        self.max_makespan = max_makespan
        self.utilization = np.zeros([self.num_resources, max_makespan], dtype=DTYPE)

    def add(self, np.ndarray[DTYPE_t, ndim=2] demands, DTYPE_t start_time, DTYPE_t finish_time):
        """
        Add demands from interval <start_time, finish times) to resources.
        Expand utilization if needed.
        """
        cdef DTYPE_t[:, :] copy_util
        if finish_time > self.max_makespan:
            self.extend_makespan(finish_time)
        copy_util = self.utilization[:, start_time:finish_time] + demands
        self.utilization[:, start_time:finish_time] = copy_util

    def remove(self, np.ndarray[DTYPE_t, ndim=2] demands, DTYPE_t start_time, DTYPE_t finish_time):
        """
        Remove demands from interval <start_time, finish_time) from utilization.
        """
        cdef DTYPE_t[:, :] copy_util
        copy_util = self.utilization[:, start_time:finish_time] - demands
        self.utilization[:, start_time:finish_time] = copy_util

    def extend_makespan(self, DTYPE_t minimal_extend_time):
        """
        Extend length of utilization for at least minimal_extend_time
        """
        cdef DTYPE_t difference
        cdef DTYPE_t[:, :] extenstion
        if minimal_extend_time > self.max_makespan:
            difference = self.max_makespan * np.floor(minimal_extend_time / self.max_makespan)
            extension = np.zeros([self.num_resources, difference], dtype=DTYPE)
            self.utilization = np.hstack((self.utilization, extension))
            self.max_makespan += difference

    def get(self, DTYPE_t resource, DTYPE_t time):
        """
        Get utilization of resource in time.
        """
        return self.utilization[resource][time]

    def get_capacity(self, DTYPE_t resource, DTYPE_t time):
        """
        Get residual capacity of resource in time
        """
        return self.res_constraints[resource] - self.get(resource, time)

    def is_free(self, np.ndarray[DTYPE_t, ndim=2] demands, DTYPE_t start_time, DTYPE_t finish_time):
        """
        Check whether we can add demands to interval <start_time, finish_time)
        """
        return np.all(self.utilization[:, start_time:finish_time] + demands <= self.res_constraints)

在这里，您可以看到使用的示例：

def test_ru():
    res_constraints = np.array([[4, 6, 2, 3]], dtype=np.int).T
    num_resources = 4
    max_makespan = 16
    ru = ResourceUtilization(res_constraints, num_resources, max_makespan)
    demands = np.array([[4, 3, 0, 1]], dtype=np.int).T
    assert ru.is_free(demands, 0, 4)
    ru.add(demands, 0, 4)
    assert not ru.is_free(demands, 0, 4)
    ru.remove(demands, 0, 4)

我试图在整个算法中测试我的类的性能，因为ResourceUtilization.is_free()是调用最多的函数之一，因此是瓶颈。当我运行这段代码时，它与纯Python/NumPy解决方案一样快。我还以为它会跑得更快呢。我尝试了cython -a resource_utilization.pyx，它仍然包含很多python调用(您可以找到它这里)。我第一次尝试使用Cython，所以我根本不确定我是否使用得好。你有什么办法来加速我的课吗？

Answer 1

如果您查看生成的代码，难怪该解决方案与常规的NumPy/Python相同，因为它没有以任何方式利用Cython。仍然有对相同NumPy函数的调用，循环/np.all调用没有内联，因此没有加速的机会。

除了算法更改之外，这里的一个选项是创建一个循环，它与np.all加切片的组合做同样的事情，并测试它是否更快。如果是这样的话，那么也会有并行处理/线程处理的替代方案，以使测试更快。再一次，数组需要相当大才能抵消增加的复杂性。

对于向量/矩阵的预期形状，我遇到了一些麻烦；这样的想法是这样的(但到目前为止，代码还没有完全工作！，因为test变量可能应该是向量吗？)：

def is_free(self, np.ndarray[DTYPE_t, ndim=2] demands, DTYPE_t start_time, DTYPE_t finish_time):
    """
    Check whether we can add demands to interval <start_time, finish_time)
    """
    # return np.all(self.utilization[:, start_time:finish_time] + demands <= self.res_constraints)

    cdef np.ndarray[DTYPE_t, ndim=2] test
    test = self.res_constraints - demands

    for i in range(start_time, finish_time):
        if np.all(self.utilization[:, i] > test):
            return False
        # OR inline this test, iterate through the vector directly
        for j in range(self.utilization.shape[0]):
            if self.utilization[j, i] > test[j]):
                return False

    return True

此外，具有来自get_capacity的设置的test_ru抛出了一个与形状混淆相关的异常：

>>> ru.get_capacity(0, 1)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "resource_ru.pyx", line 61, in resource_ru.ResourceUtilization.get_capacity (...)
    return self.res_constraints[resource] - self.get(resource, time)
TypeError: unsupported operand type(s) for -: 'resource_ru._memoryviewslice' and 'int'