21世纪的制造企业面临的是众多客户群体各式各样的需求,多品种、中小批量的生产需求已经成为企业生产运行的常态,制造系统的关键越来越集中地体现为生产调度的灵活性与准确性。企业的生产是一个复杂的过程,在某种程度上说,“动态”是“正常”的生产,一成不变的静态生产是不存在。例如,生产环境的变化、生产资源获得情况的改变以及不可预知的灾变事件等等这些异常的情况都会影响生产,以上干扰事件使得与当前生产计划的偏离是不可避免的,如果干扰事件不能适当和及时地处理,这个偏离会严重影响企业的效益、管理效率、顾客满意度和核心竞争力。因此,在干扰事件发生情况下的生产调度已经成为一个新兴的研究领域,有利于指导企业应对日常动态生产过程中突发事件的应用实践。所谓调度[1],就是为了实现某一目的而对共同使用的资源进行时间上的分配。从数学规划的角度来说,生产调度问题可表述为在等式或不等式约束下,对目标函数所进行的优化。现代典型的生产调度问题就是[2]:将作业均衡地安排到各机床上,并合理地安排作业的加工次序和加工开始时间,在满足约束条件的同时优化一些性能指标。但在生产调度调度中,经常会有不确定因素发生,也就是干扰事件的发生。关于干扰的研究早在20世纪70年代~80年代就已经开始,但是直到90年代干扰管理这一概念才明确提出。干扰管理[3]被定义为在计划开始阶段,用优化模型和求解算法得出一个好的运行计划;计划实施中,由于内外部不确定因素导致干扰事件的发生,使原计划变得不可行,需要实时地产生新计划,新计划要考虑到原来的优化目标,同时又要使干扰带来的负作用最小化。目前国内外研究多集中于航空调度、供应链管理、物流技术以及信息系统等方面。在航空调度领域,Jarrah等学者[4]研究了航空领域里,遭遇到干扰时间影响航班的正常运行时,如何应用干扰管理的方法有效地化解这些影响,保证航班正常运行。Larsen等学者[5]在处理某个航班任务被干扰事件破坏,导致影响整个航班被迫调整,采用干扰管理的思想产生启发式算法,重新调度航班的运行、航班的取消以及航班的变更问题。Smith[6]等研究了将飞机及机组人员作为优先资源的情况下,如何能保证在干扰情况下维持持续有效的航空调度能力,从而保障有效的运力供给和最好的经济性能。干扰管理方法出现的较晚,虽有些研究成果,但很不全面,在生产调度领域应用范围表现为这些研究大都集中在单机以及平行机的生产环境下,较为复杂的流水车间调度,作业车间调度和自由车间调度以及更加复杂的生产环境下的干扰管理应用研究明显不足。干扰管理的方法与生产调度系统中已有的应对不确定性的方法如重调度、鲁棒性以及寻找稳定的调度方法之间的区别和联系还未得到明确,如何在生产调度系统中合理使用这些方法才能使得整个生产系统有序高效地运转,这将是干扰管理应用于生产调度中的关键,是非常必要的。流水车间调度问题(Flow-shopSchedulingProblem,FSP),又称为同序作业调度问题,是与城市不对称情况下的货郎担问题(TSP)难度相当的同一类型NP完全问题中最困难的问题之一。它把许多实际流水线生产调度问题简化成模型,也是目前车间调度研究中最广泛的一类典型调度问题,在离散制造工业和流程工业中都具有广泛的应用,具有一定的代表性。针对这些情况,本文将干扰管理与流水线车间调度问题结合起来,建立流水线干扰管理调度模型,并利用微粒群算法来解读这一模型。
2流水线干扰管理调度模型
在一个成组流水线上或成组加工的生产单位里,经常会遇到这样一个问题:有n种零件需要在m台设备上加工,这些零件的工艺路线完全相同,在月初安排生产计划时,他们同时到达车间。如何安排这些零件的加工顺序,才能使所有零件全部加工完的总流程时间(即全部零件的总生产周期)为最小或者使各零件的平均流程时间(即零件的平均生产周期)为最小,这就是一个比较普遍的Flow-shop排序问题[7]。而干扰调度问题为原定工件集合调度计划已完成,新工件集合在加工前突然到达,对整个调度系统产生冲击干扰,目标包括所有工件集合调度的原工件的预定目标以及原工件的干扰时间差的混合。当目标函数最小时,干扰工件对原调度产生的偏离最小。对该问题常常作如下假设:(1)每个工件在机器上的加工顺序是给定的;(2)每台机器同时只能加工一个工件;(3)一个工件不能同时在不同的机器上加工;(4)工序不能预定;(5)工序的准备时间与顺序无关,且包含在加工时间中;(6)工件在每台机器上的加工顺序相同,且是确定的。令c(ji,k)表示工件ji在机器k上的加工完成时间,ti,j表示工件i在机器j上的加工时间,π*表示最优调度排序,cmax(σ)表示调度排序σ的最大完成时间,又称为makespan,{j1,j2,…,jn}表示工件的调度,k=1,2,…,m。对于无限中间存储方式,n式(3)~式(6)表示最大完工时间和干扰时间差混合问题的目标函数。以上模型建立在对原计划调度已经建立最优调度π*的基础上,其中式中α表示原工件按时完工的重要程度,α越大,干扰对目标函数的影响也越大,反映原工件的按时完工的重要性。
3微粒群优化算法在FSP问题中的应用
对于Flow-shop这类排序问题,许多科技工作者进行了大量的研究,提出了许多算法,如分支定界法[8]、线性规划法、动态规划法、启发式算法[9]和免疫算法[10]等。但每种算法都存在着一定的不足,本文中引入微粒群算法来求解Flow-shop问题。现假设在Flow-shop问题中有n个工件需要在m台机器上加工,令c(ji,k)表示工件ji在机器k上的加工时间,{j1,j2,…,jn}表示工件的调度,k=1,2,…,m,共有n*m个加工时间。在PSO中,我们把某一种工件的调度顺序看作是一个粒子,在这种工件的调度顺序下形成的流程总时间看作是该粒子的适应值,适应值越小越好。为了将微粒群优化算法运用到FlowShop调度问题等组合优化问题上,需要对微粒的位置和速度做出重新定义。设一共有n个工件,不妨设某个位置X=(x1,x2,…,xn),该位置的速度为V=(v1,v2,…,vn)。通俗地说,每一个微粒的位置就是该批工件的加工顺序,而速度就是对加工顺序的修正数。P=(p1,p2,…,pn),Pi为微粒i所经历的最好位置,也就是微粒i所经历的具有最好适应值的位置,成为个体最好位置。Pg则是指微粒群中所有微粒所经历过的最好位置,成为全局最好位置。设置参数及初始值,包括种群数pop_size,惯性权值ω,学习因子c1和c2,初始速度V,最大速度Vmax,
4算法测试与分析
4.1六工件四机器的干扰调度仿真实验当原定工件集合调度计划已完成,新工件集合在加工前突然到达,对整个调度系统产生冲击干扰,目标包括所有工件集合调度的原工件的预定目标以及原工件的干扰时间差的混合。当目标函数最小时,干扰工件对原调度产生的偏离最小。现举例一个4机器6工件的Flow-shop干扰调度问题,工件6为干扰工件。该问题的工件加工时间如表1所示;仿真结果的最优解数据如表2所示。
4.2八工件四机器的干扰调度仿真实验现举例一个8工件4机器的Flow-shop干扰调度问题,工件6、7和8为干扰工件。该问题的工件加工时间如表3所示;仿真结果的最优解数据如表4所示。5结束语本文针对流水线车间的干扰管理问题的特殊性,运用微粒群优化算法的基本理论对它求解,实践证明微粒群优化算法在收敛速度和寻优能力上有独特的优越性。现在微粒群算法在国内外的流水线车间干扰管理问题中都研究得比较少,虽然微粒群算法在流水线车间干扰管理问题中的应用还存在着很多改进,但可以作为一个新的研究方向,开展各项有意义的研究工作。
