一种求解资源受限多项目调度问题的分解算法

针对资源受限多项目调度的多目标优化问题,采用约束逐层分解策略,提出了依次处理项目时序约束和资源约束的两阶段分解算法.第一阶段为时序约束优化阶段,采用蚁群算法进行任务列表的优化求解.通过改进信息素增量规则并采用并联进度生成机制,提高蚁群算法的求解效率和质量.其中,在构建任务合成链表的过程中遇到并联活动抢夺资源情形,采用基于熵权的逼近理想解排序法和基于有序加权平均算子的多属性决策方法来确定活动的综合权重,并依据权重对冲突活动进行排序,实现资源的冲突消解.第二阶段为资源约束优化阶段,以获得的优化任务合成链表为输入,逐项进行资源能力约束的核查与调整,最终生成项目调度的优化方案.通过多项目算例仿真结果验证了所提方法的有效性.     

含串行批处理机的三阶段混合流水车间调度问题

基于钢铁行业炼钢-连铸-热轧一体化生产作业,提炼出新的三阶段混合流水车间调度问题。其中第二阶段有多台串行批处理机而其他阶段为离散机,批加工时间等于同一批内所有工件在第二阶段的加工时间之和,且考虑了设备需要调整时间等实际生产特征。以最小化总加权完成时间为目标函数,对该问题建立数学模型,提出基于工件分解策略的拉格朗日松弛算法,引入拉格朗日乘子将机器能力约束和批加工约束松弛到目标函数中,进而将形成的松弛问题分解为较易求解的多个工件级子问题,利用动态规划算法求解子问题,设计启发式算法将松弛问题的解转换为原问题的可行解。仿真实验表明,所设计的算法能够在可接受的运行时间内得到较好的近优解。     

一类带工艺约束的关键工序作业排序问题

关键工序的作业排序问题是生产车间的一项重要内容,讨论了把n个带工艺约束的任务安排给m台设备加工,使得总加工时间最短的一类排序问题。在建立了该问题的数学模型的基础上,巧妙地把这个排序问题转化为指派问题,并采用匈牙利算法对该问题进行了求解。实例证明,建立的数学模型和提出的问题转换方法便于理解,求解快速有效。     

带模糊排序的移动瓶颈法求解不确定调度问题

综合应用模糊排序法和移动瓶颈法（Shifting Bottleneck Procedures．SBP）来求解加工时间不确定的Job—shop调度问题。首先对移动瓶颈法作简要介绍,并给出将模糊数转换为确定数的相关方程式．然后通过一个实际的算例演示该算法的详细求解过程。结果表明,该算法可用来有效求解一类带模糊加工时间的Job—shop调度问题。     

基于工件聚类的并行机调度算法及其应用

针对纺织生产广泛存在的带工件释放时间、以最小化总拖期工件数和总拖期时间为目标的大规模并行机调度问题,提出一种基于工件聚类的遗传算法。该算法将求解过程分为工件聚类和工件排序两个阶段。在工件聚类阶段,基于影响并行机调度性能的重要调度特征量,采用改进的模糊C-均值聚类方法将所有待上机工件分为多个聚类;在工件排序阶段,采用基于规则编码的遗传算法,优化各聚类内工件的加工顺序。数值计算结果及实际应用效果表明,所提出的算法适用于求解带工件释放时间的大规模并行机调度问题。     

加工装配式流水车间节能调度建模与优化

为解决具有加工装配一体化的流水车间节能调度问题,以加工机器最小能耗为优化目标,建立加工装配式流水车间节能调度模型。该模型将装配线视为具有特殊约束的加工生产线,再结合考虑车间工件工序、装配工序、装配子件加工等约束条件。分别针对简单和复杂装配约束的问题,采用混合差分进化算法求解最小能耗下工件调度方案,并与自适应差分算法对比。实验结果证明了混合差分进化算法求解该问题的有效性。     

基于约束矩阵的启发式工序排序方法

针对零件工艺设计过程中的工序排序问题,提出一种基于约束矩阵的启发式工序排序方法。在该方法中,工序排序被转化为以加工活动为对象的组合排序问题,并构建其数学模型。该模型将工序排序中需要满足的工艺规则分为聚类规则和顺序规则两类,建立了工艺规则与加工活动信息之间的量化关联关系,通过工艺规则的作用确定加工活动间的约束关系;定义聚类约束关系和顺序约束关系向矩阵转化的机制,生成加工活动间的聚类约束矩阵和顺序约束矩阵,在此基础上建立启发式算法对其进行聚类分组,并对聚类的加工活动进行排序,得到加工活动的组合和次序。最后通过工序排序算例验证了该方法的可行性。     

