Portal

Algoritmos y Fórmulas Técnicas — BimTrazER

Algoritmos extraídos del código fuente de los microservicios Go/TypeScript con fórmulas matemáticas, pseudo-código y ejemplos numéricos.
Fecha: 2026-05-03

Algoritmo 1: Cálculo de Secuencias de Ejecución (CPM/DFS)

Ubicación en código

sequences/internal/sequencesOptimized.go — Función SequencesOptimized()

Propósito

Determinar todas las cadenas de ejecución válidas en un proyecto de construcción modeladas como un Grafo Dirigido Acíclico (DAG). Cada camino de nodo raíz a nodo terminal representa una secuencia de precedencia que el motor de desplazamientos usará para calcular impactos de retrasos.

Modelo matemático: Grafo DAG

El proyecto se modela como $ G = (V, E) $ donde:

$ V $ = conjunto de bloques constructivos
$ E $ = conjunto de relaciones de precedencia $ (A, B) $ si B depende de A

Un nodo $ v \in V $ es un nodo raíz (start node) si no tiene predecesores:

$$\text{StartNodes} = \{ v \in V \mid \nexists\, u \in V : (u, v) \in E \}$$

Fórmula: Detección de ciclos

$$\text{HayCiclo}(G) \iff \exists \text{ camino } v_1 \to v_2 \to \cdots \to v_n \to v_1$$

El algoritmo usa un conjunto visited por rama de recursión para detectar ciclos en O(V+E).

Pseudo-código con backtracking

función SequencesOptimized(bloques[], reverseOrder, projectId):
    G = NewGraph(bloques)        // 3 passes: crear nodos, conectar edges, identificar raíces
    return G.findAllSequences(reverseOrder, projectId)

función NewGraph(bloques[]):
    // Pass 1: crear nodos
    para cada bloque b en bloques:
        nodes[b.code] = Node{block: b}

    // Pass 2: conectar dependencias (edges)
    para cada nodo n en nodes:
        para cada depCode en n.block.Dependence:
            nodes[depCode].Dependents.append(n)
            isDependent[n.code] = true

    // Pass 3: identificar raíces
    startNodes = [n para n en nodes si NOT isDependent[n.code]]
    return Graph{nodes, startNodes}

función dfs(nodo, state):
    SI state.visited[nodo.code]:
        LANZAR ERROR "Ciclo detectado en: " + state.path
    
    state.visited[nodo.code] = true     // MARCAR
    state.path.append(nodo.code)        // AVANZAR
    
    SI nodo.Dependents está vacío:      // BASE: nodo terminal
        pathCopy = copiar(state.path)
        SI reverseOrder: invertir(pathCopy)
        state.allPaths.append(join(pathCopy, "-"))
    SI NO:
        para cada hijo en nodo.Dependents:
            dfs(hijo, state)            // RECURSIÓN
    
    delete state.visited[nodo.code]    // BACKTRACK: desmarcar
    state.path.pop()                   // BACKTRACK: remover

Complejidad

Operación	Tiempo	Espacio
Construcción del grafo (3 passes)	O(V + E)	O(V)
DFS con backtracking	O(V + E)	O(V) — solo la pila de recursión
Total	O(V + E)	O(V)

Ejemplo numérico

Proyecto con 5 bloques y dependencias: A→B→D, A→C→D, D→E

graph LR A([A]) --> B([B]) A --> C([C]) B --> D([D]) C --> D D --> E([E]) style A fill:#1899D9,color:#fff style E fill:#00E5C2,color:#333

Secuencias calculadas (start=A, terminal=E):

A-B-D-E
A-C-D-E

Benchmark del código fuente:

Escenario	Bloques	Max Deps	Implementación	Resultado
SmallProject	50	2	Optimized	~microsegundos
MediumProject	150	3	Optimized	~milisegundos
LargeProject	1000	5	Optimized	viable
LargeProject	1000	5	Original	⚠️ OMITIDO (explosión combinatoria)

Algoritmo 2: Cálculo de Desplazamientos de Cronograma

Ubicación en código

displacements/displacements/algorithm.go + logic.go — Función CalculateDisplacements()

Propósito

Dado un conjunto de bloques con fechas programadas, fechas de ejecución real y secuencias de dependencias, calcular para cada bloque no ejecutado: (a) su nueva fecha estimada de finalización y (b) sus días de atraso acumulado.

Fórmulas principales

Frame de estado (7 bits):

$$\mathbf{P} = [P_0, P_1, P_2, P_3, P_4, P_5, P_6]$$

donde cada $P_i \in \{0, 1\}$ y se define:

$$P_0 = \begin{cases} 1 & \text{si } \text{Bloque}_A \text{ está certificado (executed=true)} \\ 0 & \text{si no} \end{cases}$$ $$P_2 = \begin{cases} 1 & \text{si } A_{scheduled} \geq \text{hoy} \\ 0 & \text{si no} \end{cases}$$ $$P_3 = \begin{cases} 1 & \text{si } A'_{displacement} \geq \text{hoy} \\ 0 & \text{si no} \end{cases}$$ $$P_4 = \begin{cases} 1 & \text{si } P_0 = 1 \text{ Y } A''_{execution} \geq \text{hoy} \\ 0 & \text{si no} \end{cases}$$

