Scheduling with Two Types of Penalties Under Uncertainty and Its Application to Maintenance Planning
- Publication Type:
- Thesis
- Issue Date:
- 2022
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
This thesis studies a number of combinatorial optimization problems with uncertainty, which have applications in the fields of maintenance planning. In particulars, the research in Chapter 3 was conducted as part of the project with a major maintenance center, and Chapter 4 considers a maintenance planning problem faced by a French electricity transmission
system operator. The problem was subject of the recent ROADEF/EURO challenge 2020 competition.
This thesis is comprised of several chapters. Chapters 1 and 2 introduce the thesis topics and provide the literature survey, respectively. Chapter 3 focuses on developing maintenance plans for a fleet of passenger trains. The key feature of our model is that it considers the uncertain duration of maintenance, the center’s engineering restrictions, and the rail operator’s operational requirements. We propose a Genetic Algorithm, an Iterated Local Search, and a hybrid two-stage optimization procedure that combines Jensen’s Inequality based relaxation with Iterated Local Search to solve the problem.
Chapter 4 focuses on improving the utilization of resources when scheduling jobs that share multiple resources. The motivation for this research comes from scheduling problems that arise in healthcare and rolling stock maintenance services. The problem is distinct from the problem in Chapter 3: the processing of each job requires several types of resources; and the penalty for capacity violation is calculated based on not only the capacity of resource but also an upper bound on the resource expansion. The solution approaches presented in Chapter 3 cannot be directly applied to this problem because their performances rely on having a good-quality initial solution produced by an exact method. We instead propose a Genetic Algorithm enhanced by local search and present a method for assessing solution quality based on Sample Average Approximation.
Chapter 5 is concerned with a large-scale planning problem arising in the maintenance of power distribution grid. Due to the extreme hazards involved when performing maintenance operations on the high-voltage lines, individual transmission lines have to be shut down for the duration of maintenance. The goal is to build intervention schedules that minimize the impact of planned outages on the reliability of power networks. A unique feature of this problem is that the duration, resource consumption, and risk value of an intervention depend on when it starts. Using the problem instances provided by the ROADEF competition, we demonstrated the effectiveness of the proposed Iterated Local Search with self-adaptive perturbation and
obtained the 2nd prize.
Please use this identifier to cite or link to this item: