《Decision Analytics Journal》：A multi-objective open shop model for optimizing scheduling in automotive repair shops
编辑推荐：
本研究聚焦于汽车维修行业售后服务的效率提升难题。针对维修车间每日调度中的资源分配与服务效率平衡问题，作者Mohammad Behbahani、Reza Izadbakhsh和Hamidreza Izadbakhsh开发了一个双目标开放式车间调度模型。该模型旨在同时最小化车辆总流程时间以及维修工位的空闲与加班成本。通过构建混合整数线性规划模型和提出改进的NSGA-II算法，并结合来自伊朗大型汽修中心的真实案例进行验证，研究结果表明，相较于人工调度，所提方法能将总流程时间减少约42%，并将空闲与加班成本降低约47%，显著验证了基于优化的调度方案在提升汽车售后服务运营效率方面的实际价值。
随着汽车制造厂商日益重视售后服务质量，高效的维修车间调度已成为提升客户满意度和控制运营成本的关键环节。汽车维修运营涉及复杂的物流管理，尤其是针对诸如专业化技工和维修工位等有限资源的调配。维修车间每天需要处理多辆汽车，每辆车又可能需要多项维修工序，如何在满足工位资质限制和车辆不重叠等约束下，合理安排这些工序的顺序和分配，同时兼顾减少车辆等待时间（以降低客户不满）和提高工位利用率（以控制成本和提升效率），是行业面临的普遍挑战。传统的开放式车间调度问题（OSSP）为这种工序顺序不固定的场景提供了理论框架，但将其应用于同时优化客户导向和资源导向双重目标的维修调度实践，仍需要更精细的模型和高效的求解方法。为了应对这一挑战，研究人员在《Decision Analytics Journal》上发表了一项研究，系统性地提出了一个针对汽车维修车间的双目标调度优化方案。
本研究主要采用了几项关键技术方法。首先，基于确定的工序时间、工位资质及容量等参数，研究人员构建了一个双目标混合整数线性规划模型，以在数学上精确描述工位分配、工序排序、流程时间计算以及空闲与加班成本的优化问题，该模型适用于中小规模问题求取精确解或近优解。其次，针对大规模问题实例中MILP模型求解计算量过大的挑战，作者们提出了一种改进的非支配排序遗传算法II，该算法采用“工位-序列”染色体编码方案，并集成了具有冲突修复（时间平移）功能的可行性解码机制，以确保每个车辆的工序在不同工位间不发生时间重叠。此外，研究还设计了针对问题的交叉和变异算子，以提高算法的搜索效率和解决方案的质量。
4.1. 问题定义、输入与假设
该研究将汽车维修的日常调度问题建模为一个多工位的开放式车间调度问题。研究假设所有车辆及其维修需求（工序集合及预估时间）在每日计划开始前已通过预约系统确定（即离线调度）。每辆车的各项维修工序可以在符合资质的工位上以任意顺序执行，但同一时间一辆车只能在一个工位上接受服务。工位有其标准工作时长和允许的最大加班时长，并对应着空闲成本和加班成本。研究的目标是在满足工位资质和车辆工序不重叠等约束下，同时最小化两个冲突的目标：所有车辆的总流程时间（从第一项工序开始到最后一项工序结束的总时长）以及所有工位的空闲与加班总成本。
4.2. 维修车间特征描述
研究所基于的系统是一个基于预约的“开放访问”模式维修车间。客户通过在线系统预约，并根据预定义列表报告故障类型，系统基于历史数据为每项维修类别预估标准工时。在实际运营日，车辆按计划顺序进入车间，依次在不同专业工位（如机械、服务、电子）接受维修、进行质检并流转。
4.3. 目标函数
研究明确提出了两个优化目标：一是最小化车辆总流程时间（客户满意度指标），二是最小化工位的空闲与加班成本（运营效率指标）。这两个目标存在内在冲突：为减少车辆流程时间而紧凑安排工序，可能导致某些工位出现空闲等待；而为均衡工位负荷、减少空闲和加班，又可能延长某些车辆的等待时间。文章通过一个包含三辆车、三个工位的甘特图示例直观展示了这种权衡：
5. 维修车间调度的MILP模型
为解决此优化问题，研究者建立了一个双目标混合整数线性规划模型。模型定义了决策变量，包括工序在工位的分配变量、工序间的先后顺序变量、工序完成时间变量、车辆流程时间变量以及各工位的空闲和加班时间变量。目标函数如公式(1)和(2)所示，分别最小化总成本（∑r(trOr+ irIr)）和总流程时间（∑cFTc）。约束条件则确保了：每个工序必须且只能分配给一个有资质的工位（公式3）；在同一个工位上，工序要么是第一个开始，要么紧接在前一个工序之后（公式4）；对于同一辆车，其工序之间必须顺序执行，不能重叠（公式5,7）；车辆流程时间由其最早开始和最晚结束的工序决定（公式8）；以及工位的空闲和加班时间计算（公式9），且加班时间不能超过上限（公式10）。
6. 改进的NSGA-II算法
针对MILP模型难以求解大规模问题的局限性，研究提出了一种改进的NSGA-II算法。标准的NSGA-II是一种多目标进化算法，通过非支配排序和拥挤距离计算来逼近问题的帕累托最优解集。本研究的关键改进在于编码和可行性解码策略。算法采用一种“工位-序列”染色体表示法，并结合了能够感知约束的解码器。该解码器在将染色体解码为具体调度方案时，会主动检测并修复可能出现的冲突（例如，同一车辆的工序在时间上重叠），通过时间平移操作确保生成的调度方案完全可行。这种设计显著降低了进化过程中产生不可行解的比例，提高了搜索效率。
7. 计算研究与案例应用
研究通过合成的测试算例和一个来自伊朗大型汽车维修中心的真实案例对所提出的方法进行了验证。计算结果表明，改进的NSGA-II算法在求解大规模问题时，能够在合理时间内找到高质量的双目标近似帕累托前沿解。在真实案例中，将算法生成的优化调度方案与车间原有的人工调度方案进行对比，优化方案能够将总流程时间降低约42%，同时将空闲与加班成本减少约47%，充分证明了所提出方法的有效性和实际应用价值。
8. 结论与讨论
本研究成功地将汽车维修车间的日常调度问题构建为一个双目标开放式车间调度模型，并分别提供了适用于小规模问题的精确MILP模型和适用于大规模问题的改进NSGA-II启发式算法。其主要贡献在于：第一，首次在汽车维修调度中联合优化了客户导向（总流程时间）和资源导向（空闲/加班成本）的双重绩效指标；第二，所开发的MILP模型为小规模实例提供了基准解；第三，所设计的改进NSGA-II算法通过特定的编码和可行性修复机制，有效解决了高约束调度问题中可行解生成难的挑战；第四，通过真实案例验证了该方法能带来显著的绩效提升。这项工作为汽车售后服务运营的智能化、高效化调度提供了切实可行的优化框架和工具，具有重要的管理启示和实践意义。未来研究可以考虑引入维修时间的不确定性、动态预约到达等更复杂的现实因素，以进一步增强模型的鲁棒性和适用性。
