预算与资格受限的分布式异构流水车间调度分解算法OA
针对有限预算和生产资格约束的分布式异构置换流水车间调度问题(DHPFSP),以最小化生产成本与最大完工时间(Makespan)加权和为目标,本文建立了该问题的混合整数线性规划(MILP)模型和约束规划(CP)模型,并设计了两种能够精确求解的分解算法.首先,运用逻辑Benders分解(LBBD)技术将原问题分解为指派主问题和一系列调度子问题;其次,为提升LBBD收敛速度,引入基于瓶颈机器的调度子问题松弛策略加强主问题MILP模型并采用CP求解调度子问题;然后,在算法迭代过程中将根据子问题最优解产生的最优割加入到指派主问题以逐渐缩小解空间.基于以上框架,设计了两种LBBD算法:迭代式逻辑Benders分解(ILBBD)算法和分支检查(BCH)算法.计算结果表明,所提出的两种分解算法能够在合理时间内获得最优解或者近优解.与MILP和CP模型相比,两种分解算法在求解大规模问题上具有显著优势,而CP模型则在求解小规模问题上表现最佳.
熊福力;师江波;史浩君;潘静;刘恒冲
西安建筑科技大学信息与控制工程学院,陕西西安710311西安建筑科技大学信息与控制工程学院,陕西西安710311西安建筑科技大学信息与控制工程学院,陕西西安710311西安建筑科技大学信息与控制工程学院,陕西西安710311西安建筑科技大学信息与控制工程学院,陕西西安710311
信息技术与安全科学
分布式异构置换流水车间调度问题混合整数线性规划约束规划逻辑Benders分解算法分支检查算法
《控制理论与应用》 2026 (7)
P.1513-1522,10
国家自然科学基金项目(61473216)陕西省自然科学基础研究计划项目(2023-JC-YB-582)资助.
评论