Mathematische Schriften Kasselhttps://kobra.uni-kassel.de:443/handle/123456789/20100818340902024-03-19T09:12:34Z2024-03-19T09:12:34ZPropagation and branching strategies for job shop scheduling minimizing the weighted energy consumptionBley, AndreasLinß, Andreashttps://kobra.uni-kassel.de:443/handle/123456789/151802023-11-15T09:01:11Z2023-01-01T00:00:00ZWe consider a job shop scheduling problem with time windows, flexible energy prices, and machines whose energy consumption depends on their operational state (offline, ramp-up, setup, processing, standby or ramp-down). The goal is to find a valid schedule that minimizes the overall energy cost. To solve this problem to optimality, we developed a branch-and-bound algorithm based on a time-indexed integer linear programming (ILP) formulation, which uses binary variables that describe blocks spanning multiple inactive periods on the machines. In this paper, we discuss the propagation and branching schemes used in that algorithm. The strategies, which are specifically tailored for energy related machine scheduling problems, primarily aim to determine and sharpen the activity profiles of the machines (and thus reduce the number of the inactive block variables) and address the workload profile of the tasks with lower priority.
2023-01-01T00:00:00ZBley, AndreasLinß, AndreasWe consider a job shop scheduling problem with time windows, flexible energy prices, and machines whose energy consumption depends on their operational state (offline, ramp-up, setup, processing, standby or ramp-down). The goal is to find a valid schedule that minimizes the overall energy cost. To solve this problem to optimality, we developed a branch-and-bound algorithm based on a time-indexed integer linear programming (ILP) formulation, which uses binary variables that describe blocks spanning multiple inactive periods on the machines. In this paper, we discuss the propagation and branching schemes used in that algorithm. The strategies, which are specifically tailored for energy related machine scheduling problems, primarily aim to determine and sharpen the activity profiles of the machines (and thus reduce the number of the inactive block variables) and address the workload profile of the tasks with lower priority.Identifying critical demand periods in capacity planning for networks including storageBley, AndreasHahn, Philipphttps://kobra.uni-kassel.de:443/handle/123456789/151792023-11-15T08:33:12Z2023-01-01T00:00:00ZWe consider a capacity planning problem for networks including storage. Given a graph and a time series of demands and supplies, we seek for integer link and storage capacities that permit a single commodity flow with valid storage in- and outtakes over all time steps. This problem arises, for example, in power systems planning, where storage can be used to buffer peaks of varying supplies and demands. For typical time series spanning a full year at hourly resolution, this leads to huge optimization models. To reduce the model size, time series aggregation is commonly used. The time horizon is sliced into fixed size periods, e.g. days or weeks, a small set of representative periods is chosen via clustering methods, and a much smaller model involving only the chosen periods is solved. Representative periods, however, typically do not contain the situations with the most extreme demands and supplies and the strongest effects on storage. In this paper, we show how to identify such critical periods using principal component analysis (PCA) and convex hull computations and we compare the quality and solution time of the reduced models to the original ones for benchmark instances derived from power systems planning.
2023-01-01T00:00:00ZBley, AndreasHahn, PhilippWe consider a capacity planning problem for networks including storage. Given a graph and a time series of demands and supplies, we seek for integer link and storage capacities that permit a single commodity flow with valid storage in- and outtakes over all time steps. This problem arises, for example, in power systems planning, where storage can be used to buffer peaks of varying supplies and demands. For typical time series spanning a full year at hourly resolution, this leads to huge optimization models. To reduce the model size, time series aggregation is commonly used. The time horizon is sliced into fixed size periods, e.g. days or weeks, a small set of representative periods is chosen via clustering methods, and a much smaller model involving only the chosen periods is solved. Representative periods, however, typically do not contain the situations with the most extreme demands and supplies and the strongest effects on storage. In this paper, we show how to identify such critical periods using principal component analysis (PCA) and convex hull computations and we compare the quality and solution time of the reduced models to the original ones for benchmark instances derived from power systems planning.Identifying critical demand scenarios for the robust capacitated network design problem using principal component analysisBley, AndreasHahn, Philipphttps://kobra.uni-kassel.de:443/handle/123456789/135842022-02-02T13:00:05Z2021-11-30T00:00:00ZIn this paper, we consider the single-commodity robust network design problem. Given an undirected graph with capacity installation costs on its edges and a set S of scenarios with associated flow balance vectors that represent different scenarios of node supplies and demands, the goal is to find integer edge capacities that minimize the total installation cost and permit a feasible single commodity flow for each scenario. This problem arises, for example, in the design of power networks, which are dimensioned to accommodate many different load scenarios.
We propose a new method to identify a small subset S′ of the given scenarios, such that solving the robust network design problem for the smaller scenario set S′ leads to almost the same capacities as solving it for the full scenario set S. By considering only the scenarios in S′ , the size of the model that needs to be solved can be reduced substantially, while the error introduced by neglecting the remaining scenarios is kept very small. Our method only employs simple techniques from statistical data analysis, namely principal component analysis (PCA), and convex hull computations in low dimensions. Thus, its computational effort is very small and it is easily applicable to more complex network design problems.
We evaluate the effectiveness of the method in computational experiments for instances stemming from offshore power grid planning or telecommunication networks. Our results show that the proposed techniques are indeed well suited to identify small scenario subsets that lead to significantly reduced models with high quality solutions.
2021-11-30T00:00:00ZBley, AndreasHahn, PhilippIn this paper, we consider the single-commodity robust network design problem. Given an undirected graph with capacity installation costs on its edges and a set S of scenarios with associated flow balance vectors that represent different scenarios of node supplies and demands, the goal is to find integer edge capacities that minimize the total installation cost and permit a feasible single commodity flow for each scenario. This problem arises, for example, in the design of power networks, which are dimensioned to accommodate many different load scenarios.
We propose a new method to identify a small subset S′ of the given scenarios, such that solving the robust network design problem for the smaller scenario set S′ leads to almost the same capacities as solving it for the full scenario set S. By considering only the scenarios in S′ , the size of the model that needs to be solved can be reduced substantially, while the error introduced by neglecting the remaining scenarios is kept very small. Our method only employs simple techniques from statistical data analysis, namely principal component analysis (PCA), and convex hull computations in low dimensions. Thus, its computational effort is very small and it is easily applicable to more complex network design problems.
We evaluate the effectiveness of the method in computational experiments for instances stemming from offshore power grid planning or telecommunication networks. Our results show that the proposed techniques are indeed well suited to identify small scenario subsets that lead to significantly reduced models with high quality solutions.No Chaos in Dixon's SystemSeiler, Werner M.Seiß, Matthiashttps://kobra.uni-kassel.de:443/handle/123456789/114702021-06-23T15:03:17Z2020-01-01T00:00:00ZThe so-called Dixon system is often cited as an example of a two-dimensional (continuous) dynamical system that exhibits chaotic behaviour, if its two parameters take their value in a certain domain. We provide first a rigorous proof that there is no chaos in Dixon's system. Then we perform a complete bifurcation analysis of the system showing that the parameter space can be decomposed into sixteen different regions in each of which the system exhibits qualitatively the same behaviour. In particular, we prove that in some regions two elliptic sectors with infinitely many homoclinic orbits exist which can easily create in numerical computations the impression of chaotic behaviour.
2020-01-01T00:00:00ZSeiler, Werner M.Seiß, MatthiasThe so-called Dixon system is often cited as an example of a two-dimensional (continuous) dynamical system that exhibits chaotic behaviour, if its two parameters take their value in a certain domain. We provide first a rigorous proof that there is no chaos in Dixon's system. Then we perform a complete bifurcation analysis of the system showing that the parameter space can be decomposed into sixteen different regions in each of which the system exhibits qualitatively the same behaviour. In particular, we prove that in some regions two elliptic sectors with infinitely many homoclinic orbits exist which can easily create in numerical computations the impression of chaotic behaviour.