带释放时间与固定周期维护约束的单机双代理组合优化模型与分支定界精确算法

A Combinatorial Optimization Model and Exact Branch-and-Bound Algorithm for a Single-Machine Two-Agent Scheduling Problem with Release Dates and Fixed Periodic Maintenance

摘要: 针对释放时间和固定周期维护约束下的单机双代理调度问题，以最小化两代理最大完工时间的加权和min Z = C_A + θC_B为目标，建立混合整数规划模型。考虑到释放时间、维护停机和不可中断加工共同导致的搜索空间扩张，设计一种分支定界算法。首先利用多种排序规则及局部邻域变换构造可行解，从而获得搜索树的初始上界；再通过放松不可抢占约束建立可抢占松弛下界，并分别利用释放时间阈值下的有效加工容量约束和周期运行窗口的装箱可行性约束构造容量下界与装箱下界，取三者最大值形成节点复合下界。在此基础上，根据节点状态之间的偏序关系建立状态支配规则，并利用同代理工件的可行插入关系构造插入支配规则，在保持全局最优性的条件下消除重复状态和劣势分支。数值实验采用不同规模随机实例，并与混合整数规划求解器CPLEX进行比较。在30组测试实例中，所构造分支定界算法有18组获得更小的限时目标函数值，其余12组与CPLEX所得结果相同；所构造初始上下界的平均最优性间隙约为2.80%，状态支配规则的总体剪枝命中率达到44.15%。实验结果表明，基于整数规划、松弛下界与支配关系构造的分支定界方法能够有效压缩离散可行解空间，并提高该类单机双代理组合优化问题的精确求解效率。

Abstract: For the single-machine dual-agent scheduling problem under release time and fixed periodic maintenance constraints, this study establishes a mixed-integer programming model with the objective of minimizing the weighted sum of the maximum completion times of the two agents, i.e., min Z = C_A + θC_B. To address the expansion of the search space caused by release times, maintenance downtime, and non-preemptive processing, a branch-and-bound algorithm is designed. First, feasible solutions are constructed using multiple sorting rules and local neighborhood transformations to obtain the initial upper bound of the search tree. Subsequently, a preemptive relaxation is applied by relaxing the non-preemptive constraint to derive a preemptive lower bound; additionally, capacity lower bounds and packing lower bounds are constructed by employing, respectively, the effective processing capacity constraint under a release time threshold and the packing feasibility constraint under a periodic operation window. The maximum of these three bounds is then taken to form the composite node lower bound. Building upon this foundation, a state domination rule is established based on the partial order between node states, and an insertion domination rule is constructed using the feasible insertion relationships among workpieces belonging to the same agent. This approach eliminates duplicate states and suboptimal branches while preserving global optimality. Numerical experiments were conducted using randomly generated instances of varying sizes, and the results were compared against those obtained by the mixed-integer programming solver CPLEX. Across 30 test instances, the proposed branch-and-bound algorithm achieved smaller time-limited objective function values in 18 instances, while in the remaining 12 instances, the results were identical to those of CPLEX; the average optimality gap of the constructed initial upper and lower bounds was approximately 2.80%, and the overall pruning hit rate of the state domination rule reached 44.15%. Experimental results demonstrate that the branch-and-bound method—constructed based on integer programming, relaxation lower bounds, and dominance relations—can effectively compress the discrete feasible solution space and improve the efficiency of solving this class of single-machine dual-agent combinatorial optimization problems exactly.