| 1. |
- 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.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- 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.
|
|
| 5. |
|
|
| 6. |
- 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.
|
|
| 7. |
|
|
| 8. |
- Karlsson, Emil, et al.
(författare)
-
Explicit modelling of multiple intervals in a constraint generation procedure for multiprocessor scheduling
- 2017
-
Ingår i: Operations Research Proceedings 2017. - Cham : Springer. - 9783319899190 - 9783319899206 ; , s. 567-572
-
Konferensbidrag (refereegranskat)abstract
- Multiprocessor scheduling is a well studied NP-hard optimisation problem that occurs in variety of forms. The focus of this paper is explicit modelling of multiple task intervals. This work extends a constraint generation procedure previously developed for an avionics scheduling context. We here address a relaxation of the original problem and this relaxation can be considered as multiprocessor scheduling with precedence relations and multiple intervals.The explicit modelling of multiple intervals strengthens the formulation used in the constraint generation procedure and we illustrate the computational effects on an industrial relevant avionics scheduling problem.
|
|
| 9. |
|
|
| 10. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
Instance dataset for a multiprocessor scheduling problem with multiple time windows and time lags : Similar instances with large differences in difficulty
- 2022
-
Ingår i: Data in Brief. - : Elsevier. - 2352-3409. ; 45
-
Tidskriftsartikel (refereegranskat)abstract
- The dataset presented in this paper introduces 384 new instances for the feasibility version of a multiprocessor scheduling problem with multiple time windows, positive time lags and exact time lags. The instances are constructed from subproblems in a logic-based Benders decomposition scheme introduced in "Logic-based Benders decomposition with a partial assignment acceleration technique for an avionics scheduling problem" (Karlsson, E., Rönnberg, E., Computers & Operations Research, 2022) [1]. A key aspect of the dataset is that even if two instances are highly similar, the computational performance of solving them with an IBM ILOG CP Optimizer model can be vastly different. There exists for example 47 pairs of instances with the same number of tasks and exact time lags, and the number of positive time lags differs with at most two, where one instance can be solved within 5 minutes and the other instance cannot be solved within 24 hours. Such differences make the instance dataset useful for investigating differences in computational performance of constraint programming solvers. The dataset can also be used to benchmark methods for multiprocessor scheduling. The dataset has been released under the Creative Commons Attribution 4.0 International license and can be used as it is or be adapted.
|
|
