Page 137 - IJOCTA-15-2

E. Karabulut T¨urkseven, E. Gen¸c, and I. Safak / Vol.15, No.2, pp.330-342 (2025)

Table 1. Literature Summary system. Although FixedTasks are not part of the
scheduling problem, they still consume resources
Multi- Exact from the same pool. In a deterministic setting
Heuristic
Mode Method where the duration of each task is constant in
Alvarez et al. 6 execution, resource reduction due to FixedTasks
Boctor 7 would be modeled as varying resource availabili-
¨
Ozdamar et al. 8 ties throughout the time span. However, due to
Ulusoy et al. 9 · · ✓ variances in task execution durations, a method
Lawrence 10 that requires such a level of precision was not
Kolisch et al. 11
¨
Ozdamar et al. 12 deemed to be a good fit.
Ulusoy et al. 13 To account for the necessity of allocating a
Talbot 20 portion of these two resources for the FixedTasks,
Patterson et al. 21 which are beyond the model’s scope, the proposed
Sprecher et al. 22 ✓ ✓ · method designates a fraction of the resources for
Hartmann et al. 23 the FixedTasks and solves the optimization prob-
Sprecher et al. 24 lem assuming the remaining resource availability.
Boctor 25 Additional sensitivity analysis is conducted to ob-
Boctor 26 serve the impact of the reserved resources on the
Bouleimen et al. 27 EOD project span, and the results are provided
J´ozefowska et al. 28 ✓ · ✓ in Section 5.
Mori et al. 29
¨
Ozdamar 30 An important feature of our problem is de-
Alcaraz et al. 31 termining the number of threads to allocate for
the execution of each task. Task durations are
generally defined as a problem parameter to pre-
3. Problem definition
serve the linearity of the formulation. However, in
This section describes the specifics of the con- our problem, task durations are directly impacted
sidered system. However, due to confidentiality by the thread allocation decisions. In order to
considerations, the numerical values provided will preserve linearity of the mathematical model, we
be approximate rather than exact, intended to refrain from defining the number of threads allo-
demonstrate the scale of the problem. cated to each task as an independent integer vari-
The EOD system consists of 400 tasks ex- able. Instead, by careful examination of the data
ecuted at the end of each day. 170 of these and the task structure, we determine several alter-
tasks referred to as FixedTasks, have fixed sched- native thread counts, and define each alternative
uled execution times. Hence, these tasks are not as a mode for executing the task. Hence, we arrive
included in the optimization problem. The re- at a combinatorial problem of finding an optimal
maining 230 EOD tasks are partitioned into dif- mode of execution for each task. Furthermore,
ferent stages. The stage structure is modeled recall that the two resources in the system men-
with dummy stage tasks with zero duration and tioned above are both renewable and currently
zero resource consumption that denote the begin- integrated into the infrastructure. Therefore, our
ning of a stage, STAGE1, STAGE2, STAGE3, problem should not be considered as a time/cost
STAGE4, and STAGE5. All tasks in the first trade-off RCPSP as described in, 32 as having only
stage have STAGE2 task as their final successor, renewable resources and no additional costs dif-
and all tasks in the second stage have STAGE2 ferentiates the current situation from crashing. It
task as their original predecessor. Due to this can, however, be interpreted as a time/resource
structure, instead of solving a large scheduling trade-off RCPSP, wherein only one of the two re-
problem with 230 tasks, we break the problem sources influences the task duration.
down based on the stages, and determine the To be used as model parameters, we are given
schedule for each stage separately. two sets of data: (1) infrastructural data, which
The system infrastructure can simultaneously includes information on the precedence relations,
execute 20 tasks in parallel and allocate 250 the stage information of each task, and whether
threads for the execution of EOD operations. each task can be parallelized or not; and (2) daily
A thread is the smallest unit of execution in a job logs, that include information regarding past 6
process and enables a software to execute nu- months on what time each task started and ended
merous tasks simultaneously, utilizing shared re- execution (and hence the duration) and how many
sources like memory and file handles. Tasks and threads are allocated to each task. The number
threads are the only renewable resources in the of threads allocated to each task has been kept
332