多目的批处理过程的优化周期调度

基于状态任务网络（State Task Network,STN)描述批处理过程，提出了多目的批处理过程的混合整数规划（Mixed Integer Linear Programming,MILP)周期调度数学模型。建模采用连续时间描述，并将任务和设备分配结合事件点集决表达为一类0-1变量。相对于已有的多目的批处理过程周期调度数学模型，该模型规模小，计算速度快。     

基于预排序的并行批处理过程调度模型

针对并行批处理调度过程,以总提前完成时间最小化为目标函数,建立了一个基于交货期的调度模型.该模型考虑了订单的交货期等约束条件,将订单和设备之间的分配关系表达为0-1变量,采用预排序方法确定订单的处理顺序.采用分支定界法对模型进行求解,并与已有模型的计算结果比较,证明所提出的模型整数变量少且容易求解.     

一种改进的非顺序型多目的工厂间歇调度模型

提出了一种考虑原料库存约束的非顺序型多目的工厂间歇调度的混合整数线性规划(MILP)模型.该模型主要包括两个部分:工厂原料库存的MILP模型和采用无限中间储罐(UIS)生产方式的非顺序型多目的工厂间歇调度的MILP模型.将这两个数学模型进行综合求解,从而得到原料库存约束条件下非顺序型多目的工厂的调度方案.最后通过算例研究证明了用该方法得到的调度方案更符合工厂实际生产的要求.     

面向节能的阻塞混合流水车间调度问题建模

针对能耗目标的阻塞混合流水车间调度问题(HFSP-B),分别构建了考虑调整时间及不考虑调整时间的阻塞混合流水车间调度问题(MILP)模型.为了减少机床待机能耗,在MILP模型中考虑关机/重启节能策略.针对MILP模型,从目标函数、目标函数的线性化过程、决策变量和约束方程进行介绍.最后,通过对具体实例的求解,验证了所提MILP模型的有效性.通过对MILP所得最优解的分析,挖掘了阻塞因素对能耗目标的影响规律,有助于今后设计基于元启发式算法的近似算法.     

油品调合调度优化问题的分步求解策略

针对炼油厂的成品油调合调度优化问题，提出了一种分步求解策略，即将调合调度问题分解为三个子优化问题，采用NLP和MILP模型对其分四步求解，这一策略不仅降低了问题的复杂度，还同时解决了油品调合调度中的配方优化、任务调度问题。实际算例结果表明该方法是有效的．     

基于MILP的应用服务器集群能耗与性能实时优化

在节能减排和激烈同行竞争的环境下，应用服务器集群的能耗与性能优化十分迫切.针对已有研究在性能指标和实时性方面的不足，提出一种集群能耗与性能实时优化方案.该方案结合采用线性加权法和主目标法优化集群功率与请求丢弃率这两个目标，将双目标优化转换成一个单目标约束优化.首先基于CPU频率等效连续调整模式下的服务器负载-功率模型，定义很少的变量将集群优化描述成混合整数二次规划问题，然后采用变量拆分和变量转换将其转化成混合整数线性规划（mixed integer linear programming，MILP）问题并引入特殊顺序集约束，最后采用Gurobi优化器求解该MILP.通过对CPU频率调整的进一步优化，大幅度减少了CPU频率的切换.多种场景下的测试表明，该方案的求解时间约在10 ms左右，特殊顺序集约束的引入使求解时间更为稳定，从而能够保证优化的实时进行.     

基于数学规划的平行机批量调度固定优化算法

以半导体制造行业为应用背景,研究带产能约束的平行机批量调度问题。该问题需要同时考虑基于产品加工顺序的生产准备时间约束、产品加工的时间窗约束、设备和产品的匹配约束以及设备偏好性等约束。为此,构建了混合整数规划(MIP)模型,并设计了基于MIP模型的固定优化启发式算法。该算法先按照随机设备柔性最小优先规则把设备预先分配给需要加工的产品,从而可以通过更新设备和产品匹配关系矩阵来降低子问题的求解难度;再利用基于设备分解和基于时间分解的两种分解方法,固定住MIP模型中的大部分0-1变量,从而可以有效地利用MIP求解器优化剩余的一小部分0-1变量。大量随机产生的实验算例和半导体工厂真实算例表明:该算法优于现有文献中其他基于MIP的启发式算法,特别是当算例中设备柔性较高和需求变动较大时,该算法绩效更加显著。     

