An optimization-based heuristic for the robotic cell problem |
| |
Authors: | Jacques Carlier Mohamed Haouari Mohamed Kharbeche Aziz Moukrim |
| |
Institution: | aUMR CNRS 6599 Heudiasyc, Centre de Recherches de Royallieu, Université de Technologie de Compiègne, France;bDepartment of Industrial Engineering, Faculty of Engineering, Ozyegin University, Istanbul, Turkey;cPrincess Fatimah Alnijris’ Research Chair for AMT, College of Engineering, King Saud University, Saudi Arabia;dROI – Combinatorial Optimization Research Group, Ecole Polytechnique de Tunisie, 2078 La Marsa, Tunisia |
| |
Abstract: | This study investigates an optimization-based heuristic for the robotic cell problem. This problem arises in automated cells and is a complex flow shop problem with a single transportation robot and a blocking constraint. We propose an approximate decomposition algorithm. The proposed approach breaks the problem into two scheduling problems that are solved sequentially: a flow shop problem with additional constraints (blocking and transportation times) and a single machine problem with precedence constraints, time lags, and setup times. For each of these problems, we propose an exact branch-and-bound algorithm. Also, we describe a genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that the proposed optimization-based approach delivers high-quality solutions and consistently outperforms the genetic algorithm. However, the genetic algorithm delivers reasonably good solutions while requiring significantly shorter CPU times. |
| |
Keywords: | Flow shop Robotic cell Blocking Branch-and-bound Genetic algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|