Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs
Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs
复制标题
DOI：
10.1016/j.omega.2005.01.005
复制
发表时间：
2006-12-01
影响因子：
6.9
通讯作者：
Lambert, AJD
中科院分区：
文献类型：
--
作者：
Lambert, AJD
通过网络表示和随后的数学建模来正式地处理复杂产品的拆卸，旨在选择一个良好或最佳的拆卸操作序列。这是通过启发式、元启发式或数学规划来完成的。与选择近似最优解的启发式和元启发式不同，数学规划保证了全局最优解的选择。如果假定拆解成本与序列无关，这个问题就相对简单了。然而，在实践中，经常会遇到序列相关的拆卸成本，这导致了np -完备性问题。尽管基于两种商品网络流方法等方法可以严格地解决这种受限的非对称旅行销售员问题，但这需要引入整数变量。本文提出了一种改进的双商品网络流方法，减少了整数变量的数量。这适用于可由拆卸优先图表示的产品结构。通过迭代求解二进制整数线性规划问题，证明了整数变量的使用是完全避免的。这似乎比解决相应的整数线性规划问题更有效。在一些案例的基础上证明，与文献中迄今为止讨论的问题相比，这种方法可能为复杂性增加的问题提供精确的解决方案。这对于评估启发式和元启发式方法特别有用。(c) 2005 Elsevier Ltd版权所有。
Disassembling complex products is formally approached via network representation and subsequent mathematical modeling, aimed at selecting a good or optimum sequence of disassembly operations. This is done via heuristics, metaheuristics or mathematical programming. In contrast with heuristics and metaheuristics, which select a near-optimum solution, mathematical programming guarantees the selection of the global optimum. This problem is relatively simple if the disassembly costs can be assumed sequence independent. In practice, however, sequence dependent disassembly costs are frequently encountered, which causes NP-completeness of the problem. Although methods, e.g., based on the two-commodity network flow approach, are available to solve this constrained asymmetric Traveling Salesperson problem rigorously, this requires the introduction of integer variables. In this paper, a modification of the two-commodity network flow approach is proposed, which reduces the number of integer variables. This is applied to product structures that can be represented by a disassembly precedence graph. It is demonstrated that use of integer variables is completely avoided by iteratively solving a binary integer linear programming problem. This appears to be more efficient than solving the corresponding integer linear programming problem. It is demonstrated, on the basis of some cases, that this method might provide the exact solution of problems with increased complexity compared to those discussed so far in the literature. This appears particularly useful for evaluating heuristic and metaheuristic approaches. (c) 2005 Elsevier Ltd. All rights reserved.