作业车间排序重调度问题及其改进修复约束满足算法

作业车间往往因出现新作业而需要进行重调度.为尽量减少由重调度带来的计划变更,除了优化原有的性能指标外,还应减小重调度结果与原排序之间的差异.由此,提出一种双目标优化模型.为方便求解,将模型进行了分解,构建了可以分步求解的分级模型.对分级模型提出改进的修复约束满足算法(修复法),通过采用新的变量表示形式,设计了变量排序的启发式算法,并采用变量互换启发式算法,以保证全局搜索性能.以90个作业车间标准算例为基础,设计了重调度算例,并与现有代表性的第二代非支配排序遗传算法优化结果进行了对比,结果表明在相同运行时间下,所提算法更具优越性.     

基于可行工序序列遗传算法的工序排序优化

针对CAPP中工序排序优化这一NP-hard问题的求解,以最小化总成本为目标,提出一种新型的面向可行工序序列的遗传算法(FOSOGA)。该算法中,染色体以排列数的形式直接表征满足工序优先关系约束的可行工序序列;设计了可保证染色体可行性的自适应交叉算子和自适应变异算子来演化工序序列和各工序的加工资源;引入新的精英参与的交叉策略。将FOSOGA应用于两个案例,并与现有遗传算法、粒子群算法和蚁群算法进行了对比。结果表明,FOSOGA获取的解的平均质量优于现有遗传算法、粒子群和蚁群算法。     

工序集中型设备的作业排序系统开发

通过对制造业作业分配问题的分析,设计了作业排序系统的信息框架,并确定了系统的总体方案和功能模块。继而进行了系统数据库和前台程序的设计与开发。在作业排序方面,采用了Johnson-Bellman算法,实现总加工流程时间最短。同时设计了工件能按先到先服务或按交货期自动确定合适加工时间段的程序。从系统运行的效果可知,所开发的系统性能良好。     

工艺路线排序的基因遗传法

工艺员通常是根据经验对工艺路线进行排序,也就是定性的方法.本文提出一种定量方法,它采用基因遗传算法对零件工艺路线进行排序.实践证明,它是一种行之有效的方法.     

回转类零件基于分级约束的加工方法排序算法

根据分级规划原理,将加工方法排序这个复杂问题分解成五个阶段（或层次）进行求解。各阶段包含了若干个性质类似的子问题（或子任务）和求解这些问题的约束。加工方法排序的过程就是各层次的子任务在相应约束下求解的过程。通过合理安排各层次的任务和构造各层次的约束,简化了加工方法排序算法,提高了算法的实用性、通用性和灵活性,较好地解决了回转类零件ＣＡＰＰ系统实用化与工具化面临的一个难题。     

创成式CAPP中的工艺排序与工艺决策

在若干特征构成的零件工艺过程设计中,工步顺序不能有效地确定。本文通过对工艺设计过程的分析,结合杭州叉车总厂创成式ＣＡＰＰ系统（ＨＣ－ＣＡＰＰ）的开发,提出特征排序、工步排序与工艺决策优化、决策方法确定符合车间作业资源能力的零件工艺路线。     

状态演化的工艺路线排序

本文提出了状态演化的工艺路线排序方法,它通过对原有的排序结构的不断调整与扩展,产生新的排序结果,通过状态演化,实现与系统过程中同步并行,渐进完善的排序过程,排序目标是寻求满足精度要求,具有加工技术与时间最少的工艺路线,对此,通过建立路径权值最小的目标函数实现排序优化,优化过程通过两个排序模型来完成,初始状态的排序模型与中间过程的排序模型,前者应用分枝定界法求解,后者通过集合交,并,差及工序结点权值     

特征组合、工艺排序决策法研究

提取零件的输入特征信息，通过特征组合成组合特征单元，对组合特征单元进行编号，并根据工艺规则，工艺数据库和资源库对组合特征单元进一步进行分解成可作为加工工序的特征组合元。根据工艺规则，资源库，工艺数据库，对组合特征单元进行排序，即进行工艺决策。     

启发式算法在单件车间工序排序问题中的应用

本文探讨了车间作业计划的排序问题 ,深入分析和研究了启发式算法 ,结合模具车间的实际情况 ,采用基于无延迟作业计划的概率调度法 ,并进行适当的改进 ,实现对模具车间作业计划的排序 ,取得了较好的效果。     

具有工件约束的模具制造优化调度算法研究

为解决具有工件约束的模具制造优化调度问题,提出了一种利用蚁群算法和优先分配启发式调度算法相结合的调度算法。该算法能够方便地描述问题的约束条件的特点。首先,由蚁群算法确定模具零件各工序所用的加工机床,用节点模式下的有向图描述问题的解空间,用蚂蚁种子信息素踪迹更新策略对信息素进行更新,以获得问题的解;然后,利用优先分配启发式调度算法确定在同一台机床上加工的各零件的先后顺序。实验结果验证了算法的有效性。     

Minimising total tardiness for the worker assignment scheduling problem in identical parallel-machine models

