The agile earth observation satellite scheduling problem (AEOSSP) with time-dependent transition times is a complex combinational optimization problem that has emerged from the development of large-scale satellite management techniques. To address this problem, we propose a deep reinforcement learning-based construction model (DRL-CM) that consists of five parts: 1) a Markov decision process (MDP); 2) a feature engineering; 3) a constructive heuristic neural network (CHNN); 4) an RL training method; and 5) an evaluation system. Specifically, the CHNN comprises six modules containing three special components that we propose: a dynamic encoder, a dynamic global layer, and a two-stage attention layer. First, we build the MDP of the AEOSSP and the feature engineering with effective features required for decision-making. Second, we design the CHNN to function as the MDP policy and train it with an RL model. Finally, we propose a comprehensive evaluation system for the validation of our model. The experimental results indicate that the proposed DRL-CM outperforms the state-of-the-art algorithm in terms of both optimization speed and quality. In addition, the feature engineering and network architecture built in our model are verified to be effective in comprehensive experiments.

We investigate a general solution based on reinforcement learning for the agile satellite scheduling problem. The core idea of this method is to determine a value function for evaluating the long-term benefit under a certain state by training from experiences, and then apply this value function to guide decisions in unknown situations. First, the process of agile satellite scheduling is modeled as a finite Markov decision process with continuous state space and discrete action space. Two subproblems of the agile Earth observation satellite scheduling problem, i.e., the sequencing problem and the timing problem are solved by the part of the agent and the environment in the model, respectively. A satisfactory solution of the timing problem can be quickly produced by a constructive heuristic algorithm. The objective function of this problem is to maximize the total reward of the entire scheduling process. Based on the above design, we demonstrate that Q-network has advantages in fitting the long-term benefit of such problems. After that, we train the Q-network by Q-learning. The experimental results show that the trained Q-network performs efficiently to cope with unknown data, and can generate high total profit in a short time. The method has good scalability and can be applied to different types of satellite scheduling problems by customizing only the constraints checking process and reward signals.

Modern military operations in high-tech information warfare settings are dynamic processes involving various types of combat systems connected via multiple channels, which can be abstracted as a type of complex temporal combat network (TCN). The equipment contribution analysis in TCNs is of significant military value for optimizing operation process planning and improving network resilience in complex electromagnetic battlefields. This paper presents an integrated framework called capability oriented equipment contribution analysis (CECA) to analyze key equipment in TCNs. Specifically, a temporal network model is proposed to characterize TCNs by considering their dynamic nature and the heterogeneity capabilities of different types of functional entities during military operations. Based on this model, an operation capability contribution index is proposed to measure the contribution of each piece of equipment involved in executing operational tasks. Finally, the reliability and effectiveness of the CECA are demonstrated based on a TCN case study. This paper provides a detailed and precise quantitative analysis of the equipment contributions in TCNs, which yields useful insights for operation guidance and designing a more resilient combat system-of-systems.

The task planning of satellite-ground time synchronization (SGTSTP) in global navigation satellite system is a complex many-objective ground station scheduling problem. In this paper, we first provide a mathematical formulation of the over-subscribed problem and compare with traditional scheduling problems likes job-shop scheduling problem (JSP) and satellite range scheduling problems (SRSP). In application of the Beidou Navigation System of China, with the limit of ground resource and visible time between satellites and antennas, it is no doubt a difficult problem to solve, besides, there are several objectives for SGTSTP. To solve this SGTSTP problem with efficiency and effectiveness, we propose a solving method based on decomposition-and-integration (DI), and transform SGTSTP from many-objective optimization problem (MaOPs) into a multi-objective optimization problem (MOP), to make it suitable for a multi-objective evolutionary algorithm (MOEA). Meanwhile, evolutionary many-objective optimization algorithm (EMOA) is used for original objectives as comparison. We embed the DI method into two classes of evolutionary algorithm frameworks. DI-MOEA works on a transformed two-objective version of the SGTSTP while DI-EMOA deals with the original four-objective SGTSTP problem. Computational results on two well-designed instances show that the DI-MOEA achieves worse convergence and diversity but better objective value and computational efficiency compared to the DI-EMOA.

Agile earth observing satellites(AEOS) scheduling problem has drawn much research attention in the last few years due to its wide range of applications in both military and civilian areas. Recently, a state-of-the-art adaptive large neighborhood search algorithm(ALNS) was proposed for solving this problem where a dichotomy algorithm was used to calculate the time-dependent transition time. ALNS was demonstrated to be very effective in comparison to CPLEX and other heuristic algorithms at the time of publishment. However, we find two major drawbacks of ALNS. First, the imbalance between diversification and intensification leads to premature convergence; Second, the frequent invoke of the dichotomy algorithm leads to tremendous duplicate calculations and thus high computational complexity of ALNS. In this paper, we propose a simple and fast heuristic algorithm (SFHA) which is composed of an intensified local improvement procedure and a diversified perturbation operation. SFHA also includes a preprocessing procedure to precalculate all possible transition times, which avoids duplicate calculation and speeds up search process. Computational results show that the proposed SFHA outperforms ALNS in terms of both solution quality and computational time. In particular, SFHA consistently attains better solutions than ALNS in half of its running time.

