The Study On The Algorithm And Application Of A Special Kind Of Assignment Problem

Assignment problem (AP) is a classical model of operations research. A great number of the present researches are focused on the non-standard-form assignment problem generated in the practical requirement. This paper studied a kind of special constrained assignment problem. The corresponding mathematic model is built and the solutions are proposed in this paper.The general method adopted by other non-standard-form assignment problem can not be feasible to this problem because of its special constraint. An m-accacmutative-carry implicit enumeration algorithm is designed to obtain the optimal solutions according to the distinction of the problem. The attributes of the optimal solution are concluded by analyzing the test results using the algorithm above. The partheno-genetic algorithm (PGA) is used to obtain the solution which can't obtained by the implicit enumeration algorithm when there are too much variables in the model. The character-position-based ways of generating population and the doing PGA operator are proposed by the distinction of the constraints. An application is illustrated by the algorithm's succeeding in pratical case.