Lagrangian Relaxation for Stochastic Disassembly Line Balancing Problem

International audienceThis study deals with the problem of profit oriented disassembly line balancing considering partial disassembly, presence of hazardous parts and uncertainty of task times. The objective of this paper is to design a serial line that obtains the maximum profit under uncertainty. Tasks of the best selected disassembly alternative are to be assigned to a sequence of workstations while respecting precedence and cycle time constraints. The line profit is computed as the difference between the positive revenue generated by the retrieved parts of the End of Life (EOL) product and the line operation cost. The latter includes the workstation operation costs and additional costs for handling hazardous parts. Task times are assumed to be random variables with known probability distributions. An AND/OR graph is used to model the disassembly alternatives and the precedence relationships among tasks and subassemblies. To cope with uncertainties, a solution method based on Lagrangian relaxation and Monte Carlo sampling technique is developed. To show the relevance and applicability of the proposed method, it is evaluated on a set of problem instances from the literature