School of Mathematics and Statistics - Theses
Permanent URI for this collection
Search Results
1 - 3 of 3
-
ItemEconomic and Social Aspects of Heterogeneous Assembly Lines( 2023-10)Assembly lines with heterogeneous resources are widely present in manufacturing industries. The procedures to build a broad range of products employ various skilled workers or robots equipped with diverse tools. In order to remain competitive, it is crucial for a company to efficiently meet the market demand and reduce expenses at the same time. Since resources such as facilities, workforce wages, machines, and tools are quite costly, this requirement gives rise to the need to design economically viable lines. Conversely, we must take a myriad of technological and physical factors into account as well. For instance, assembly lines might appear in straight or U-shaped layouts, have continuous/(a)synchronous paces, operate with two-sided or multi-manned stations, manufacture multiple products in a mixed-model fashion, and employ a specialised workforce with different capabilities. Furthermore, as demonstrated by the COVID-19 pandemic scenario, possessing some resiliency for quick adaptations is a desirable feature. In addition, taking good care of employees fosters job satisfaction and reduces ergonomic risks, avoiding unnecessary turnover. Finally, it is also manageable to positively contribute towards societal issues, such as integrating workers with disabilities among ``conventional'' or robotic ones. Therefore, this thesis proposes three problems to investigate the complexities of economic and social aspects found in assembly lines with resource and workforce heterogeneity: the Resource-Constrained Assembly Line Balancing Problem (RCALBP), the Assembly Line Worker Assignment and Rebalancing Problem (ALWARP), and the Multi-manned Assembly Line Worker Integration and Balancing Problem (MALWIBP) are herein studied and discussed. We develop Mixed-Integer Linear Programming (MILP) formulations for all three problems. They either aim at minimising the cycle time given limited resources or wages and facilities costs at the desired production rate. Moreover, a state-of-the-art survey on Benders Decomposition (BD) approaches applied to the Assembly Line Balancing Problem (ALBP) is also presented. In the RCALBP and ALWARP, we explore resource and workforce heterogeneity appearing in real-world industrial applications. The former minimises cycle time given a limited number of stations and resources, whilst the latter aims at preserving jobs while minimising labour costs. We consider dedicated and alternative resource types for tasks, take scenarios with falling demands into account, and impose regularity metrics on workload reductions. These problems are mathematically modelled within a MILP framework, and benchmark instances are solved in commercial solvers along with case studies. As both RCALBP and ALWARP instances have very restrictive constraints, we can optimally solve large cases with commercial solvers by making problem-specific adjustments in the parameter tuning, as well as incorporating strong valid inequalities, variable reduction, and lower bounding techniques into the formulation. However, when the problem grows too complex, we may have to resort to heuristic approaches to obtain near-optimal solutions in a reduced computational time. The MALWIBP examines the balancing of assembly lines with multi-manned stations running on a heterogeneous workforce. This union creates a highly combinatorial problem: we must further link the already coupled decisions on assigning tasks to heterogeneous workers and workers to stations with task scheduling assessments. Thus, two heuristic solution procedures are developed, which tackle the problem with a hierarchical decomposition approach, showing that multi-operated stations can reduce the assembly line's length even in the presence of a heterogeneous workforce. Lastly, inspired by the decomposition methods realm, a well-established exact strategy for solving large optimisation problems is surveyed. More specifically, a comprehensive literature review on applying classical and logic-based BD approaches to ALBP variations is inspected. As several literature contributions have recently employed BD algorithms to tackle ALBPs with practical extensions, this survey attempts to consolidate the current body of knowledge by providing a detailed literature review on each application's particular aspects and ideas. We summarise existing gaps to offer insights into the BD efficiency for combinatorial problems such as ALBPs from a managerial perspective and indicate a shift in the research trend. In concluding remarks, the contributions of the developed works are summarised and future research avenues are suggested for all problems.
-
ItemMathematical model and heuristics for relief transportation in the aftermath of sudden-onset natural disasters( 2023-08)Floods and landslides are the most common natural disasters in Brazil. These disasters can have a long-term impact on the affected communities and leave whole populations in need of support. We study the efficient transportation of relief goods from depots to distribution points in the aftermath of such disasters. Although the field of humanitarian logistics has received increased attention in Operations Research, recent reviews highlighted gaps related to unrealistic assumptions, such as static post-disaster travel times, demands, and supply availability. As predicting future information in humanitarian logistics is harder than in its commercial counterpart, more research that accounts for information updates and dynamic parameters is needed. We addressed these gaps by proposing a more realistic model in order to study practical aspects of relief distribution, hoping to contribute to decision making in the real world. As black-box solvers can only handle very small instances of our proposed mathematical model, we developed heuristics that work within a fix-and-optimise framework, allowing for information updates in a rolling planning horizon. The proposed heuristics could adequately solve real-sized instances, enabling a comparison between deterministic and dynamic data approaches. Fairness is another key characteristic in humanitarian logistics which sets it apart from its commercial counterpart. To ensure fairness, we integrated a priority index in our constructive heuristic that prioritises underserved nodes over densely populated ones. In the improvement heuristics, fairness is considered through inequity penalties. Results indicate that fairness can be enforced without significantly increasing transportation costs.
-
ItemStress testing mixed integer programming solvers through new test instance generation methods( 2019)Optimisation algorithms require careful tuning and analysis to perform well in practice. Their performance is strongly affected by algorithm parameter choices, software, and hardware and must be analysed empirically. To conduct such analysis, researchers and developers require high-quality libraries of test instances. Improving the diversity of these test sets is essential to driving the development of well-tested algorithms. This thesis is focused on producing synthetic test sets for Mixed Integer Programming (MIP) solvers. Synthetic data should be carefully designed to be unbiased, diverse with respect to measurable features of instances, have tunable properties to replicate real-world problems, and challenge the vast array of algorithms available. This thesis outlines a framework, methods and algorithms developed to ensure these requirements can be met with synthetically generated data for a given problem. Over many years of development, MIP solvers have become increasingly complex. Their overall performance depends on the interactions of many different components. To cope with this complexity, we propose several extensions over existing approaches to generating optimisation test cases. First, we develop alternative encodings for problem instances which restrict consideration to relevant instances. This approach provides more control over instance features and reduces the computational effort required when we have to resort to search-based generation approaches. Second, we consider more detailed performance metrics for MIP solvers in order to produce test cases which are not only challenging but from which useful insights can be gained. This work makes several key contributions: 1. Performance metrics are identified which are relevant to component algorithms in MIP solvers. This helps to define a more comprehensive performance metric space which looks beyond benchmarking statistics such as CPU time required to solve a problem. Using these more detailed performance metrics we aim to produce explainable and insightful predictions of algorithm performance in terms of instance features. 2. A framework is developed for encoding problem instances to support the design of new instance generators. The concepts of completeness and correctness defined in this framework guide the design process and ensure all problem instances of potential interest are captured in the scheme. Instance encodings can be generalised to develop search algorithms in problem space with the same guarantees as the generator. 3. Using this framework new generators are defined for LP and MIP instances which control feasibility and boundedness of the LP relaxation, and integer feasibility of the resulting MIP. Key features of the LP relaxation solution, which are directly controlled by the generator, are shown to affect problem difficulty in our analysis of the results. The encodings used to control these properties are extended into problem space search operators to generate further instances which discriminate between solver configurations. This work represents the early stages of an iterative methodology required to generate diverse test sets which continue to challenge the state of the art. The framework, algorithms and codes developed in this thesis are intended to support continuing development in this area.