A network modeling and resilience quantification approach is described for multiple-beam, geosynchronous-orbit satellite communications (SATCOM) systems operating in the millimeter wave (similar to 20-300 GHz) spectra...
详细信息
ISBN:
(纸本)9798350321814
A network modeling and resilience quantification approach is described for multiple-beam, geosynchronous-orbit satellite communications (SATCOM) systems operating in the millimeter wave (similar to 20-300 GHz) spectral region providing frequency reuse and dual polarization coverage of user terminals (UTs) and gateways. Focus is on the UT service restoration process in face of jamming attacks on multiple beams, including the retainment of service to collaterally affected UTs. The combinatorial optimization approach used to determine alternative pointing of UTs to beams on the attacked satellite, or to beams on satellites in adjacent orbital slots, is a Multiple Knapsack Problem (MKP) formulation. The cascading effect of jamming attacks on connected UTs removed by one or more satellite hops from jammed UTs is addressed and related to the graph theoretical component structure of the UT network;this forms an analytical basis for addressing overall network disruption due to jamming attacks. The MKP formulation is extended to include the case of multiple service provider ( SP) sharing of the satellite spectrum, enabling assessment of the effect on competitive SPs due to cooperation in the form of the sharing of beam capacity. The MKP is solved using a constraint programming (CP) technique which allows latitude in the choice of objective functions.
Since combinatorial scheduling problems are usually NP-hard, this paper investigates whether machine learning (ML) can accelerate exact solving of a problem instance. We adopt supervised learning on a corpus of proble...
详细信息
ISBN:
(数字)9783031332715
ISBN:
(纸本)9783031332708;9783031332715
Since combinatorial scheduling problems are usually NP-hard, this paper investigates whether machine learning (ML) can accelerate exact solving of a problem instance. We adopt supervised learning on a corpus of problem instances, to acquire a function that predicts the optimal makespan for a given instance. The learned predictor is invariant to the instance size as it uses statistics of instance attributes. We provide this prediction to a solving algorithm in the form of bounds on the objective function. Specifically, this approach is applied to the well-studied Cyclic Hoist Scheduling Problem (CHSP). The goal for a CHSP instance is to find a feasible schedule for a hoist which moves objects between tanks with minimal cyclic period. Taking an existing constraint programming (CP) model for this problem, and an exact CP-SAT solver, we implement a Deep Neural Network, a Random Forest and a Gradient Boosting Tree in order to predict the optimal period p. Experimental results find that, first, ML models (in particular DNNs), can be good predictors of the optimal p;and, second, providing tight bounds for p around the predicted value to an exact solver significantly reduces the solving time without compromising the optimality of the solutions.
We solve a challenging scheduling problem with parallel batch processing and two-dimensional shelf strip packing constraints that arises in the tool coating field. Tools are assembled on so-called planetaries (batches...
详细信息
Transport problems are a significant challenge for companies, i.e. due to concerns about climate change and the constant increase in raw material prices, such as for petrol. One issue in transporting bulk materials is...
详细信息
ISBN:
(纸本)9783031398209;9783031398216
Transport problems are a significant challenge for companies, i.e. due to concerns about climate change and the constant increase in raw material prices, such as for petrol. One issue in transporting bulk materials is the Stockyard Planning Problem (SPP), which plays a crucial role in mine production scheduling and bulk material transportation by using stockpiles to store and blend raw material. The SPP aims to: 1) blend superior and inferior components to achieve a desired quality, 2) transfer material from import (e.g. ocean-going ships) to interim storage (e.g. stockpiles) and then to export (e.g. docks at inland ports), and 3) find a time-/cost-optimized schedule for working steps of 1 and 2. This paper presents a novel constraint-based approach for solving the Stockyard Planning Problem (SPP) by utilizing new abstractions such as time, storage, and potential movements within a stockyard system.
The concept of balance plays an important role in many combinatorial optimization problems. Yet there exist various ways of expressing balance, and it is not always obvious how best to achieve it. In this methodology-...
详细信息
The concept of balance plays an important role in many combinatorial optimization problems. Yet there exist various ways of expressing balance, and it is not always obvious how best to achieve it. In this methodology-focused paper, we study three cases where its integration is deficient and analyze the causes of these inadequacies. We examine the characteristics and performance of the measures of balance used in these cases, and provide general guidelines regarding the choice of a measure.
In a context of labor shortage and strong global competition for talent, salary management is becoming a critical issue for companies wishing to attract, engage and retain qualified employees. This paper presents a mu...
详细信息
ISBN:
(纸本)9783031332708;9783031332715
In a context of labor shortage and strong global competition for talent, salary management is becoming a critical issue for companies wishing to attract, engage and retain qualified employees. This paper presents a multi-objective optimization model to balance the internal equity, external equity and costs trade-offs associated with the design of salary structures. Solutions are generated to estimate and explore the Pareto frontier using real compensation data from a unionized establishment in the public sector. Our work shows the interest of using combinatorial optimization techniques in the design of salary structures.
This work presents guillotine constraints for two- and three-dimensional cutting problems. These problems look for a subset of rectangular items of maximum value that can be cut from a single rectangular container. Gu...
详细信息
This work presents guillotine constraints for two- and three-dimensional cutting problems. These problems look for a subset of rectangular items of maximum value that can be cut from a single rectangular container. Guillotine constraints seek to ensure that items are arranged in such a way that cuts from one edge of the container to the opposite edge completely separate them. In particular, we consider the possibility of 2, 3, and 4 cutting stages in a predefined sequence. These constraints are considered within a two-level iterative approach that combines the resolution of integer linear programming and constraint programming models. Experiments with instances of the literature are carried out, and the results show that the proposed approach can solve in less than 500 s approximately 60% and 50% of the instances for the two- and three-dimensional cases, respectively. For the two-dimensional case, in comparison with the recent literature, it was possible to improve the upper bound for 16% of the instances.
Scheduling and resource allocation problems are widespread in many areas of today's technology and management. Their different forms and structures appear in production, logistics, software engineering, computer n...
详细信息
Scheduling and resource allocation problems are widespread in many areas of today's technology and management. Their different forms and structures appear in production, logistics, software engineering, computer networks, project and human resources management, services, etc. The literature (problem classification, scheduling and resource allocation models, solutions) is vast and exhaustive. In practice, however, classical scheduling problems with fixed structures and standard constraints (precedence, disjoint, etc.) are rare. Practical scheduling problems include also logical and nonlinear constraints, and they use nonstandard criteria of schedule evaluations. Indeed, in many cases, decision makers are interested in the feasibility and/or optimality of a given schedule for specified conditions formulated as general and/or specific questions. Thus, there is a need to develop a programming framework that will facilitate the modeling and solving of a variety of diverse scheduling problems. The framework should be able to (a) model any types of constraints, (b) ask questions/criteria relating to the schedule execution mode and (c) be highly effective in finding solutions (schedule development). This paper proposes such a constraint-based declarative programming framework for modeling and solving scheduling problems which satisfies the assumptions above. It was built with the constraint Logic programming (CLP) environment and supported with Mathematical programming (MP). The functionality and effectiveness of this framework are presented with the use of an illustrative example for the resource-constrained scheduling problem with additional resources.
In confronting the "Memory Wall", the design of embedded vision systems exhibits many challenges regarding design cost, energy consumption, and performance. This paper considers a variant of the Job Shop Sch...
详细信息
In confronting the "Memory Wall", the design of embedded vision systems exhibits many challenges regarding design cost, energy consumption, and performance. This paper considers a variant of the Job Shop Scheduling Problem with tooling constraints, arising in this context, in which the completion time (makespan) is to be minimized. This objective corresponds to the performance of the produced circuit. We discuss different formulations using integer linear programming and point out their characteristics, namely the size and the quality of the linear programming relaxation bound. To solve this scheduling problem with large size, we compare various approaches, including a constraint programming model, two constructive greedy heuristics, two models of LocalSolver, a Simulated Annealing algorithm, and a Beam Search algorithm. Numerical experiments are conducted on 16 benchmark instances from the literature and 12 real-life non-linear image processing kernels for validating their efficiency.
We use constraint Satisfaction methods to enumerate and construct set-theoretic solutions to the Yang???Baxter equation of small size. We show that there are 321,931 involutive solutions of size nine, 4,895,272 involu...
详细信息
We use constraint Satisfaction methods to enumerate and construct set-theoretic solutions to the Yang???Baxter equation of small size. We show that there are 321,931 involutive solutions of size nine, 4,895,272 involutive solutions of size ten and 422,449,480 non-involutive solution of size eight. Our method is then used to enumerate non-involutive biquandles.
暂无评论