基于生物免疫机理的智能调度系统建模与仿真

根据生物免疫系统的基本概念和免疫应答机理，构造了一种融生物免疫机理和专家系统为一体的生产调度模型，提出了基于工序约束的抗体优生方法和基于机床作业序列的抗体编码规则，介绍了基于生物免疫机理的智能生产调度关键算法，给出了作业车间生产调度案例及其多目标动态优化结果，通过生物免疫记忆，激增和抑制机理，基于工序约束的种子抗体优选方法和抗体进化约束性检验专家系统，有效地解决了大规模，多因素，多目标生产调度问题的求解效率和成功率。     

大规模作业车间多瓶颈调度算法

针对大规模作业车间调度问题,提出一种基于滚动窗分解的多瓶颈调度算法.该算法基于关键路径法进行多瓶颈机器的识别,沿时域将大规模调度问题分解为多个子问题进行求解.在子问题创建过程中,提出负荷均衡分布的规则,使得各工件在各子问题中的负荷均匀分布,以实现算法求解过程的稳定性;在子问题的求解过程中,遵循约束理论中瓶颈机主导非瓶颈机的原则,采用瓶颈工序最优化调度、非瓶颈工序采用分派规则快速调度的调度策略,提高算法的求解效率;通过相邻子问题间的工序衔接再优化过程,以及全局解评价子问题染色体适应度值策略,有效避免了子问题分解创建和求解过程的局限性,提高了算法的求解质量.仿真结果表明,该算法具有较佳的求解效率和质量.     

基于瓶颈工序的多资源多目标机械加工车间调度研究

为求解多资源约束的机械加工车间调度问题,建立了包括最大完工时间、平均流经时间、总拖期惩罚和生产成本在内的多目标优化模型,并结合免疫遗传算法和约束理论提出了一种基于瓶颈工序的机械加工车间调度算法。算法依据约束理论提出了一种基于工序的多参数级联编码方法和基于鼓-缓冲器-绳索(DBR)的四阶段解码方法,以及有效的交叉、变异操作。基于瓶颈工序的免疫操作及基于浓度的选择更新机制,保证了多目标优化问题的收敛性以及Pareto解集的多样性。仿真结果表明了该算法的可行性和有效性。     

解决U形装配线平衡调度问题的免疫协同进化算法

研究了混流U形装配线平衡与调度的多目标集成优化问题,提出了一种基于Pareto最优的多目标克隆免疫协同进化算法。该算法以两个单克隆抗体群对应平衡与调度两个子问题,分别编码并协同进化,以一个多克隆抗体群保存最优完整解并采取精英策略,使得子种群间既存在协作也存在竞争。提出从抗体的基因型和表现型同时评价抗体亲和度,并改进了共生伙伴选择机制以提高算法的收敛性能。仿真实例证明算法有着更快的收敛速度且比单种群进化算法更适于U形装配线平衡调度问题的求解。     

调整时间与搬运时间可分离的多目标流水车间成组调度

为解决调整时间与搬运时间可分离的流水车间成组调度问题,建立了以生产周期为主要目标、以停机次数和总搬运次数为次要目标的基于理想点法的多目标决策模型。针对成组零件生产周期求解和作业计划制定问题构建了三类时间模型。为有效对成组零件进行调度,设计了调整时间与搬运时间可分离的遗传算法。通过两个小规模仿真实验验证了该算法的有效性。为进一步评估该算法对较大规模算例的求解效果,将该算法与基本遗传算法进行了对比。研究结果表明:本研究可确定成组零件的最优排序方案,并能为工艺工序的加工、设备的调整以及运输工序的搬运制定精确的作业计划;同时,新设计的遗传算法在可接受的计算时间内能获得理想解。     

基于并行协同进化遗传算法的多协作车间计划调度

为求解多协作车间的计划调度问题,提出了并行协同进化遗传算法。该算法采用基于工序的染色体编码方案。在遗传操作过程中,首先利用提出的基于工序约束的基因调整算法进行交叉操作和变异操作,保证了新个体满足工序约束。在解码操作过程中,采用考虑设备能力空间的解码算法,使得解码产生的调度为活动调度。此外,运用协同进化的思想,提出了协同适应值计算的算法,使协作环境的变化能灵敏地反映在个体的适应值上,从而有效地指导种群的进化。实例表明,该算法能够满足多协作车间并行协同调度的要求。     

免疫算法求解多目标柔性作业车间调度研究

研究了多目标柔性作业车间调度问题，优化了设备分派方案。建立了多目标柔性作业车间调度的数学模型。提出了双种群双倍体自适应免疫算法，并用该算法求解某航空制造企业的多目标柔性作业车间调度问题，得到了优化调度方案。仿真结果表明，双种群双倍体自适应免疫算法是求解多目标柔性作业车间调度问题的有效算法。     

