成像卫星星地联合成像调度

成像卫星星地联合调度问题,涉及调度对象众多,约束条件复杂,需要考虑任务的观测、回传2个过程,是一个具有两层时间窗口约束的双层优化问题,统一建模困难。根据问题的特点,采用基于阶段优化的方式,降低了问题的复杂性。把问题分为观测调度阶段和数据回传调度阶段,分别给出了优化目标和约束条件,建立了基于阶段优化的成像卫星星地联合调度模型,实现了从任务观测到数据回传的全过程调度。仿真实例表明,该方法能够有效解决多星多站的协同任务调度问题。     

A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints

We study a real-world complex hybrid flow-shop scheduling problem arising from a bio-process industry. There are a variety of constraints to be taken into account, in particular zero intermediate capacity and limited waiting time between processing stages. We propose an exact solution approach for this optimization problem, based on a discrete time representation and a mixed-integer linear programming formulation. The proposed solution algorithm makes use of a new family of valid inequalities exploiting the fact that a limited waiting time is imposed on jobs between two successive production stages. The results of our computational experiments confirm that the proposed method produces good feasible schedules for industrial instances.     

Modeling and solving the steelmaking and casting scheduling problem

We propose a general model for the problem of planning and scheduling steelmaking and casting activities obtained by combining common features and constraints of the operations from a real plant and the literature. For tackling the problem, we develop a simulated annealing approach based on a solution space made of job permutations, which uses as submodule a chronological constructive procedure that assigns processing times and resources to jobs. Our technique, properly tuned in a statistically principled way, is able to find good solutions for a large range of different settings and horizons. In addition, it outperforms both a greedy procedure and a constraint‐based solver developed for comparison purposes on almost all instances. Finally, we have collected several real‐world instances that we make available on the web along with the solution validator and our best results.     

置换表示方法求解多卫星多地面站调度问题

针对多卫星成像和多地面站数传并存的对地成像调度问题,从置换空间到调度解空间的映射方法和置换空间的搜索算法两方面进行了研究.提出了一种数传时间窗优先的置换序列映射算法,并证明该映射算法可以将置换序列映射到调度解空间上的最优解.提出了一种遗传随机搜索算法,基于有记忆随机邻域搜索,在置换空间上进行搜索.仿真计算表明,随机邻域搜索可以增强遗传算法的局部搜索能力,搜索结果平均获得了4.64%的改进.     

An Agent-Based Approach for Scheduling Multiple Machines

We present a new agent-based solution approach for the problem of scheduling multiple non-identical machines in the face of sequence dependent setups, job machine restrictions, batch size preferences, fixed costs of assigning jobs to machines and downstream considerations. We consider multiple objectives such as minimizing (weighted) earliness and tardiness, and minimizing job-machine assignment costs. We use an agent-based architecture called Asynchronous Team (A-Team), in which each agent encapsulates a different problem solving strategy and agents cooperate by exchanging results. Computational experiments on large instances of real-world scheduling problems show that the results obtained by this approach are significantly better than any single algorithm or the scheduler alone. This approach has been successfully implemented in an industrial scheduling system.     

基于深度强化学习的微电网在线优化调度

提出一种基于深度强化学习的微电网在线优化调度策略.针对可再生能源的随机性及复杂的潮流约束对微电网经济安全运行带来的挑战,以成本最小为目标,考虑微电网运行状态及调度动作的约束,将微电网在线调度问题建模为一个约束马尔可夫决策过程.为避免求解复杂的非线性潮流优化、降低对高精度预测信息及系统模型的依赖,设计一个卷积神经网络结构学习最优的调度策略.所提出的神经网络结构可以从微电网原始观测数据中提取高质量的特征,并基于提取到的特征直接产生调度决策.为了确保该神经网络产生的调度决策能够满足复杂的网络潮流约束,结合拉格朗日乘子法与soft actor-critic,提出一种新的深度强化学习算法来训练该神经网络.最后,为验证所提出方法的有效性,利用真实的电力系统数据进行仿真.仿真结果表明,所提出的在线优化调度方法可以有效地从数据中学习到满足潮流约束且具有成本效益的调度策略,降低随机性对微电网运行的影响.     

一种求解车间作业调度问题的混合邻域结构搜索算法

车间作业调度问题是优化组合中一个著名的难题,问题的目标是在满足约束条件的前提下,使调度的加工周期尽可能小。文章中提出了利用新的混合邻域结构进行搜索来求解车间作业调度问题。对于算法关键的邻域构造问题以及跳坑策略给出了提高算法优度的解决方案。采用43个不同规模和难度的国际标准算例做为本算法的测试实验集,39个算例找到了最优解,其中包括著名的难例FT10。与当前国外学者提出的一种先进算法进行了比较,算法的优度高于被比较的先进算法。     

