卫星数传接收规划模型与算法研究

作为对地观测卫星任务执行的两个重要阶段之一,数传接收的规划任务是一个具有多时间窗口、多优化目标和多资源约束的NP-Hard优化问题。中继星的引入为数据全天候近实时传输提供可能,同时也为数传规划提出新的问题。本文主要完成两项工作:第一,建立风险控制的卫星数传接收规划模型;第二,阐述基于遗传禁忌的模型求解方法,进一步采用分布式并行求解策略,改善了求解算法的收敛速度和鲁棒性。最后,通过STK提供基础仿真数据,验证了本文规划模型和求解算法的有效性。     

考虑任务优先约束的同类岸桥作业调度优化

分析了以箱组为任务对象QCSP与以整贝为任务对象QCSP的异同,指出前者更能均衡各岸桥作业负荷,并减少船舶装卸作业时间。考虑到岸桥具有作业效率差异的特点,将其视为同类平行机调度问题,同时结合任务优先约束、岸桥作业不可相互穿越与安全距离等特有约束,建立了更加符合实际的以箱组为任务对象的岸桥作业调度混合整数规划模型,其优化目标是最小化装卸作业的makespan。针对模型求解的复杂度,设计了一种遗传算法,对算法搜索空间进行了讨论,并推导了问题的低界。实验算例表明所建立的模型能够反映岸桥作业调度过程中作业效率差异及任务优先约束现象,其算法能够在允许的运算时间内获得稳定的满意解,并且优化结果要全面优于以整贝为任务对象QCSP的调度方案。     

货运列车的编组调度问题的研究

对于货运列车的编组调度问题,建立了以压缩中时和增加运量为双目标、多约束的0-1规划模型,采用逐步紧缩中时约束的方法得到了问题一的调度方案.在此基础上对装载特别物资的车辆施加更强的中时约束得到了问题二的调度方案.提出了列车匹配系数的概念并建立了列车最优配对原则,根据该原则对列车进行优化编组得到了问题三的调度方案.基于问题二的数据转换处理得到了问题四的调度方案.     

工期-费用权衡问题的两个不确定机会约束规划模型

项目调度问题是指管理者通过资源分配,延长或缩短某些工序的持续时间,达到项目费用和工期之间的平衡。在实际工程项目中,环境的不确定性往往是项目管理者需要考虑的因素之一。本文应用不确定理论描述不确定环境中的项目调度问题,将每道工序的持续时间分为正常持续时间和可变动持续时间。其中,假设工序的正常持续时间为不确定变量,可变动持续时间为决策变量,分别构建在项目费用和项目工期约束下的两个不确定机会约束规划模型。依据不确定变量运算法则,将所建立的不确定规划模型转化为等价的确定模型。最后,通过一个工程实例验证模型的合理性。     

安全约束条件下的经济调度优化模型研究

发电侧放开竞争的电力系统需要更加有效、准确的决策工具对有限的资源进行调度规划。短期经济调度优化问题是一个混合整数非线性规划问题,很难得到有效最优解,尤其是对于大规模电力系统。为了提高求解效率,本文提出了一个考虑安全约束的经济调度优化模型(Security-Constrained Economics Dispatch,SCED),主要采用线性化思想处理经济调度优化问题的模型以及各种约束,采用基于校正的交替求解方法,使得调度优化结果在运行成本最小化的前提下满足系统的安全稳定约束。同时,将本文方法运用到IEEE 30节点系统进行测试,从而验证本文方法有效性。     

考虑空重箱转换的港口集装箱甩挂运输问题研究

针对港口堆场与内陆腹地客户之间的空重集装箱运输问题,本文结合甩挂运输的特点将客户的进出港需求拆分为相互关联的空箱和重箱任务,实现单个决策期内运输系统中集装箱的状态转换与回收工作。状态转换受集装箱货物装卸时间影响,因此需要合理调度牵引车路线,以满足前置任务约束。针对此类问题的特点,本文建立了空重箱运输任务整合的整数规划模型,并设计了基于集群选择的改进蚁群算法进行求解。最后,通过不同规模的仿真算例与现有数学模型及优化算法对比结果可知,本文所提出的改进蚁群算法在此类问题的最优解搜索中具有良好的稳定性和求解效率。     