模具企业生产优化调度研究及软件系统实现

基于关键链项目管理（Critical Chain Project Management，CCPM），是利用一种混合智能优化算法求解多资源约束项目调度问题，解决传统调度优化算法的不足，提高这类问题的求解质量。首先运用一类启发式算法识别项目关键链，并设置缓冲区尺寸，其次以项目总工期和在制品库存为优化目标建立数学模型，设计一种混合智能优化算法求解调度中出现的问题。基于VisualC#．NET和SQL Server2000软件，开发了生产调度软件系统，并在企业运行，效果良好。     

作业车间类型多机器人制造单元调度算法

针对带多台机器人的作业车间类型机器人制造单元调度问题的特点,研究了以最小化最大完工时间为优化目标、将邻域搜索策略与启发式规则相结合的混合遗传算法,建立了作业车间类型多机器人制造单元调度问题的数学优化模型和析取图模型。基于析取图关键路径,采取移动机床块、交换机器人块、调整任务分配来构建搜索邻域;用启发式搬运工序插入法和启发式搬运任务分配法相结合的三层调度方法初始化种群;将基于邻域结构的局部搜索算法和基于三层调度的遗传算法相结合,有效实现问题的求解。通过基准算例测试表明,混合遗传算法有效并优于其他算法。     

基于改进免疫遗传算法的混合车间调度研究

建立了以最大总完成时间最小为目标的混合车间调度模型。该模型包括作业车间和并行流水装配车间两部分调度问题。为降低问题求解难度,采用分解的策略对调度问题分阶段求解,并引入多Agent协商机制和模拟退火算法与免疫遗传算法相结合,提出了基于分解策略的免疫遗传算法,并通过在某汽车减振器企业的实施验证了模型和算法的有效性。     

考虑批量和辅助时间等生产工况的智能调度方法

根据车间调度实际要求,综合考虑批量、毛坯到达时间和辅助时间等生产工况,研究复杂生产调度问题。给出了此问题的模型及求解此问题的生物免疫算法模型,并介绍了基于生物免疫机理的智能调度方法实现过程中的关键技术,包括抗体编码设计、工件起始加工时间的计算准则和优化方法、交叉和变异操作等。对考虑辅助时间、批量等多工况问题的测试结果表明,所提出的综合考虑批量和辅助时间等生产工况的智能调度方法是有效的, 且在调度过程中考虑批量是必要的。     

Study on job shop scheduling with sequence-dependent setup times using biological immune algorithm

Sequence-dependent setup times are one of the most important factors for the optimization of scheduling the production targets. Usually, they include the changing of tools, fixtures, cutting tools and the cleaning of production equipments. Some of them are relevant not only to the sequence requirement of the products to be processed on the equipment, but also to the processing requirement of the adjoining sequence. In this paper, a job shop scheduling problem with sequence-dependent setup times is described. A mixed integer program model is adopted to deal with this type of problem, and a scheduling algorithm based on biologic immunity mechanism is introduced. The result shows that the antibody encoding method and the mechanism of antibody proliferation and suppression can not only ensure the diversity of the antibody, but can also greatly improve the effectiveness of dealing with complex problems. Finally, a scheduling problem of finishing processing for a woollen mill is analyzed with its result described.     

An immune algorithm for hybrid flow shop scheduling problem with time lags and sequence-dependent setup times

This paper deals with hybrid flow shop scheduling problems considering time lags and sequence-dependent setup times which have wide application in real-world problems. Most of the researches on operations scheduling problems have ignored time lags. A mathematical model is presented which is capable of solving the small size of the considered problem in a reasonable time. Since these problems are strongly NP-hard, a meta-heuristic algorithm based on the immune algorithm is developed. The optimization criterion considered in this paper is the minimization of the makespan. Numerical experiments are used to evaluate the performance and effectiveness of the proposed algorithm. The results of the proposed algorithm are compared with the presented mathematical programming model and a benchmark algorithm. Computational results indicate that the proposed algorithm can produce near-optimal solutions in a short computational time. Moreover, it can be applied easily in real factory conditions and for large-sized problems.     

两机零等待流水车间调度问题的启发式算法

为实现两机零等待流水车间调度问题的总流程时间最小化,结合问题的结构信息提出了一种快速求解近优解的启发式算法。在该类问题中,工件在每台机器上的操作包括调整、加工和移除3部分,且调整和移除时间都与工件的加工时间相互分离。首先分析了该类问题的优化性质,结合优化性质进而构造出求解算法。在中小规模和大规模问题上,将启发式算法的结果分别与最优解和最优解的下界值进行了比较。大量数值计算实验表明了该算法的有效性和解决大规模实际问题的潜力。     

