Efficient Adaptive Implementation of the Serial Schedule Generation Scheme using Preprocessing and Bloom Filters
Daniel Karapetyan Alexei Vernitski




Hamiltonian Mechanics  





D. Karapetyan and A. Vernitsky. 


Institute for Analytics and Data Science, University of Essex, Essex, UK

daniel.karapetyan@gmail.com
Department of Mathematical Sciences, University of Essex, Essex, UK

asvern@essex.ac.uk

Efficient Adaptive Implementation of the Serial Schedule Generation Scheme using Preprocessing and Bloom Filters
    Daniel Karapetyan1 Alexei Vernitski2
    December 30, 2023
================================================================================================================




 
 
 The majority of scheduling metaheuristics use indirect representation of solutions as a way to efficiently explore the search space.
 Thus, a crucial part of such metaheuristics is a “schedule generation scheme” – procedure translating the indirect solution representation into a schedule.
 Schedule generation scheme is used every time a new candidate solution needs to be evaluated.
 Being relatively slow, it eats up most of the running time of the metaheuristic and, thus, its speed plays significant role in performance of the metaheuristic.
 
 
 
 Despite its importance, little attention has been paid in the literature to efficient implementation of schedule generation schemes.
 We give detailed description of serial schedule generation scheme, including new improvements, and propose a new approach for speeding it up, by using Bloom filters.
 The results are further strengthened by automated control of parameters.
 Finally, we employ online algorithm selection to dynamically choose which of the two implementations to use.
 This hybrid approach significantly outperforms conventional implementation on a wide range of instances.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 




§ INTRODUCTION


 Resource Constrained Project Scheduling Problem (RCPSP) is to schedule a set of jobs J subject to precedence relationships and resource constraints.
 RCPSP is a powerful model generalising several classic scheduling problems such as job shop scheduling, flow shop scheduling and parallel machine scheduling.
 
 
 In RCPSP, we are given a set of resources R and their capacities c_r, r ∈ R.
 In each time slot, c_r units of resource r are available and can be shared between jobs.
 Each job j ∈ J has a prescribed consumption v_j,r of each resource r ∈ R.
 We are also given the duration d_j of a job j ∈ J.
 A job consumes v_j,r units of resource r in every time slot that it occupies.
 Once started, a job cannot be interrupted (no preemption is allowed).
 Finally, each resource is assigned a set 𝑝𝑟𝑒𝑑_j ⊂ J of jobs that need to be completed before j can start.
 
 There exist multiple extensions of RCPSP.
 In the multi-mode extension, each job can be executed in one of several modes, and then resource consumption and duration depend on the selected mode.
 In some applications, resource availability may vary with time.
 There could be set-up times associated with certain jobs.
 In multi-project extension, several projects run in parallel sharing some but not all resources.
 In this paper we focus on the basic version of RCPSP, however some of our results can be easily generalised to many of its extensions and variations.

 Most of the real-world scheduling problems, including RCPSP, are NP-hard, and hence only problems of small size can be solved to optimality, whereas for larger problems (meta)heuristics are commonly used.
 Metaheuristics usually search in the space of feasible solutions; with a highly constrained problem such as RCPSP, browsing the space of feasible solutions is hard.
 Indeed, if a schedule is represented as a vector of job start times, then changing the start time of a single job is likely to cause constraint violations.
 Usual approach is to use indirect solution representation that could be conveniently handled by the metaheuristic but could also be efficiently translated into the direct representation.
 
 Two translation procedures widely used in scheduling are serial schedule generation scheme (SSGS) and parallel schedule generation scheme <cit.>.
 Some studies conclude that SSGS gives better performance <cit.>, while others suggest to employ both procedures within a metaheuristic <cit.>.
 Our research focuses on SSGS.

 With SSGS, the indirect solution representation is a permutation π of jobs.
 The metaheuristic handles candidate solutions in indirect (permutation) form.
 Every time a candidate solution needs to be evaluated, SSGS is executed to translate the solution into a schedule (t_j, j ∈ J), and only then the objective value can be computed, see Figure <ref>.

 

 SSGS is a simple procedure that iterates through J in the order given by π, and schedules one job at a time, choosing the earliest feasible slot for each job.
 The only requirement for π is to respect the precedence relations; otherwise SSGS produces a feasible schedule for any permutation of jobs.
 The pseudo-code of SSGS is given in Algorithm <ref>, and its two subroutines 𝑓𝑖𝑛𝑑 and 𝑢𝑝𝑑𝑎𝑡𝑒 in Algorithms <ref> and <ref>.
 
 
 

 

 
 

 
 
 

 Commonly, the objective of RCPSP is to find a schedule that minimises the makespan, i.e. the time required to complete all jobs; however other objective functions are also considered in the literature.
 We say that an objective function of a scheduling problem is regular if advancing the start time of a job cannot worsen the solution's objective value.
 Typical objective functions of RCPSP, including makespan, are regular.
 If the scheduling problem has a regular objective function, then SSGS guarantees to produce active solutions, i.e. solutions that cannot be improved by changing t_j for a single j ∈ J.
 Moreover, it was shown <cit.> that for any active schedule S there exists a permutation π for which SSGS will generate S.
 Since any optimal solution S is active, searching in the space of feasible permutations π is sufficient to solve the problem.
 This is an important property of SSGS; the parallel schedule generation scheme, mentioned above, does not provide this guarantee <cit.> and, hence, may not in some circumstances allow a metaheuristic finding optimal or near-optimal solutions.


 
 
 
 
 
 
 

 
 

 The runtime of a metaheuristic is divided between its search control mechanism that modifies solutions and makes decisions such as accepting or rejecting new solutions, and SSGS.
 While SSGS is a polynomial algorithm, in practice it eats up the majority of the metaheuristic runtime (over 98% as reported in <cit.>).
 
 
 In other words, by improving the speed of SSGS twofold, one will (almost) double the number of iterations a metaheuristic performs within the same time budget, and this increase in the number of iterations is likely to have a major effect on the quality of obtained solutions.
 
 In our opinion, not enough attention was paid to SSGS – a crucial component of many scheduling algorithms, and this study is to close this gap.
 In this paper we discuss approaches to speed up the conventional implementation of SSGS.
 Main contributions of our paper are:

	
  * A detailed description of SSGS including old and new speed-ups (Section <ref>).

    
  * New implementation of SSGS employing Bloom filters for quick testing of resource availability (Section <ref>).

    
  * A hybrid control mechanism that employs intelligent learning to dynamically select the best performing SSGS implementation (Section <ref>).

 
 Empirical evaluation in Section <ref> confirms that both of our implementations of SSGS perform significantly better than the conventional SSGS, and the hybrid control mechanism is capable of correctly choosing the best implementation while generating only negligible overheads.

 
 
 
 
 
 
 