基于变量分离的生产调度空间划分算法

静态生产调度大多形成MILP或MINLP模型，由于调度规模大及混合整数规划的组合优化特性，造成调度求解困难。通过对混合整数规划模型空间的分析，提出依据整数变量和连续变量的分离策略进行空间的自然划分，从而将模型的求解转化为多个较小规模连续子空间的寻优。对典型间歇调度模型的分析表明，将空间划分后进行连续寻优的策略较大地降低了实际运算的规模，降低了求解难度，可以提高问题的求解速度和效率。     

含时间窗的司售员调度模型及多邻域结构设计

形式化定义了司售员调度中的关键因素:车辆运营工作、调度方案、劳动法规和调度目标,建立了一个能够准确反映实际问题的模型.设计出能够有效处理时间窗的多邻域结构,为应用基于邻域搜索的各种算法求解该模型奠定了基础.最后将其应用于基于禁忌搜索的构造式方法——启发式自动司售员调度(HACS)中.实验表明:应用该模型及多领域结构改进了HACS,有效解决了含时间窗的司售员调度问题并得到更优解,对大规模问题,解的改进更加明显.     

集中通勤接送服务的车辆路径与调度模型及算法

基于最优化理论与方法,对集中通勤接送服务的车辆路径与调度问题进行了研究,以节约运营成本、提高服务质量。由于该优化问题与传统的车辆路径规划有所不同,具有多目标抵达地、多车协作和多行程车次的特征事实,现有的模型与算法不能直接应用于该问题的求解。首次建立了集中通勤接送服务模式下以最小化运营成本为目标的车辆路径与调度问题的0-1整数规划模型,并开发了一种基于特征点的启发式算法求解该模型。在实证研究中,实验结果表明本文所设计的模型和算法是可行的、有效的。     

出口箱随机入港下的箱区选择与箱位分配协调调度

针对出口箱随机入港下的分散堆放与随机选位对集装箱卡车行驶和场桥取箱作业的影响,提出了出口箱的箱区选择与箱位分配协调调度问题,并以箱区位置、箱量分配、箱位分配为决策变量,以集装箱卡车接运单位TEU平均作业时间最少、场桥作业成本最低为目标,构建了出口箱箱区选择与箱位分配两阶段非线性整数规划模型.设计了基于遗传算法的双层启发式算法,上层用于箱区搜索,确定出口箱堆放箱区及箱量分配;下层用于箱位搜寻,并依据场桥取箱顺序规则,确定具体堆放箱位或重选堆放箱区.通过算例分析结果表明:与集中入港下集中堆放相比,对出口箱随机入港下分散堆放的箱区选择与箱位分配进行协调调度同步优化,可以减少单位TEU平均装卸时间5.46%,并显著降低堆场作业成本,模型与算法可行有效.     

工件相同且发送批数受限的供应链排序问题

工件完工后成批发送的供应链排序问题是从实际生产中提炼出来的,针对发送批数受限制,最小化生产费用及发送费用的情况,当工件的权重与加工时间均相等时,生产费用是关于发送批数的单调递减函数,进而根据二分搜索法可以得到最优的发送批数。因此问题是多项式时间可解的。     

混合MAC协议和流量分化QoS的WSN智能算法

针对无线传感器网络(WSNs)中负载很大的情况下网络能量效率较低的问题,提出了一种基于MAC协议混合流量分化QoS的WSN智能算法。为关键或时延敏感的数据包缩减了时延。首先,通过使用智能CSMA和TDMA加强方法充分利用信道;然后,同时使用广播调度和链路调度,根据网络负载动态地从广播调度切换至链路调度从而获得最佳效率;最后,利用分散处理方法完成调度,即节点在本地使用时钟算法找到时隙,并为之分配。仿真实验验证了所提算法的理论思路及高效率,结果表明,适当的变化发射功率方式降低了能量消耗,并行发射的使用进一步降低了时延。     

SSA:一种面向CQF模型的TSN资源调度算法

