Page 136 - IJOCTA-15-2

End of day process optimization
EOD process can be more challenging, leading to which requires time-discretization, and flow-based
5
an extended EOD process duration. As a result, formulation. The time-indexed formulation pro-
traditional batch processing methods may not be vides fairly good linear relaxation bounds. How-
sufficiently efficient for managing EOD batch pro- ever, it performs poorly with broad time horizons.
cesses in such systems. Therefore, there is a need In either of the two cases above, solving a MIP
for a new EOD algorithm optimized for enterprise for large-scale projects is cumbersome. Hence, a
systems, including microservices applications. wide majority of heuristic algorithms have been
This paper presents a case study of a Turkish developed for RCPSP.
bank that seeks to minimize the duration of the A significant portion of these heuristics is se-
EOD process by optimizing resource allocation quencing algorithms that are constructive greedy
and task sequencing. We thus consider the order heuristics. These algorithms assign each task
of execution of the EOD tasks and the amount with a priority based on certain properties, and
of resources allocated to execute each task. This sequences them in a serial or parallel manner
problem can be modeled as a variant of Project in a single or a multi-pass with respect to the
Scheduling Problem, called Multi-Mode Resource resource constraints. There exists a wide vari-
Constrained Project Scheduling Problem (MR- ety of publications for different priority rules, se-
CPSP). In this paper, we propose an exact so- quence order, or number of passes. 6–13 Kolisch
lution to this problem to be used as a bench- and Hartmann 14,15 and Hartmann and Briskorn 16
mark and a heuristic approach for practical im- provide a broad overview and comparison of
plementation. Our contribution is a mixed inte- these algorithms. In addition to these prior-
ger programming formulation of the problem, and ity rule-based algorithms, Li and Willis 17 pro-
performance analysis of the heuristic approach in pose a forward-backward scheduling algorithm,
this case study. We have further demonstrated Valls et al. 18 propose a hybrid genetic algorithm,
how our optimization tool can be utilized as a and Lee and Kim 19 use search heuristics to solve
simulator for analyzing how efficiently the re- RCPSP.
sources are used and identifying bottleneck re- A more complicated variant of RCPSP is MR-
sources. CPSP, where the tasks have multiple modes with
The paper is organized as follows: Section 2 different resource requirements and durations. It
provides a brief overview of the literature on Re- is important to note that increased resource us-
source Constrained Project Scheduling Problem age will not only reduce task durations but also
(RCPSP). In Section 3 we describe the system in decrease the number of tasks that can be exe-
our case study and establish the specifics of this cuted simultaneously. Hence, it will lead to an
problem. Section 4 presents the two solution ap- increase in the total makespan. Due to this addi-
proaches. Computational results are provided in tional trade-off, MRCPSP requires more complex
Section 5, and concluding remarks are in Section heuristics than straightforward sequencing algo-
6. rithms. Exact solution methods such as 20–24 have
been stated to be effective for problems up to
2. Literature survey 20 activities and two modes per activity. 24 For
larger instances, various meta-heuristic based al-
Project Scheduling Problem (PSP) is a relatively 25–28
simple problem in the literature to determine the gorithms, such as Simulated Annealing and
29–31
order in which the tasks should be executed in an Genetic Algorithm have been proposed to
optimal manner with respect to the precedence solve MRCPSP.
constraints such that the total makespan of the A general distribution of the work in the afore-
2
project is minimized. PERT Algorithm solves mentioned literature is summarized in Table 1.
Where we stand in the literature is the second
this problem in polynomial time.
category, that focuses on the exact solution of the
RCPSP has the same goal and precedence
Multi-Mode Resource Constrained Project Sched-
constraints as PSP. In addition, in RCPSP each
uling Problem. All of the stated papers utilize the
task requires a non-perishable resource usage dur-
time-indexed formulation of the problem; and our
ing execution, and the limited amount of re-
contribution is the flow-based formulation. In this
sources available places an additional constraint
paper we also describe Simulated Annealing im-
on the tasks that can be executed simultane-
plementation of the same problem. However, that
ously. should not be considered as a scientific contribu-
3
Kone et al. provide a thorough overview of
tion (due to the abundance of existing studies),
the literature on RCPSP. The two most popu-
but rather as an implementation choice from a
lar Mixed Integer Programming (MIP) formula- practical application context.
tions of RCPSP are time-indexed formulation, 4
331