有负荷约束的指派问题

摘 要通过组合最优化的理论和方法,研究机器有负荷（时间）限制的指派问题,证明其NP困难性,并建立多项式可解的特殊情形算法及一般情形的隐枚举算法.

关 键 词组合优化；指派问题；负荷约束；算法分析

1引言

组合最优化中的运输与指派问题在各种离散系统的资源分配中有广泛的应用,因而得到深入的研究.进一步的发展是各种推广模型的出现.例如,能力受限的运输问题[1]、广义指派问题[2]、时限运输问题[3]等都引起众多学者的关注.随后,文献＼[4＼]提出一类带负荷（时间）约束的指派问题,即每台机器有执行任务的负荷限制,并给出分枝定界算法.这实际上等价于文献中的一类“广义指派问题”（thegeneralizedassignmentproblem,详见综述论文献＼[5＼]）.关于此类广义指派问题,最近文献＼[6＼]还讨论混合禁忌搜索算法.本文主要针对文献＼[4＼]的结果和方法,给出计算复杂性及多项式可解情形的结果,并改进其分枝定界算法.

众所周知,指派问题及运输问题,作为特殊的线性规划,都有十分有效的多项式时间算法,如匈牙利算法和网络流算法（参见文献＼[7-9＼]）.过去的推广问题（如文献＼[1-3＼]）都存在多项式时间算法.但是,上述＼[4＼]提出的有负荷约束的指派问题（作为特殊的0-1规划）,即使只求可行解（不求最优解）也是NP困难的.因此,进一步的研究工作就应该是多项式可解的特殊情形、近似算法及实用的隐枚举方法等.

2数学模型的讨论

5结论

对有负荷约束的指派问题,我们首先给出计算复杂性的理论结果,进而对配对型及一致性机器的特殊情形给出多项式时间算法或近似算法.至于分枝定界算法,定界和截枝规则均改进了文献＼[4＼]中的方法,从而加速了枚举进程如果在算法开始时能够求出一个可行解,得到最小值的上界z,便可以尽早进行截枝,加速求解过程.如前所述,配对型问题存在多项式时间算法.所以开始时可以先解一个配对型问题,如果能求出一个可行解（如前面的例题就存在这样的可行解）,便可以作为初始解,得到上界z.

既然有负荷约束的指派问题是困难问题,在实用上可以采取一些简化措施.例如取消整值约束,用线性规划求分数最优解；或者加上匹配约束（不一定一对一）,转化为运输或网络流问题.