Cálculo de delta de días (casos de propagación):

$$\Delta_{casos\ 2,5,6,8,21} = \left\lfloor \frac{(\text{hoy} - A_{scheduled})}{86400} \right\rfloor \text{ días}$$ $$\Delta_{casos\ 3,4,9,\ldots,27} = \left\lfloor \frac{(A''_{execution} - A_{scheduled})}{86400} \right\rfloor \text{ días}$$

Fecha desplazada del bloque sucesor B:

$$B' = B_{scheduled} + (A'_{displacement} - A_{scheduled})$$

Días de atraso final:

$$\text{DaysLate}(bloque) = \max\left(\Delta_{cascada},\ \left\lceil \frac{(\text{hoy} - B_{scheduled})}{86400} \right\rceil\right)$$

Regla de desempate (worst-case):

$$\text{DaysLate}_{final} = \max(\Delta_{existente},\ \Delta_{nuevo})$$

Tabla completa de 27 casos del frame

Frame (P₀-P₁-P₂-P₃-P₄-P₅-P₆)	Caso	Regla Delta
`0-0-1-1-0-0-0`	1	Δ = 0 (sin desplazamiento)
`0-0-0-1-0-0-0`	2	Δ = hoy − A_scheduled
`1-0-0-0-0-0-0`	3	Δ = A_exec − A_scheduled
`1-0-1-0-0-0-0`	3	Δ = A_exec − A_scheduled
`1-0-0-1-1-0-0`	4	Δ = A_exec − A_scheduled
`0-1-0-1-0-0-1`	5	Δ = hoy − A_scheduled
`0-1-0-1-0-1-1`	6	Δ = hoy − A_scheduled
`0-1-1-1-0-1-1`	7	Δ = 0
`1-1-0-1-1-0-1`	8	Δ = hoy − A_scheduled
`1-1-0-0-0-0-1`	9	Δ = A_exec − A_scheduled
`1-1-0-0-0-1-1`	10	Δ = A_exec − A_scheduled
`1-1-0-0-0-0-0`	11	Δ = A_exec − A_scheduled + delta_sucesor_today
`1-1-1-0-0-1-1`	12	Δ = A_exec − A_scheduled
`1-1-1-1-1-1-1`	14	Δ = A_exec − A_scheduled
`1-1-0-1-1-1-1`	15	Δ = A_exec − A_scheduled
`0-1-0-0-0-0-0`	18	Δ = 0
`0-0-0-0-0-0-0`	21	Δ = hoy − A_scheduled

Diagrama de flujo del algoritmo

flowchart TD A([CalculateDisplacements
blocks, sequences, holidays]) --> B[Paso 1: newContext
blockMap + holidayMap] B --> C[Paso 2: Para cada secuencia
reverseSequenceString] C --> D[findExecutionAnchor
primer bloque no ejecutado] D --> E[Paso 3: calculateAllDisplacements
por cada SequencePosition] E --> F[buildFrame
vector P de 7 bits] F --> G[mapFrameToCase
frame → número 1..27] G --> H{caseNum == 0?} H -->|Sí| I[⚠️ Warning: frame no reconocido
email de alerta] H -->|No| J[applyDisplacementRule
calcular Δ días] J --> K[newUpdateResult por cada bloque
en la cola de la secuencia] K --> L{¿Nuevo Δ > Δ existente?} L -->|Sí| M[Actualizar finalResults
DaysLate = Δ, Date = original + Δ] L -->|No| N[Mantener resultado existente] M --> O[Paso 4: Formatear
map code → Displacement] N --> O O --> P([Retornar finalDisplacements])

Ejemplo numérico paso a paso

Secuencia: A-B-C donde A fue ejecutado con 5 días de retraso.

A: scheduled=2025-03-01, executed=true, execDate=2025-03-06
B: scheduled=2025-03-10, executed=false
C: scheduled=2025-03-20, executed=false
Hoy: 2025-03-15

Frame para A (ancla):

