Balancing reconfigurable machining lines via a set partitioning model

Abstract

We consider the problem of constructing an optimal machining line as a sequence of workstations performing specific sets of operations. The line is required to satisfy the given precedence order on operations, inclusion, exclusion and accessibility constraints. The cycle times of workstations are computed taking into account the processing and sequence dependent set-up times of operations and must not exceed the given bound. For solving the problem, we propose a reduction of this machining line design problem to a set partitioning type problem. This approach implies generating all possible workstations and, for each workstation, solving a scheduling problem in order to find the sequence of operations which minimises the total set-up time. To do this, a dynamic programming algorithm is developed. Several preprocessing procedures are suggested to reduce the number of workstations. A set of exact algorithms are proposed to solve the obtained set partitioning type problem: a constraint generation, a branch and cut, and a parallel branch and cut algorithms. Our experimental investigation demonstrated that the proposed method achieves a significant improvement in CPU times over those required by a previous study that is based on a different model formulation, and also, that the proposed method is able to solve large-sized problem instances.

Keywords:

• reconfigurable machining line
• line balancing
• sequence dependent set-up times
• dynamic programming
• constraints generation
• branch and cut
• parallel computing

Acknowledgements

The research was partially supported by the Region Rhone-Alps government (Project EuroLean of cluster GOSPI), as well as by Labex IMobS3, European project AmePLM and by Russian Foundation for Basic Research Grant 12-01-00122.