带机器准备时间的同类机调度问题的启发式算法

研究了带机器准备时间的同类机最大完工时间调度问题, 首先证明了工件互换的四个性质, 进而提出了一种启发式算法, 此算法以LPT算法得到的序列作为初始解, 利用互换性质重复对最大完工时间最大和最大完工时间最小的两台机器上的工件进行交换, 以提高解的质量. 实验结果证明了此算法的有效性.     

加工时间依赖于资源消耗量的平行机调度问题

研究了一类平行机调度问题,其中假定作业加工时间是资源消耗量的线性减函数,调度的目标是在限定最大完工时间时最小化资源消耗总量. 分析了对应单机问题的最优算法和下界构造方法,进而提出了两个优化策略用于构造模拟退火算法和禁忌搜索算法.考虑了多种最大完工时间限制情形, 构造了大量随机实验数据,对算法解的精确度及计算效率进行了测试.实验表明所构造的模拟退火算法能够在合理的时间内提供高质量的满意解.     

含有到达时间的最大完成时间同类机调度算法

研究了目标函数是最小最大完成时间的同类机调度问题,其中作业到达时间可能不同。此问题被证明是NP-hard问题。通过对单机和同型机的相应问题研究成果的推广,提出5个启发式算法,给出算例及其计算结果,并通过实验对算法的性能及算法适应的情形进行了分析,与现有Koulamas＆Kyparisis的算法进行了比较。     

含作业到达时间的同类机调度问题启发式算法

研究了目标函数是最小化完成时间和的同类机调度问题,其中作业到达时间可能不同.此问题被证明是强NP-hard问题.由于同类机调度是一种重要的平行机调度问题,而最小完成时间和目标是最常见的正则目标之一,因此完成时间和的同类机调度问题在相关研究领域具有非常重要的地位.为此问题建立数学模型,通过对单机和同型机的相应问题研究成果的推广,提出6个启发式算法,给出算例及其计算结果,并通过实验对算法的性能及算法适应的情形进行了分析.     

面向两客户的差异工件平行机批调度问题

将差异工件的批调度问题扩展到两客户生产环境,建立了两个客户分别以最小化制造时间跨度和最小化最大工件延迟时间为生产目标的差异工件平行机批调度模型.首先提出了一种启发式算法TSEDD(two-set earliest due date)对分批方案进行排序并安排到平行机,然后设计了一个多目标蚁群优化算法MOACO(multi-objective ant colony optimization)对不同客户中的工件进行分批并结合TSEDD完成对问题Pareto最优解集的求解.实验结果表明,与经典的多目标问题求解算法NSGA-Ⅱ和SPEA2算法相比,MOACO具有较好的求解效果,且随着问题中工件规模的增大,算法的优势更加明显.     

求解目标是最小完成时间和的同类机调度的改进算法

研究了目标函数是完成时间和的同类机调度问题。同类机调度是一种重要的平行机调度问题,而最小完成时间和目标是最常见的规则目标一种,完成时间和的同类机调度问题在相关研究领域具有非常重要的地位。首先为此问题建立数学模型,然后提出一种改进的启发式算法,并通过实验验证了算法的性能。     

模糊作业时间的并行多机调度问题与算法研究

结合抚顺钢厂实际,利用模糊数学理论,对生产实际中的模糊作业时间进行处理,通过定理将模糊作业时间问题转换为非模糊的精确问题,利用禁忌搜索智能优化方法,对问题进行了求解,使调度计划具有一定的柔性,让管理者能够掌握调度时间范围,从而使计划调度更接近现实,大大缩短总完工时间,对于钢厂一体化管理,使连铸生产的高温铸坯,能够在允许时间范围到达热轧厂,降低了能源消耗,缩短生产周期。     

加工时间线性递减的平行机排序问题

主要讨论了具有两台处理机的平行机排序问题和每批恰为k个工件的串行工件同时加工排序的平行机排序问题。在这两个问题中,工件加工时间均为开工时间的线性递减函数,目标函数为极小化总完工时间。对于第一个问题,证明了其最优排序可由工件按基本加工时间不减排列得到,由此得出其最优算法,并指出了该结论对于加工时间随开工时间线性递增的情况并不成立。对于第二个问题,根据其与第一个问题在某些性质上的相似性,给出了其最优算法。最后指出所讨论的两个问题的结论均可推广到m台处理机的情况。     

基于MMAS算法的带到达时间批调度问题研究

研究了工件带到达时间的目标为极小最大完工时间(Cmax)的单机批调度问题,采用最大-最小蚂蚁系统(max-min ant system,MMAS)进行求解.针对问题带到达时间以及分批的特性,提出了两种候选列表(candidate list)构建批序列,有效地缩小了搜索空间的维度;考虑两种候选列表的工件对构造解具有不同的影响,针对不同的候选列表设计了相应的启发式信息.仿真实验部分从求解质量和时间性能两方面比较了本文提出的算法和标准的蚂蚁系统(ant system,AS)算法以及使用不同候选列表的MMAS算法.结果表明,本文的算法在质量和时间两方面均全面优于标准的AS算法,而提出的候选列表使得该算法在大幅度提高时间性能的同时,仍然能够取得近似最优解,从而在求解质量和时间性能两方面取得平衡.     

基于机动时间的平行序链顺序优化算法设计

平行序链的顺序优化问题一直是目前网络计划优化理论研究的焦点问题之一.从网络本身的规律性出发,对具有很大推广价值的四个平行序链的顺序优化问题进行研究,利用路长定理计算序链调整过程中新增路线的路长,并给出了可靠、有效的删减路长计算的方法,在此基础上,设计出了该问题的优化算法.实例表明,该算法简单易行,便于应用.     

