Improved Hungarian algorithm for assignment problems of serial-parallel systems
| Autor: | Tingpeng Li, Yue Li, Yanling Qian |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Total cost Computer science 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Plan (drawing) Manufacturing systems 01 natural sciences 010201 computation theory & mathematics Order (business) Hungarian algorithm 0202 electrical engineering electronic engineering information engineering Serial system Assignment problem |
| Zdroj: | Journal of Systems Engineering and Electronics. 27:858-870 |
| ISSN: | 1004-4132 |
| DOI: | 10.21629/jsee.2016.04.14 |
| Popis: | In order to overcome the shortcoming of the classical Hungarian algorithm that it can only solve the problems where the total cost is the sum of that of each job, an improved Hungarian algorithm is proposed and used to solve the assignment problem of serial-parallel systems. First of all, by replacing parallel jobs with virtual jobs, the proposed algorithm converts the serial-parallel system into a pure serial system, where the classical Hungarian algorithm can be used to generate a temporal assignment plan via optimization. Afterwards, the assignment plan is validated by checking whether the virtual jobs can be realized by real jobs through local searching. If the assignment plan is not valid, the converted system will be adapted by adjusting the parameters of virtual jobs, and then be optimized again. Through iterative searching, the valid optimal assignment plan can eventually be obtained. To evaluate the proposed algorithm, the valid optimal assignment plan is applied to labor allocation of a manufacturing system which is a typical serial-parallel system. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|