§ SSGS IMPLEMENTATION DETAILS



 Before we proceed to introducing our main new contributions in Sections <ref> and <ref>, we describe what state-of-the-art implementation of SSGS we use, including some previously unpublished improvements.
 


 §.§ Initialisation of A

 
 
 The initialisation of A in line <ref> of Algorithm <ref> iterates through T slots, where T is the upper bound on the makespan.
 It was noted in <cit.> that instead of initialising A at every execution of SSGS, one can reuse this data structure between the executions. 
 To correctly initialise A, at the end of SSGS we restore A_t, r for each r ∈ R and each slot where some job was scheduled: A_t, r c_r for r ∈ R and t = 1, 2, …, M, where M is the makespan of the solution.
 Since M ≤ T and usually M ≪ T, this notably improves the performance of SSGS <cit.>.
 
 
 













 §.§ Efficient search of the earliest feasible slot for a job



 The function 𝑓𝑖𝑛𝑑(j, t^0, I, A)  finds the earliest slot feasible for scheduling job j. 
 Its conventional implementation (Algorithm <ref>) takes O(T |R|) time, where T is the upper bound of the time horizon.
 Our enhanced implementation of 𝑓𝑖𝑛𝑑 (Algorithm <ref>), first proposed in <cit.>, has the same worst case complexity but is more efficient in practice.
 
 
 It is inspired by the Knuth-Morris-Pratt substring search algorithm.
 Let t_j be the assumed starting time of job J.
 To verify if it is feasible, we need to test sufficiency of resources in slots t_j, t_j + 1, …, t_j + d_j - 1.
 Unlike the conventional implementation, our enhanced version tests these slots in the reversed order.
 The order makes no difference if the slot is feasible, but otherwise testing in reversed order allows us to skip some slots; in particular, if slot t is found to have insufficient resources then we know that feasible t_j is at least t + 1.
 
 A further speed up, which was not discussed in the literature before, is to avoid re-testing of slots with sufficient resources.
 Consider the point when we find that the resources in slot t are insufficient.
 By that time we know that the resources in t + 1, t + 2, …, t_j + d_j - 1 are sufficient.
 Our heuristic is to remember that the earliest slot t^test to be tested in future iterations is t_j + d_j.







 
 
 
 
 
 

 




	
	
	cell base/.style=minimum width=1cm, minimum height=1cm, draw=none, transform shape,
	unknown/.style=cell base, fill=white!90!black, label=[font=]center:?,
	available/.style=cell base, fill=none, label=[font=]center:+,
	unavailable/.style=cell base, fill=none, label=[font=]center:-,
    known available/.style=cell base, pattern=north east lines, pattern color=gray,label=[font=]center:+














 
 


 








 §.§ Preprocessing and Automated Parameter Control





 
 We observe that in many applications, jobs are likely to require only a subset of resources.
 For example, in construction works, to dig a hole one does not need cranes or electricians, hence the `dig a hole' job will not consume those resources.
 To exploit this observation, we pre-compute vector R_j of resources used by job j, and then iterate only through resources in R_j when testing resource sufficiency in 𝑓𝑖𝑛𝑑 (Algorithm <ref>, line <ref>) and updating resource availability in 𝑢𝑝𝑑𝑎𝑡𝑒 (Algorithm <ref>, line <ref>).
 
 Despite the simplicity of this idea, we are not aware of anyone using or mentioning it before.
 
 We further observe that some jobs may consume only one resource.
 By creating specialised implementations of 𝑓𝑖𝑛𝑑 and 𝑢𝑝𝑑𝑎𝑡𝑒, we can reduce the depth of nested loops.
 While this makes no difference from the theoretical point of view, in practice this leads to considerable improvement of performance.
 Correct implementations of 𝑓𝑖𝑛𝑑 and 𝑢𝑝𝑑𝑎𝑡𝑒 are identified during preprocessing and do not cause overheads during executions of SSGS.
 
 Having individual vectors R_j of consumed resources for each job, we can also intelligently learn the order in which resource availability is tested (Algorithm <ref>, line <ref>).
 By doing this, we are aiming at minimising the expected number of iterations within the resource availability test.
 For example, if resource r is scarce and job j requires significant amount of r, then we are likely to place r at the beginning of R_j.
 More formally, we sort R_j in descending order of probability that the resource is found to be insufficient during the search.
 This probability is obtained empirically by a special implementation of SSGS which we call .
  is used once to count how many times each resource turned out to be insufficient during scheduling of a job.
 (To avoid bias,  tests every resource in R_j even if the test could be terminated early.)
 After a single execution of , vectors R_j are optimised, and in further executions default implementation of SSGS is used.
 
 
 
 
 
 One may notice that the data collected in the first execution of SSGS may get outdated after some time; this problem in addressed in Section <ref>.

 Ordering of R_j is likely to be particularly effective on instances with asymmetric use of resources, i.e. on real instances.
 Nevertheless, we observed improvement of runtime even on pseudo-random instances as reported in Section <ref>.

 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 







§ SSGS IMPLEMENTATION USING BLOOM FILTERS








 Performance bottleneck of an algorithm is usually its innermost loop.
 Observe that the innermost loop of the 𝑓𝑖𝑛𝑑 function is the test of resource sufficiency in a slot, see Algorithm <ref>, line <ref>.
 In this section we try to reduce average runtime of this test from O(|R|) to O(1) time.
 For this, we propose a novel way of using a data structure known as Bloom filter.

 Bloom filters were introduced in <cit.> as a way of optimising dictionary lookups, and found many applications in computer science and electronic system engineering <cit.>. 
 
 Bloom filters usually utilise pseudo-random hash functions to encode data, but in some applications <cit.> non-hash-based approaches are used.
 In our paper, we also use a non-hash-based approach, and to our knowledge, our paper is the first in which the structure of Bloom filters is chosen dynamically according to the statistical properties of the data, with the purpose of improving the speed of an optimisation algorithm.
 
 
 
 In general, Bloom filters can be defined as a way of using data, and they are characterised by two aspects: first, all data is represented by short binary arrays of a fixed length (perhaps with a loss of accuracy); second, the process of querying data involves only bitwise comparison of binary arrays (which makes querying data very fast).
 
 
 
 
 
 
 
 
 
 

 
 
 
 
 
 
 
 
 
 We represent both each job's resource consumption and resource availability at each time slot, by binary arrays of a fixed length; we call these binary arrays Bloom filters.
 Our Bloom filters will consist of bits which we call resource level bits.
 Each resource bit, denoted by u_r,k, r ∈ R, k ∈{ 1, 2, …, c_r }, means “k units of resource r” (see details below). Let U be the set of all possible resource bits.
 
 A Bloom filter structure is  an ordered subset L ⊆ U, see Figure <ref> for an example.
 
 Suppose that a certain Bloom filter structure L is fixed.
 Then we can introduce B^L(j), the Bloom filter of job j, and B^L(t), the Bloom filter of time slot t, for each j and t.
 Each B^L(j) and B^L(t) consists of |L| bits defined as follows: if u_r,k is the ith element of L then
 
    B^L(j)_i = 
     	1    if  v_j,r≥ k, 
    
        0    otherwise,    and    
     B^L(t)_i = 
     	1    if  A_t,r≥ k, 
    
        0    otherwise.

 

 
 
 
 




	bf bit/.style=minimum width=1cm, minimum height=0.5cm, draw=black, transform shape, font=,
    brace/.style=decorate,decoration=brace,amplitude=5pt,raise=1pt








 

 To query if a job j can be scheduled in a time slot t, we compare Bloom filters B^L(j) and B^L(t) bitwise; then one of three situations is possible, as the following examples show.
 Consider a job j and three slots, t, t' and t”, with the following resource consumption/availabilities, and Bloom filter structure as in Figure <ref>:
 
 v_j,1    = 3         v_j,2    = 2         v_j,3    = 0         B^L(j)    = (110 10 000) 

 A_t,1    = 2         A_t,2    = 3         A_t,3    = 4         B^L(t)    = (100 11 111) 

 A_t',1    = 3         A_t',2    = 1         A_t',3    = 4         B^L(t')    = (110 10 111) 

 A_t”,1    = 3         A_t”,2    = 2         A_t”,3    = 2         B^L(t”)    = (110 10 100)
 
 For two bit arrays of the same length, let notation `≤' mean bitwise less or equal.
