求解多层生产计划集成问题的一种遗传算法

对于多层生产计划集成问题,目前多采用递阶计划模型求解.利用单个模型来描述和解决集成化的多层生产计划问题在理论上具有更好的求解效果,但实现上却有很大的难度.基于JIT思想,提出了一种新的优化目标函数,建立了一个批量规划和作业排序的集成模型,并采用遗传算法求解,取得了较为满意的结果.     

混合HOGA-SVM财务风险预警模型实证研究

目前涉及遗传算法与支持向量机相结合的预测模型中,遗传算法基本上采用的是标准算法.但是在对全局函数的优化中,一般的遗传算法容易陷入局部最优,从而降低遗传算法收敛速度和搜索精度,进而影响财务风险预警模型的精度与速度.基于此,提出了基于混合全局优化正交遗传算法(HOGA)和支持向量机(SVM)的财务风险预警模型(HOGA-SVM),通过使用混合全局优化正交遗传算法连同支持向量机来改进支持向量机进行财务风险预警的效果.结果显示,提出的模型不仅提高了财务风险预警的准确率和速度,而且模型的两类分类错误率(尤其是第一类分类错误率)相对其他模型也有了明显下降.未来的工作可以把模型的应用扩大到多分类的财务风险预警问题中.     

带有单件流的混流生产方式提前期的分析与优化

通过数学分析说明了提前期问题的重要性,建立了带有单件流的混流生产方式的提前期模型,找到影响提前的关键因素为最大工序调整时间之和与品种的最大工序加工时间,并通过作业排序和平衡生产线等方法优化了这两个因素,通过一个算例说明制造提前期得到了显著缩短.     

考虑学习率和搬运时间的人工作业系统生产过程时间组织与优化

在同时考虑员工学习率和运输工序时间的基础上,对该类型人工工序作业系统的批量加工模式生产周期模型及优化问题进行研究。给出批量工件以不同移动方式完成加工的生产周期形式,并详细地对该研究背景下的批量工件以平行顺序移动方式完成加工的生产周期模型进行理论证明。在给定算例的基础上,对仅考虑搬运时间、考虑学习率和搬运时间等两种情况的生产周期进行对比分析。最后,在详细分析工艺工序时间、员工学习率、运输工序时间、增加峰工艺工序员工人数等优化措施对批量工件生产周期优化效果影响的基础上,提出针对不同移动方式完成加工的批量工件进行生产周期优化的策略,为该类型制造系统正确进行现场改善提供可以借鉴的准则。     

多调机环境下的树枝形铁路专用线作业车同步取送优化

围绕服务铁路枢纽地方货物流的小运转作业系统，研究一类多调机环境下的树枝形铁路专用线作业车同步取送优化问题。考虑取送顺序间隔、调机牵引能力等约束条件，以调机作业均衡为上层优化目标，以调机取送成本和货车停留成本最小化为下层优化目标建立双重目标规划模型。根据模型特点，提出融合综合关联度和异步启发式过程的两阶段融合求解方法。该方法首先基于聚类划分思想，引入综合关联度确定调机最佳数量，并对作业区进行划分，从而为调机指派作业范围。进而基于迭代寻优思路，设计异步循环启发式过程，该过程根据多调机取送车作业特点赋予循环体表述，设计循环体更新规则，引入遗传算法中的交叉与变异操作对循环体进行寻优，进而导入人工鱼群聚群行为实现循环体二次寻优，从而完成所有调机在各自作业区内取送顺序的逐步寻优过程。最后，设计实验场景对所提出的两阶段算法进行过程验证，并设计不同规模试验进行对比测试，结果表明了所提算法的有效性和较优性。     

面向成套订单问题的工艺规划与排序的集成研究