基于STK_Matlab的共形相控阵对卫星可见性分析

近年来中国在轨卫星数量与日俱增，航天地面测控资源日益紧张，地面站现有的球面共形相控阵存在极大的阵面资源浪费，针对地面测控站阵面波束资源的调度分配可以有效利用现有阵面资源，为日后数量更庞大的航天测控任务需求增加资源裕度，为此需要对中国在轨卫星相对阵面的分布情况进行可见性分析；设计了一种基于STK与Matlab互联的仿真计算方法，该方法利用中国在轨卫星实时TLE数据，通过Matlab对STK控制仿真卫星相对地面站的分布及可见性，并把仿真数据存入Matlab，进一步仿真卫星对子阵的可见性，统计对各子阵的可见性结果；仿真结果得出了球面阵上各子阵在全天时刻的可见卫星数量以及资源较为紧张的子阵分布，该结果可以为球面共形相控阵波束资源调度设计提供参考。     

基于统一资源编码的成像卫星联合任务规划算法框架

对于大量的卫星和地面站资源,随着观测任务与日俱增,如何高效安排对应的一体化成像数传活动成为提升卫星管控效能的关键.在综合考虑实际约束的基础上,建立数学模型详细描述成像卫星联合任务规划问题,通过采用统一资源编码的思想设计一种简单且易于理解的个体表示方法,并利用任务有效执行期的潜在冲突关系提出相互冲突任务集的概念以降低问题...     

Dynamic patient admission scheduling with operating room constraints,flexible horizons,and patient delays

We revisit and extend the patient admission scheduling problem, in order to make it suitable for practical applications. The main novelty is that we consider constraints on the utilisation of operating rooms for patients requiring a surgery. In addition, we propose a more elaborate model that includes a flexible planning horizon, a complex notion of patient delay, and new components of the objective function. We design a solution approach based on local search, which explores the search space using a composite neighbourhood. In addition, we develop an instance generator that uses real-world data and statistical distributions so as to synthesise realistic and challenging case studies, which are made available on the web along with our solutions and the validator. Finally, we perform an extensive experimental evaluation of our solution method including statistically principled parameter tuning and an analysis of some features of the model and their corresponding impact on the objective function.     

基于禁忌搜索算法测地卫星任务调度研究

研究测地卫星调度问题,它是一个复杂的组合优化问题,涉及多个卫星,大量的任务与约束限制,何时和如何执行每项任务。分析了问题的主要约束,在合理的假设基础上建立了带有时间窗口多资源调度问题模型,提出一种改进的禁忌搜索算法求解该模型。用实例对模型和算法进行了验证,并将结果与动态规划方法求解结果比较分析,结果表明模型和算法是有效的。     

An evolutionary algorithm based on constraint set partitioning for nurse rostering problems

The nurse rostering problem (NRP) is a representative of NP-hard combinatorial optimization problems. The hardness of NRP is mainly due to its multiple complex constraints. Several approaches, which are based on an evolutionary algorithm (EA) framework and integrated with a penalty-function technique, were proposed in the literature to handle the constraints found in NRP. However, these approaches are not very efficient in dealing with large-scale NPR instances and thus need to be improved upon. In this paper, we investigate a large-scale NRP in a real-world setting, i.e., Chinese NRP (CNRP), which requires us to arrange many nurses (up to 30) across a 1-month scheduling period. The CNRP poses various constraints that lead to a large solution space with multiple isolated areas of infeasible solutions. We propose a single-individual EA for the CNRP. The novelty of the proposed approach is threefold: (1) using a constraint separation to partition the constraints into hard and soft constraints; (2) using a revised integer programming to generate a high-quality initial individual (solution), which then leads the subsequent EA search to a promising feasible solution space; and (3) using an efficient mutation operator to quickly search for a better solution in the restricted feasible solution space. The experimental results based on extensive simulations indicate that our proposed approach significantly outperforms several existing representative algorithms, in terms of solution quality within the same calculation times of the objective function.     

A model and a solution algorithm for the car pooling problem with pre-matching information

Most past car pooling studies have focused on the to-work problem (from different origins to a common destination) or the return-from-work problem (from the same origin to different destinations). Pre-matching information, including the carpool partners and the route/schedule for each previously participating vehicle, have rarely been considered. As a result, there has not yet been a suitable method/model developed for solving practical many-to-many car pooling problem with multiple vehicle and person types, as well as pre-matching information, that occur in real-world. In this study we strive to make up this lack by employing a time–space network flow technique to develop a model for this type of car pooling problem with pre-matching information (CPPPMI). The model is formulated as an integer multiple commodity network flow problem. A solution algorithm, based on Lagrangian relaxation and a heuristic for the upper bound solution, is developed to solve the model. To test how well the model and the solution algorithm may be applied to real-world, numerical tests are performed with several problem instances randomly generated based upon data reported from a past study carried out in northern Taiwan. The test results show the effectiveness of the proposed model and solution algorithm.     