一类带有安装时间的单机成组排序问题

针对一类带有准备时间和安装时间的单机成组排序问题,给出了求解最优排序的多项式算法。其中每个工件都具有自己的准备时间,组和组之间具有安装时间,并且安装时间和已经加工完工件的加工时间有关。所有工件在机器上加工时,一次只能加工一个工件,工件不可中断,组内工件连续加工,组和组之间需要安装时间。对目标函数为极小化最大完工时间的单机成组排序问题,给出了求解最优排序的多项式算法。原问题不是成组问题,为此在原问题的基础上添加了工件的成组问题且组内每个工件都具有自己准备时间,其结果是依然能给出求解最优排序的多项式算法。     

IFF算法求解顺序依赖的单机总权重拖期调度问题

转换(启动)时间是工业中带有清洗、更换物料工序的生产过程所需要的, 该时间一般很大程度上依赖于紧接工序. 这种环境下的调度问题都是工件顺序依赖的. 本文研究顺序依赖的单机总权重拖期调度问题, 为NP难的组合优化问题. 针对该问题, 提出了一种迭代的过滤-扇出算法(IFF), 算法以分支树的结构形式在解空间中搜索. 在算法中, 当分支移动不能改进根节点时, 重新产生有继承性的根节点, 使得算法继续进行. 根据问题特性, 提出了带序列片段重组和参考局部搜索的分支移动策略, 获得分支节点. 对文献中的120组数据的算法测试结果表明: 对大多数实例, IFF算法的计算结果优于或不劣于DE算法和DPSO算法的计算结果, 同时改进了42个实例的最好解.     

平顺移动模式下考虑加工时间与调整时间可分离的多目标流水车间批量调度

对平行顺序移动模式下考虑加工时间与调整时间可分离的多目标流水车间批量调度问题展开研究.构建以加工制造设备总停机次数、批量工件生产周期以及搬运批量工件的总次数为决策目标的基于分层序列法的多目标决策模型,利用该模型可确定批量工件的最优加工排序方案.建立平行顺序移动模式的加工与调整时间模型,该模型是求解生产周期的基础,也是为批量工件的最优调度方案制定生产作业计划的依据.提出并设计平行顺序移动模式下考虑加工时间与调整时间可分离的禁忌搜索算法对问题进行求解.研究结果表明:本研究可为平顺移动模式下考虑加工时间与调整时间可分离的批量生产流水车间选出批量工件的最优调度方案,同时可为批量工件的加工和加工制造设备的调整制定精确的生产作业计划.     

一类安装时间受资源约束的单机成组排序问题

讨论了具有连续资源的单机成组排序问题。在这类问题中,同一组内的工件不允许分开加工,各工件组的安装时间是所消耗资源的线性非增连续函数,同一组内的工件具有同位置有关的学习效应。考虑三类问题,第一类问题的目标函数是在满足最大完工时间限制条件下,极小化资源消耗总量;第二类问题是在满足资源消耗总量限制条件下,极小化最大完工时间;第三类问题是在满足资源消耗总量限制条件下,极小化最大完工时间与资源加权消耗总量的加权线性组合。对三类问题分别给出了求解最优资源分配的方法,并通过数值例子进行了说明。     

交货期窗口下的并行机调度问题的遗传算法

给出了一种求解不同交货期窗口的并行机调度问题的混合遗传算法，根据问题的特征采用扩展排列编码方式表示工件的分配和排列，利用给出的调度优先级规则和最好适应值规则相结合的启发式算法对每台机器上工件的顺序进行调整，实验表明所给的算法是有效的。     

Adaptive subsequence adjustment with evolutionary asymmetric path-relinking for TDRSS scheduling

Due to the limited transmission resources for data relay in the tracking and data relay satellite system （TDRSS）, there are many job requirements in busy days which will be discarded in the conventional job scheduling model. Therefore, the improvement of scheduling efficiency in the TDRSS can not only help to increase the resource utilities, but also to reduce the scheduling failure ratio. A model of nonhomogeneous parallel machines scheduling problems with time window （NPM-TW） is firstly built up for the TDRSS, considering the distinct features of the variable preparation time and the nonhomogeneous transmission rates for different types of antennas on each tracking and data relay satellite （TDRS）. Then, an adaptive subsequence adjustment （ASA） framework with evolutionary asymmetric path-relinking （EvAPR） is proposed to solve this problem, in which an asymmetric progressive crossover operation is involved to overcome the local optima by the conventional job inserting methods. The numerical results show that, compared with the classical greedy randomized adaptive search procedure （GRASP） algorithm, the scheduling failure ratio of jobs can be reduced over 11% on average by the proposed ASA with EvAPR.     

An improved branch-and-bound algorithm to minimize the weighted flowtime on identical parallel machines with family setup times

This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.     

基于并行机加工能力配置的多轮拍卖机制研究

在私有信息不公开的分散决策下,针对需要承诺交货期限的稀缺并行机加工能力配置问题,以改善分散系统无秩序代价为目标,设计了一种基于时间维度配置稀缺资源的多轮拍卖机制.具体地,该机制根据资源稀缺性受机器加工能力和订单交货期限双重影响的特点,设计线性歧视资源定价方式,既保证定价的公平性,合理性和有效性,又引导任务主体披露真实订单信息,实现分散系统下稀缺资源配置的高效率;该机制中的定标问题是具有NP难属性的组合优化问题,本文设计基于拉格朗日松弛技术的启发式算法,以提高该问题的计算效率和实际应用性.数值实验结果显示,该拍卖机制能显著改善分散决策下并行机加工能力配置的无秩序代价,拍卖机制下的系统总收益平均达全局系统总收益的93.9%.