应用混合蚁群算法求解并行批处理机组批与调度问题

晶圆制造系统的批处理机具有长加工时间的特征,其调度性能指标对车间总体绩效有重要影响.批处理机调度分为组批与批次调度.针对工件的动态到达特性导致组批困难,提出了一种混合型蚁群算法.利用该算法的全局并行搜索能力对工件进行组批,并使用BATC算法对批次进行调度,可以解决多产品并行批处理机调度问题.以工件总拖期最小为性能指标,通过实例仿真,对蚁群算法性能进行分析评价和比较.结果表明,所提出的算法具有有效性和实用性.     

基于改进蚁群算法的化工批处理生产调度研究

首先介绍了化工企业生产的特点,然后给出了蚁群算法的基本模型和化工批处理生产调度的描述,指出了其调度过程要考虑到的约束条件——半成品的放置时间不能太长,把半成品的放置时间作为信息因子放入到概率选择公式中,使用改进的蚁群算法对该生产调度进行了求解,最后对化工间歇作业调度发展趋势做了探讨。     

一种基于混合Petri网的批过程动态调度算法

针对批处理过程动态调度问题的特点，以赋色时间限制混合Petri网为工具，建立了批过程动态调度的混合Petri网模型，将批过程的调度问题映射技术为求Petri网中变迁的最优激发序列问题。在此模型基础上，根据动态规划基本原理，以资源的终极利用即最短生产周期作为调度目标，提出了一种基于赋色时间限制混合网模型求取变迁的最优激发序列的方法，并针对实际情况中出现的复杂的中间产品存贮策略，讨论了在各存贮策略约束下该模型中时间限制区间的确定方法，最后以炼钢－连铸生产系统的过程调度为例，对该算法进行仿真。多次仿真结果表明，当任务和设备的初始时刻或者过程的动态过程发生改变时，调度结果各不相同，从而验证了该算法的有效性。     

基于改进烟花算法的焊接综合调度研究

针对复杂结构件焊接生产同时具有工艺树输入和需要不同资源等特点,在现有综合调度基础上考虑焊接相关平台和设备约束,建立以最小化最大完工时间为目标的焊接综合调度数学模型,并提出一种改进烟花算法进行求解．首先提出了一种编码方式以适应工艺树输入;然后改进了烟花的爆炸及高斯变异算子等搜索方式,使整个迭代过程不会产生非法解,以避免修复操作引起的时间成本问题;最后设计了一种混合烟花爆炸框架,以迭代次数为控制参数自适应选择烟花生成方式,从而增加算法的搜索能力．通过不同规模下的综合调度算例和焊接综合调度工程实例双重验证,结果表明：与传统算法相比,本算法的求解精度平均提升17%,能更有效获得最优解．     

工件有尺寸的单机批调度问题的在线算法

16160的在线算法,并给出了此问题的一个下界。     

单件车间关键工序调度问题的定界算法

提出了一种以“定界权值”为主要参数的求解有交货期的单件车间生产调度问题的定界算法。引入“关键工序定界权值、非关键工序定界权值”的概念，并依据“关键工序排序加工，非关键工序即刻加工”的构想，确定工件各工序的加工时间范围，并根据计算结果编制机台作业计划。当关键工序加工时间发生冲突时，修正其定界权值，重新计算其加工时间范围。该方法简化问题，运算速度提高。     

设备空闲时间段调整的设备驱动综合调度算法

针对设备驱动的综合调度算法没有考虑工序的结束时间,以及其同设备加工的下一道不可调度工序的开始时间形成该设备的空闲时间段可缩短的调度优化问题,提出了设备空闲时间段调整的设备驱动综合调度算法.该算法为使空闲设备即将加工的不可调度工序提前加工,缩短了设备闲置等待时间,提出该不可调度工序的最短加工路径,通过优先加工该路径上工序,使其紧前工序尽早加工完成.实例验证该算法可以有效缩短设备空闲等待时间,提高设备利用率.      

半导体生产批处理调度的研究现状与对策

批处理机调度是一类复杂组合优化问题,研究半导体批处理机调度,实现批处理机调度的智能优化,有利于半导体生产企业产生更多的经济效益,对企业的生产和发展有相当重要的意义。本文讨论了批处理机调度的研究现状和不足,指出了未来研究需要关注的问题和相应对策。     

基于设备驱动的综合柔性调度冲突调解算法

设备驱动时刻按最短加工用时确定工序设备,为避免两个设备选择同一工序发生冲突导致可调度工序延迟完成影响调度结果的问题,提出基于设备驱动的综合柔性调度冲突调解算法. 该算法分别从可调度工序集中为发生冲突的两个空闲设备选择加工时间次短的预调度工序,通过对可能加工的组合方案预调度,选择设备驱动时刻尽早结束的组合方案调度;当存在一个空闲设备有多个可调度最短加工工序时,采用实质短路径策略确定调度工序. 分析和实例表明,本文算法可缩短存在设备/工序选择冲突的综合柔性调度总加工时间.      