P₀ = 1 (ejecutado)
P₁ = 1 (tiene sucesor B)
P₂ = 0 (A_scheduled = Mar-01 < hoy = Mar-15)
P₃ = 0 (A_displacement no definido → 0)
P₄ = 0 (execDate = Mar-06 < hoy = Mar-15)
P₅ = 0 (B_scheduled = Mar-10 < hoy = Mar-15)
P₆ = 0 (B' = Mar-10 + 5d = Mar-15 = hoy → < hoy)

Frame = 1-1-0-0-0-0-0 → Caso 11

$$\Delta = A''_{exec} - A_{scheduled} = \text{Mar-06} - \text{Mar-01} = 5 \text{ días}$$ $$\Delta_{sucesor\_B} = \text{hoy} - B_{scheduled} = \text{Mar-15} - \text{Mar-10} = 5 \text{ días}$$

Resultado:

B: DaysLate = 5, DisplacedDate = Mar-10 + 5d = Mar-15
C: DaysLate = 5, DisplacedDate = Mar-20 + 5d = Mar-25

Benchmark documentado: 1.3M secuencias · 1,200 bloques procesados en un ciclo de benchmark sin errors.

Algoritmo 3: Clasificación de Estado de Bloque (LBP)

Ubicación en código

lbp/services/ — lógica de mapeo de estados

Diagrama de estados

stateDiagram-v2 [*] --> NOT_EXECUTED : Bloque creado, dependencias no OK NOT_EXECUTED --> BLOCKED : Falta al menos 1 dependencia BLOCKED --> NOT_EXECUTED : Todas dependencias cumplidas (AVAILABLE) NOT_EXECUTED --> PARTIAL : ejecutedValue > 0 AND < 100 PARTIAL --> ON_TIME : ejecutedValue = 100 AND execDate ≤ endDate PARTIAL --> LATE : ejecutedValue = 100 AND execDate > endDate NOT_EXECUTED --> OVERDUE : endDate < hoy AND executed = false ON_TIME --> [*] LATE --> [*]

Fórmulas de clasificación

Condición BLOCKED:

$$\text{BLOCKED} \iff \exists\, d \in \text{Dependence}(B) : \text{execution}(d) \neq \text{ON\_TIME} \land \text{execution}(d) \neq \text{LATE}$$

Condición OVERDUE:

$$\text{OVERDUE} \iff \text{executed} = false \land \text{endDate} < \text{hoy}$$

Condición LATE (ejecutado):

$$\text{LATE} \iff \text{executed} = true \land \text{execDate} > \text{endDate}$$

Condición ON_TIME:

$$\text{ON\_TIME} \iff \text{executed} = true \land \text{execDate} \leq \text{endDate}$$

Prioridad de bloque (DSP — Días Sin Programar):

$$\text{DSP}(B) = \max(0,\ \text{hoy} - \text{endDate}(B)) + \sum_{d \in \text{Dependence}(B)} \text{DaysLate}(d)$$

Algoritmo 4: Cálculo de Ruta Crítica (Holgura Cero)

Ubicación en código

sequences/internal/sequence.go (algoritmo original) + sequencesOptimized.go (refactorizado)

Definición formal

Forward Pass — Tiempo de inicio temprano (ES) y fin temprano (EF):

$$ES(j) = \max_{i \in \text{Pred}(j)} EF(i)$$ $$EF(j) = ES(j) + D(j)$$

Backward Pass — Tiempo de inicio tardío (LS) y fin tardío (LF):

$$LF(i) = \min_{j \in \text{Succ}(i)} LS(j)$$ $$LS(i) = LF(i) - D(i)$$

Holgura total (Slack):

$$\text{Slack}(i) = LF(i) - EF(i) = LS(i) - ES(i)$$

Ruta Crítica:

$$\text{RutaCrítica} = \{ i \in V \mid \text{Slack}(i) = 0 \}$$

Ejemplo numérico CPM

Bloque	D (días)	Pred	ES	EF	LF	LS	Slack	Crítico?
A	3	—	0	3	3	0	0	✅
B	5	A	3	8	8	3	0	✅
C	2	A	3	5	8	6	3	❌
D	4	B, C	8	12	12	8	0	✅

Ruta Crítica: A → B → D (duración total: 12 días)

Algoritmo 5: Cálculo de Avance General de Obra

Propósito

El KPI "Avance real / Programado" del dashboard se calcula comparando el progreso acumulado certificado vs el cronograma teórico.

Fórmulas

Avance real acumulado (%):

$$\text{AvanceReal} = \frac{\sum_{i \in \text{Certificados}} w_i \cdot P_i}{\sum_{i \in V} w_i} \times 100$$

donde $w_i$ = peso ponderado del bloque (basado en duración o costo), $P_i$ = porcentaje de ejecución física (0–100%).

Avance programado a la fecha (%):

$$\text{AvanceProg}(t) = \frac{\sum_{i : \text{endDate}_i \leq t} w_i}{\sum_{i \in V} w_i} \times 100$$

Índice de rendimiento de cronograma (SPI):

$$\text{SPI} = \frac{\text{AvanceReal}}{\text{AvanceProg}(t_{\text{hoy}})}$$

$\text{SPI} < 1$: proyecto atrasado
$\text{SPI} = 1$: proyecto en tiempo
$\text{SPI} > 1$: proyecto adelantado

Fecha estimada de finalización (a ritmo actual):

$$\hat{T}_{fin} = T_{inicio} + \frac{T_{duraci\acute{o}n\_planeada}}{\text{SPI}}$$

Días de atraso esperados:

$$\text{DiasAtraso} = \max\left(0,\ \hat{T}_{fin} - T_{fin\_planeado}\right)$$