有負(fù)荷約束的指派問題

摘要通過組合最優(yōu)化的理論和方法，研究機(jī)器有負(fù)荷（時(shí)間）限制的指派問題，證明其NP困難性，并建立多項(xiàng)式可解的特殊情形算法及一般情形的隱枚舉算法.

關(guān)鍵詞組合優(yōu)化；指派問題；負(fù)荷約束；算法分析

1引言

組合最優(yōu)化中的運(yùn)輸與指派問題在各種離散系統(tǒng)的資源分配中有廣泛的應(yīng)用，因而得到深入的研究.進(jìn)一步的發(fā)展是各種推廣模型的出現(xiàn).例如，能力受限的運(yùn)輸問題[1]、廣義指派問題[2]、時(shí)限運(yùn)輸問題[3]等都引起眾多學(xué)者的關(guān)注.隨后，文獻(xiàn)＼[4＼]提出一類帶負(fù)荷（時(shí)間）約束的指派問題，即每臺(tái)機(jī)器有執(zhí)行任務(wù)的負(fù)荷限制，并給出分枝定界算法.這實(shí)際上等價(jià)于文獻(xiàn)中的一類“廣義指派問題” （the generalized assignment problem，詳見綜述論文獻(xiàn)＼[5＼]）.關(guān)于此類廣義指派問題，最近文獻(xiàn)＼[6＼]還討論混合禁忌搜索算法. 本文主要針對(duì)文獻(xiàn)＼[4＼]的結(jié)果和方法，給出計(jì)算復(fù)雜性及多項(xiàng)式可解情形的結(jié)果，并改進(jìn)其分枝定界算法.

眾所周知，指派問題及運(yùn)輸問題，作為特殊的線性規(guī)劃，都有十分有效的多項(xiàng)式時(shí)間算法，如匈牙利算法和網(wǎng)絡(luò)流算法（參見文獻(xiàn)＼[7-9＼]）.過去的推廣問題（如文獻(xiàn)＼[1-3＼]）都存在多項(xiàng)式時(shí)間算法.但是，上述＼[4＼]提出的有負(fù)荷約束的指派問題（作為特殊的0-1規(guī)劃），即使只求可行解（不求最優(yōu)解）也是NP困難的.因此， 進(jìn)一步的研究工作就應(yīng)該是多項(xiàng)式可解的特殊情形、近似算法及實(shí)用的隱枚舉方法等.

2數(shù)學(xué)模型的討論

5結(jié)論

對(duì)有負(fù)荷約束的指派問題，我們首先給出計(jì)算復(fù)雜性的理論結(jié)果， 進(jìn)而對(duì)配對(duì)型及一致性機(jī)器的特殊情形給出多項(xiàng)式時(shí)間算法或近似算法. 至于分枝定界算法，定界和截枝規(guī)則均改進(jìn)了文獻(xiàn)＼[4＼]中的方法，從而加速了枚舉進(jìn)程如果在算法開始時(shí)能夠求出一個(gè)可行解，得到最小值的上界z，便可以盡早進(jìn)行截枝，加速求解過程. 如前所述，配對(duì)型問題存在多項(xiàng)式時(shí)間算法. 所以開始時(shí)可以先解一個(gè)配對(duì)型問題，如果能求出一個(gè)可行解（如前面的例題就存在這樣的可行解），便可以作為初始解，得到上界z.

既然有負(fù)荷約束的指派問題是困難問題， 在實(shí)用上可以采取一些簡化措施. 例如取消整值約束， 用線性規(guī)劃求分?jǐn)?shù)最優(yōu)解； 或者加上匹配約束（ 不一定一對(duì)一）， 轉(zhuǎn)化為運(yùn)輸或網(wǎng)絡(luò)流問題.

參考文獻(xiàn)

[1]王寅初.能力受限的運(yùn)輸問題的算法＼[J＼]. 數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，1981， 2（3）： 143-148.

＼[2＼]石忠民.廣義指派問題＼[J＼]. 運(yùn)籌與管理，1999，8（1）：21-26.

＼[3＼]李珍萍.最短時(shí)限運(yùn)輸問題的解法＼[J＼].中國管理科學(xué)，2001，9（1）：50-56.

＼[4＼]李引珍，郭耀煌.一類帶時(shí)間約束指派問題的分枝定界算法＼[J＼].系統(tǒng)工程理論與實(shí)踐，2005，25（6）：39-42，75.

＼[5＼]D W PENTICO. Assignment problems： a golden anniversary survey ＼[J＼]. European Journal of Operational Research， 2007， 176（2）： 774-783.

＼[6＼]A J WOODCOCK， J M WILSON. A hybrid tabu search / branch bound approach to solving the generalized assignment problem ＼[J＼]. European Journal of Operational Research， 2010， 207（2）： 566-578.

＼[7＼]C H PAPADIMITRIOY， K STEIGLITZ. Combinatorial Optimization： Algorithms and Complexity ＼[M＼]. New Jersey： PrenticeHall，1982.

＼[8＼]R K AHJUA，T L MAGNANTI，J B ORLIN. Network flows： Theory， Algorithms，and Applications ＼[M＼]. New Jersey：PrenticeHall，1993.

＼[9＼]T C HU. Combinatorial Algorithms ＼[M＼]. Massachusetts： AddisonWesley，1982.

＼[10＼]M R GAREY， D S JOHNSON. Computers and intractability： a guide to the theory of NPcompletemess ＼[M＼].San Francisco： Freeman，1979.

＼[11＼]M PINEDO. Scheduling： theory，algorithms，and systems ＼[M＼]. New Jersey： PrenticeHall，1995.