By observing that B^L(j) ≰B^L(t), we conclude that resources in slot t are insufficient for j; this conclusion is guaranteed to be correct.
 By observing that B^L(j) ≤ B^L(t'), we conclude tentatively that resources in slot t' may be sufficient for j; however, further verification of the complete data related to j and t' (that is, v_j,· and A_t',·) is required to get a precise answer; one can see that v_j,2≥ A_t',2, hence this is what is called a false positive.
 Finally, we observe that B^L(j) ≤ B^L(t”), and a further test (comparing v_j,· and A_t”,·) confirms that resources in t” are indeed sufficient for j.

 
 

 
 
 
 

 Values of B^L(j), j ∈ J, are pre-computed when L is constructed, and B^L(t), t = 1, 2, …, T, are maintained by the algorithm.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
 
 
 
 
 
 


 §.§ Optimisation of Bloom Filter Structure

 
 The length |L| of a Bloom filter is limited to reduce space requirements and, more importantly for our application, speed up Bloom filter tests. 
 Note that if |L| is small (such as 32 or 64 bits) then we can exploit efficient bitwise operators implemented by all modern CPUs; then each Bloom filter test takes only one CPU operation.
 We set |L| = 32 in our implementation.
 While obeying this constraint, we aim at minimising the number of false positives, because false positives slow down the implementation.
 
 
 
 
 
 
 
 
 

 Our L building algorithm is as follows:

	
  * Start with L=U, such as in Figure <ref>.
    
    
  * 
 	If |L| is within the prescribed limit, stop.
    
    
  * Otherwise select u_r,k∈ L that is least important and delete it.
    Go to step <ref>.

 By `least important' we mean that the deletion of it is expected to have minimal impact of the expected number of false positives.
 Let L = (…, u_r,q, u_r,k, u_r, m, …).
 Consider a job j such that k ≤ v_j,r < m and a slot t such that q ≤ A_t,r < k.
 With L as defined above, Bloom filters correctly identify that resources in slot t are insufficient for job j: B^L(j) ≰B^L(t).
 However, without the resource level bit u_r,k we get a false positive: B^L(j) ≤ B^L(t).
 Thus, the probability of false positives caused by deleting u_r,k from L in is as follows:
 
    ( ∑_k = i^m - 1 D^r_k ) ·( ∑_k = q^i - 1 E^r_k )  ,
 
 where D^r_k is the probability that a randomly chosen job needs exactly k units of resource r, and E^r_k is the probability that a certain slot, when we examine it for scheduling a job, has exactly k units of resource r available.
 The probability distribution D^r is produced from the RCPSP instance data during pre-processing.
 [In multi-mode extension of RCPSP, this distribution depends on selected modes and hence needs to be obtained empirically, similarly to how we obtain E^r.]
 The probability distribution E^r is obtained empirically during the run of  (see Section <ref>); each time resource sufficiency is tested within , its availability is recorded.

 
 

 











 
 
 
 
 
 
 
 
 
 
 
 



 §.§ Additional Speed-ups

 
 While positive result of a Bloom filter test generally requires further verification using full data, in some circumstances its correctness can be guaranteed.
 In particular, if for some r ∈ R and j ∈ J we have u_r,k∈ L and v_j,r = k, then the Bloom filter result, whether positive or negative, does not require verification.
 
 
 Another observation is that updating B^L(t) in 𝑢𝑝𝑑𝑎𝑡𝑒 can be done in O(|R_j|) operations instead of O(|R|) operations.
 Indeed, instead of computing B^L(t) from scratch, we can exploit our structure of Bloom filters.
 We update each bit related to resources r ∈ R_j, but we keep intact other bits.
 With some trivial pre-processing, this requires only O(|R_j|) CPU operations.
 
 We also note that if |R_j| = 1, i.e. job j uses only one resource, then Bloom filters will not speed up the 𝑓𝑖𝑛𝑑 function for that job and, hence, in such cases we use the standard 𝑓𝑖𝑛𝑑 function specialised for one resource (see Section <ref>).
 

 Performance bottleneck of an algorithm is usually its innermost loop.
 Observe that the innermost loop of the 𝑓𝑖𝑛𝑑 function is the test of resource sufficiency in a slot, see Algorithm <ref>, line <ref>.
 In this section we try to reduce expected runtime of this loop from O(|R|) to O(1) time.
 We propose a novel way of using a data structure known as a Bloom filter; we shall start with explaining how Bloom filters can be applied to the problem we study, and provide a general definition of Bloom filters later in this subsection.




We represent both each job's resource consumption and the availability
of resources at each time slot by binary arrays of a fixed length; we call these binary arrays Bloom filters. Let us start with an example. Suppose we have three resources, each with
capacity 10. We can represent a job's resource consumption as a
binary array of length 6 whose bits contain answers to the following
questions:


  * Does the job need at least 1 unit of resource 1?

  * Does the job need at least 6 units of resource 1?

  * Does the job need at least 1 unit of resource 2?

  * Does the job need at least 6 units of resource 2?

  * Does the job need at least 1 unit of resource 3?

  * Does the job need at least 6 units of resource 3?


(As you are looking at this simple example, the choice of precisely two levels 1 and 6 for each of three resources seems arbitrary, and in this example, actually, it is arbitrary. Further in this section we propose how to make an optimal choice of the number and values of levels of each resource individually when designing the structure of Bloom filters representing jobs and slots.)

On the other hand, for each time slot we can represent availability
of resources during that slot as an array of the same length, that
is:


  * Is at least 1 unit of resource 1 available?

  * Are at least 6 units of resource 1 available?

  * Is at least 1 unit of resource 2 available?

  * Are at least 6 units of resource 2 available?

  * Is at least 1 unit of resource 3 available?

  * Are at least 6 units of resource 3 available?

For each job and each slot, checking whether the job's resource consumption
can be satisfied in this time slot is done simply by comparing these
two short binary arrays bitwise; this is faster than comparing several
pairs of numbers representing the job's resource consumption and availability
of resources. For example, suppose a job j requires 1, 5, 10 units
of resources 1, 2, 3, respectively, and in a slot t_1 we have
10, 5, 10 units of resources 1, 2, 3, respectively, available. Then
the Bloom filter of j is 101011, and the Bloom filter of t_1
is 111011. Comparing these two arrays bitwise, we observe that the
latter one is greater[a bit array a_1 … a_n is greater than a bit array b_1 … b_n if a_i ≥ b_i for each i = 1, …, n.] than the former one; hence, we can tentatively conclude that j can be scheduled in
t_1.

Now consider a slot t_2 in which we have 10, 5, 5 units
of resources 1, 2, 3, respectively, available. The Bloom filter of
t_2 is 111010. Comparing the Bloom filter of j with the
Bloom filter of t_2, we observe that the
latter one is not greater than the former one (due to 0 in the
6th bit of the latter one and 1 in the 6th bit of the former
one); thus, we conclude correctly that j cannot be scheduled in
t_1.

Now consider a slot t_3 in which we have 10, 5, 6 units
of resources 1, 2, 3, respectively, available. The Bloom filter of
t_3 is 111011. Comparing the Bloom filter of j with the
Bloom filter of t_3 we conclude, incorrectly, that j can
be scheduled in t_3. Thus, if Bloom filters give us a positive
answer (like in the examples with t_1 and t_3), it needs to be checked against the complete data, that is,
the job's resource consumption and availability of resources. If Bloom
filters frequently give us an incorrect positive answer (called a
false positive), this slows down the algorithm, and we want
to minimise the number of such errors.


In the example above, the range of capacity of each resource was split
into three subranges: (0), (1, 2, …, 5) and (6, 7, …, 10). In the
rest of this section we discuss how we can split the capacity of each
resource into subranges in a way which minimises the probability of
false positives produced by Bloom filters, thus making the algorithm
faster.

In general, Bloom filters can be defined as a way of using data characterised by two aspects: first, all data is represented by short binary arrays of a fixed length (perhaps with a loss of accuracy); second, the process of querying data involves only bitwise comparison of binary arrays (which makes querying data
very fast). Bloom filters were introduced in <cit.> as a way of optimising dictionary lookups, and found many applications in computer science and electronic system engineering <cit.>. To our knowledge, our paper is the first in which the structure of Bloom filters is chosen dynamically according to the statistical properties of the data, with the purpose of improving the speed of an optimisation algorithm.



 §.§ Distributions needed for the algorithm


To make the description simpler, we shall first assume that we only
have one resource with capacity c. A generalisation to several
resources is below in Subsection <ref>.

Our method of minimising the number of false positives uses two empirically found probability distributions, D and E. By D we denote the distribution of the probability that
a randomly chosen job needs exactly k units of the resource. This
distribution can be easily produced in advance from the list of jobs.
(In case of a multi-mode extension of RCPSP, D also depends on probability of each mode being selected and can be obtained empirically, similarly to how we obtain distribution E below.)

By E we denote the distribution of the probability that
when we examine a certain time slot (in order to decide whether a
job can be scheduled at this time slot), exactly k units of the
resource are available. 
E is obtained empirically within the 𝑓𝑖𝑛𝑑^data(j, t^0, I, A) functions (see Section <ref>).
 Every time resource sufficiency is tested within 𝑓𝑖𝑛𝑑^data(j, t^0, I, A), its availability is recorded.




 §.§ Building the Bloom filter





Like in the example above, the whole range of levels of a resource 1, …, c will be split into several subranges 1, …, p_1; p_1+1, …, p_2; … ; p_L-1, …, p_L = c. For each job, its Bloom filter will consist of L bits, and the i-th bit will be 1 if and only if the number of units of the resource required by the job is greater than or equal to p_i. For each slot, its Bloom filter will also consist of L bits, and the i-th bit will be 1 if and only if the number of units of the resource available is greater than or equal to p_i.

Denote the k-th entry in distribution D (or E) by d_k (or e_k); that is, d_k is the probability that
a randomly chosen job needs exactly k units of the resource, and e_k is the probability that a certain slot, when we examine it to schedule a job, has exactly k units of the resource available. If two levels k and k+1 of a resource are represented by the same bit in Bloom filters (that is, k and k+1 are within the same subrange p_i+1, …, p_i+1), there will be false positives if a certain job requires exactly k+1 units of the resource, but there are only k units of the resource available.  Since we want to minimise the probability of false positives, when we allocate resource levels to Bloom filters, we want to minimise the products d_k+1e_k whenever levels of a resource k and k+1 are represented by the same bit of a Bloom filter. More generally, we want to minimise the products d_k+ie_k whenever levels of a resource k and k+i are represented by the same bit of a Bloom filter. In our code we use a fast greedy algorithm which aims to minimise these products, as described below. 

Consider a dictionary
Δ whose index consists of intervals within 1,2,…,c,
and whose two entries for each value of the index is the corresponding
probability in D and E. To start, we let Δ be
as follows:


    [   1   2   …   c; d_1 d_2   … d_c; e_1 e_2   … e_c ]



For each k=1,…,r-1 calculate the product d_k+1e_k;
it expresses the probability of false positives if we denote k
and k+1 by the same bit of the Bloom filter. Choose a value of
k for which this product is minimal. Recalculate Δ by merging
the two columns, as follows: 


    [         1         …   (k,k+1)         …         c;       d_1         … d_k+d_k+1         …       d_c;       e_1         … e_k+e_k+1         …       e_c ]



Repeat this process until the size of the index is equal to the desired
length L of the Bloom filter.





If there are several resources, to decide on the structure of the
Bloom filter, proceed like above, but instead of considering one
pair of distributions D and E, build a dictionary with
a longer index, which will
correspond to all possible numbers of units of the first resource,
then all possible numbers of units of the second resource, etc., with
entries reflecting the corresponding two distributions D^r and
E^r for each resource r ∈ R. Thus, is we have a set R of resources with capacities c_r, r ∈ R, we build a dictionary whose index consists of all pairs (r, k), where r ∈ R and k ∈ 1, …, c_r, and whose two entries for each value of index are d_k^r and e_k^r. For each r ∈ R and for each k ∈ 1, …, c_r, calculate the product d_k+1^r e_k^r; this is the probability of false positives if levels k and k+1 of resource r are represented by the same bit of a Bloom filter. Choose the minimal one among these products and merge the corresponding two indices and entries of the dictionary. Repeat this process until the size of the index is equal to the desired
length L of the Bloom filter.

One can be tempted to conjecture that some resources are, in some
way, more important than others, and this should be somehow reflected
in the algorithm; actually, our algorithm implicitly takes this information
into account, because it aims to minimise false positives across all
resources, thus comparing each resource against others. 









§ HYBRID CONTROL MECHANISM


 
 So far we have proposed two improved implementations of SSGS: one using Bloom filters (which we denote ), and the other one not using Bloom filters (which we denote ).
 While it may look like  should always be superior to , in practice  is often faster.
 Indeed, Bloom filters usually speed up the 𝑓𝑖𝑛𝑑 function, but they also slow down 𝑢𝑝𝑑𝑎𝑡𝑒, as in  we need to update not only the values A_t,r but also the Bloom filters B^L(t) encoding resource availability.
 If, for example, the RCPSP instance has tight precedence relations and loose resource constraints then 𝑓𝑖𝑛𝑑 may take only a few iterations, and then the gain in the speed of 𝑓𝑖𝑛𝑑 may be less than the loss of speed of 𝑢𝑝𝑑𝑎𝑡𝑒.
 In such cases  is likely to be slower then .

 In short, either of the two SSGS implementations can be superior in certain circumstances, and which one is faster mostly depends on the problem instance.
 In this section we discuss how to adaptively select the best SSGS implementation.
 Automated algorithm selection is commonly used in areas such as sorting, where multiple algorithms exist.
 A typical approach is then to extract easy to compute input data features and then apply off-line learning to develop a predictor of which algorithm is likely to perform best, see e.g. <cit.>.
 With sorting, this seems to be the most appropriate approach as the input data may vary significantly between executions of the algorithm.
 Our case is different in that the most crucial input data (the RCPSP instance) does not change between executions of SSGS.
 Thus, during the first few executions of SSGS, we can test how each implementation performs, and then select the faster one.
 This is a simple yet effective control mechanism which we call .
 

 

	cell base/.style=minimum width=1cm, minimum height=1cm, draw=black, transform shape,
	BF/.style=cell base, pattern=north east lines, pattern color=white!60!black, label=[font=]center:BF,
	NBF/.style=cell base, pattern=north west lines, pattern color=white!80!black, label=[font=]center:NBF,
	data/.style=cell base, pattern=grid, pattern color=white!80!black, label=[font=]center:data











 

  is entirely transparent for the metaheuristic; the metaheuristic simply calls SSGS whenever it needs to evaluate a candidate solution and/or generate a schedule.
 The  control mechanism is then intelligently deciding each time which implementation of SSGS to use based on information learnt during previous runs.
 
 An example of how  performs is illustrated in Figure <ref>.
 
 In the first execution, it uses  to collect data required for both  and .
 For the next few executions, it alternates between  and , measuring the time each of them takes.
 During this stage,  counts how many times  was faster than the next execution of .
 Then we use the sign test <cit.> to compare the implementations.
 If the difference is significant (we use a 5% significance level for the sign test) then we stop alternating the implementations and in future use only the faster one.
 Otherwise we continue alternating the implementations, but for at most 100 executions.
 (Without such a limitation, there is a danger that the alternation will never stop – if the implementations perform similarly; since there are overheads associated with the alternation and time measurement, it is better to pick one of the implementations and use it in future executions.)
 
 Our decision to use the sign test is based on two considerations: first, it is very fast, and second, it works for distributions which are not normal.
 This makes our approach different from <cit.> where the distributions of runtimes are assumed to be normal.
 (Note that in our experiments we observed that the distribution of running times of an SSGS implementation resembles Poisson distribution.)

 
 As pointed out in this and previous sections, optimal choices of parameters of the SSGS implementations mostly depend on the RCPSP instance – which does not change throughout the metaheuristic run; however solution π also affects the performance.
 It should be noted though that metaheuristics usually apply only small changes to the solution at each iteration, and hence solution properties tend to change relatively slowly over time.
 Consequently, we assume that parameters chosen in one execution of SSGS are likely to remain efficient for some further executions.
 Thus,  `restarts' every 10,000 executions, by which we mean that all the internal data collected by SSGS is erased, and learning starts from scratch, see Figure <ref>.
 This periodicity of restarts is a compromise between accuracy of choices and overheads, and it was shown to be practical in our experiments.
 
 

 
 
 
 


 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 



































 
 
 
 
 
 