A genetic algorithm and particle swarm optimization for no-wait flow shop problem with separable setup times and makespan criterion

This paper considers the problem of no-wait flow shop scheduling, in which a number of jobs are available for processing on a number of machines in a flow shop context with the added constraint that there should be no waiting time between consecutive operations of a job. Each operation has a separable setup time, meaning that the setup time of an operation is independent on the previous operations; and the machine can be prepared for a specific operation and remain idle before the operation actually starts. The considered objective function in this paper is the makespan. The problem is proven to be NP-hard. In this paper, two frameworks based on genetic algorithm and particle swarm optimization are developed to deal with the problem. For the case of no-wait flow shop problem without setup times, the developed algorithms are applied to a large number of benchmark problems from the literature. Computational results confirm that the proposed algorithms outperform other methods by improving many of the best-known solutions for the test problems. For the problems with setup time, the algorithms are compared against the famous 2-Opt algorithm. Such comparison reveals the efficiency of the proposed method in solving the problem when separable setup times are considered.     

Robust metaheuristics for group scheduling with sequence-dependent setup times in hybrid flexible flow shops

This paper considers group scheduling problem in hybrid flexible flow shop with sequence-dependent setup times to minimize makespan. Group scheduling problem consists of two levels, namely scheduling of groups and jobs within each group. In order to solve problems with this context, two new metaheuristics based on simulated annealing (SA) and genetic algorithm (GA) are developed. A design procedure is developed to specify and adjust significant parameters for SA- and GA-based metaheuristics. The proposed procedure is based on the response surface methodology and two types of objective function are considered to develop multiple-objective decision making model. For comparing metaheuristics, makespan and elapsed time to obtain it are considered as two response variables representing effectiveness and efficiency of algorithms. Based on obtained results in the aspect of makespan, GA-based metaheuristic is recommended for solving group scheduling problems in hybrid flexible flow shop in all sizes and for elapsed time SA-based metaheuristic has better results.     

基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题

针对多目标柔性作业车间调度问题搜索空间的离散性和求解算法的收敛性,提出一种基于Pareto优化的离散自由搜索算法来求解多目标柔性作业车间调度问题。在建立基于Markov链数学模型的基础上,证明了算法以概率1收敛;引入首达最优解期望时间来分析算法收敛速度,并分析了算法时间复杂度。采用基于工序排序和机器分配的个体表达方式,在多目标柔性作业车间离散域,利用自由搜索算法在邻域小步幅精确搜索和在全局空间大步幅勘测进行寻优;通过自由搜索算法自适应赋予个体各异辨别能力和Pareto优化概念来比较个体优劣性,不仅保留优化个体,而且使个体寻优方向沿多目标柔性作业车间调度问题Pareto前沿逼近。通过对搜索过程中产生的伪调度方案进行可行性判定,以确保调度方案可行。采用10×10FJSP和8×8FJSP问题的实例进行寻优测试,验证了所提算法的可行性和有效性。     

基于强化学习的分布式光伏运维资源动态调度

针对分布式光伏运维资源调度过程中因动态因素影响导致调度计划难以实施的问题,提出基于强化学习的分布式光伏运维资源动态调度方法.该方法通过构建动态调度规则同步调整运维任务的优先级,并以新计划完成成本最低和完成时间最短为优化目标构建动态调度模型.采用Q-Learning求解模型,通过实验对比,Q-Learning算法的求解速...     

基于混沌粒子群算法的单台批加工设备调度

提出了一种基于混沌粒子群算法的双层调度方法。双层调度的外层基于加工时间最小的目标构建组批方法集,然后将其作为内层算法的搜索空间;双层调度的内层以加工时间最小为适应值函数,采用混沌粒子群算法求解批次排序的最优解,得到最优的组批方法及其排序。通过仿真验证了该算法在搜索时间和搜索精度的可行性。     

带准备时间的柔性流水车间多序列有限缓冲区排产优化问题

针对带准备时间的柔性流水车间多序列有限缓冲区排产优化问题,提出一种改进的紧致遗传算法（Improved compactgenetic algorithm,ICGA）与局部指派规则结合的方法来解决该问题。全局优化过程采用改进的紧致遗传算法,为了克服紧致遗传算法（Compact genetic algorithm,CGA）易早熟收敛的问题,提出一种基于高斯映射的概率模型更新方式,在保持紧致遗传算法快速收敛特性的前提下,扩展了种群中个体的多样性,增强了算法进化活力。为减少生产阻塞和降低准备时间对排产过程的影响,设计了多种局部启发式规则来指导工件进出多序列有限缓冲区的分配和选择过程。采用某客车制造企业中的实例数据进行测试,测试结果表明,改进的紧致遗传算法与局部指派规则配合使用,能够有效解决带准备时间的柔性流水车间多序列有限缓冲区排产优化问题。