“合成链”算法与一类链优先约束的单机分批排序问题

讨论问题1|chains,B|Cmax具体可描述为:有n条链,其中一条链上有n个工件,其余的n-1条链上的工件数之和为常数k,且工件的加工时间不限制,目标函数为最大完工时间。我们对该问题B=2的情况进行了深入的探讨,在研究过程中首次提出"合成链"算法,给出了时间复杂性为O(nk))的多项式时间算法     

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

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

具有链式约束的单机随机排序问题

研究具有链式约束的单机随机排序问题，目标函数为加权总完工时间的数学期望．分别对于链可中断和链不可中断两种情况，通过理论分析，给出了该问题的优先策略．     

同时可加工多种零件的一类单机排序问题的多项式时间算法

本文研究同时可加工多种零件的单机排序问题，在加工速度全同的条件下，导出了多项式时间算法，在每次只能加工两个零件且有可再生资源约束的条件下建立了匹配算法，并得到这种算法的计算复杂性。     

一类复合并行机排序问题的多项式时间算法

在经典排序论中，一般都作以下两条假设；每台机器在任一时刻至多加工一个零件，每个零件在任一时至多被一台机器加工。本文研究在并行加工中多台机器可同时加工一个零件的斐邓问题，且每个零件可在固定的一个机器的子集上加工。在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究这种问题的计算复杂性。     

单机有界分批排序

本文研究了当所有工件同时到达且工期相同时的单机有界分批排序问题,给出了求解加权总误工数∑WJUJ问题的多项式时间算法．     

一类复合并行机排序问题计算复杂性研究

研究确定性排序理论的一个新模型;考虑４台机器的集合Ｍ＝（Ｍ１,Ｍ２,Ｍ３,Ｍ４）和ｎ个零件的集合Ｊ＝（ｊ８,ｊ２,…ｊｎ）,每个零件同时被２＾ｉ＝（ｉ＝０,１,２）台机器同时加工。证明了在不允许间断,优化指标为作业排序长度的条件下,该问题是强ＮＰ－完全问题,没有多项式时间算法。     

一类装配式作业排序问题计算复杂性研究

探讨新型工作业排序问题的计算复杂性，证明了在优化指标为作业排序长度的条件下该问题是ＮＰ－完全问题。     

一类加工时间依赖资源的链约束排序问题

考虑了一类工件的加工时间依赖资源,工件具有链约束,目标函数为极小化加权完工时间和的单机排序问题,给出了一个有效的下降算法。     

An Optimization Method for a Single Machine Multi-family Scheduling Problem with Qualification Run Constraints

考虑设备资格约束的单机多产品族问题调度优化

周炳海,顾佳颖

（同济大学 机械与能源工程学院,上海 201804）

创新点说明：

除考虑传统的换模外,考虑控制产品质量的设备资格验证过程,建立数学模型,提出产生可行解的性质、定理,以减少算法的搜索空间,并构建一种基于差分进化的自适应混合灾变算法,并证明其优于已有算法。

研究目的：

为控制产品质量的同时减少产品完工时间,构建一种高效的算法以寻找设备资格验证和换模次数之间的平衡点。

研究方法：

1）问题描述及数学建模：复杂系统调度理论,运筹学理论,约束理论;

2）算法构造：进化算法,启发式规则,定理构造推导;

3）实验分析：敏感性分析、数值仿真实验、对比实验

结果：

1） 通过实验验证了设备资格验证时间对调度造成的影响,当设备资格验证时间越长,换模次数和设备资格验证次数之间的权衡对调度的影响也越大;

2）与差分进化算法对比发现,引入自适应灾变算子及邻域搜索算子后的差分进化算法性能更优,执行速度更快;

3）与已有的解决此类问题的结构式算法相比,该改进后的算法不论在算法时间还是性能上都具有明显的竞争力。

结论：

设备资格验证时间会对调度造成影响,所提出的基于差分进化的自适应混合灾变算法可有效解决考虑设备资格验证时间的单机调度问题,并且其性能优于已有算法,这为解决相似调度问题提供了技术上的支持和借鉴。