The active-scan agile earth observation satellite (AS-AEOS) is highly agile in three axis which enables in-motion imaging, allowing any imaging direction for a given ground target. Such a high agility drastically increases the difficulty of the scheduling problem. In this paper, we consider a bi-objective AS-AEOS scheduling problem such that we simultaneously maximize the total reward and the overall quality of the scheduled requests, seeking to maximize the profit gain of the satellite owners and the satisfaction of the customers. The main contributions of this paper are two folds: the proposal of a constrained optimization model for formulating the problem, and the design of a Hybrid Coding Based Multi-objective Differential Evolution (HCBMDE) method for the problem solution. In computational experiments, two category scenarios are designed to test the effectiveness of the proposed HCBMDE method. Computational results show that, the proposed method is able to achieve a high quality approximate Pareto front.

Agile Earth Observing Satellite (AEOS) scheduling problem (AEOSSP) consists in selecting a subset of tasks from a given task set which are then scheduled on the agile satellite with the purpose of maximizing the total reward of scheduled tasks. AEOSSP is strongly NP-hard and therefore existing solution approaches mainly fall in the field of heuristics and metaheuristics. According to the no free lunch theory, it is impossible to find a single heuristic that is well-applied to any problem instance and a problem-tailored heuristic is always needed. In this paper, we propose a genetic programming based evolutionary approach (GPEA) to automatically evolve a best-suited constructive heuristic for any given AEOSSP instance. The programs (individuals) of GPEA are heuristic rules encoded as trees of mathematical functions. The fitness of the program is evaluated through mapping the mathematical function to an AEOSSP solution using a timeline-based construction algorithm. Computational results on a set of well-designed AEOSSP scenarios show that the proposed GPEA leads to a heuristic algorithm that outperforms recently published sophisticated meta-heuristic algorithm (ALNS). Additional experiments were carried out to demonstrate that the timeline based construction algorithm plays a significant role in matching time-related characteristics in comparison to four commonly used heuristic algorithms. Our results also showed that the evolved heuristic rules preserve a certain extent of generality.

Observation requests for autonomous observation satellites are dynamically generated. Considering the limited computing resources, a data-driven onboard scheduling method combining AI techniques and polynomial-time heuristics is proposed in this work. To construct observation schedules, a framework with offline learning and onboard scheduling is adopted. A neural network is trained offline in ground stations to assign the scheduling priority to observation requests in the onboard scheduling, based on the optimized historical schedules obtained by genetic algorithms which are computationally demanding to run onboard. The computational simulations show that the performance of the scheduling heuristic is enhanced using the data-driven framework.

This paper presents an improved genetic algorithm to solve the agile earth observing satellite mission planning problem. We study how to rapidly generate high quality initial solutions, and four generation strategies are proposed. The effect of the settings of operator parameters on the performance of the algorithm is analyzed. The experiment results show that the genetic algorithm based on high quality initial solutions generated by Hybrid Random Heuristic Strategy (HRHS) is more effective in solving the agile satellite mission planning problem, but in a certain time cost. We expect that our results will provide insights for the future application of genetic algorithm to satellites mission planning problems.

Planning problems, such as mission capability planning in defense, can traditionally be modeled as a resource investment project scheduling problem (RIPSP) with unconstrained resources and cost. This formulation is too abstract in some real-world applications. In these applications, the durations of tasks depend on the allocated resources. In this paper, we first propose a new version of RIPSPs, namely extended RIPSPs (ERIPSPs), in which the durations of tasks are a function of allocated resources. Moreover, we introduce a resource proportion coefficient to manifest the contribution degree of various resources to activities. Since the more realistic nature of projects in practice implies that the circumstances under which the plan will be executed are stochastic in nature, we present a stochastic version of ERIPSPs, namely stochastic extended RIPSPs (SERIPSPs). To solve SERIPSPs, we first use scenarios to capture the space of possibilities (i.e., stochastic elements of the problem). We focus on three sources of uncertainty: duration perturbation, resource breakdown, and precedence alteration. We propose a robustness measure for the solutions of SEPIPSPs when uncertainties interact. We then formulate an SERIPSP as a multiobjective optimization model with three optimization objectives: makespan, cost, and robustness. A knowledge-based multiobjective evolutionary algorithm (K-MOEA) is proposed to solve the problem. The mechanism of K-MOEA is simple and time efficient. The algorithm has two main characteristics. The first is that useful information (knowledge) contained in the obtained approximated nondominated solutions is extracted during the evolutionary process. The second is that extracted knowledge is utilized by updating the population periodically to guide subsequent search. The approach is illustrated using a synthetic case study. Randomly generated benchmark instances are used to analyze the performance of the proposed K-MOEA. The experimental results illustrate the effectiveness of the proposed algorithm and its potential for solving SERIPSPs.