时间敏感网络(time sensitive networking,TSN)的目标是在工业控制和5G领域为时间敏感流提供低延迟、低抖动的确定性传输服务.资源调度是保证TSN服务质量的关键技术之一.为此,TSN标准中提出循环队列转发模型(cyclic queuing and forwarding,CQF),但是缺乏相应的资源调度算法对多流进行合理的资源分配以避免传输冲突.由于时间敏感流量具有周期性、特征预知的特点,主要从时间维度研究如何将CQF模型中的队列资源合理分配给多条数据流.将该问题抽象为多约束条件下的资源规划最大化问题,提出基于起始时隙分配的轻量级资源调度算法(start-slot assignment based scheduling algorithm,SSA).SSA通过对端系统上发送时隙进行调节,在满足约束条件的前提下最大化对队列资源的使用,避免了端到端逐跳的时隙分配.实验结果表明,与不控制时隙的直接调度方式相比,该算法能够将成功调度的流数目平均提高41.84%.     

基于小波分析的a-多样性k-匿名大数据自适应延迟调度算法

为提高采用k-匿名模型进行a-多样性大数据延迟调度的自适应性和控制准确性, 提出一种基于小波分析的a-多样性k-匿名大数据自适应延迟调度算法. 首先采用小波分析方法对数据进行去噪处理, 通过去噪数据构建优先级列表控制模型; 然后利用高效时分多址协议设计负载均衡传输的信道模型, 并结合自适应加权控制方法建立调度控制的目标函数, 通过时隙分配进行目标函数的最优化求解, 实现调度算法改进设计. 仿真实验结果表明, 采用该方法进行a-多样性k-匿名大数据调度的自适应均衡性能较好, 数据调度的相对误差较低, 数据的召回率优于传统方法.     

Ant colony optimization approach for test scheduling of system on chip

It is necessary to perform the test of system on chip, the test scheduling determines the test start and finishing time of every core in the system on chip such that the overall test time is minimized. A new test scheduling approach based on chaotic ant colony algorithm is presented in this paper. The optimization model of test scheduling was studied, the model uses the information such as the scale of test sets of both cores and user defined logic. An approach based on chaotic ant colony algorithm was proposed to solve the optimization model of test scheduling. The test of signal integrity faults such as crosstalk were also investigated when performing the test scheduling. Experimental results on many circuits show that the proposed approach can be used to solve test scheduling problems.     

基于环Zn上的圆锥曲线数字签名和多重数字签名

提出了一个基于环Zn上的圆锥曲线公钥密码体系的数字签名方案．该方案综合利用了大数分解的困难性和有限群上计算离散对数的困难性，从而增强了该数字签名方案的安全性．在此基础上，通过将多个圆锥曲线数字签名联合起来生成对消息的签名，设计实现了多人对同一文件的多重数字签名，最后给出了多重数字签名方案的数值模拟．由于整个签名运算在环Zn上的圆锥曲线上，使得明文嵌入方便，求逆元速度快，元素阶的计算及曲线上点的运算都比较容易，因此更易于实现．在引进标准二进制计算群元素的情况下，还能节约1／4计算量．     

基于定向天线的移动自组网接入控制协议

移动自组网使用全向天线进行数据传输时,会产生信号干扰严重和网络收敛较慢等缺陷,为了克服这些缺陷,本文提出了一个基于定向天线的移动自组织网(MANETs)接入控制协议(DAND-MAC).本协议可以统一协调定向天线与全向天线同步工作,全向天线进行拓扑发现和邻居监控,定向天线用于链路建立和数据传输.详细分析了DAND-MAC协议系统结构、关键技术和核心算法,使用OPNET Modeler进行网络仿真建模.仿真结果表明:该协议相比传统的静态时隙分配协议和全向天线动态时隙分配协议,DAND-MAC在端到端延迟、吞吐量和时隙利用率等网络性能上有显著的提升.     

WiMAX WMN中基于扩展图的链路调度优化

链路调度是Wi MAX WMN设计中面临的关键问题.为了最大化网络吞吐量,建模了无干扰最优链路调度模型.针对单位时隙需求的链路集,提出一种Wi MAX WMN中的启发式链路调度算法.进一步,针对WMN中节点的中继特性,设计了基于节点与链路分解的扩展图模型.通过细化传输过程以增强时隙的空间复用性,能够满足链路单次与多次传输的统一调度需求.一系列仿真实验结果表明,所提出的链路调度算法能够有效减少网络调度周期,提高网络吞吐量.