面向虚拟企业构造的合作企业搜索方法研究

为了解决虚拟企业快速寻找潜在的合作企业问题,提出了一种基于任务特征、企业能力特征描述和自动匹配的合作企业搜索方法。以加工型协作任务为例,提出了基于协作任务特征和企业能力特征的描述方法和模型。这种方法将加工协作任务以特征为单元进行分解,形成子任务,然后以企业的制造资源为约束,在制造协作网中自动搜索能完成某个子任务或全部子任务的所有企业。针对协作任务的多样性,着重研究了面向单一加工任务和多种零件加工任务的合作企业搜索模型及算法。最后,介绍了一个制造协作网系统,给出了合作企业搜索模块的功能和运行实例,以验证合作企业搜索方法和算法的有效性。     

双资源约束的航天结构件车间生产调度方法

针对航天结构件生产调度过程中工序加工时间随操作人员能力级别而变化,关重件和关键工序特定设备和人员要求约束等问题,构建综合考虑关键设备和人员双资源约束的柔性车间作业调度数学模型,解决航天结构件生产设备资源维、人员资源维、工序信息维的描述。为实现双资源约束下的柔性调度,提出嵌套式蚁群-遗传混合算法,针对结构件加工工序设备和人员双资源选择问题,建立资源选择问题与蚁群并行搜索的映射关系,设计蚁群算法实现资源选择;为提高算法搜索性能,利用遗传算法求解当前蚂蚁资源选择下的调度问题,在避免人员资源使用冲突前提下实现设备加工工序的优化排序,使得关键设备利用率最大,总完工时间最短,并通过综合考虑蚁群和遗传算法阶段的求解目标进行蚁群算法信息素的更新,大大提高算法获得较优解的性能。最后,通过航天结构件车间实际案例进行算法测试,测试结果表明,嵌套式蚁群-遗传混合算法能有效地求解双资源约束的航天结构件车间生产调度问题,可降低资源总负荷,提高关键设备利用率,避免人员资源冲突,具有良好的综合调度性能。     

基于模糊时间并具有成组约束的车间排序算法

针对模具制造过程工件到达时间和加工时间难以精确的特点,以最小化最大完成时间为调度目标,研究了前阶段带有成组约束的两阶段柔性同序加工车间的排序问题.借助模糊数学理论,将工件的加工时间和到达时间作模糊数处理,采用均匀分布的Lee-Li法将模糊数转化为精确值,通过遗传算法优化排序,应用企业实际算例仿真说明该算法的有效性和可行性.     

Optimization of operation sequencing in CAPP using simulated annealing technique (SAT)

Computer-aided process planning (CAPP) is an important interface between computer-aided design (CAD) and computer-aided manufacturing (CAM) in computer-integrated manufacturing environment. A problem in traditional CAPP system is that the multiple planning tasks are treated in a linear approach. This leads to an over constrained overall solution space and the final solution is normally far from optimal or even non-feasible. The operation-sequencing problem in process planning is considered to produce a part with the objective of minimizing the sum of machine, setup and tool change costs. In general, the problem has combinatorial characteristics and complex precedence relations, which makes the problem more difficult to solve. In this paper, the feasible sequences of operations are generated based on the precedence cost matrix and reward–penalty matrix using simulated annealing technique (SAT), a meta-heuristic. A number of benchmark case studies are carried out to demonstrate the feasibility and robustness of the proposed algorithm. This algorithm performs well on all the test problems, exceeding or matching the solution quality of the results reported in the literature for most problems. The main contribution of this work focuses on reducing the optimal cost with a lesser computational time along with generation of more alternate optimal feasible sequences. The proposed SAT integrates robustness, convergence and trapping out of local minima.     

CBC技术在动态可重构CAPP系统中的应用

文章分析了目前CAPP系统普遍存在的问题,针对这些问题,提出了利用面向对象的方法对CAPP系统进行分析和设计,利用基于COM的组件（COM Based Component;CBC）技术对CAPP系统进行开发,并通过实例,详细论述了利用面向对象方法和组件技术对CAPP系统进行分析、设计和开发的过程。     

优先约束的混合实时任务动态调度算法

