分支定界算法求解带有释放时间的单机双代理调度问题

A Branch and Bound Algorithm for the Bi-agent Single-machine Scheduling Problem with Release Dates

本文研究了带有释放时间的单机双代理调度问题,目标函数为极小化最大完工时间和。为了便于利用优化软件求解,建立了混合整数规划模型。考虑到该问题具有NP困难性,因此采用近似与精确算法分别求解不同规模问题。针对大规模问题,提出了优势代理优先启发式算法,并证明了其渐近最优性。针对小规模问题,设计了分支定界法进行最优求解,其中基于释放时间的分支规则和基于加工中断的下界有效地减少了运算时间。最后,通过数值测试验证了分支定界算法的有效性以及启发式算法的收敛性。

This paper investigates a bi-agent single-machine scheduling problem with release dates. The objective is to minimize the sum of makespans. A mixed integer programming model is established for solving the problem by using optimization software. Given the NP-hardness of the problem, approximate and accurate algorithms are presented to handle different scale instances. For large-scale problems, available dominance agent first heuristic algorithm is proposed and its asymptotic optimality is proved. For small-scale problems, a branch and bound algorithm is designed to obtain optimal solution, in which a release-date-based branching rule and a preemption-based lower bound reduce the running time effectively. Numerical experiments show the effectiveness of the proposed algorithms.