加工时间可控的同时加工排序问题

同时加工排序和可控排序是两类很重要的现代排序模型,有着深刻的实际背景和广阔的应用前景,已经取得许多有意义的成果,然而,还没有看到把两者结合起来的研究。把这两类排序模型相结合,讨论加工时间可控的同时加工排序问题:工件可以有不同的加工时间,每个加工时间对应一个控制费用,所有工件在单台机器上平行同时加工,即同时加工的一批工件的加工时间等于这批工件中所有工件加工时间的最大者;分别使误工工件个数和最大延迟加上加工时间可控所需费用的总和为最小作为优化的目标。讨论了这两个问题的最优解的性质,并以此为基础提出了相应的动态规划算法。     

不误工工件加工时间之和最小的最优解

误工排序问题是经典排序论中最基本的问题之一。1968年Moore提出解决这个问题的算法,可以在时间O（nlogn）内得到最优解。误工问题推广到以下情况：或者某些工件必须不误工;或者工件的加工时间与工件的权有反向一致性;或者工件的加工时间与工件的权具有反向一致性,并且某些工件必须不误工等等。对于这些误工问题及其推广问题提出了多项式时间算法,证明了算法的最优性,并且证明了算法得到的最优解是所有最优解中不误工工件加工时间之和是最小的。     

Moore-Hodgson算法的最优性

经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题,是排序论中最基本的问题之一。著名的Moore—Hodgson算法可以在时间O（n log n）内得到误工问题的最优解。Pinedo在1995年对于Moore—Hodgson算法的最优性给出一个证明。虽然这个证明不严格,许多关键的地方交待不清,但是Pinedo证明的过程表明Moore—Hodgson算法得到解是所有最优解中不误工工件的总的加工时间最短的。这是一个很本质的性质,是其他所有的证明中没有提及的。本文补充和完善了Pinedo的证明。此外,对于推广的误工问题,例如,某些工件必须不误工的排序问题,或者工件的就绪时间不相同、但是与交货期有“一致性”关系的排序问题,或者工件的加工时间与工件的权有反向“一致性”关系的排序问题等,是否也有类似的性质？这是非常有意义的进一步研究方向。     

生产和运输时间具有一致性的单机在线最优算法

探讨工件带运输时间实时在线排序问题,目标是极小化所有工件被运达目的地的时间.在工件的加工时间和运输时间具备一致性的情况下,即若工件Ji和Jj的加工时间满足pi≥pj,则它们的运输时间有qi≥qj,给出了竞争比为2的最优在线算法.     

具有多重公共工期的单机退化工件排序

研究了需要同时确定最优工件工期和加工序列的单机排序问题。工件的加工时间是其开工时间的线性增长函数。每个工件的惩罚费用包含两部分,一部分是分配给它的工期费用,另一部分是由机器上产生的提前及延迟惩罚费用。管理者的目标为最小化所有工件的总惩罚费用。对于公共工期个数固定的情形,给出了一个多项式时间算法。     

期望按期完工工件数最大化算法研究

该文讨论工件加工时间为随机变量的单台机排序极大化期望按期完工工件数问题。在确定性排序问题中，Moore算法给出问题的最优解，但事实上Moore算法的期望值版本不能给出期望按期完工工件数最大化问题的最优解。文章从研究排序中工件的按期完工置信系数人手，结合Moore算法，提出了一个启发式算法，有效地解决了该随机排序问题的实际计算。     

基于累计按期完工概率增量的一个排序算法

讨论工件加工时间为随机变量的单机静态列表排序极大化期望按期完工工件数问题。对于单机排序加工时间为独立同分布随机变量问题1／Xi-F／E∑Uj以及EXi≥EXjD di≤dj时，该文给出了预期按期完工工件和预期误工工件的最优划分算法。对于一般问题，对给定的置信度，该文采用倒序算法逐个剔除累计按期完工概率增量最大工件，完成预期按期完工工件集与预期误工工件集的划分，并以此为依据给出排序，最后通过搜索最优置信系数得出排序结果。     

加工时间线性递减的链约束单机排序问题

讨论了工件的加工时间是开工时间的线性递减函数、工件之间有平行链约束的单机排序问题.对于链可中断和不可中断两种情况,给出了极小化总完工时间的最优算法.     

误工工件个数最少的多目标排序问题

考虑在误工工件个数最少的约束条件下使得工件集合的总完工时间为最小的单台机器多目标排序问题.首先要使得误工工件个数∑Uj为最少,著名的Moore-Hodgson算法得到的排序就是一个可行解,并且该算法在遇到误工工件时总是尽可能把加工时间最长的工件放到误工工件集合L中,这也符合使总完工时间∑Cj为最小的目的.然而以往文献中的例子显示,这样得到的解并不总是最优解,这就暗示了该问题的复杂性,因此给出了不同于以往文献的分支定界算法及其Matlab解,简化了计算过程.     

具有学习效应的单机可控加工时间排序问题研究

在经典排序问题中,工件的加工时间往往是一个常数,但在现代生产过程中,工件的加工时间受许多因素的影响。因此,研究工件具有学习效应的单机可控加工时间排序问题,其中工件的加工时间是其所在位置的函数,且与加工时间的控制变量有关。目标是求出最优的加工时间控制变量和最优的排序使得目标函数最小,目标函数包括极小化时间表长与控制费用的和、极小化总完工时间与控制费用的和、极小化总完工时间偏差和与控制费用和。证明他们都能转化为指派问题,从而多项式时间可解。并给出数值例子来说明问题是如何求解的。     

动态时间错位理论及应用研究

