Abstract: The bin packing problem with precedence constraints (BPP-P) is a recently proposed variation of the classical bin packing problem (BPP), which corresponds to a basic model featuring many underlying characteristics of several scheduling and assembly line balancing problems. The formulation builds upon the BPP by incorporating precedence constraints among items, which force successor items to be packed into later bins than their predecessors. In this paper we propose a dynamic programming based heuristic, and a modified exact enumeration procedure to solve the problem. These methods make use of several new lower bounds and dominance rules tailored for the problem in hand. The results of a computational experiment show the effectiveness of the proposed methods, which are able to close all of the previous open instances from the benchmark instance set within very reduced running times. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

Abstract: Supply chain network design aims at the integration of the different actors of a supply chain within a single framework in order to optimise the total profit of the system. In this paper, we consider the integration of line balancing issues within the tactical decisions of the supply chain, and we offer a novel model and a solution approach for the problem. The new approach decomposes the problem into multiple line balancing problems and a mixed integer linear model, which is easier to solve than the previously available non-linear mixed integer formulation. The results show that the new method is able to solve previously studied models within a fraction of the reported running times, and also allows us to solve larger instances than those reported in earlier works. Finally, we also provide some analysis on the influence of the cost structure, the demand and the structure of the assembly process on the final configuration of the assemblies and the distribution network.

Abstract: This paper studies a single machine problem related to the just-In-Time (JIT) production objective in which the goal is to minimize the sum of weighted mean squared deviation of the completion times with respect to a common due date. In order to solve the problem, several structural and dominance properties of the optimal solution are investigated. These properties are then integrated within a branch and-cut approach to solve a time-indexed formulation of the problem. The results of a computational experiment with the proposed algorithm show that the method is able to optimally solve instances with up to 300 jobs within reduced running times, improving other integer programming approaches. (C) 2017 Elsevier B.V. All rights reserved.

Abstract: This work studies an assembly line balancing problem with uncertainty on the task times. In order to deal with the uncertainty, a robust formulation to handle changes in the operation times is put forward. In order to solve the problem, several lower bounds, dominance rules and an enumeration procedure are proposed. These methods are tested in a computational experiment using different instances derived from the literature and then compared to similar previous approaches. The results of the experiment show that the method is able to solve larger instances in shorter running times. Furthermore, the cost of protecting a solution against uncertainty is also investigated. The results highlight that protecting an assembly line against moderate levels of uncertainty can be achieved at the expense of small quantities of additional resources (stations). (C) 2017 Elsevier Ltd. All rights reserved.

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.

Abstract: In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-andprice approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem. (C) 2019 Elsevier Inc. All rights reserved.

Abstract: The objective of territorial design for a distribution company is the definition of geographic areas that group customers. These geographic areas, usually called districts or territories, should comply with operational rules while maximizing potential sales and minimizing incurred costs. Consequently, territorial design can be seen as a clustering problem in which clients are geographically grouped according to certain criteria which usually vary according to specific objectives and requirements (e.g. costs, delivery times, workload, number of clients, etc.). In this work, we provide a novel hybrid approach for territorial design by means of combining a K-means-based approach for clustering construction with an optimization framework. The K-means approach incorporates the novelty of using tour length approximation techniques to satisfy the conditions of a pork and poultry distributor based in the region of Valparaiso in Chile. The resulting method proves to be robust in the experiments performed, and the Valparaiso case study shows significant savings when compared to the original solution used by the company.

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.

Abstract: The simple assembly line balancing problem (SALBP) considers work division among different workstations of a serially arranged assembly process to maximise its efficiency under workload (cumulative) and technological (precedence) constraints. In this work, we consider a variant of the SALBP which allows parallel workstations. To study the effect of parallel stations, we propose a new problem (the parallel station assembly line balancing problem or PSALBP) in which the objective is to minimise the number of parallel stations required to obtain the maximum theoretical efficiency of the assembly process. We study the complexity of the problem and identify a polynomially solvable case. This result is then used as a building block for the development of a heuristic solution procedure. Finally, we carry out a computational experiment to identify the characteristics of assembly lines that may benefit from station paralleling and to evaluate the performance of the proposed heuristic.

Abstract: In recent years, a wide range of techniques has been developed to predict electoral results and to measure the influence of different factors in these results. In this paper, we analyze the influence of the political profile of candidates (characterized by personal and political features) and their campaign effort (characterized by electoral expenditure and by territorial deployment strategies retrieved from social networks activity) on the electoral results. This analysis is carried out by using three of the most frequent data analyitcs algorithms in the literature. For our analysis, we consider the 2017 Parliamentary elections in Chile, which are the first elections after a major reform of the electoral system, that encompassed a transition from a binomial to a proportional system, a modification of the districts' structure, an increase in the number of seats, and the requirement of gender parity in the lists of the different coalitions. The obtained results reveal that, regardless of the political coalition, the electoral experience of candidates, in particular in the same seat they are running for (even when the corresponding district is modified), is by large the most influential factor to explain the electoral results. However, the attained results show that the influence of other features, such as campaign expenditures, depends on the political coalition. Additionally, by means of a simulation procedure, we show how different levels of territorial deployment efforts might impact on the results of candidates. This procedure could be used by parties and coalitions when planning their campaign strategies.