A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems' another feature lies in oversubscription, namely no...A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems' another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.展开更多
In this paper,a combined optimization of a coupled electricity and gas system is presented.For the electricity network a unit commitment problem with optimization of energy and reserves under a power pool,considering ...In this paper,a combined optimization of a coupled electricity and gas system is presented.For the electricity network a unit commitment problem with optimization of energy and reserves under a power pool,considering all system operational and unit technical constraints is solved.The gas network subproblem is a medium-scale mixed-integer nonconvex and nonlinear programming problem.The coupling constraints between the two networks are nonlinear as well.The resulting mixed-integer nonlinear program is linearized with the extended incremental method and an outer approximation technique.The resulting model is evaluated using the Greek power and gas system comprising fourteen gas-fired units under four different approximation accuracy levels.The results indicate the efficiency of the proposed mixed-integer linear program model and the interplay between computational requirements and accuracy.展开更多
In this paper,we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items.We propose a polynomial heuristic in order to establish both lower and upper bound l...In this paper,we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items.We propose a polynomial heuristic in order to establish both lower and upper bound limits of the sensitivity interval.The aim is to stabilize any given optimal solution obtained by applying any exact algorithm.We then evaluate the effectiveness of the proposed solution procedure on an example and a set of randomly generated problem instances.展开更多
In this paper, we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items. We propose a polynomial heuristic in order to establish both lower and upper bound...In this paper, we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items. We propose a polynomial heuristic in order to establish both lower and upper bound limits of the sensitivity interval. The aim is to stabilize any given optimal solution obtained by applying any exact algorithm. We then evaluate the effectiveness of the proposed solution procedure on an example and a set of randomly generated problem instances.展开更多
基金supported by the National Natural Science Foundation of China (7060103570801062)
文摘A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems' another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.
基金funding through the DFG SFB/Transregio 154, Subprojects A05 and Z01
文摘In this paper,a combined optimization of a coupled electricity and gas system is presented.For the electricity network a unit commitment problem with optimization of energy and reserves under a power pool,considering all system operational and unit technical constraints is solved.The gas network subproblem is a medium-scale mixed-integer nonconvex and nonlinear programming problem.The coupling constraints between the two networks are nonlinear as well.The resulting mixed-integer nonlinear program is linearized with the extended incremental method and an outer approximation technique.The resulting model is evaluated using the Greek power and gas system comprising fourteen gas-fired units under four different approximation accuracy levels.The results indicate the efficiency of the proposed mixed-integer linear program model and the interplay between computational requirements and accuracy.
文摘In this paper,we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items.We propose a polynomial heuristic in order to establish both lower and upper bound limits of the sensitivity interval.The aim is to stabilize any given optimal solution obtained by applying any exact algorithm.We then evaluate the effectiveness of the proposed solution procedure on an example and a set of randomly generated problem instances.
文摘In this paper, we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items. We propose a polynomial heuristic in order to establish both lower and upper bound limits of the sensitivity interval. The aim is to stabilize any given optimal solution obtained by applying any exact algorithm. We then evaluate the effectiveness of the proposed solution procedure on an example and a set of randomly generated problem instances.