将动态时间错位（DTW）理论运用于分析和处理间歇反应过程中批次轨迹不同步问题，在间歇反应过程中，由于批次与批次之间物理特性和约束的影响，批次轨迹常常具有持续时间不同步的特点，如果要用统计的方法分析和比较2个批次轨迹的数据特征，首先必须使2个批次的持续时间长度保持一致，动态时间错位（DTW）理论可适时转换、扩张或压缩2个批次轨迹的局部模式特征，取得2轨迹之间的最短距离和最优同步路径，使2批次轨迹实现同步化。     

最短准备时间排序

本文证明了最短准备时间(SRT)排序使总的完工时间取得最小,并进一步分析了带有准备时间的带权误工工件数排序问题的一些性质.     

基于KM算法的分布式无线节点任务分配方法

单个节点无法满足各种新颖的应用程序对时延或能耗的要求,为此提出了一种分布式无线节点任务协同分配方法,通过利用周围节点的空闲资源,来降低所有节点处理任务的总时延或总能耗.首先根据层次分析法（AHP）综合任务的多维属性,如计算负载、最晚完成时间等,确定任务执行的优先级;然后建立时延和能耗的优化模型,并将其转化为二分图最大权值的匹配问题,采用Kuhn Munkras （KM）算法求解得到任务分配的最优解,实现终端节点在网络边缘高效地协同执行任务.仿真结果表明,该算法能够有效地降低任务处理的时延和能耗.     

空间相关高斯噪声中基于四阶累积量的自适应时延估计方法

针对高斯色噪声中零均值、具有非零三谱信号,提出了一种基于四阶(互)累积量的自适应时延估计方法,并分析了算法的收敛性。该方法不仅具有抑制空间相关(或不相关)高斯色噪声的能力,而且可估计正弦信号的时延,理论和仿真实验均证明了该方法在空间相关高斯色噪声背景下,具有优越于互相关方法的时延估计性能。     

An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times

Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutually independent and available at time zero. The machine processes the jobs sequentially and it is not idle if there is any job to be processed. The operation of each job cannot be interrupted. The machine cannot process more than one job at a time. A setup time is needed if the machine switches from one type of job to another. The objective is to find an optimal schedule with the minimal total jobs' completion time. While the sum of jobs' processing time is always a constant, the objective is to minimize the sum of setup times. Ant colony optimization (ACO) is a meta-heuristic that has recently been applied to scheduling problem. In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation (DPBAC) algorithm for the single-machine scheduling problem. DPBAC improves traditional ACO in following aspects: introducing Branching Method to choose starting points; improving state transition rules; introducing Mutation Method to shorten tours; improving pheromone updating rules and introducing Conditional Dynamic Perturbation Strategy. Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.     

On the Range of the Common Cycle Time in a Road Network

In a coordinated road network, the optimal common cycle time is determined by evaluating the performance of the network in the given range of cycles. Normally, this range is determined by users’ experience. And a large range of common cycle time, e.g. \[0,0\] is chosen, which requires long computation time. This study considers that the optimal common cycle time ranges between the minimal and maximal value of intersections’ individual optimal cycle time. It is proved mathematically from the convexity condition, that the delay of the network and each individual intersection are convex functions of the cycle time according to Webster delay model. Finally, 2 000 random cases for the network composed of two intersections and of eight intersections are created to underline the proposed conclusions. The results of all cases confirm the validity, and show up to 90% improvement in computation time to compare with experience range. The signal optimization tool, Synchro, is also used to validate the conclusion by 50 random cases. The results confirm reliability further.     

近似变换大纯滞后的过程最优控制

结合一个特大纯滞后的温控系统,探讨用PADE近似描述特大纯滞后,获得被控对象不速 指数函数的有理多项式传递函数模型,实现泛函条件极值的求解,再根据军事用途的最优控制与工业控制之间描述方法的区别,对最优控制系统进行改造,获得一个特大纯滞后的温度最优控制系统;用MATLAB理工算法语言对此系统进行仿真,获得它的动态性能指标、稳定性与鲁棒性,说明PID难以控制的特大纯滞后的温度对象能够采用最优控制。     

基于小波时间延迟估计的宽带信号波束形成算法研究

在阵列信号接收中,由于信号多径效应,阵列天线接收到不同时间延迟的期望信号,这使得高精度的波束形成技术成为信号处理中的一个难点。该文提出了一种考虑时延的波束形成算法。该算法首先通过小波算法对宽带接收信号进行接收信号时间延迟估计,将时延估计值与预存时延估计值进行误差比较,并对接近期望信号方向的空间多波束进行迭代优化,最后实现在空间中形成整体的自适应波束。仿真结果验证了改进算法的有效性。     

相空间重构中最优滞时的确定

针对混沌理论的相空间重构技术中,自相关函数法和互信息函数法在确定延迟时间时存在的不足,提出了根据不同嵌套维下的混沌吸引子所包含的信息量Shannon熵随延迟时间τ的变化情况,来确定不同嵌套维下重构混沌吸引子的最优滞时,这种方法把物理问题转化为纯几何问题。     

High Resolution Multipath Time Delay Estimation Based on FLOCCS-ESPRIT

The non-Gaussian α-stable distribution is introduced to model impulsive noise. Based on the theory of fractional lower order statistics （FLOS）, the fractional lower order cross-covariance （FLOCC） sequence for two received signals is obtained and the fractional lower order cross-covariance spectrum （FLOCCS） can be approached by taking a Fourier transform for the FLOCC sequence. When the FLOCCS is treated as a sequence in the time domain, the problem of multipath time delay estimation （TDE） may be converted into one on multi-frequencies estimation or directions of arrival estimation. Accordingly, the high resolution multipath TDE can be realized with the ESPRIT technology. This idea on multipath TDE is referred to as FLOCCS-ESPRIT in this paper. Computer simulations show that this method has good performance both in a Gaussian noise and in an impulsive noise environment.