Klein, Nicklas (2025). Models and Algorithms for Scheduling and Resource Allocation. (Thesis). Universität Bern, Bern
|
Text
25klein_n.pdf - Thesis Available under License Creative Commons: Attribution (CC-BY 4.0). Download (655kB) | Preview |
Abstract
Companies today are confronted with an increasingly complex and competitive business environment. Emerging trends such as rising energy costs, stricter sustainability requirements, and a growing shortage of skilled workers have led to an increased scarcity of resources. As a result, it is essential for companies to plan their operations and allocate their resources in the most efficient way. The planning process of allocating scarce resources to operations over time is called scheduling (cf., e.g., Pinedo, 2022). This planning process plays a vital role in many companies across a diverse range of industries, such as construction companies that allocate workers and equipment to various activities within a construction project, software companies that allocate developers and hardware to develop new software, or semiconductor manufacturing companies that allocate the machines in their facility to produce wafers. For many companies, such as the ones described above, optimized scheduling can lead to shorter construction times, faster product launches, and increased output through more efficient use of scarce resources. Optimizing such scheduling and resource-allocation decisions in practice is often highly challenging, i.e., no efficient algorithm or closed-form expression to determine an optimal schedule is known for many such problems. Considerable research effort has been dedicated to addressing these challenges, and many models and algorithms have been developed that either exhibit a strong performance for specific scheduling problems, or offer flexibility to address a wide range of scheduling problems. However, these methods frequently struggle to achieve both of these strengths simultaneously, which remains a major challenge in the literature. Consequently, developing novel models and algorithms for scheduling and resource allocation problems that combine both of these strengths is essential for enhancing cost efficiency and ensuring the profitability of companies. Two common approaches for solving scheduling problems in practice are mathematical programming (cf., e.g., Bixby & Rothberg, 2007, Achterberg et al., 2020), and priority rules (also referred to as dispatching rules, cf., e.g., Haupt, 1989, Pinedo, 2022). When applying an optimization approach based on mathematical programming, the planning problem is formulated as a mathematical model, which comprises decisions to be made (e.g., when to start an activity within a project), constraints these decisions must comply with (e.g., the availability of workers), and an objective function that should be minimized (e.g., project completion time) or maximized (e.g., factory output). This model is then solved using software known as a mathematical programming solver for given data that is specific to the planning situation at hand. For mathematical models to be effective in practical scheduling, they must be flexible to accommodate the dynamically changing requirements of companies, such as the varying conditions between different construction projects or the software needs of clients in different industries. At the same time, solver performance can vary significantly with the model formulation chosen (cf., e.g., Kon´e et al., 2011, Vielma, 2015), highlighting the need to develop and evaluate flexible mathematical models with good computational performance for scheduling problems. When applying an optimization approach based on priority rules, the operations are sorted according to a predefined measure and subsequently scheduled in that order. In a semiconductor manufacturing company, the different wafers may be scheduled according to the ratio of their importance to their processing time requirement. The major advantages of this approach are its simplicity and explainability, which make it highly scalable and easily applicable in practice. Despite this simplicity, well-designed priority rules frequently devise good schedules regarding various objectives, highlighting the need to develop, evaluate, and apply novel priority rules to emerging scheduling problems. This thesis is composed of three papers on modeling and solving challenging scheduling problems. We address two project scheduling problems and one production scheduling problem. For the project scheduling problems, we develop novel mathematical models that combine flexibility to handle different types of activities and resource constraints with simplicity and interpretability in practical project contexts. In extensive computational experiments, these models consistently outperform the state-of-the-art models across a wide range of problem instances. For the production scheduling problem, we propose novel priority rules and dedicated algorithms. Through a theoretical analysis, we show that these priority rules and algorithms are guaranteed to devise optimal or near-optimal schedules for all problem instances. The models and algorithms developed in this thesis have in common that they are flexible, with computational and theoretical analyses demonstrating a relatively good performance across problem instances with varying characteristics. In the first paper, we consider the scheduling of a project, where the project activities require time and capacities of renewable resources, e.g., personnel or equipment, and of storage resources, e.g., funds, energy, or utilities (cf., e.g., Agha et al., 2010), for execution. The problem comprises determining the start times of all project activities such that the project completion time is minimized, while completion-start precedences between pairs of activities are respected, the availabilities of the renewable resources are never exceeded, and the stock of all storage resources never falls below a given threshold. Such a problem arises, e.g., in a long-term construction project, where sufficient personnel and equipment must be allocated to the project activities (renewable resources), but also project milestones, frequently linked to interim payments, must be achieved regularly to ensure the company’s liquidity. For this problem, we propose a novel mathematical model based on a novel type of start-start sequencing variables. The main advantages of this sequence-based model are that its variables can be easily interpreted in the problem context and are sufficient to simultaneously capture the renewable and storage resources, whereas all reference models require additional variables to capture the storage resources. In a computational experiment, the proposed model consistently outperformed the state-of-the-art models for a wide range of benchmark instances. In particular, the model consistently devised project schedules with a relatively short project duration for the most challenging problem instances, for which all reference models struggled to devise resource-feasible project schedules. In the second paper, we extend the sequence-based model to address a project scheduling problem where the project activities can be executed in multiple modes. These execution modes represent different ways to execute a project activity and can reflect trade-offs between execution time and resource requirements, e.g., a software company can either assign a task to a junior developer or to a senior developer who can complete the task faster but is unavailable for other tasks during that time. In a computational experiment, the sequence-based model outperformed the state-of-the-art models for a wide range of benchmark instances, especially instances comprising a relatively large number of project activities, resources, and execution modes, for which all reference models struggle to devise resource-feasible project schedules with a short project duration. The obtained results demonstrate that the developed sequence-based model provides great flexibility to address a wide range of challenging project scheduling problems, while exhibiting a favorable computational performance compared to the state-of-the-art models. In the third paper, we consider a production scheduling problem where the products require multiple loops through a flow line. The planning problem is to schedule all required loops of all products while minimizing the total weighted completion time of the products. This problem frequently arises in semiconductor manufacturing, where multiple layers of material are sequentially placed on the same wafer. Since some of the machines that are required to produce these wafers cost more than 100 million US Dollars (cf., e.g., Tembey et al., 2023), it is essential that these machines are utilized in the most efficient way. Therefore, products in different stages of the production cycle must be produced on the same machines, which poses significant challenges. For this problem, we propose a novel and simple priority rule that can be used to devise feasible production schedules in a relatively short time. We show that, under certain conditions, this priority rule can even devise optimal schedules. Furthermore, we show that the theoretical worst-case deviation from the optimum is about 20%. This analysis of the worst-case deviation guarantees manufacturers using this priority rule in practice that the rule will devise near-optimal production schedules regardless of potential variations in product or factory characteristics. In a computational experiment, we observed that despite its simplicity, the total weighted completion time of schedules devised using this rule is, on average, only about 1% larger than the optimum. Finally, we present an exact algorithm and an approximation scheme for this problem, which can be used to devise schedules that are arbitrarily close to the optimum. While this thesis focuses on three specific scheduling problems, the proposed models and priority rules can be adapted, with minor modifications, to address related scheduling problems. An example of such a related problem is resource-constrained project scheduling with minimal and maximal time lags that generalize the precedence relations between pairs of activities (cf., e.g., de Azevedo et al., 2021). For this problem, the novel start-start sequencing variables can be used to efficiently model positive time lags between pairs of activities, which may enhance the computational performance of solvers. Another related problem is the resource investment problem (cf., e.g., Zhu et al., 2017). In this problem, a project schedule is sought that completes the project within a given deadline while minimizing the investment cost for renewable resources. A third related problem are stochastic flow shops with reentry. In this problem, the number of passes through the flow line is not deterministically known in advance, but each time a product has passed through the flow line, it has a probability of reentry, e.g., to repair a detected defect. For this problem, a variant of the proposed priority rule that takes into account the expected number of passes through the flow line may minimize the total expected completion time of the products.
| Item Type: | Thesis |
|---|---|
| Dissertation Type: | Cumulative |
| Date of Defense: | 20 February 2025 |
| Subjects: | 600 Technology > 650 Management & public relations |
| Institute / Center: | 03 Faculty of Business, Economics and Social Sciences |
| Depositing User: | Hammer Igor |
| Date Deposited: | 19 Sep 2025 09:28 |
| Last Modified: | 19 Sep 2025 09:29 |
| URI: | https://boristheses.unibe.ch/id/eprint/6717 |
Actions (login required)
 |
View Item |