A Primal-dual Steepest-edge Method for Even-flow Harvest Scheduling Problems

The even-flow harvest scheduling problem arises when the forestry agency has evolved into a rigid non-declining even-flow policy. In this paper, we investigate model formulation and solution strategies for the even-flow harvest scheduling problem. A multiple-objective linear programming problem is formulated for even-flow harvest scheduling problems with multiple-site classes and multiple periods. The aim of this problem is to simultaneously maximize a desired harvest-volume per hectare for each period of planning horizon and the total economic return. A block diagonal constraint structure, with many sets of network sub-problems and a set of coupling constraints, is identified in this linear programming problem. A longest path method for each of network sub-problems and a primal-dual steepest-edge algorithm for the entire problem are developed. The developed algorithm has been coded in Borland C++ and implemented on a personal computer. An illustrative example is used to display the detailed procedure for the developed algorithm and a real-world case study is used to show the trade-off between desired even-flow harvest volume policy and total economic return. Results show the potential benefits of this approach.     

基于Hopfield神经网络的作业车间生产调度方法

该文提出了基于Hopfield神经网络的作业车间生产调度的新方法.文中给出了作业车 间生产调度问题(JSP)的约束条件及其换位矩阵表示,提出了新的包括所有约束条件的计算能 量函数表达式,得到相应的作业车间调度问题的Hopfield神经网络结构与权值解析表达式,并 提出相应的Hopfield神经网络作业车间调度方法.为了避免Hopfield神经网络容易收敛到局部 极小,从而产生非法调度解的缺点,将模拟退火算法应用于Hopfield神经网络求解,使Hopfield 神经网络收敛到计算能量函数的最小值0,从而保证神经网络输出是一个可行调度方案.该文 改进了已有文献中提出的作业调度问题的Hopfield神经网络方法,与已有算法相比,能够保证 神经网络稳态输出为可行的作业车间调度方案.     

A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem

Job shop scheduling problem (JSP) which is widespread in the real-world production system is one of the most general and important problems in various scheduling problems. Nowadays, the effective method for JSP is a hot topic in research area of manufacturing system. JSP is a typical NP-hard combinatorial optimization problem and has a broad engineering application background. Due to the large and complicated solution space and process constraints, JSP is very difficult to find an optimal solution within a reasonable time even for small instances. In this paper, a hybrid particle swarm optimization algorithm (PSO) based on variable neighborhood search (VNS) has been proposed to solve this problem. In order to overcome the blind selection of neighborhood structures during the hybrid algorithm design, a new neighborhood structure evaluation method based on logistic model has been developed to guide the neighborhood structures selection. This method is utilized to evaluate the performance of different neighborhood structures. Then the neighborhood structures which have good performance are selected as the main neighborhood structures in VNS. Finally, a set of benchmark instances have been conducted to evaluate the performance of proposed hybrid algorithm and the comparisons among some other state-of-art reported algorithms are also presented. The experimental results show that the proposed hybrid algorithm has achieved good improvement on the optimization of JSP, which also verifies the effectiveness and efficiency of the proposed neighborhood structure evaluation method.     

High-performance technique for satellite range scheduling

As the number of daily satellite service requests increases, the satellite range scheduling problem becomes more intractable during the ground station operations management. The NP-complete problem involves scheduling satellite requests to ground station antennas within their time windows so that the profit from the scheduled requests is maximized. This paper analyzes various conflicts between satellite requests and then develops a conflict-resolution technique. The technique first builds an elite initial schedule using a prescheduling strategy and then improves the initial schedule using a rescheduling strategy in a subspace of feasible solutions. The main highlight of the technique is its dual functions of quickly generating a high-quality solution and providing a good bound. As shown in the experimental results from the actual data and more difficult random instances, the proposed technique is significantly better than the best-known heuristic.     

Efficient meta-heuristics based on various dominance criteria for a single-machine bi-criteria scheduling problem with rejection

In this paper, we try to fill in the gap between theory and practice in production scheduling by defining a new term as “rejection” and treating the corresponding scheduling problem with multi-objective optimization approach. We study a bi-objective single machine scheduling problem with rejection. At the beginning of scheduling time horizon, scheduler needs to decide which job shall be rejected due to the resource constraints regarding two objective functions: minimization of total weighted completion time of accepted jobs and total rejection penalty of rejected jobs. We develop different algorithms to find the best estimation of Pareto-optimal front for this problem. In order to improve the quality of the solutions, on the one hand, and facilitate the process of selecting best solution for the final decision maker, on the other hand, we integrate various dominance criteria into our proposed algorithms. Finally we compare the performance of those methods by testing on a large set of instances and highlight the advantages and weak points of each one.     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.