有負荷約束的指派問題

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

關鍵詞組合優化；指派問題；負荷約束；算法分析

1引言

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

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

2數學模型的討論

5結論

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

既然有負荷約束的指派問題是困難問題， 在實用上可以采取一些簡化措施. 例如取消整值約束， 用線性規劃求分數最優解； 或者加上匹配約束（ 不一定一對一）， 轉化為運輸或網絡流問題.

參考文獻

[1]王寅初.能力受限的運輸問題的算法＼[J＼]. 數值計算與計算機應用，1981， 2（3）： 143-148.

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

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

＼[4＼]李引珍，郭耀煌.一類帶時間約束指派問題的分枝定界算法＼[J＼].系統工程理論與實踐，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.