分批次均衡处理的非对称三车间综合调度算法

针对复杂产品在非对称三车间生产调度的问题,提出分批次均衡处理的非对称三车间综合调度算法。该算法先按设备所在车间属性将设备分成非对称资源、局部对称资源和对称资源。对非对称资源上工序根据设备属性确定车间,局部对称和对称资源上可按加工工序采用批次处理,其中部分工序按提出的工序关联策略确定车间,不能确定车间的工序形成缓存集,按提出的排列均衡调整策略确定集中工序的车间。已确定车间工序采用长路径等策略确定调度次序,再根据工序约束条件确定加工时间。通过实例分析,该算法可在二次复杂度内解决非对称三车间综合调度,提高非对称设备利用率。      

机器带准备时间的平行机分批排序

首次研究了机器带准备时间的平行机上的分批排序问题,这里的目标函数为极小化工件的最大完工时间,这类问题是NP-难的.我们根据FBLPT算法、Multifit算法和LPT算法,分别对机器是同型机和同类机的两种情形设计出两个近似算法,并证明它们的最差性能比分别不超过(2-1B)[97 (12)k]和53(2-1B).     

工件有到达时间的平行机分批排序问题的一个PTAS算法(英文)

研究工件有到达时间的最小化加权完工时间和的平行机分批排序问题,通过综合运用实例转换,工件分类和动态规划等方法提出了一个多项式时间近似框架.     

批数确定的分批排序问题最优解的结构性质

研究了目标函数为总完工时间、工件恰分N批的单机分批排序问题最优解的结构性质,其中N为1与工件数之间的任意整数.分批方式为继列分批和平行分批.     

轧辊热处理过程中具有组批的并行机调度问题

研究了在轧辊热处理过程中加热炉体积相同的情况下,具有组批的并行机调度问题.以使最长完成时间最小化为目标建立了该问题的数学模型.提出了辊坯组批启发式算法和批次调度启发式算法,并将二者结合形成了一个两阶段启发式算法,对模型进行求解.通过对实验结果的比较与分析,验证了方法的有效性.针对不同规模的问题给出了相应的最优求解方法,提高了轧辊的生产效率,为决策者合理安排生产提供了有效的策略.     

批处理机上有就绪和截止时间的等长度工件排序

一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间.本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题,目标是求一个可行时间表.就该问题,Baptiste已经提出了一个复杂性为O(n8)的算法,在此基础上,本文推广Garey等人关于对应的经典排序问题的算法,得到了一个复杂性为O(n2)的算法.算法分两个阶段执行:在阶级I,算法找出所谓的禁止开工区间,在这些区间中将不允许有工件开工;在阶段II,算法从时刻零开始,每当机器有空闲且不属于禁止开工区间的时候,就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工,若当前的机器空闲时刻属于某个禁止开工区间,则首先更新其到该禁止开工区间的右端点再进行决策.     

工件尺寸不同的平行机分批排序

研究了工件有尺寸大小在平行机上的分批排序问题，这里目标函数为工件的极大完工时间，这类问题是m完备的，对同型机情况，给出了它的近似算法PM，并运用了拆分的技巧，证明它的最差性能比不超过11/4-1/m。     

无容量限制的批处理机时间表问题

研究无容量限制的批处理机时间表问题，在工件有到达时间和工期约束下，证明了当工件的到达时间和工期，或到达时间和加工时间一致单调时，该问题是多项式时间可解的；当加工时间和工期一致单调时，该问题是NP困难的。     

基于规则的批处理设备调度方法在半导体晶圆制造系统中应用

针对半导体炉管区瓶颈设备的批处理调度问题,提出满足工艺约束和设备限制的组批调度算法.在考虑产品动态到达的基础上,根据半导体制造系统大规模、多重入、混合型生产等特征,针对晶圆平均等待时间进行优化,实现多产品、多机台的实时组合派工.仿真实验在一个虚拟的晶圆制造系统上进行.结果表明,该算法在实时派工中对瓶颈设备填充率和利用率显著提升,有效地缩短了产品加工周期.
     

单机分批加工最大迟后问题的一个快速算法

本文考虑了下述单机分批加工问题，在时刻零同到达的ｎ个工件需分成若干批在同台机器上加工，同批中的工件相邻，任一工件的完工时间为所在批中全部工件完工时间的，机器每加工一批工件需一相同的调整时间，文中以工件的最大迟后为目标函数，对上述分别问题用动态规划技术给出了一多项式时间算法。