本文从工艺规划与排序的集成优化角度研究了成套订单问题^[1],克服了单独研究工艺规划和排序局部优化的局限性.文章中考虑了同一工件内部各道工序之间存在的优先加工限制,以及工件在不同机器上加工需要转移时间和工序间接连加工需要机器调整时间的情况,建立了成套订单问题的集成排序模型,并提出了针对求解大规模问题的基于遗传算法的启发式算法,最后通过一个算例对所研究的集成排序问题和所提出的算法进行了说明,计算结果表明了算法的有效性.     

基于机动时间的可分解平行工序顺序优化研究

平行工序的顺序优化是解决资源有限项目进度计划问题的最有效、最普遍的方法之一。对于该类问题的研究目前主要基于工序的不可分解性,而现实情况下有些工序是任意可分的。基于此,本文首先提出了最小路长定理,在其基础上,建立了任意可分的两个平行工序调整为顺序工序的亏值模型,并进行了理论证明,此外,针对从n个可分解平行工序中选取一个与指定工序调整为顺序工序的优化问题进行了研究,在已给亏值模型的基础上设计出了优化算法,越是大型网络,该方法的优越性越明显。     

网络计划优化中资源平衡的混合遗传算法

目前网络计划优化的问题有两个第一,网络计划优化技术中的顺序优化没有统一的数学模型;第二,网络计划优化中的资源平衡的理念比较陈旧.资源平衡的混合遗传算法克服了过去的弱点,采用了合理的编码方法,建立了遗传算法的资源平衡模型,该算法首次考虑了资源日历,彻底解决了资源平衡与资源得不到的矛盾.     

数控加工工艺分析的一般步骤与方法

数控机床的出现是工业一大进步的表现,它能较好的解决复杂、精密、小批、多变的零件加工问题,是一种灵活的、高效率的自动化机床.程序编制人员在利用数控机床加工时,首先得进行工艺分析.根据被加工工件的材料、轮廓形状、加工精度等选用合适的机床,制定加工方案,确定零件的加工顺序,各工序所用刀具,夹具和切削用量等.     

计及软逻辑的重复性项目离散时间费用权衡及其约束规划模型研究

在重复性项目中,如果一个工序适用软逻辑,则其在所有单元上的子工序可以任意改变施工顺序;当雇佣额外工作队后,同一工序中的多个子工序甚至可以同时执行。考虑软逻辑的重复性项目离散时间费用权衡问题(DTCTP-RPSL)旨在确定每个工序的执行模式、工作队分配方案和单元间的施工顺序,从而在满足给定截止日期条件下最小化项目总费用。已有研究均采用遗传算法求解此问题。但是,遗传算法属于启发式方法,不能保证解的最优性。本文首先建立了描述DTCTP-RPSL的混合整数线性规划(MILP)模型,然后从约束规划(CP)角度提出了求解此问题的CP模型。该模型以区间变量定义每个子工序,并利用CP表达式强迫所有变量在可行域内取值。与MILP模型相比,CP模型在保证解最优性的同时,减少了变量和约束的规模,提升了求解效率。数值实验表明,CP模型的性能优于MILP模型和遗传算法,能够在短时间内求出小规模和中等规模问题的最优解,以及较大规模问题的高质量解。     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

社区应急疏散动态协作调度优化研究

针对灾民数量和路网通行时间的动态性以及灾民疏散反应系数的随机性，本文提出了社区应急疏散协作调度优化流程，并以疏散灾民数量最大化和疏散成本最小化为目标，构建了社区应急疏散多种运输方式协作调度优化模型，并给出了求解该模型的改进多目标遗传算法。然后，论文使用Tansmodeler模拟社区应急疏散协作调度优化过程，加载疏散灾民动态需求和历史出行时间表，并对模型和算法进行验证。结果表明，该模型和算法可以在有效刻画疏散灾民数量和路网通行时间的基础上，为不同时刻的交通工具配置及疏散路径选取提供决策。     

On single machine scheduling with resource constraint