§ EMPIRICAL EVALUATION



 
 
 
 In this Section we evaluate the implementations of SSGS discussed above.
 To replicate conditions within a metaheuristic, we designed a simplified version of Simulated Annealing.
 In each iteration of our metaheuristic, current solution is modified by moving a randomly selected job into a new randomly selected position (within the feasible range).
 If the new solution is not worse than the previous one, it is accepted.
 Otherwise the new solution is accepted with 50% probability.
 Our metaheuristic performs 1,000,000 iterations before terminating.
 
 We evaluate ,  and .
 These implementations are compared to `conventional' SSGS, denoted by , which does not employ any preprocessing or Bloom filters and uses conventional implementation of 𝑓𝑖𝑛𝑑 (Algorithm <ref>).
 
 

 We found that instances in the standard RCPSP benchmark set PSPLIB <cit.> occupy a relatively small area of the feature space.
 For example, all the RCPSP instances in PSPLIB have exactly four resources, and the maximum job duration is always set to 10.
 Thus, we chose to use the PSPLIB instance generator, but with a wider range of settings.
 Note that for this study, we modified the PSPLIB instance generator by allowing jobs not to have any precedence relations.
 This was necessary to extend the range of network complexity parameter (to include instances with scarce precedence relations), and to speed up the generator, as the original implementation would not allow us to generate large instances within reasonable time.

 All the experiments are conducted on a Windows Server 2012 machine based on Intel Xeon E5-2690 v4 2.60 GHz CPU.
 No concurrency is employed in any of the implementations or tests.
 
 
 To see the effect of various instance features on SSGS performance, we select one feature at a time and plot average SSGS performance against the values of that feature.
 The rest of the features (or generator parameters) are then set as follows: number of jobs 120, number of resources 4, maximum duration of job 10, network complexity 1, resource factor 0.75, and resource strength 0.1.
 These values correspond to some typical settings used in PSPLIB.
 For formal definitions of the parameters we refer to <cit.>.
 
 For each combination of the instance generator settings, we produce 50 instances using different random generator seed values, and in each of our experiments the metaheuristic solves each instance once.
 
 Then the runtime of SSGS is said to be the overall time spent on solving those 50 instances, over 50,000,000 (which is the number of SSGS executions).
 The metaheuristic overheads are relatively small and are ignored.


 
Hybrid line/.append style=line width=5pt, black, opacity=0.3
BF line/.append style=black, mark=x, mark size=3pt
Non-BF line/.append style=thick, black, mark=*










 From the results reported in Figure <ref> one can see that our implementations of SSGS are generally significantly faster than , but performance of each implementation varies with the instance features.
 In some regions of the instance space  outperforms , whereas in other regions  outperforms .
 The difference in running times is significant, up to a factor of two in our experiments.
 At the same time,  is always close to the best of  and , which shows efficiency of our algorithm selection approach.
 In fact, when  and  perform similarly,  sometimes outperforms both; this behaviour is discussed below.

 Another observation is that  is always faster than  (always below the 100% mark) which is not surprising; indeed,  improves the performance of both 𝑓𝑖𝑛𝑑 and 𝑢𝑝𝑑𝑎𝑡𝑒.
 In contrast,  is sometimes slower than ; on some instances, the speed-up of the 𝑓𝑖𝑛𝑑 function is overweighed by overheads in both 𝑓𝑖𝑛𝑑 and 𝑢𝑝𝑑𝑎𝑡𝑒.
 Most important though is that  outperforms  in each of our experiments by 8 to 68%, averaging at 43%.
 In other words, within a fixed time budget, an RCPSP metaheuristic employing  will be able to run around 1.8 times more iterations than if it used .
 















 To verify that  exhibits the adaptive behaviour and does not just stick to whichever implementation has been chosen initially, we recorded the implementation it used in every execution for several problems, see Figure <ref>. 
 For this experiment, we produced three instances: first instance has standard parameters except Resource Strength is 0.2; second instance has standard parameters except Resource Factor is 0.45; third instance has standard parameters except Maximum Job Duration is 20.
 These parameter values were selected such that the two SSGS implementations would be competitive and, therefore, switching between them would be a reasonable strategy. 
 One can see that the switches occur several times throughout the run of the metaheuristic, indicating that  adapts to the changes of solution.
 For comparison, we disabled the adaptiveness and measured the performance if only implementation chosen initially is used throughout all iterations; the results are shown on Figure <ref>.
 We conclude that  benefits from its adaptiveness.







§ CONCLUSIONS AND FUTURE WORK


 In this paper we discussed the crucial component of many scheduling metaheuristics, the serial schedule generation scheme (SSGS).
 SSGS eats up most of the runtime in a typical scheduling metaheuristic, therefore performance of SSGS is critical to the performance of the entire metaheuristic, and thus each speed-up of SSGS has significant impact.
 We described existing and some new speed-ups to SSGS, including preprocessing and automated parameter control.
 This implementation clearly outperformed the `conventional' SSGS in our experiments.
 We further proposed a new implementation that uses Bloom filters, particularly efficient in certain regions of the instance space.
 To exploit strengths of both implementations, we proposed a hybrid control mechanism that learns the performance of each implementation and then adaptively chooses the SSGS version that is best for a particular problem instance and phase of the search.
 Experiments showed that this online algorithm selection mechanism is effective and makes  our clear choice.
 Note that  is entirely transparent for the metaheuristic which uses it as if it would be simple SSGS; all the learning and adaptation is hidden inside the implementation.

 The idea behind online algorithm selection used in this project can be further developed by making the number of executions between restarts adaptable.
 To determine the point when the established relation between the SSGS implementations may have got outdated, we could treat the dynamics of the implementations' performance change as two random walks, and use the properties of these two random walks to predict when they may intersect.
 
 All the implementations discussed in the paper, in C++, are available for downloading from <http://csee.essex.ac.uk/staff/dkarap/rcpsp-ssgs.zip>.
 The implementations are transparent and straightforward to use.
 
 While we have only discussed SSGS for the simple RCPSP, our ideas can easily be applied in RCPSP extensions.
 We expect some of these ideas to work particularly well in multi-project RCPSP, where the overall number of resources is typically large but only a few of them are used by each job. 
 
 



Acknowledgements 
 We would like to thank Prof. Rainer Kolisch for providing us with a C++ implementation of the PSPLIB generator.
 It should be noted that, although the C++ implementation was developed to reproduce the original Pascal implementation, the exact equivalence cannot be guaranteed; also, in our experiments we used a modification of the provided C++ code.


plain


