Resource-constrained project scheduling

Question

I'm trying to implement an algorithm for a resource-constrained project scheduling problem. I have several resources, resource constraints and all of this is in integer time domain. With my class ResourceUtilization I want to assure that resource constraints are not violated in all time. Key element of my class is array utilization with size (num_resources, max_makespan). I add an activity of given resource demands to ResourceUtilization from start_time to finish_time. I also need to remove that activity at some point. Most called method is_free() checks whether I can add an activity to a time interval.

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)

Here you can see example of usage:

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)

I'm trying to test my class performance in whole algorithm, because ResourceUtilization.is_free() is one of the most called function and therefore bottleneck. When I run this code it is as fast as pure Python/NumPy solution. I was expecting that it will run much faster. I tried cython -a resource_utilization.pyx and it still contains a lot python call (you can find it here). I'm trying to use Cython for the fist time so I'm not sure at all whether I use it well. Do you have any ideas how to speed up my class?

Answer 1

If you look at the generated code it's no wonder that the solution is the same as regular NumPy/Python since it's not taking advantage of Cython in any way. There are still calls to the same NumPy functions and the loop/np.all call isn't inlined, so there's no opportunity for a speed-up.

Except for algorithmic changes, one option here is to create a loop which does the same thing as the combination of np.all plus slicing and test if that's faster. If so, then there'd also be alternatives with parallel processing/threading to make the test faster. Then again, the arrays need to be quite large for that to offset the increased complexity.

I'm having a bit of trouble with the intended shapes of the vectors/matrixes; the idea would be to have something like this (but the code doesn't quite work so far!, as the test variable should probably be a vector instead?):

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

Also, get_capacity with the settings from test_ru throws an exception relating to the shapes confusion:

>>> 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'