The single machine scheduling with resource constraint is a nonlinear combinatorial optimization problem in cloud computing applications. Given a set of jobs and certain resource, the problem is to find a permutation of jobs and a distribution of resource to optimize certain objective function. The processing time of each job is a nonlinear function with respect to the resource assigned to it. In this paper, we propose a naive algorithm and study a subproblem in the algorithm that suppose the permutation of jobs is also given, how to find a resource distribution to minimize the total weighted flow time. We found a polynomial-time optimal solution for a special case and an approximation solution in general case.     

考虑分时电价的多目标批调度问题蚁群算法求解

对同时优化电力成本和制造跨度的多目标批处理机调度问题进行了研究,设计了两种多目标蚁群算法,基于工件序的多目标蚁群算法(J-PACO,Job-based Pareto Ant Colony Optimization)和基于成批的多目标蚁群算法(B-PACO,Batch-based Pareto Ant Colony Optimization)对问题进行求解分析。由于分时电价中电价是时间的函数,因而在传统批调度进行批排序的基础上,需要进一步确定批加工时间点以测定电力成本。提出的两种蚁群算法分别将工件和批与时间线相结合进行调度对此类问题进行求解。通过仿真实验将两种算法对问题的求解进行了比较,仿真实验表明B-PACO算法通过结合FFLPT(First Fit Longest Processing Time)启发式算法先将工件成批再生成最终方案,提高了算法搜索效率,并且在衡量算法搜索非支配解数量的Q指标和衡量非支配集与Pareto边界接近程度的HV指标上,均优于J-PACO算法。     

加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.     

三台平行机排序的一个复合半在线问题的算法

本文讨论一个三台平行机半在线排序问题.对预先知道工件的总加工时间和最大的工件的加工时间的复合半在线模型,我们证明了不存在半在线算法,其竞争比为4/3,并给出了一个竞争比为7/5的半在线算法,两者的差距小于0.067.     

Single machine scheduling problems with subcontracting options

In this paper, we study a scheduling model as follows: there are n jobs which can be processed in house on a single machine or subcontracted to a subcontractor. If a job is subcontracted, its processing cost is different from the in-house cost and its delivery lead time is a stepwise function of the total processing time of outsourced jobs. Two objective functions are studied (1) to minimize the weighted sum of the maximal completion time and the total processing cost and (2) to minimize the weighted sum of the number of tardy jobs and the total processing cost. For the first problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm. For the second problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm for a special case.     

面向并行制造的多生产单元协同调度研究

为提升多生产单元制造系统整体效率，在其系统内开展面向并行制造的协同调度研究，在考虑运输、换线等时间的基础上，构建多生产单元并行协同调度模型，采用并行分段协同遗传算法求解；在此基础上，将所研究协同调度方法应用于某复杂机电产品多生产单元制造车间，并与变批量调度与等批量调度比较。研究表明，所提的并行协同调度方法可以显著提升生产单元效率，提高生产单元设备和人员利用率。     

Non-resumable scheduling on a single bounded parallel-batch machine with periodic maintenance

We consider the problem of scheduling a set of jobs with different processing times and sizes on a single bounded parallel-batch machine with periodic maintenance. Because the machine is in batch-processing model and the capacity is fixed, several jobs can be processed simultaneously in a batch provided that the total size of the jobs in the batch doesn’t exceed the machine capacity. And the processing time of a batch is the largest processing time of the jobs contained in the batch. Meanwhile, the production of each batch is non-resumable, that is, if a batch cannot be completed processing before some maintenance, that batch needs to be processed anew once the machine returns available. Our goal is to minimize the makespan. We first consider two special cases where the jobs have the same sizes or the same processing times, both of which are strongly NP-hard. We present two different approximation algorithms for them and show that these two algorithms have the same tight worst-case ratio of 2. We then consider the general case where the jobs have the arbitrary processing times and arbitrary sizes, for which we propose a 17/5-approximation algorithm.