| 1. |
- Amankwah, Henry, et al.
(författare)
-
Open-Pit Production Scheduling - Suggestions for Lagrangian Dual Heuristic and Time Aggregation Approaches
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Open-pit production scheduling deals with the problem of deciding what and when to mine from an open-pit, given potential profits of the different fractions of the mining volume, pit-slope restrictions, and mining capacity restrictions for successive time periods. We give suggestions for Lagrangian dual heuristic approaches for the open-pit production scheduling problem. First, the case with a single mining capacity restriction per time period is considered. For this case, linear programming relaxations are solved to find values of the multipliers for the capacity restrictions, to be used in a Lagrangian relaxation of the constraints. The solution to the relaxed problem will not in general satisfy the capacity restrictions, but can be made feasible by adjusting the multiplier values for one time period at a time. Further, a time aggregation approach is suggested as a way of reducing the computational burden of solving linear programming relaxations, especially for largescale real-life mine problems. For the case with multiple capacity restrictions per time period we apply newly developed conditions for optimality and nearoptimality in general discrete optimization problems to construct a procedure for heuristically constructing near-optimal intermediate pits.
|
|
| 2. |
- Blikstad, Mathias, et al.
(författare)
-
A constraint generation procedure for pre-runtime scheduling of integrated modular avionic systems
- 2017
-
Ingår i: Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems.
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network.While the avionic systems are growing more and more complex, so is the challenge of scheduling them. Scheduling of the system has an important role in the development of new avionic systems since functionality typically is added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, in case this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one.In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20 000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within reasonable time.
|
|
| 3. |
- Blikstad, Mathias, et al.
(författare)
-
An Optimisation Approach for Pre-Runtime Scheduling of Tasks and Communication in an Integrated Modular Avionic System
- 2017
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network.While the avionic systems are growing more and more complex, so is the challenge of scheduling them. Scheduling of the system has an important role in the development of new avionic systems since functionality typically is added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, in case this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one.In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20 000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within reasonable time.
|
|
| 4. |
- Blikstad, Mathias, et al.
(författare)
-
An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system
- 2018
-
Ingår i: Optimization and Engineering. - : Springer Science and Business Media LLC. - 1389-4420 .- 1573-2924. ; 19:4, s. 977-1004
-
Tidskriftsartikel (refereegranskat)abstract
- In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network. While avionic systems are growing more and more complex, so is the challenge of scheduling them. The scheduling of the system has an important role in the development of new avionic systems, since functionality is typically added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, if this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one. In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for the scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20,000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within a reasonable time.
|
|
| 5. |
- Hajizadeh, Roghayeh, 1986-, et al.
(författare)
-
A Dantzig-Wolfe Reformulation for AutomatedAircraft Arrival Scheduling in TMAs
- 2024
-
Ingår i: Proceedings of the 14th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2024. - 9780992998462 ; , s. 268-271
-
Konferensbidrag (refereegranskat)abstract
- In this paper, we introduce a Dantzig-Wolfe reformulation to compute aircraft arrival routes in a terminal maneuvering area (TMA) where the aircraft are flying according to theoptimal continuous-descent-operation (CDO) speed profile with idle thrust. This model assumes fixed entry times for all aircraft and a single separation time that is independent of wake-turbulence categories.Preliminary experiments show that this approach leads to significantly reduced runtimes.Moreover, the results indicate the possiblity of extending the reformulation to the full model and applying it to address additional practical considerations, such as wind effects in the future.
|
|
| 6. |
- Hajizadeh, Roghayeh, 1986-
(författare)
-
Optimization of Snow Removal in Cities
- 2023
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Removing snow in a city is an unavoidable task in Nordic countries like Sweden. A number of streets in an area need to be cleared of snow by a limited number of vehicles and the tours for the vehicles must be planned in order to minimize the time and/or cost. Since the amount of snow can vary significantly from one year to another, the plans/tours of one year cannot be used for the next year. Hence, new tours need to be planned each time. Snow removal can be done in rural or urban areas and in addition during snowfall or after a snowfall. In this thesis, we study urban snow removal after a snowfall. There are different relevant specifics of the urban snow removal problem. For instance, there are different types of streets which need different numbers of sweeps in order to remove the snow. In addition, some tasks must be done before other tasks can be started. This leads to precedence constraints. Furthermore, each vehicle needs a certain time to switch from a task to another task. The problem can be formulated as a huge time-indexed mixed integer programming which often is not directly solvable in practice. The contributions of this thesis include the study of different relaxations and heuristics to find feasible solutions and improve the bounds on the optimal objective function values which are discussed in five papers. Paper I deals with single vehicle snow removal. A branch-and-dive heuristic based on branch-and-bound principles is given in order to improve the solutions and bounds. In Paper II, feasible solutions for the snow removal problem with a limited number of identical vehicles are obtained. First, the work is broken down into smaller parts, one for each vehicle. Based on the obtained allocation, a feasible tour for each single vehicle snow removal is obtained. Finally, combined solution approaches and co-ordination of the vehicles to find a feasible solution for the original problem are discussed. In order to improve the computational efficiency, one can take advantage of the tree structure, since modern real life city networks often contain parts that are trees. In Paper III, tree parts are studied and a tree elimination procedure is given for the snow removal problem, to be used before searching for optimal tours. Two variations encountered in practice for normal streets are compared in Paper IV. The first variant is doing a middle sweep before the two side sweeps and the second one is doing only side sweeps. Paper V studies the problem from modeling perspective. The problem is formulated as a mixed integer programming model and different relaxations of it are investigated. Finally, Lagrangian relaxation of the problem is studied in Paper VI. Different possibilities for Lagrangian relaxations are investigated and subgradient optimization is used to solve the Lagrangian dual.
|
|
| 7. |
- Horn, Matthias, et al.
(författare)
-
A*-based construction of decision diagrams for a prize-collecting scheduling problem
- 2021
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 126
-
Tidskriftsartikel (refereegranskat)abstract
- Decision diagrams (DDs) have proven to be useful tools in combinatorial optimization. Relaxed DDs represent discrete relaxations of problems, can encode essential structural information in a compact form, and may yield strong dual bounds. We propose a novel construction scheme for relaxed multi-valued DDs for a scheduling problem in which a subset of elements has to be selected from a ground set and the selected elements need to be sequenced. The proposed construction scheme builds upon A search guided by a fast-to-calculate problem-specific dual bound heuristic. In contrast to traditional DD compilation methods, the new approach does not rely on a correspondence of DD layers to decision variables. For the considered kind of problem, this implies that multiple nodes representing the same state at different layers can be avoided, and consequently also many redundant isomorphic substructures. For keeping the relaxed DD compact, a new mechanism for merging nodes in a layer-independent way is suggested. For our prize-collecting job sequencing problem, experimental results show that the DDs from our A -based approach provide substantially better bounds while frequently being an order-ofmagnitude smaller than DDs obtained from traditional compilation methods, given about the same time. To obtain a heuristic solution and a corresponding lower bound, we further propose to construct a restricted DD based on the relaxed one, thereby substantially exploiting already gained information. This approach outperforms a standalone restricted DD construction, basic constraint programming and mixed integer linear programming approaches, and a variable neighborhood search in terms of solution quality on most of our benchmark instances.
|
|
| 8. |
- Horn, Matthias, et al.
(författare)
-
A* Search for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources
- 2021
-
Ingår i: Annals of Operations Research. - : SPRINGER. - 0254-5330 .- 1572-9338. ; 302, s. 477-505
-
Tidskriftsartikel (refereegranskat)abstract
- We consider a sequencing problem with time windows, in which a subset of a given set of jobs shall be scheduled. A scheduled job has to execute without preemption and during this time, the job needs both a common resource for a part of the execution as well as a secondary resource for the whole execution time. The common resource is shared by all jobs while a secondary resource is shared only by a subset of the jobs. Each job has one or more time windows and due to these, it is not possible to schedule all jobs. Instead, each job is associated with a prize and the task is to select a subset of jobs which yields a feasible schedule with a maximum sum of prizes. First, we argue that the problem is NP-hard. Then, we present an exact A* algorithm and derive different upper bounds for the total prize; these bounds are based on constraint and Lagrangian relaxations of a linear programming relaxation of a multidimensional knapsack problem. For comparison, a compact mixed integer programming (MIP) model and a constraint programming model are also presented. An extensive experimental evaluation on three types of problem instances shows that the A* algorithm outperforms the other approaches and is able to solve small to medium size instances with up to about 40 jobs to proven optimality. In cases where A* does not prove that an optimal solution is found, the obtained upper bounds are stronger than those of the MIP model.
|
|
| 9. |
|
|
| 10. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
A matheuristic approach to large-scale avionic scheduling
- 2019
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Pre-runtime scheduling of avionic systems is used to ensure that the systems provide the desired functionality at the correct time. This paper considers scheduling of an integrated modular avionic system which from a more general perspective can be seen as a multiprocessor scheduling problem that includes a communication network. The addressed system is practically relevant and the computational evaluations are made on large-scale instances developed together with the industrial partner Saab. A subset of the instances is made publicly available.Our contribution is a matheuristic for solving these large-scale instances and it is obtained by improving the model formulations used in a previously suggested constraint generation procedure and by including an adaptive large neighbourhood search to extend it into a matheuristic. Characteristics of our adaptive large neighbourhood search are that it is made over both discrete and continuous variables and that it needs to balance the search for feasibility and profitable objective value. The repair operation is to apply a mixed-integer programming solver on a model where most of the constraints are treated as soft and a violation of them is instead penalised in the objective function. The largest solved instance, with respect to the number of tasks, has 45 988 tasks and 2 011 communication messages.
|
|
