高效计算团队成员基于项目分配与产能的下一个可用日期

问题背景 #

我们有25名团队成员，每人拥有多组可用产能规则与项目分配规则：

• 可用产能：定义为某日期区间内的可用时间占比（100%=全职），结束日期为null则表示无限期有效；产能可为0，适配借调、育儿假等场景。
• 项目分配：成员在指定日期区间内为项目投入的时间占比，可同时参与多个项目，总投入占比不得超过当前产能。

当前通过暴力逐天循环的方式计算每位成员的下一个可用日期（即总项目分配占比低于产能的最早日期），但效率极低，需要更优实现思路。技术栈为NodeJS+Vue，当前使用Luxon库实现暴力法，最终需转为JS代码。

优化核心思路 #

暴力法的低效根源在于逐天遍历，优化方向是只关注所有规则的日期节点（区间开始/结束日期）——因为成员的产能或项目分配状态只会在这些节点发生变化。具体步骤：

1. 收集所有影响成员状态的关键日期：包括所有产能区间的开始/结束日期、所有项目分配区间的开始/结束日期，再加上当前日期（作为起始检查点）。
2. 对这些关键日期去重并按时间升序排序。
3. 遍历排序后的关键日期，依次检查每个日期（以及该日期所在区间的有效性）：
   • 计算该日期对应的成员当前产能值。
   • 计算该日期所有生效的项目分配占比总和。
   • 若总分配占比 < 当前产能，则该日期即为下一个可用日期；若所有关键日期都不满足，则取最后一个关键日期之后的第一天（或根据无限期规则处理）。
4. 特殊处理：若存在无限期的产能/分配规则，需将其纳入最后区间的检查。

伪代码示例 #

function findNextAvailableDate(member, currentDate) {
    // 收集所有关键日期
    let keyDates = new Set()
    keyDates.add(currentDate)
    
    // 添加产能规则的关键日期（结束日期的次日才会触发状态变化）
    for each capacityRule in member.capacities {
        keyDates.add(capacityRule.startDate)
        if (capacityRule.endDate !== null) {
            keyDates.add(capacityRule.endDate.plusDays(1))
        }
    }
    
    // 添加项目分配规则的关键日期
    for each assignmentRule in member.assignments {
        keyDates.add(assignmentRule.startDate)
        if (assignmentRule.endDate !== null) {
            keyDates.add(assignmentRule.endDate.plusDays(1))
        }
    }
    
    // 排序关键日期
    let sortedDates = Array.from(keyDates).sort((a, b) => a - b)
    
    // 遍历检查每个关键日期
    for each date in sortedDates {
        if (date < currentDate) continue
        
        // 获取当前日期的有效产能
        let currentCapacity = getEffectiveCapacity(member, date)
        if (currentCapacity === 0) continue
        
        // 获取当前日期的总项目分配占比
        let totalAssignment = getTotalAssignment(member, date)
        
        if (totalAssignment < currentCapacity) {
            return date
        }
    }
    
    // 若所有关键日期都满负荷，返回最后一个日期的次日
    let lastDate = sortedDates[sortedDates.length - 1]
    return lastDate.plusDays(1)
}

// 辅助函数：获取指定日期的有效产能
function getEffectiveCapacity(member, date) {
    for each capacityRule in member.capacities {
        let start = capacityRule.startDate
        let end = capacityRule.endDate ?? Infinity
        if (date >= start && date < end) {
            return capacityRule.percentage
        }
    }
    return 0 // 默认无产能
}

// 辅助函数：获取指定日期的总项目分配占比
function getTotalAssignment(member, date) {
    let total = 0
    for each assignmentRule in member.assignments {
        let start = assignmentRule.startDate
        let end = assignmentRule.endDate ?? Infinity
        if (date >= start && date < end) {
            total += assignmentRule.percentage
        }
    }
    return total
}

JS + Luxon 实现示例片段 #

import { DateTime } from 'luxon'

function findNextAvailableDate(member, currentDate = DateTime.now()) {
    const keyDates = new Set()
    keyDates.add(currentDate)

    // 处理产能规则的关键日期
    member.capacities.forEach(cap => {
        keyDates.add(cap.startDate)
        if (cap.endDate) {
            // 结束日期的次日才会改变产能状态
            keyDates.add(cap.endDate.plus({ days: 1 }))
        }
    })

    // 处理项目分配规则的关键日期
    member.assignments.forEach(assign => {
        keyDates.add(assign.startDate)
        if (assign.endDate) {
            keyDates.add(assign.endDate.plus({ days: 1 }))
        }
    })

    // 按时间顺序排序日期
    const sortedDates = Array.from(keyDates).sort((a, b) => a.toMillis() - b.toMillis())

    for (const date of sortedDates) {
        if (date < currentDate) continue

        const currentCapacity = getEffectiveCapacity(member, date)
        if (currentCapacity === 0) continue

        const totalAssignment = getTotalAssignment(member, date)

        if (totalAssignment < currentCapacity) {
            return date
        }
    }

    // 若无满足条件的关键日期，返回最后一个日期的次日
    const lastDate = sortedDates[sortedDates.length - 1]
    return lastDate.plus({ days: 1 })
}

function getEffectiveCapacity(member, date) {
    for (const cap of member.capacities) {
        const start = cap.startDate
        const end = cap.endDate ?? DateTime.fromMillis(Number.MAX_SAFE_INTEGER)
        if (date >= start && date < end) {
            return cap.percentage
        }
    }
    return 0
}

function getTotalAssignment(member, date) {
    let total = 0
    for (const assign of member.assignments) {
        const start = assign.startDate
        const end = assign.endDate ?? DateTime.fromMillis(Number.MAX_SAFE_INTEGER)
        if (date >= start && date < end) {
            total += assign.percentage
        }
    }
    return total
}

额外优化点 #

• 提前对成员的产能/分配规则按日期排序，检查时用二分查找快速定位生效规则，进一步减少遍历次数。
• 批量处理所有成员的计算时，可共享部分日期排序逻辑，但需注意每个成员规则的独立性。

内容的提问来源于stack exchange，提问作者Mark