关键词：换模;设备资格验证;多产品族;调度;混合差分进化算法

     

两个代理的单机排序问题研究

研究了两个代理的单机排序问题.其中第一个代理以完工时间和为目标函数,第二个代理以误工工件个数为目标函数.排序问题的目标是寻找一种排序,使得在第二个代理的目标函数不超过给定上界的情况下,第一个代理的目标函数最小.本文还对这一问题设计了一个拟多项式时间算法.     

网格环境下基于多QoS约束的任务调度算法研究

针对网格任务调度过程中的QoS （Quality of Service）约束可扩展性不足、资源利用率低等问题,提出一种多QoS约束的Min_Min任务调度算法。该算法首先计算待调度任务QoS与每个资源QoS的匹配值,并根据匹配值的大小确定任务分配的先后顺序,然后再依次对已排序的任务选取具有最小最早完成时间所对应的资源进行分配。在保证QoS匹配质量的同时,也注重资源节点的利用率。仿真实验结果表明,该算法在综合性能上明显优于Min_Min算法。     

基于功耗约束的SOC测试调度研究

通过研究SOC测试中满足功耗约束条件的测试规划问题,比较并总结了当前普遍使用的几种功耗约束的SOC测试调度算法.经过对功耗约束条件下SOC测试的现状和存在的基本问题,以及SOC测试期间由于测试功耗剧增而导致的安全可靠性问题进行了分析,提出了一种基于量子算法满足功耗约束的SOC测试调度算法,与同类算法相比,该算法提高了SOC测试的可靠性与实用性,优化结果较好.     

Parallel Machine Scheduling Models with Fuzzy Parameters and Precedence Constraints： A Credibility Approach

A method for modeling the parallel machine scheduling problems with fuzzy parameters and precedence constraints based on credibility measure is provided. For the given n jobs to be processed on m machines, it is assumed that the processing times and the due dates are nonnegative fuzzy numbers and all the weights are positive, crisp numbers. Based on credibility measure, three parallel machine scheduling problems and a goal-programming model are formulated. Feasible schedules are evaluated not only by their objective values but also by the credibility degree of satisfaction with their precedence constraints. The genetic algorithm is utilized to find the best solutions in a short period of time. An illustrative numerical example is also given. Simulation results show that the proposed models are effective, which can deal with the parallel machine scheduling problems with fuzzy parameters and precedence constraints based on credibility measure.     

基于CICQ交换结构的低复杂度调度算法

针对CICQ权值仲裁策略复杂度高的不足,提出一种新的调度策略——LQP-RR（Long Queue Prioritized-Round Robin）。该算法利用VOQ队列局部变化的特性,简化了权值仲裁策略复杂的排序操作,只在输入端进行一次比较操作,并采用辅助轮询指针配合调度以保证算法的公平性,其算法复杂度仅为O（1）,硬件实现简单,扩展性能良好。通过流体模型证明该算法对满足强大数定律的许可输入流量能够达到100%的吞吐率性能。仿真结果进一步表明LQP-RR调度算法在各种流量模型下都能稳定运行,且具有良好的时延和吞吐率性能。     

成组排序中确定公共交货期使误工工件数最小问题

本文讨论的问题是在单台机器成组加工中为已经到达的工件集确定公共的交货期和工件的加工顺序，使因确定交货期所化代价和因误工造成的损失之和为最小。本文对满足成组技术假设和不满足成组技术假设这两种情况分别给出寻找最优解的多项式算法。     

基于单机排序问题的降落飞机分组排序方法

为使单跑道降落飞机排序结果在实际操作时可行、简单，首先限制同一航路段上的飞机按照先来先服务的原则排序，在最终的排序中，其拓扑次序不变；其次提出了将飞机分组排序的思想，对同一航路段上刚好满足最小安全间隔的飞机做为一个飞机组参与排序。使用1|chains|∑wjcj做为排序模型，通过求解各飞机链的ρ因子可以快速得到排序结果。将本方法用于对双流国际机场和其它几个机场的实际航迹数据进行计算，得到的排序序列完全符合实际管制需要，具有很高的推广应用价值。