Page 141 - IJOCTA-15-2

E. Karabulut T¨urkseven, E. Gen¸c, and I. Safak / Vol.15, No.2, pp.330-342 (2025)
availability over time; and each decrease of each values. At every iteration a neighbor solution is
resource as a rectangular block is modelled as a randomly selected. If this new solution has a bet-
dummy task as described above. Let A d be the ter objective, then the search jumps on to the next
′
set of such dummy tasks; and A = A ∪ A d . The point. If the new solution does not have a better
tasks in A d have predetermined start times σ i , 0 solution, then the search either remains on the
as their sole predecessor, n + 1 as their sole suc- current solution, or jumps on to the new solution
cessor; and they all have a single mode. with a probability that is a function of the differ-
The varying resource model can be formulated ence in the objective values and a concept called
′
as (2) - (14) using A instead of A, and an addi- the temperature. Just like the actual annealing
tional constraint process applied to metals, SA algorithm starts
with high temperature, more likely to jump to
S i = σ i ∀ i ∈ A d . (15)
other solutions and explore the region; and grad-
Although this new formulation appears to be ually decreases the temperature to ensure conver-
suitable for dealing with FixedTasks in our prob- gence.
lem, it is not directly applicable. The main reason The search is conducted for C chains, where
for this is that although the start times of Fixed- each chain is initialized at different solutions. In
Tasks are fixed, the durations are not. In other each chain, there are S steps, where the number

words, although t 1 values are predetermined, t 2 of neighbors generated n s , and the temperature
changes during the execution. Underestimating T is constant at each step. After each step, n s is
t 2 values would cause the model to utilize a re- increased and T is decreased. The general frame-
source that has not yet been released by the Fixed- work of the algorithm is given in Figure 5.
Task. Therefore, for our specific implementation,
A very important concept in SA is the concept
we stick with the resource reduction strategy ex-
of neighborhood among the solutions. The neigh-
plained in Section 3.
boring solutions should be easy to generate. With
4.2. Simulated annealing minor changes in the solution vector, one should
be able to create feasible solutions. Hence, it is
The lack of access to a commercial solver through- of the utmost importance that the project exe-
out the bank’s implementation requires the uti- cution schedules have an appropriate representa-
lization of a heuristic strategy for the solution tion. The variables in Section 4.1 (S, x, z, y,
tool’s deployment. For this purpose, we pre- and f) constitute a representation; a subset of
ferred Simulated Annealing algorithm, which has these variables may also constitute a representa-
been used as an approximation tool for RCPSP tion (such as S and z). However, minor modifi-
and MRCPSP. 26–28 Simulated Annealing (SA) is cations in these vectors are very likely to lead to
a neighborhood-based local search algorithm that, infeasible solutions. In our algorithm, we use a
unlike greedy search algorithms, allows itself to representation that consists of two lists, similar
explore solutions with worse objective function to the work in. 27

Find initial solution x_0, and set x_{best} = x_{current} = x_0
and f_{best} = f_{current} = f(x_0)
For C chains
Initialize T and n_s
For S steps
For n_s neighbors
Generate a neighbor x of x_{current}
Delta = f(x) - f_{current}
If Delta < 0
x_{current} = x, f_{current} = f(x)
If f_{current}<f_{best}
x_{best} = x_{current}, f_{best} = f_{current}
Else
With probability e^{-Delta /T}
x_{current} = x, f_{current} = f(x)
Decrease T, increase n_s

Figure 5. A Generic SA Algorithm
336