为了对较大规模问题在短时间内给出满意的解并调度随机到达的非周期任务,提出了一种动态混合调度算法。在第一个截止期限错失时刻,通过分析系统的运行情况,推导出具有优先约束的实时任务可调度的充分条件。在系统运行前,判定周期任务的可调度性,预分配足够的处理机。当非周期任务到达系统时,在保证周期任务可调度的前提下重新给周期任务和非周期任务分配处理机。该算法具有多项式时间复杂性,适合解决较大规模的多处理机调度问题。实验结果表明,该算法有效提高了处理机的利用率和非周期任务的接收率。     

分布式CAPP中协作智能体的构造

基于智能体的分布式CAPP中 ,各功能智能体共同协调工作是解决网络化制造环境下CAPP自动化的关键。针对焊接结构件CAPP系统的开发 ,提出协作智能体的构造方法 ,建立其工作过程模型 ,实现了CAPP中多用户、多任务的并行协作     

CAPP中参数化规格表的建立及可视化填写的实现

计算机辅助工艺设计（CAPP）软件能否高效地发挥其功用，其基础数据库建立的好坏起着极其重要的作用。在对众多商品化CAPP软件进行详细调研的基础上，开发出了能由用户自行建立参数化规格表并实现可视化填写的CAPP系统，并在国家863/CF-CIMS应用示范工程中得到应用。     

双边装配线第二类平衡问题研究

与传统的单边装配线平衡问题不同,双边装配线平衡不仅要考虑任务优先顺序关系,而且要考虑任务操作方位以及双边并行作业的要求.为有效地解决双边装配线第二类平衡问题,建立了数学模型,并提出一种基于归组策略的启发式平衡算法.该算法利用图深度优先搜索方法,将任务进行归组,然后运用一系列启发式规则对组进行选择分配.最后,通过在某装载机总装生产线上的应用,验证了算法的有效性.     

求解分布式混合流水线调度问题的改进双层嵌套式遗传算法

针对分布式混合流水线生产的生产调度问题,模拟实际排产中的排产到线和排产到时的排产策略,提出了基于改进双层嵌套式遗传算法的两层优化模型。外层依据流水线分配平衡和准时交货等基本原则总体上解决生产订单在流水线之间的分配问题,内层以最小生产时间为主要目的求解流水线的生产订单生产次序问题。考虑到双层嵌套式遗传算法的时间复杂性,基于模糊逻辑理论设计了一种模糊控制器来动态调整遗传算子,并采用主动检测停止方法,提高算法效率。使用某空调工厂的实际生产数据验证了算法的可行性、计算结果的准确性及排产策略的有效性,为高级计划与排程(Advanced Planning and Scheduling,APS)中大规模复杂供应链调度问题提供了可借鉴的方法。     

Concurrent process/inspection planning for a customized manufacturing system based on genetic algorithm

Producing products with multiple quality characteristics is always one of the concerns for an advanced manufacturing system. To assure product quality, finite manufacturing resources (i.e., process workstations and inspection stations) could be available and employed. The manufacturing resource allocation problem then occurs, therefore, process planning and inspection planning should be performed. Both of these are traditionally regarded as individual tasks and conducted separately. Actually, these two tasks are related. Greater performance of an advanced manufacturing system can be achieved if process planning and inspection planning can be performed concurrently to manage the limited manufacturing resources. Since the product variety in batch production or job-shop production will be increased for satisfying the changing requirements of various customers, the specified tolerance of each quality characteristic will vary from time to time. Except for finite manufacturing resource constraints, the manufacturing capability, inspection capability, and tolerance specified by customer requirement are also considered for a customized manufacturing system in this research. Then, the unit cost model is constructed to represent the overall performance of an advanced manufacturing system by considering both internal and external costs. Process planning and inspection planning can then be concurrently solved by practically reflecting the customer requirements. Since determining the optimal manufacturing resource allocation plan seems to be impractical as the problem size becomes quite large, in this research, genetic algorithm is successfully applied with the realistic unit cost embedded. The performance of genetic algorithm is measured in comparison with the enumeration method that generates the optimal solution. The result shows that a near-optimal manufacturing resource allocation plan can be determined efficiently for meeting the changing requirement of customers as the problem size becomes quite large.     

智能化电火花加工CAPP系统的研究

针对电火花加工工艺的特点,采用专家系统与人工神经网络相给合实现电火花加工智能化CAPP系统——I-EDM-CAPP系统。建立了基于规则的简易Petri网SPN模型以实现加工方法的智能选取;采用复合神经网络（CNN）实现电参数学习模型,从而能够准确地选择并合理地扩展电加工工艺参数。