A heuristic multi-start decomposition approach for optimal design of serial machining lines |
| |
Authors: | O Guschinskaya A Dolgui N Guschinsky G Levin |
| |
Institution: | 1. Ecole des Mines de Saint Etienne, 158, cours Fauriel 42023 Saint Etienne Cedex 2, France;2. United Institute of Informatics Problems, Surganov Str, 6, 220012 Minsk, Belarus |
| |
Abstract: | We study an optimal design problem for serial machining lines. Such lines consist of a sequence of stations. At every station, the operations to manufacture a product are grouped into blocks. The operations within each block are performed simultaneously by the same spindle head and the blocks of the same station are executed sequentially. The inclusion and exclusion constraints for combining operations into blocks and stations as well as the precedence constraints on the set of operations are given. The problem is to group the operations into blocks and stations minimizing the total line cost. A feasible solution must respect the given cycle time and all given constraints. In this paper, a heuristic multi-start decomposition approach is proposed. It utilizes a decomposition of the initial problem into several sub-problems on the basis of a heuristic solution. Then each obtained sub-problem is solved by an exact algorithm. This procedure is repeated many times, each time it starts with a new heuristic solution. Computational tests show that the proposed approach outperforms simple heuristic algorithms for large-scale problems. |
| |
Keywords: | Machining line Logical layout design Combinatorial optimization Graph approach Mixed integer programming Decomposition Heuristics |
本文献已被 ScienceDirect 等数据库收录! |
|