基于优先规则的活动成本目标资源受限工程调度

首先给出了该问题的数学模型,问题分析得出该问题也是一类NP完全问题,继而讨论了启发式方法进行问题求解的基本思想,基于此,结合活动成本目标的特性提出了问题求解的串行调度方案和并行调度方案,并设计了相应的几种优先规则,分析了算法的时间复杂性.基于改造PSPLIB中的单模式算例测试,并行调度方案的结果大多优于串行调度方案,而在最大最早完成时间和最大活动先序相关成本等两种优先规则下的调度方法计算效果相对较好.     

基于深度学习的RCPSP调度优先规则实时动态选择算法

针对资源受限项目调度问题,以最小化项目完成时间为目标,设计基于深度学习的调度优先规则实时动态选择算法,在每个调度阶段实时选择优先规则进行活动安排.通过构建深度神经网络模型,确定已调度项目在各阶段的项目状态与最佳优先规则之间的映射关系,再据此为待调度项目实时动态选择优先规则,结合串行调度机制生成最终调度计划.实验研究表明:实时动态选择优先规则算法表现优于文中所涉及的单一优先规则算法及混合优先规则算法,且具有更好的泛化性;此外,与元启发式算法相比该算法具有更高的求解效率.     

软计算求解并行多机成组工件调度问题

自从Zade将模糊理论引入求解组合优化问题以来，出现了很多基于模糊规则与智能优化算法相结合的软计算方法，文章尝试将这种方法用于解决并行多机成组工件flow-time问题，本问题中，设有n个工件计划在M台并行一致的机器上加工，这n个工作根据相似性分为b组，开始加工时，需要一个准备时间，当工件接续在同组工件之后加工时，不需要准备时间，反之，接续在不同组工件之后加工时，需要一个准备时间，本问题的目标是找到一个工件加工的调度顺序序列，使M台机器总的流水时间最小，在文章中，作者首次利用模糊规则量化结合遗传算法的软计算方法求解这类复杂的组合优化问题，最后给出计算实例及仿真结果。     

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

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

基于模糊规则的货运车调度方法

传统上 ,调度员在安排车辆满足客户的要求时 ,主要考虑车辆与需车点的距离 ,即让靠客户最近的货车去提供服务以减少时间 .但实际上 ,调度员还应设法对所有的司机提供相对平等的“生意机会”,即具备公正性 .因此 ,实际调度原则至少应考虑“距离的远近”和“使用次数多少”两个因素 .对此 ,本文提出了一种用模糊规则协调这两个因素的方法 ,并进行了相应的计算机仿真.     

具有时间窗口约束的并行机床调度问题研究

具有时间窗口约束的并行机床调度问题可以被描述为在M台互不相同机器上安排加工N个工件。每个工件只能在一个给定机器子集中的一台机器上加工，且加工过程只能在给定的离散时间窗口内进行，并且工件的加工时间长度和时间窗口约束与加工机器有关。为了解决该问题，本文给出一种集成约束规划与禁忌搜索的搜索算法，其中约束规划系统被作为验证解的可行性和确定变量的值，而禁忌搜索过程被用来对解空间进行搜索。讨论禁忌搜索过程中的初始解产生、邻域结构、禁忌列表、解空间搜索等算法设计问题。最后给出算法在不同问题实例上的算法效率比较及分析。     

带不可用时间段的单机调度问题的启发式算法

研究了机器带有一个不可用时间段的部分可续型单机最大完工时间调度问题,提出了一种启发式算法,证明了其相对误差界,并举例说明该界是紧的,而且据此推出了该算法对相应不可续问题的相对误差界,此界低于该问题现有算法的界.将此算法与其它算法进行了多方面的比较,包括利用随机数据进行实验以评估其相对误差,结果表明此算法是一种非常高效的启发式算法.     

带运输和设置时间的无等待并行流水车间调度问题研究

研究了一类从无缝钢管生产作业中提炼出的新的并行流水车间调度问题.该问题具有工件无等待、工序之间存在运输时间、设备需要调整时间等特点.这些特点使得问题变得相当复杂.建立了大规模的混合整数规划模型,通过提出的变换方法简化和降低了模型的规模.针对此模型,提出并开发了适合此问题的遗传算法.通过实验比较六种规则调度方法及遗传算法的性能.计算结果表明,六种规则调度中最好的方法是SPT,而遗传算法调度的性能优于SPT.     

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

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

基于仿真的双目标并行机开放车间自适应动态调度

针对工件到达时间与加工时间不确定,且存在紧急工件的并行机开放车间调度问题,以TWC(total weighted completion time)与TWT(total weighted tardiness)为优化目标,设计了一种集成FlexSim仿真模型与NSGA-Ⅱ算法的自适应动态调度方法。该方法以FlexSim模型仿真工件的生成和加工为基础,根据车间实时负荷确定动态调度周期,对紧急工件进行右移重调度,利用NSGA-Ⅱ算法生成双目标优化的调度方案。某晶粒拣选车间生产数据的实验结果表明,相较于利用规则的实时动态调度与固定周期重调度,提出的方法能够在最小化调度偏离度的同时获得满意解。     

Heuristic algorithms for scheduling on uniform parallel machines with heads and tails

This paper considers the uniform parallel machine scheduling problem with unequal release dates and delivery times to minimize the maximum completion time.For this NP-hard problem,the largest sum of release date,processing time and delivery time first rule is designed to determine a certain machine for each job,and the largest difference between delivery time and release date first rule is designed to sequence the jobs scheduled on the same machine,and then a novel algorithm for the scheduling problem is built.To evaluate the performance of the proposed algorithm,a lower bound for the problem is proposed.The accuracy of the proposed algorithm is tested based on the data with problem size varying from 200 jobs to 600 jobs.The computational results indicate that the average relative error between the proposed algorithm and the lower bound is only 0.667%,therefore the solutions obtained by the proposed algorithm are very accurate.     

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

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

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.     

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

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

基于递阶遗传算法的最小加权完工时间并行机调度

针对最小化加权完工时间的等同和非等同并行多机调度一类问题,提出了一种递阶遗传算法.该算法根据问题的特点,采用一种染色体递阶编码方案,此编码与调度方案一一对应.计算结果表明,递阶遗传算法是有效的,能适用于大规模等同和非等同并行多机调度问题,通过与Cheng所作编码的遗传算法比较,用递阶遗传算法优化并行机调度操作简单并且收敛速度快.     

含释放时间的同类机问题的可变邻域搜索算法

研究了目标函数是最小化完成时间和的同类机调度问题,其中作业释放时间可能不同.此问题被证明是强NP-hard问题.为此问题构造了一种启发式算法HRS,进而以HRS算法求解结果为初始解构造了问题的可变邻域搜索算法HRS-VNS.大量的随机数据实验用于验证算法的性能和效率.     

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

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