Multi-Task Assignment 0-1 Programming Model and Algorithm Based on the Improved Contract Net Protocol

Abstract:

For the problem of multi-task assignment based on the contract net protocol, this paper improved the traditional contract net protocol after analyzing its defects ,such as broad bidding scope and low efficiency etc. The research proposed a method of screening the bidders for each task by using distance matrix in task distribution ,employed the 0-1 programming model established to determine the successful bidders for each task in bidding process. Meanwhile, the study applied the auction mechanism to realize the dynamic assignment of multi-task, provided a concrete model algorithm and analyzed the performances of the algorithm proposed as well. The results show that the model algorithm effectively improves the overall performances of the task assignment system.

• Periodical: Applied Mechanics and Materials (Volumes 568-570)
• Pages: 1376-1383
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.568-570.1376
• Online since: June 2014
• Authors: Hong Wang, Dan Luo, Fan Zhang, De Gang Wang
• Keywords: 0-1 Programming Model, Auction Mechanism, Distance Matrix, Improved Contract Net Protocol, Multi-Task Assignment

References

[1] Smith R G. : IEEE Trans on Computer, Vol. 29C-12( 1980), pp.1104-1113.

[2] Cao Z Q, Zhang B and Tan M. : Robots, Vol. 23-5(2001) pp.450-454, In Chinese.

[3] DIAS M B, ROBERT Z, NIDHI K, et al.: Proceeding of the IEEE, Vol. 94-7(2006) pp.1257-1270.

[4] BRIAN P G, MAJA J M.: IEEE Trans on Robotics and Automation, Vol. 18-5(2002) pp.758-768.

[5] Thistle J G.: Discrete Event Dynamic Systems: Theory and Applications, Vol. 10-1(2000) pp.131-156.

[6] Gao Z J, Yan G Z and Ding G Q.: Computer Engineering, Vol. 31-10(2005) pp.19-21. In Chinese.