A novel approach based on the graph model for conflict resolution (GMCR) methodology is proposed to address the problem of multistakeholder system portfolio decision analysis encountered in architecting a system of systems (SoS) with desired capabilities. More specifically, a flexible four-process framework for capability-based SoS architecting containing interactive portfolio decision analysis to promote multistakeholder design negotiations on system portfolio selections is presented. By taking full advantage of the inherent realistic and flexible design of the GMCR paradigm, an interactive portfolio decision analysis approach is designed to facilitate the systematic modeling and analysis of system portfolio decisions at the SoS level in order to achieve potential compromises among all key stakeholders having disparate preferences and interacting according to different conflict behavior patterns. This approach permits the prediction of possible mutually agreeable system portfolios for SoS architecture development. Last, the feasibility of the proposed approach is demonstrated using an illustrative example.

In order to solve group decision making (GDM) problems where the preference relations are provided by decision makers with incomplete fuzzy and interval numbers, this paper develops a GDM approach on the basis of multiple objective optimization and goal programming methods. The proposed approach first analyzes the two types of preference relations and then builds their respective optimization models. Subsequently, an integrated programming model combining the two preference relations is developed to minimize the inconsistency among the decision makers' opinions. By solving the programming model, the ranking of alternatives or selection of the most desirable alternative can be obtained using the intermediate priority vector. Two numerical examples including incomplete fuzzy and interval preference relations are examined to illustrate and show the applicability of the proposed approach.

Many planning problems, such as mission capability planning, can be modelled as project scheduling problems. Unlike conventional deterministic project scheduling problems, project scheduling problems involve uncertainty and the execution of the plan is very likely to be perturbed by many factors. In other words, the circumstances under which the plan will be executed are changing and stochastic. In this paper, we first use scenarios to represent the stochastic elements in the problem; these are: perturbation strength and perturbation occurrence time. We define and explain the Stochastic Resource Investment Project Scheduling (SRIPS) problem. A multi-objective optimization model of SRIPS is proposed where three optimization objectives are considered simultaneously: makespan, cost, and robustness. A multi-objective genetic algorithm is employed to solve the problem. Finally, we generate two test problems with 30 and 60 non-dummy activities to validate the performance of the proposed approach and analyze the sensitivity of the results to different parameter settings.

The capacitated arc routing problem (CARP) is representative of numerous practical applications, and in order to widen its scope, we consider an extended version of this problem that entails both total service time and fixed investment costs. We subsequently propose a hybrid ant colony optimization (ACO) algorithm (HACOA) to solve instances of the extended CARP. This approach is characterized by the exploitation of heuristic information, adaptive parameters, and local optimization techniques: Two kinds of heuristic information, arc cluster information and arc priority information, are obtained continuously from the solutions sampled to guide the subsequent optimization process. The adaptive parameters ease the burden of choosing initial values and facilitate improved and more robust results. Finally, local optimization, based on the two-opt heuristic, is employed to improve the overall performance of the proposed algorithm. The resulting HACOA is tested on four sets of benchmark problems containing a total of 87 instances with up to 140 nodes and 380 arcs. In order to evaluate the effectiveness of the proposed method, some existing capacitated arc routing heuristics are extended to cope with the extended version of this problem; the experimental results indicate that the proposed ACO method outperforms these heuristics.

The capacitated arc routing problem (CARP) is a challenging vehicle routing problem with numerous real world applications. In this paper, an extended version of CARP, the multidepot capacitated arc routing problem (MCARP), is presented to tackle practical requirements. Existing CARP heuristics are extended to cope with MCARP and are integrated into a novel evolutionary framework: the initial population is constructed either by random generation, the extended random path-scanning heuristic, or the extended random Ulusoy's heuristic. Subsequently, multiple distinct operators are employed to perform selection, crossover, and mutation. Finally, the partial replacement procedure is implemented to maintain population diversity. The proposed evolutionary approach (EA) is primarily characterized by the exploitation of attributes found in near-optimal MCARP solutions that are obtained throughout the execution of the algorithm. Two techniques are employed toward this end: the performance information of an operator is applied to select from a range of operators for selection, crossover, and mutation. Furthermore, the arc assignment priority information is employed to determine promising positions along the genome for operations of crossover and mutation. The EA is evaluated on 107 instances with up to 140 nodes and 380 arcs. The experimental results suggest that the integrated evolutionary framework significantly outperforms these individual extended heuristics.