“货到人”拣选系统机器人任务分配的鲁棒双层规划模型

在电商“货到人”拣选系统中,如何调度系统中的机器人并对任务进行合理地分配决定着整个系统的运行效率与成本。分析“货到人”拣选系统作业流程,建立机器人数量配置、机器人调度与机器人任务分配的双层规划模型。上层模型以批量订单完成总成本最小为目标函数,以机器人调度为决策变量,构建整数规划模型;下层模型以机器人完成所有任务的平均空闲率最小为目标函数,以任务分配为决策变量,考虑机器人在完成任务过程中由于调度、避障、路径规划等导致的行走距离不确定因素,构建鲁棒优化模型。上层的调度结果制约了下层的最小平均空闲率,下层的任务分配结果影响上层的最小成本,上下层结果共同决定机器人配置决策。利用遗传算法求解模型,通过实例仿真验证了模型的有效性。     

广义优先关系约束下Max-npv项目调度问题及其遗传算法

以往Max-npv项目调度问题的研究都假定活动之间的关系为单一结束-开始类型,现实中活动之间关系复杂多变,因此,将广义优先关系引入Max-npv项目调度问题中,构建了广义优先关系约束下的Max-npv项目调度模型。针对该优化模型设计了一种双层遗传算法,外层遗传算法负责任务执行模式的优化,内层遗传算法负责任务调度的优化。在内层遗传算法中,采用任务开始时间之差作为新的编码方式,大大简化了交叉变异算子,针对网络图中的环状结构设计了修复算子,确保了编码的有效性。通过一个算例对算法进行了测试,实验结果验证了算法的有效性。     

一类复杂约束下的并行机重调度问题研究

研究一类从实际指挥和保障系统提炼的考虑机器多发故障、且具有工件释放时间、机器可用时间、以及机器适用限制等约束的并行同速机重调度问题.首先,建立同时考虑效率、安全和稳定性的混合整数规划重调度模型,该模型利用最大完工时间和总完工时间来度量效率,用重调度前后分配不同机器的工件总数来度量安全性和稳定性;其次,考虑到该问题的NP-hard性和实际调度对机器故障快速响应的要求,提出基于优先规则和右移重调度策略混合的重调度算法框架;最后,将所提重调度算法框架应用于实际案例,分析比较不同优先规则和右移重调度策略组合的求解效果.结果表明,与工件释放时间相关的优先准则与右移重调度策略结合具有较好的优化效果.值得一提的是,文章首次研究具有多重约束的并行机重调度问题(Pm|r_j,a_j,M_j,brkdwn|C_(max),TC,ND).     

公交车调度问题的数学模型

对2001年全国大学生数学建模竞赛的B题－公交车调度问题进行了分析，建立了调度的目标规划模型及0－1规划模型。在假设各站上、下车人数服从均匀分布的条件下，通过对模型的求解，求出了公交公司的最小运行车辆数52辆，并给出了发车时刻表，其中上行方向运行225班次，下行方向运行220班次，该模型简单，求解容易，能较好地考虑各方利益。     

Using Benders Decomposition to Implicitly Model Tour Scheduling

This paper introduces a new integrated model for the combined days-off and shift scheduling problem (the tour scheduling problem). This model generalizes the forward and backward constraints, previously introduced by Bechtold and Jacobs for the shift scheduling problem, to the tour scheduling problem. This results in a general and compact formulation that can handle several types of scheduling flexibility. We also provide a new proof of the correctness of forward and backward constraints based on Benders decomposition. The latter approach is interesting in itself because it can be used to solve the problem when extraordinary overlap of break windows or start-time bands is present. A discussion of model size for a set of hypothetical test problems is presented to show the merits of the new formulation.     

Algorithms for parallel machine scheduling: a case study of the tracking and data relay satellite system

