A Determinant Elimination Method for Bottleneck Assignment and Generalized Assignment Problems

Wen Bo Wu; Yu Fu Jia; Hong Xing Sun

doi:10.4028/www.scientific.net/AMM.239-240.1522

Paper Titles

A Joint Energy Consumption Optimization Algorithm for Hybrid Air-Cushion Vehicles
p.1501

A Novel Grid Phase Estimating Algorithm Based on BP Neutral Network
p.1507

The Study on Convergence and Convergence Rate of Genetic Algorithm Based on an Absorbing Markov Chain
p.1511

Fuzzy-Neural Networks Based on Subtractive Clustering and its Applications in Soft Sensor
p.1516

A Determinant Elimination Method for Bottleneck Assignment and Generalized Assignment Problems
p.1522

An Improved Quantum-Inspired Evolutionary Algorithm Based on P Systems with a Dynamic Membrane Structure for Knapsack Problems
p.1528

Classification of Chinese Herbal Medicine Based on Improved LDA Algorithm Using Machine Olfaction
p.1532

A Kind of Index Technology Based on Binary Tree Efficient Space
p.1537

A Parallel BP Neural Network Based on the FPGA
p.1541

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 239-240A Determinant Elimination Method for Bottleneck...

A Determinant Elimination Method for Bottleneck Assignment and Generalized Assignment Problems

Abstract:

The bottleneck assignment (BA) and the generalized assignment (GA) problems and their exact solutions are explored in this paper. Firstly, a determinant elimination (DE) method is proposed based on the discussion of the time and space complexity of the enumeration method for both BA and GA problems. The optimization algorithm to the pre-assignment problem is then discussed and the adjusting and transformation to the cost matrix is adopted to reduce the computational complexity of the DE method. Finally, a synthesis method for both BA and GA problems is presented. The numerical experiments are carried out and the results indicate that the proposed method is feasible and of high efficiency.

You might also be interested in these eBooks

Measurement Technology and its Application

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 239-240)

Pages:

1522-1527

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.239-240.1522

Citation:

Cite this paper

Online since:

December 2012

Authors:

Wen Bo Wu, Yu Fu Jia, Hong Xing Sun

Keywords:

Bottleneck Assignment, Determinant Elimination, Generalized Assignment Problem, Optimization Algorithm, Pre-Assignment Problem

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Xu Wang-bao, Chen Xue-bo. Artificial moment method for swarm-robot formation control. Science in China Series F: Information Science, 2008, 5(10): 1521-1531.

DOI: 10.1007/s11432-008-0084-3

Google Scholar

[2] Xu Wangbao, Chen Xuebo, Zhang Guoqiong. Model and application of swarm-robot systems based on distance-optimization correspondence. Proceedings of WCICA, Chongqing, 2008: 2625-2630.

Google Scholar

[3] Garfinkel, R. S. An improved algorithm for the bottleneck assignment problem. Operations Research. 1971, 19: 1747-1751.

DOI: 10.1287/opre.19.7.1747

Google Scholar

[4] Kuhn H. W. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quart, 1955, 12(2): 83-87.

Google Scholar

[5] Gu Daquan, Zuo Li, Hou Taiping and Wang Yinhu. Existing Problem and Improvement of Hungary Arithmetic. Microcomputer Development. 2003, 13(4): 76-74.

Google Scholar

[6] Benjamin Lev, Howard J. Weiss. Introduction to mathematical programming. Amsterdam, Holland: North Holland, 1982: 159-161.

Google Scholar

[7] Yin Renkun, Wu Yang and Zhang Jingwei. Research and Application of the Ant Colony Algorithm in the Assignment Problem. Computer Engineering and Science. 2008, 30(4): 43-45.

Google Scholar

[8] Chu P. C., Beaslay J. E. A genetic algorithm for the generalized assignment problem. Computers and Operations Research. 1997, 24(1): 17-23.

Google Scholar

[9] Zhang Yanduo, Lu Jing, Tian Hui. A novel improved adaptive genetic algorithm for the solution to optimal assignment problem. International Journal of Systems and Control. 2007, 2(3): 253-261.

Google Scholar