| Article ID: | iaor19941810 |
| Country: | South Korea |
| Volume: | 18 |
| Issue: | 3 |
| Start Page Number: | 13 |
| End Page Number: | 34 |
| Publication Date: | Dec 1993 |
| Journal: | Journal of the Korean ORMS Society |
| Authors: | Lee Hochang |
| Keywords: | Lagrangean methods |
By operating on many parts of a software system concurrently, the parallel processing computers may provide several orders of magnitude more computing power than traditional serial computers. If the Lagrangean approximation procedure is applied to a large scale manufacturing problem which is decomposable into many subproblems, the procedure is a perfect candidate for parallel processing. By distributing Lagrangean subproblems for given multiplier to multiple processors, concurrently running processors and modifying Lagrangean multipliers at the end of each iteration of a subgradient method, a parallel processing of a Lagrangean approximation procedure may provide a significant speedup. The purpose of this research is to investigate the potential of the parallelized Lagrangean approximation procedure (PLAP) for certain combinatorial optimization problems in manufacturing systems. The framework of a PLAP is proposed for some combinatorial manufacturing problems which are decomposable into well-structured subproblems. The synchronous PLAP for the multistage dynamic lot-sizing problem is implemented on a parallel computer Alliant FX/4 and its computational experience is reported as a promising application of vector-concurrent computing. [In Korean.]