This paper presents two algorithms for scheduling a set of jobs with multiple priorities on non-homogeneous, parallel machines. The application of interest involves the tracking and data relay satellite system run by the US National Aeronautics and Space Administration. This system acts as a relay platform for Earth-orbiting vehicles that wish to communicate periodically with ground stations. The problem is introduced and then compared to other more common scheduling and routing problems. Next, a mixed-integer linear programming formulation is given but was found to be too difficult to solve for instances of realistic size. This led to the development of a dynamic programming-like heuristic and a greedy randomized adaptive search procedure. Each is described in some detail and then compared using data from a typical busy day scenario.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

A note on “A mixed integer programming model for advanced planning and scheduling (APS)”

In a recent paper, Chen and Ji [Chen, K., Ji, P., 2007. A mixed integer programming model for advanced planning and scheduling (APS). European Journal of Operational Research 181, 515–522] develop a mixed integer programming model for advanced planning and scheduling problem that considers capacity constraints and precedence relations between the operations. The orders require processing of several operations on eligible machines. The model presented in the above paper works for the case where each operation can be processed on only one machine. However, machine eligibility means that only a subset of machines are capable of processing a job and this subset may include more than one machine. We provide a general model for advanced planning and scheduling problems with machine eligibility. Our model can be used for problems where there are alternative machines that an operation can be assigned to.     

ARMMS: Analogical reasoning model management system for multicriteria vehicle scheduling

The transportation industry problem of scheduling vehicles combines the spatial characteristics of routing with time domain considerations of activity schedules. The problem is complex because of the numerous interacting constraints in the spatial and time domains. Further, some of the constraints are flexible and some arise in real-time. The scheduling problem is often presented with multiple objectives that are not all economic in nature and which can be contradictory to one another. In response to these needs, this paper describes an analogical reasoning model management system, called ARMMS, designed in the domain of vehicle scheduling. ARMMS consists of knowledge bases and data bases, a truth maintenance system, a user interface, an inference engine, a learning mechanism, and a model library. Given a scheduling problem, ARMMS searches its memory for solutions. If no solution is available, ARMMS falls back on an analogical problem solving approach in which similar experience can be recalled, and solutions to new, but similar, problems can be constructed. If no similar experience exists, ARMMS intelligently selects an appropriate algorithmic model from its model library, based on the input parameters and problem type, to solve the given problem. By combining experts' knowledge, analogical problem-solving approaches, and algorithmic methods, ARMMS provides an efficient problem-solving approach for vehicle scheduling and routing. ARMMS is also a feasible base for the development of intelligent model management systems.     

An Overview of Scheduling Problems Arising in Satellite Communications

Satellite communications, like batches of work in a job shop, need to be scheduled in order to use their resources as efficiently as possible. The most common satellite communications system in use today is known as Time Division Multiple Access (TDMA), in which data from earth stations is buffered before being transmitted to the appropriate receiver on a satellite. Cycles of transmission are fixed for all stations. Since the same satellite will be used for routeing data in several different ways, a schedule must be devised to use the receivers, repeaters and transmitters on board to minimize the time needed for completion of a batch of work. This paper is a survey of current scheduling algorithms used for optimizing satellite communications resources. Apart from telecommunications, the methods presented here could be applied to more general scheduling problems with renewable resources but without precedence constraints.     

Job scheduling with technical constraints

Many scheduling problems that arise in industry have technical constraints unique to the specific industry. Scheduling methodologies must be highly customized to deal with the unique technical constraints. This study proposes a scheduling model that can incorporate technical constraints into standard scheduling constraints already present in classical models. Using this approach, technical constraints from one industry can be interchanged with those from another with little modification to the existing methodologies. The conditions under which this approach can be applied are investigated and frameworks for applying dispatching rules are proposed. Numerical experiments evaluate the performance of these dispatching rules and compare them with two meta-heuristics.     

考虑序列设置时间的混合流水车间多目标调度研究

基于混合流水车间多品种的特性,序列设置时间和工序跳跃是很多车间在调度时需要考虑的两个重要问题,论文充分考虑这两种生产约束,建立了以最大完工时间和负荷均衡指标为双目标的混合流水车间多目标调度数学模型,并运用改进的NSGA-II算法对基于实际企业生产数据假设的算例进行仿真求解,结果表明求解的调度方案符合实际需求,能够为企业的实际调度提供有效的方案。     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.