Pereira, J., & Ritt, M. (2023). Exact and heuristic methods for a workload allocation problem with chain precedence constraints. Eur. J. Oper. Res., 309(1), 387–398.
Abstract: Industrial manufacturing is often organized in assembly lines where a product is assembled on a se-quence of stations, each of which executes some of the assembly tasks. A line is balanced if the maximum total execution time of any station is minimal. Commonly, the task execution order is constrained by precedences, and task execution times are independent of the station performing the task. Here, we con -sider a recent variation, called the “(Calzedonia) Workload Allocation Problem” (WAP), where the prece-dences form a chain, and the execution time of a task depends on the worker executing it. This problem was recently proposed by Battarra et al. (2020) and it is a special case of the Assembly Line Worker As-signment and Balancing Problem Miralles et al. (2007) where precedence relations are arbitrary. In this paper we consider the computational complexity of the problem and prove its NP-hardness. To solve the problem, we provide different lower bounds and exact and heuristic procedures. The performance of the proposed methods is tested on previously proposed instances and on new, larger instances with the same characteristics. The results show that the proposed methods can solve instances with up to about 40 0 0 tasks and 29 workers, doubling the size of the instances that previously could be solved to optimality.
|
Pereira, J., & Ritt, M. (2022). A note on “Algorithms for the Calzedonia workload allocation problem”. J. Oper. Res. Soc., 73(6), 1420–1422.
Abstract: Battarra et al. recently proposed a novel assembly line balancing problem with applications to the apparel industry, where the tasks are performed in a fixed order. To solve the problem, one has to assign workers and tasks to the workstations with the objective of maximising the throughput of the assembly line. In this paper, we provide dynamic programming formulations for the general problem and some special cases. We then use these formulations to develop an exact solution approach that optimally solves the instances in Battarra et al. within seconds.
|
Pereira, J., Ritt, M., & Vasquez, O. C. (2018). A memetic algorithm for the cost-oriented robotic assembly line balancing problem. Comput. Oper. Res., 99, 249–261.
Abstract: In order to minimize costs, manufacturing companies have been relying on assembly lines for the mass production of commodity goods. Among other issues, the successful operation of an assembly line requires balancing work among the stations of the line in order to maximize its efficiency, a problem known in the literature as the assembly line balancing problem, ALBP. In this work, we consider an ALBP in which task assignment and equipment decisions are jointly considered, a problem that has been denoted as the robotic ALBP. Moreover, we focus on the case in which equipment has different costs, leading to a cost-oriented formulation. In order to solve the problem, which we denote as the cost-oriented robotic assembly line balancing problem, cRALBP, a hybrid metaheuristic is proposed. The metaheuristic embeds results obtained for two special cases of the problem within a genetic algorithm in order to obtain a memetic algorithm, applicable to the general problem. An extensive computational experiment shows the advantages of the hybrid approach and how each of the components of the algorithm contributes to the overall ability of the method to obtain good solutions. (C) 2018 Elsevier Ltd. All rights reserved.
|
Ritt, M., & Pereira, J. (2020). Heuristic and exact algorithms for minimum-weight non-spanning arborescences. Eur. J. Oper. Res., 287(1), 61–75.
Abstract: We address the problem of finding an arborescence of minimum total edge weight rooted at a given vertex in a directed, edge-weighted graph. If the arborescence must span all vertices the problem is solvable in polynomial time, but the non-spanning version is NP-hard. We propose reduction rules which determine vertices that are required or can be excluded from optimal solutions, a modification of Edmonds algorithm to construct arborescences that span a given set of selected vertices, and embed this procedure into an iterated local search for good vertex selections. Moreover, we propose a cutset-based integer linear programming formulation, provide different linear relaxations to reduce the number of variables in the model and solve the reduced model using a branch-and-cut approach. We give extensive computational results showing that both the heuristic and the exact methods are effective and obtain better solutions on instances from the literature than existing approaches, often in much less time. (C) 2020 Elsevier B.V. All rights reserved.
|