The worker assignment scheduling problem involves both the decisions of job scheduling and worker assignment. In this research, only the performance measure of total tardiness is investigated in the model of identical parallel machines with nonpreemptive jobs. Since the worker assignment scheduling problem in the selected model can be shown to be NP-complete, heuristics have been developed for minimising the total tardiness. The worker assignment scheduling problem is solved in two phases of job scheduling and worker assignment. The SES (SPT, EDD, SLACK) heuristic is used for the phase of job scheduling. For the phase of worker assignment, the largest marginal contribution (LMC) procedure is used to minimise the total tardiness. From the simulation conducted, 88 out of 100 simulated problems yielded optimal solutions while the others also obtained very good results. In conclusion, the heuristics developed have shown very impressive results in both effectiveness and efficiency aspects.Notation n Total number of jobs waiting to be processed - m Total number of machines available to process the above jobs - J _i A set of n jobs are to be processed, i=1, ..., n - M _j A set of m machines are used to process these n jobs, j=1, ..., m - t _i (W _j ) The processing time needed for job J _i processed on machine M _j , where W _j workers have been assigned to M _j - t _j,[k](W _j ) The processing time function of the k ^th job assigned to machine M _j , where W _j workers have been assigned to M _j - d _i The due date of job J _i - d _j,[k] The due date of the k ^th job assigned to machine M _j - r _i the ready time of job J _i - C _i The completion time of job J _i - C _j,[k](W _j ) The completion time function of the k ^th job assigned to machine M _j , where W _j workers have been assigned to M _j ; - F _i The flow time of job J _i , F _i =C _{i –} r _i - L _i The lateness of job J _i , L _i =C _{i –} d _i - T _i The tardiness of job J _i , T _i =max{0, L _i } - T _j,[k] The tardiness of the k ^th job assigned to machine M _j , T _j,[k]=max{0, C _j,[k](W _j )–d _j,[k]} - N _j The number of jobs assigned to machine M _j - W _j The number of workers assigned to machine M _j - W The total number of workers     

基于混合遗传算法的柔性作业车间调度研究

为更有效地求解柔性作业车间调度问题,提出一种混合遗传算法(蚁群-遗传算法)。在分层法的基础上,首先采用蚁群算法解决工艺路线选择问题,再通过遗传算法解决传统的作业车间调度问题。在混合遗传算法求解过程中,不断地在前期优化中获取调度知识,用于指导后期的优化过程。通过标准案例测试,验证了混合遗传算法对于解决柔性作业车间调度问题的有效性。     

资源调度问题研究综述

针对资源调度问题,从静态资源调度算法和动态资源调度算法两方面,详细地介绍及评述了国内外相关研究成果,并对其中关键技术的研究状况进行了总结,指出了未来的研究趋势。研究结果表明,资源调度问题虽然已经取得了很多研究成果,但远未达到完善和实用化的程度,仍有一些关键技术问题需要解决。     

Further study of minimizing total tardiness for the worker assignment scheduling problem in the identical parallel-machine models

Minimizing total tardiness in the model of an identical parallel-machine with nonpreemptive jobs of the worker assignment scheduling problem is further studied in this paper. More complicated simulation processes are established for this purpose. The specific worker assignment scheduling problem is solved in two parts of job scheduling and worker assignment. The S_PT, E_DD, S_lack (SES) heuristic is used for the job scheduling part while the largest marginal contribution (LMC) procedure is used to for the worker assignment part and then minimizes the total tardiness. From the new simulations conducted, the heuristics developed have again shown very convincing results quite efficiently.     

基于交货期和设备能力约束的作业车间调度方法研究

以往对作业车间调度问题的研究中,不少学者尝试添加新的约束条件使之更符合实际的生产情况。但对设备能力约束的考虑不够细致,往往简单地将设备能力视为常数或连续的能力空间。针对这种情况,本文建立了以交货期为指标并带有设备能力约束的作业车间调度模型,采用双向调度方法力求工件的完工时间和交货期尽量靠近,从而使惩罚成本最低。设计了利用时间坐标映射求解工序开／完工时间的方法,该方法消除了因设备能力不等造成的工作时间段间隔,最终通过遗传算法求得优化的调度方案。     

带特殊工艺约束的双目标并行多机调度问题研究

港口的拖轮调度过程是一类带特殊工艺约束的并行多机调度问题.采用基于进化策略的混合算法,设计了基于工件的编码方式,对次序杂交算子进行了扩展,设计了一种扩展“倒位”变异算子,并采用相邻不同基因多次交换的局部搜索方法.算法的设计自动满足了工艺约束,保证了种群的多样性.设计了最大完工时间和生产加工成本双目标评价函数,最后通过计算对混合算法进行了验证.     

大规模生产调度问题的研究现状与展望

为解决大多数已有调度算法无法直接应用于大规模生产调度的问题,以典型生产调度问题为背景,综述了现阶段已有大规模生产调度问题的算法。分析了大规模生产调度问题规模增长的因素,重点介绍了基于问题分解的各类方法、拉格朗日松弛／分解法及智能优化算法。在此基础上,展望了大规模生产调度问题的研究发展趋势。     

基于免疫算法的并行机间歇过程模糊生产调度

研究了一类具有顺序无关模糊产品切换时间和成本以及模糊单位加工时间和成本的并行机间歇过程调度问题,目的是确定每种产品在每个设备上处理的批次数目、批量以及批次顺序,优化目标为最小化总完成时间和最小化总生产成本。根据任意设备上同种产品的所有批次均顺序处理的性质,建立了问题的模糊运输模型。利用加权和方法将多目标函数转化为单目标函数,并使用基于积分值的方法对模糊数进行排序。提出了基于排列边集编码的免疫算法,通过求解不同规模的问题实例证明,免疫算法不仅能获得比遗传算法和免疫遗传算法更好的解,而且比免疫遗传算法更高效,同时具有良好的动态性能。     

可重组制造系统的生产调度问题研究

可重组制造系统的调度问题具有动态性、可重组性的特点。采用Multi Agent技术用于可重组制造系统的调度问题研究,确定基于Multi Agent技术的可重组制造系统的生产调度系统的结构及其实现方法。