车间作业调度问题（共7篇）
车间作业调度问题 篇1
1 引言
车间作业调度问题是NP-难问题[1],也是最难的组合优化问题之一。简单来说车间作业调度问题可以描述如下:有一些工件和一些机器,每个工件由一组工序组成(这些工序必须按给定顺序加工,加工过程中不能被打断),一台机器在任何时刻最多只能加工一个产品,一个工件不能同时在两台机器上加工。问题的目标是找到使所有工件完工时间(makespan)最短的调度。
对车间作业调度问题人们设计了很多启发式算法,包括人工神经网络、模拟退火算法、遗传算法[2]、局部搜索算法、转换瓶颈算法[3]、SB-GLS算法、TSSB算法等。这些算法各有不同的特点,它们在各种条件下的性能也各不相同。禁忌搜索是局部搜索中最有效的算法之一。本文提出了新的邻域构造方法,并利用改进的插入算法构造尽可能好的初始解,然后使用禁忌搜索算法改进当前解。实验结果表明该算法是可行的和有效的。
2 车间作业调度问题描述及模型的建立
车间作业调度(job shop scheduling)问题[4]可以简单的描述为n个工件(job)J1,J2,…,Jn在m台机器(machine)M1,M2,…,Mm上加工。每一个工件Ji有ni个工序(operation)Oi1,Oi2,…,Oini,在第Oij工序的加工时间为pij,必须按工序顺序进行加工且每一个工序必须一次加工完成(无抢占,no preemption)。一台机器在任何时刻最多只能加工一个产品,一个工件不能同时在两台机器上加工。求解如何在上面的条件下使最后一个完工的工件加工时间最短。
1)机器顺序阵M,M(i,j)表示加工i工件的第j个工序的机器号,M(i,*)表示i工件的所有工序按优先顺序加工的各机器号的排列。
2)加工时间阵T,T(i,j)为i工件的第j个工序在机器上的加工时间。
3)工件排列阵J,J(i,j)为i机器上第j次加工的工件号,J(i,*)表示i机器上依次加工的各工件的排列。
机器顺序阵即为技术约束矩阵,与加工时间阵一样,也是事先已知的。工件排列阵则是调度的一种表示形式,即最优调度的结果。 s.t.
Cij-Tij≥Cik,i=1,2,…,n,j=1,2,…,m (1)
Chj-Cij≥Thj,i,h=1,2,…,n,j=1,2,…,m (2)
Cij≥0,i=1,2,…,n,j=1,2,…,m (3)
将工件完工时间最小化作为目标,其目标函数为undefined
其中(1)式表示机器k先于机器j加工工件i;(2)式表示工件i先于工件h在机器j上加工;(3)表示初始时间从0开始。工件和机器满足:一台机器在某时刻只能同时加工一个工件的一个工序;不同工件的工序之间没有先后的,相同工件工序满足先后约束关系。
3 改进的禁忌搜索算法
禁忌搜索算法是在组合优化问题中寻找近似最优解的一种全局优化启发式算法,是Glover在1986年提出这个概念进而形成的一套完整算法。初始解、邻域函数、禁忌表、禁忌长度、候选解、特赦准则构成了禁忌搜索算法的关键因素。本文尝试给出新的初始可行解和新的邻域构造方法,提出改进的禁忌搜索方法。
3.1 改进的策略
3.1.1 初始解
禁忌搜索算法对初始解有很强的依赖性。初始解可以用随机的方法选择,也可以用一些经验的方法或其他算法计算得到。本文中利用改进插入算法[5]来得到初始解。求解步骤如下:
1)分别计算所有工件的完工时间,按工件所需的完工时间从大到小的排序,并安排最长的工件的所有工序在机器上的加工顺序即把所有工序放入机器Mi∈(M1,M2,…,Mm)中。
2)所有工件的工序全部安排到机器中,循环结束,否则,把次长工件中的所有工序放入机器Mi∈(M1,M2,…,Mm)中:把工件中的工序按照从大到小排列。每次选一个加工时间最长的工序Oini插入到机器Mi(i∈(1…m))中已经排好的序列中,假设机器Mi中已经排了m′Mi个工序,则工序Oini有m′Mi+1个位置可选(其中可能有不满足约束条件的位置),则从中选择使得经过工序Oini的最长路径最小的合法位置排放工序Oini。
3.1.2 邻域结构的构造
本文的邻域构造方法都是基于关键路径的思想,下面给出两种不同的邻域构造方法。
1)交换算子(工序):交换同在一条关键路径上且属于同一个块的两个加工工序的位置。禁忌对象为两个工序的交换,并将其放入禁忌表中。禁忌表初始为空;当一个交换被加入到禁忌表中时,若表未满,则将交换加到表的末尾;若表满,则删除表中顶头的一个,将最新禁忌对象加入表的末尾。
2)这是本文提出的一种新的邻域构造方法。这种构造方法一是块中的工序的交换,另一种是非块中工序的交换。可分别设主、次禁忌表来禁忌这两种交换。令JP(v)和JN(v)分别表示工序v在工件中的前一个工序和后一个工序,MP(v)和MN(v)分别表示工序v在机器(块)中的前一个工序和后一个工序。本邻域的构造包含三类移动,第一类可以交换块中边缘的两个相邻的工序v和w=MN(v),并且要求v不是第一块的第一个工序,w不是最后一块的最后一个工序;第二类是在第一类交换(v,w)的基础上,还交换(s=JN(v),t=MN(q))(如果s和t存在,并且L(s,N)=L(t,N)+dt)。其中L(s,N)表示有向图G(π)中以s为起点的最长路径的长度;第三类是做两对相邻的(v,w)和(x,y)的翻转,要求若两对翻转是在同一个块中,则该块中含的工序数必须大于3。
3.1.3 禁忌搜索过程
针对前面(2)中给出的两种不同邻域构造方法,制定不同的禁忌搜索策略。
禁忌搜索过程1:
STEP1:给以禁忌表(tabu list)H=⌀并选定一个初始解xnow;
STEP2:满足停止规则时,停止计算,输出结果;否则,在xnow的邻域N(xnow)中选出满足不受禁忌或已解禁的候选集Can-N(xnow);在Can-N(xnow)中选一个评价值最佳的解xnext,并禁忌对象放入禁忌表中,nnow:=xnext;若在Can-N(xnow)中的解的评价值都不优于当前的解,则选择一个最不差的未禁忌或已解禁的解xnext,nnow:=xnext;若所有邻域点都被禁忌,则特赦最优的解xnext,nnow:=xnext;更新历史记录H,重复STEP2。
禁忌搜索过程2:在邻域2)的构造过程中,不仅涉及到块中工序的交换,还涉及到非块中工序的交换,因此需设两个禁忌表即主、次禁忌表分别记录块中及非块的禁忌交换。只要有一个交换是被禁忌的,则该移动就被禁忌。
若存在好于当前最好的邻点,则选择搜索遇到的的第一个这样的邻点,并将其交换插入相应的禁忌表中。如果所有的邻点都不好于当前的解或邻点,若存在未被禁忌的邻点,则选择最不差的未被禁忌的邻点,并将其交换插入相应的禁忌表中;否则所有的邻点都被禁忌了且都不好于当前解,则从一类邻点中找在主禁忌表被禁忌时间最长的交换,并解禁该交换。当一个未被禁忌的交换插入禁忌表中时,若表中未满,则将该交换加在表的末尾;否则删除表中顶头的一个,再将该交换加在表的末尾。
4 实验结论
本文提出改进的禁忌搜索算法采用Visual C++6.0在Windows XP平台上编程实现,并以参考文献[6]中的数据(10个工件,每个工件有10个工序,机器数为10)为测试数据。下面根据文献[6]给出加工时间阵T、机器顺序阵M。
本实验中令算法的最大迭代次数为1000,最大连续无更好解次数20,禁忌表长度为30,本文对算法执行20次,取得最优解为87个时间单位,得到最佳调度如表4.1所示。
在求最优解的过程中(20次),记录每次得到的目标函数值,如表4.2所示。表4.2的结果表明改进的算法在20次运行中有5次达到最小值87,而且最差的值和最优值之间的偏差也只有4,结果差别不大。
为了验证改进的禁忌搜索算法(MTS)的有效性,对标准的禁忌搜索算法(TS)采用上述相同的参数取值进行了20次运行,得到的最优解为96,与最差值的偏差为6。通过比较可以得出,MTS比TS有较好的稳定性。
注:表中加工工件序列中的1-10为工件名
5 总结
本文利用改进的禁忌搜索算法对车间作业排序更广泛的情形进行了研究,实验结果证明提出的算法可行、有效,具有一定的应用性。另外,随着问题规模的不断扩大及约束条件的增加,可能还需建立更加经济可行的问题模型,以及对这一模型提出更加高效、先进的算法,这有待于进一步研究。
摘要：本文描述了一种解决车间作业调度最短完工时间问题的有效禁忌搜索算法,建立了该问题的数学模型,并提出了新的邻域构造方法。该算法利用改进的插入算法构造尽可能好的初始解,然后使用禁忌搜索算法改进当前解。实验结果表明该算法是可行和有效的。
关键词：禁忌搜索算法,NP-难,车间作业调度
参考文献
[1]Garey M R,Johnson D S.Computer and intrac-tability:a guide to the theory of NP-complete-ness[M].San Francisco:Freeman,1979.
[2]Shi G Y.A Genetic Algorithm Applied to aClassic Job-shop Scheduling Problem.Interna-tional Journal of Systems Science,1997,28(1):25～32
[3]Adams J,Balas E,Zawack D.The shifting bot-tleneck procedure for job shop scheduling[J].Management Science,1988,34(3):391-401.
[4]邢文训,谢金星.现代优化计算方法(第二版)[M].北京:清华大学出版社2005.
[5]黄志,黄文奇.一种基于禁忌搜索技术的作业车间调度算法[J].小型微型计算机系统,2005,2(26):222-225.
[6]王万良,吴启迪.求解作业车间调度问题的改进自适应遗传算法[J].系统工程理论与实践,2004,24(2)::58-62.
车间作业调度问题 篇2
关键词：航天,调度,车间,生产计划
随着我国社会经济的飞速发展,我国的科技实力也呈现出日新月异的变化趋势,其中航天科技的发展尤为明显。神舟系列航天飞船、嫦娥号系列探测器、天宫一号目标飞行器的出现,不仅展现出我国航天科技领域科技水平的不断提升,还显示出我国作为负责任的发展大国为世界航天领域所作的贡献。航天事业不仅要提高自身的科技含量和降低生产升本,还要形成具有完整的科学合理的航天生产计划管理以及车间作业计划的调度体系。
1 航天生产计划管理
由于航天生产自身的特殊性,决定了航天生产计划管理与其他一般生产企业不同。对于航天生产来说,其制造生产的零件属于高科技的零件,对于精密度的要求更加严格,而且比较其他生产行业来说,航天生产的数量相对较少,且对于零件的保密性要求较高。尽管所有的制造企业发展到今天,对于生产计划的管理流程都出现了太多过于相似的环节。
大致的流程都是客户提出订单,并制订详细的计划和要求。信息部门对于客户提出的要求进行分析处理,确定订单制作的可能性。如果企业满足要求,则会进入经营管理处进行专业的信息分析。信息进行专业的处理之后,交由制度部门根据本公司实际的生产计划进行统筹安排,然后确定具体进行生产的车垫和单位。车间单位根据实际的生产加工情况对信息进行反馈处理。
在生产落实阶段,首先是由计划制订部门将生产计划下派到车间以及技术部门进行生产统筹,之后通过车间调度室的调度进行各个零件的生产加工。在这些生产制造过程中,我们可以看出生产车间与技术部门之间的关系非常紧密,不仅技术部门对于生产车间有着指导作用,且生产车间在生产准备计划完毕之后还要将生产信息反馈到技术部门。
2 车间作业计划调度管理问题
就我国目前航天产业发展现状来看,我国的航天生产车间的作业计划依然存在很多问题。而这些问题出现的根源主要在于计划调度管理方案与航天生产的实际发展不相匹配。在航天事业发展到今天为止,其生产指导的企业大多数为老工业时期建立起来的,且各国之间由于竞争问题,导致航天生产经验相对保密,于是,很多过于陈旧和落后的生产技术与制造技巧依然沿用,有些车间作业计划调度的制订更是没有科学理论依据的个人经验。调度计划的制订存在很多主观性误区,导致调度不科学。
有的航天企业各部门之间的合作不及时也会导致车间作业计划调度出现管理问题。例如,技术部门没有及时对车间部门反馈的信息进行分析研究,导致没有及时对实际车间生产情况进行技术支持。计划部门为了计划而制订计划,往往忽视了实际车间作业的情况,对于各个车间的不同情况不能灵活地调整作业计划,而且统一实行相同的计划,这样就会引起各个车间的内部矛盾激化,导致整体的计划调度受到影响。为此,在实际的车间生产作业计划调度中,一定要根据实际的情况进行恰当的调度,客观公正地对问题进行及时处理。
3 车间作业计划调度问题的研究
3.1 基本问题
关于航天制造行业的车间作业计划调度问题的研究,我们一定要坚持从实际出发,将调度问题按复杂程度进行分类,或根据加工的特点进行分类。在调度的过程中要时刻保持动态调度和静态调度相结合,并根据具体情况进行具体分析。
3.2 研究分析
在对航天生产计划制造行业的车间作业计划调度问题进行研究分析时,可结合单行机与对行机之间的调度调整问题进行研究。首先,单行机调度最关键的部位在于取值问题的确定,在实际的运用中,通过将设备的取值问题进行调度,保证在运行时间能够最短的情况下对于调度进行必要的调整。尽管对于单行机的调度调整十分简单,但也要重视可能发生的突发情况。例如,在进行并行调度时,如果M和N两个值进行适当的调整,在两个值相等的情况下,可将这两个值认为是等值标准。如果一个值较大时,这种情况下进行调度的分配就比较简单,通俗来讲,就是当工作环境中的员工大于工作任务量的时候分配是比较简单的。如果这个值变小,那么就需要在车间生产的过程中进行必要的调度。当然,在实际生产生活中的调度问题不会这样有规律,所以对于调度问题的实际情况进行分析时,一定要学会选择不同的调度系统。
4 结 语
随着我国社会经济的飞速发展,我国的科技实力也迅速提升,其中航天科技的发展尤为明显。神舟系列航天飞船、嫦娥号系列探测器、天宫一号目标飞行器的出现不仅展现出我国航天科技领域科技水平的不断提升,还显示出我国作为负责任的发展大国为世界航天领域所作出的应有贡献。航天生产计划管理与其他产业的管理有着本质区别,本文对于航天生产计划管理以及车间作业计划调度的问题进行了深入的探讨,探索航天生产企业如何形成科学合理的调度计划,进而不断提高航天生产企业的竞争力。
参考文献
车间作业调度问题 篇3
模具生产属于面向资源的工程订货型单件小批量生产模式,企业生产系统中频繁受到各种不确定因素的影响,如机器故障、工件返修、急单插入、工期不确定等,使得企业生产计划更新速度根本赶不上生产执行过程中出现的频繁变化,最终导致生产计划与生产的实际执行状态完全脱节,造成预先生成的基准调度方案无法按照计划执行。其中工期不确定是当前企业生产面临的最大挑战,影响工期的主要原因是在制造过程中,由于存在着各种随机干扰因素,导致任务的工期事实上很难具有一个明确的固定值[1],并且传统的车间作业调度都假定任务具有明确、固定的工期,所形成的调度方案在现场执行过程中的指导性偏差较大,这也是造成当前调度方案可实施性不强的主要原因。为了制定可执行性强的调度排产方案,就需要对不确定工期的调度进行研究。
于晓义等[2]提出了面向随机加工时间的车间作业调度方法,将工时作为随机变量,构造扩展遗传算法解决加工时间为服从正态分布的随机变量的车间作业调度问题,取得一定的成效。朱颢、唐万生[3]对实际调度问题中存在的不确定现象,提出了加工时间服从正态分布、最大完成时间的期望值作为目标函数的随机Job Shop问题,利用遗传算法训练神经网络的智能优化算法解决该问题。其求解的目标是最大完成时间的期望值,但结果只是一种期望值意义上的调度方案。丁雷、王爱民[1]等针对Job-shop调度问题提出了面向多品种、变批量生产模式的工时不确定条件下的车间作业动态调度技术,在工时不确定条件下,通过分析车间作业调度方案制定的不确定性、执行过程的动态性、变更影响的关联性以及响应的实时性内涵,提出了解决工时不确定情况下调度问题的缓解、隔离和快速响应相结合的处理策略。潘群[4]研究了具有模糊加工时间的作业调度问题。针对企业的生产淡季、生产旺季和待加工工件重要程度不同的三种生产环境,建立了相应的模糊调度数学模型,并提出了调度方法。但形成的调度方案随机性过强。文献[5]分析加工时间为随机变量,建立以机器的作业成本和闲置成本作为目标函数的非线性规划模型,采用模拟退火和神经网络的混合算法进行求解,但并没有对随机加工时间做深入的分析。文献[6-7]分析不确定因素,建立随机的调度模型,但并没有进行进一步研究,只是建立了一个笼统的模型而已。HICKSC[8]针对成本问题,对确定工时条件下的重调度与增量调度的进行了分析,但没有论及工时不确定。Xiang[9]等针对工序间准备前后依赖一类的问题,提出了一种基于设备智能体和工件智能体相结合的蚁群动态调度算法,但没有对工时不确定做进一步研究。
车间普遍存在工期不确定的问题,成为影响车间作业有序、协调、可控和高效执行的直接瓶颈[10],为了制定可执行性强的调度排产方案,保证作业计划方案与生产现场执行同步,真正达到有序、协调、可控和高效的制造执行运行效果,就需要对不确定工期进行处理。本文以这一目的为驱动,提出了工期不确定的模具车间作业调度流程,详细阐述了工期不确定的模具车间作业调度的前置处理过程。本文的研究思路可以大幅度提高面向不确定工期调度方案的可执行性。
2 工期不确定车间作业调度流程
针对工期不确定的调度问题,提出如图1所示调度流程。
首先,建立任务工期离散概率模型;然后,用各任务工期离散值进行组合计算,对组合出来的结果做包络分析,筛选出具有代表性的、在可计算范围内的工期组合;最后为每一工期组合进行调度,寻找获得的调度方案的中心,作为基准调度,以实现不确定工期下的调度,为提高模具制造系统的运作效率奠定基础。
3 工期离散概率模型
在模具企业的生产中,任务工期不是固定不变的,一个任务可能有多个加工工期,每个工期都有着相应的发生概率,可根据企业历史经验统计而得。对于任一任务A,它可以用离散概率模型描述[1],如式(1)所示。
其中,以工期ti(A)(i=1,2,…,G)完成任务的概率为Pi(A),G为任务A可能的工期个数。t1(A)
4 工期组合计算及其包络分析
离散概率模型是以工期离散点及相应的概率来表现,任务的加工工期是呈离散概率分布的随机变量,每个可能的任务工期都对应着一个相应的概率值。这样将针对每个任务制定许多不同的可能加工计划,把每个任务的各种不同的可能工期组合起来,就生成了许多不同的可能工期组合,每个可能的工期组合都具有一定的概率值,概率值较大的就是实际生产中较可能发生的。但在任务数较大,任务可能工期点较多的情况下,每个任务的各种不同的可能工期组合结果数就会非常多。如果直接把这些组合结果作为制定后续任务调度的基础,那么将由于数据量过大而变得不可行,这里就需要对组合结果做包络分析,从组合结果中筛选出的具有代表性的工期组合。
4.1 任务工期点组合计算
根据建立的不确定工期模型,对不同任务工期点做组合计算。
4.1.1 任务工期点组合
定义1:组合。
假设共有m个任务,每个任务有n个工期点,任务之间相互独立,任务先后顺序固定,则有K=nm种工期组合,令Qk={A1k1,A2k2,…,Amkm},ki=1,2,…,n;i=1,2,…,m;k=1,2,…,K,Qk表示一个工期组合,每一组合都有相应的发生概率,表示每一个确定的任务工期组合在实际生产中发生的概率。
用Q={Qk|k=1,2,…,K}表示m个任务,每个任务有n个的工期点的组合计算结果集,该结果集共有nm种组合,结果集中所有组合的发生概率总和等于1。
4.1.2 组合的概率计算
任务工期每一种组合结果的概率值为所组成该组合的工期点的概率值的乘积,用Pαki表示任务工期组合Aαki相应的发生概率(ki=1,2,…,n;i=1,2,…,m;α=1,2,…,K),则(ki=1,2,…,n;i=1,2,…,m)为组合Qk的发生概率,概率值较大的工期组合在实际生产中发生的概率更大。
4.2 组合情况包络分析
由于上面组合计算的组合结果有nm种,这里进一步对组合结果做包络分析,从组合结果中筛选出的具有代表性的工期组合。
定义2:包络。
存在组合Q1={A11,A21,…,Am1}与Q2={A12,A22,…,Am2},假设组合Q1与Q2满足以下条件。
(1)组合Q1的每个工期值Ai1都大于等于组合的对应的工期值Ai2,即A11≥A12,A21≥A22,…,Am1>Am2。
(2)组合Q1与组合Q2的工期差值和(空闲时间t)满足工时偏差容忍度:
式(2)中ɸ为给定合适值。
(3)组合Q1的发生概率值不小于组合Q2的发生概率值。
则可以说Q1包络Q2,记为:Q1劢Q2。
一旦组合Q1被Q2包络,则按照Q1形成的调度一定可以适用Q2,只是多出来空闲时间,这里用偏差容忍度准来控制空闲时间,一旦空闲时间是容许误差范围内,可以将Q2与Q1合并,统称为Q1,同时,将Q1的概率与Q2的概率叠加,作为组合Q1的新的概率。以上分析如图2所示。
通过定义可知,在满足条件的前提下包络具有以下的性质:
(1)传递性:如果Q1⊃Q2,Q2⊃Q3,那么Q1⊃Q3;
(2)自反性:如果Q1⊃Q2,Q2⊃Q1,那么Q1=Q2。
包络的这些特性比较直观,证明从略。
5 工时偏差容忍度
如果在包络分析过程中,选择的工时偏差容忍度ɸ过大,使空闲的时间过多,造成总工期过长,如果用这样工期组合来做调度的话,必然会降低企业的生产效率,给企业制定具有可执行性和指导性的调度方案带来较大的困难,不便于企业调度方案的生成,因此给定一个企业可以接受的工时偏差容忍度ɸ,比如说0.1,则以工时偏差容忍度ɸ=0.1来做工期组合的包络分析,这样就可以得到包络了其它工期组合的组合及其发生的总概率,其中总概率为包络组合与所有满足ɸ=0.1的被包络组合的概率和。
这里引入平均容忍度的概念:把组合包络其它组合产生的空闲时间占总时间的比例的均值作为平均容忍度,其值越小,该组合包络其它组合所产生的空闲时间就越小。
6 实例
基于以上研究内容,本文在Windows XP平台上,用Visual C++开发了任务工期点的组合计算及包络分析软件。实现了工期不确定的车间作业调度前置处理,为后续调度奠定坚实基础。
以调研的模具企业为例,表1为直径为R的不同电火花钢花纹项目模板。针对关键工序电火花,通过分析不同项目模板电火花加工历史数据。得任务工期的离散概率模型得实例如表2。根据建立的不确定工期模型实例,例如取普通花纹(P0,P1)、封闭花纹(P2,P3,P4)、复杂封闭花纹(P5,P6,P7)。
通过对任务数,工时偏差容忍准的定义,实现人机交互。先根据输入的任务数直接从数据库中读取当前任务所属的项目模板类型,然后根据项目模板类型与数据库中任务工期的离散概率模型实例匹配,得到各任务可能工期值与相应概率值,最后对得到各任务可能工期值与相应概率值作组合计算与包络分析。
通过组合计算及包络分析软件对任务工期点进行组合计算结果如图3所示。总组合结果有38=6561种。每种组合都对应有发生概率。
在由计算机得出工期组合之后,则要对工期组合进行包络分析,对得出来的工期进行包络分析,就是在保证模具加工的完成时间的前提下设定容忍的参数,通过对企业的实际调研,取工时偏差容忍度准=0.05。在满足容忍的参数条件下用每个工期值较大的工期组合包含每个工期值较小的组合。工期值较大的组合形成的调度方案可以适用与所有被该组合包络的组合形成的调度方案。
最后得出的工期组合在满足工时偏差容忍度准=0.05的工期组合集,如图4所示,该集的势为726个工期组合,为企业后续调度服务,通过包络分析的工期组合数量大约缩小为原来的十分之一。平均容忍度体现了该组合包络其它的组合产生的空闲时间占总时间的比例的均值。其值越小,该组合包络其它组合所产生的空闲时间就越小。
7 结束语
本文建立工期离散概率模型,对模型中的工期点,作任务工期点组合计算,并对组合结果做包络分析,筛选出具有代表性的工期组合,为制定具有可执行性和指导性的车间作业调度方案的奠定基础。
参考文献
[1]丁雷,王爱民,宁汝新.工时不确定条件下的车间作业调度技术[J].计算机集成制造系统,2010,16(1):98-108.
[2]于晓义,孙树栋,王彦革.面向随机加工时间的车间作业调度[J].中国机械工程,2008,19(19):2319-1314.
[3]张沙清,陈新度,陈庆新,等.不确定环境下模具制造项目群随机调度[J].计算机集成制造系统,2009,15(7):1389-1396.
[4]张沙清,陈新度,陈庆新,等.基于多步Q学习的模具制造项目群随机调度算法[J].中国机械工程,2009,20(12):1439-1445.
[5]Tavakkoli—Moghaddam R,Jolai F,Vaziri F.A hybridmethod for solving stochastic job shop sch-eduling prob-lems[J].Applied Mathematics and Com-putation,2005(170):185-206.
[6]Pistikopoulos E N.Uncertainty in process design and op-eration[J].Computer and Chemical Enginee-Ring,1995,19(suppl):553-563.
[7]Honkomp S J,Reklaitis G V.Robust scheduling withprocessing time uncertainty[J].Computer and Chemi-cal Engineering,1997,21(suppl):55-60.
[8]HICKSC,SONG D P,EARLCF.Dynamic schedulingfor complex engineer-to-order products[J].Interna-tional Journal of Production Research,2007,45(15):3477-3503.
[9]XIANG W,LEEH P.Ant colony intelligence in multi-Agent Dynamic manufacturing scheduling[J].Engi-neering Applications of Artificial Intellig-Ence,2008,21(1):73-85.
[10]李保,王长华,熊靖.基于自适应蚁群算法的动态作业车间调度问题的求解方法[J].机电工程,2009(7):93-96.
车间作业调度问题 篇4
车间作业计划(Production Activity Control,PAC)是依据主生产计划(MPS)而编制的具体执行工作方案。它把车间的生产任务落实到每个人、每台设备上,是车间组织生产的依据,也是企业管理中最重要的部分[1]。PAC的实施贯穿于生产系统的各道工序,受很多因素的制约。随着生产规模的扩大和复杂程度的提高,PAC的实施与调度也出现了一些问题。本文应用车间作业调度方法,针对当前PAC与调度中存在的问题进行研究,为企业提供优化的生产作业排序和车间作业调度策略,从实践与理论方面提升PAC及其调度水平,以提高制造系统的运行效率,增强企业的市场竞争力。
1 PAC与车间调度的内涵与特点
PAC系统是一个高度复杂的系统,它有效综合了机械、信息、网络等资源。制定PAC是为了使生产设备、物料、人员和信息四者匹配,实现车间均衡、协调、持续生产。在PAC生产执行过程中,决策部门需要根据车间的生产能力及其他资源的使用等反馈情况不断地调整PAC,而调整计划贯穿于企业生产活动的全过程。因此,要最大限度地发挥生产系统的柔性潜力,满足市场需求。
1.1 PAC与车间调度的界定与内涵
PAC的编制包括确定操作顺序、分配资源和制定期量标准等。PAC与车间调度问题是一个典型的任务集,包括资源集、约束条件集、性能指标集。其中,资源集包括人员、设备、工具和材料等,而每台设备可以完成一种或多种作业,不同设备能完成的作业集可能相同也可能不同;约束条件集用以规定生产过程中需要的条件,如任务的优先级、每个作业要求完成的时间、资源的能力、生产工艺、质量标准等;性能指标集用以规定生产过程中需要优化的目标,如生产周期、在制品量、订单交货期、资源利用率和生产成本等。每一个任务都包含一组需要执行的作业序列(工序),而这些作业序列需要占用系统的机器、工具等资源,并且必须按照一定的工艺顺序执行。
调度的目标是为作业合理分配资源,为每一个加工对象合理安排具体的加工顺序、路径、时间、制造设备资源和操作等,使内部和外部约束条件被满足,其中内部约束主要为企业的资源约束、能力约束和生产过程中的技术约束等;外部约束主要为订单规定的时间要求和品质要求等,同时使大部分生产性能指标得到优化。在有限产能、库存容量及资源的约束下,通过优化配置生产资源来提高PAC的可实施性以及生产过程的可计划性、可控性[2,3]。而车间作业调度与控制则是实现生产高效率、高柔性和高可靠性的关键环节。
1.2 编制PAC的特点
在编制PAC过程中应考虑其如下特点:
(1)实用性。
以在制品加工进度为基础编制工序能力计划,使PAC紧跟生产现场,达到计划编制与生产节拍的和谐统一。PAC计划期短、计划内容具体、计划单位小等,可操作性强。
(2)合理性。
综合上级计划、在制品进展情况、工序周期、工序时差和剩余工作量等因素,通过合理的排程方法,达到满足交付和有效利用资源的目的。
(3)计算机模拟与预见性。
采用“模拟和预测”的方式,帮助计划员提前预测未来计划的执行情况,而且通过模拟可以导出最优工序排序方案、瓶颈和薄弱环节,找准切入点,分析模拟输出结果,从中选择出较满意的PAC方案,该方法可提高管理质量及效率。
(4)平衡性。
以零组件交付需求为依据,不断地平衡和处理任务与生产能力、计划与实际的关系和矛盾,特别是设备负荷的平衡和生产现场问题的有效处理,将进一步强化生产现场组织、协调与控制。
2 PAC与车间调度存在的问题
PAC处理问题的广域性、动态性和多约束性使PAC的编制容易产生各种问题[4]。加之生产环境具有不可预测性、多变性、随机性、干扰性和经验性等问题的存在,PAC的编制成为企业生产管理中的一个难点,许多问题至今尚未得到很好的解决,例如数据处理、加工排序、库存、批量与加工瓶颈等问题,这些问题都影响到PAC的适应性和效率。当前PAC与车间调度存在的主要问题如下:
(1)生产实际情况与PAC冲突。
在客户要求订货批量愈来愈少、品种愈来愈多和交货期愈来愈短的情况下,生产线负荷和能力的调控越来越复杂,不但耗费大量人力,还经常出现生产异常情况,使生产和交货脱节。另外,由于PAC的制定多考虑按时交货,少考虑生产线能力的限制,经常造成实际生产偏离计划。实际生产环境中存在着大量的随机事件,一方面由于产品的品种多,工序复杂,产品的工艺过程经常变更;另一方面又常常会面对紧急订单、订单变更及订单取消等异常情况,又很难预测订单在什么时候到来。虽然产品订单是生产制造部门的任务标的,但由于产品订单签约日期、签约产品类型和数量具有不稳定性,如果将其直接作为生产制造部门的任务来源,则会造成生产制造部门生产的波动,破坏生产过程的均衡,一旦计划与实际的出入过大,将难以保证客户订单按时完成,影响企业的交货信用。企业要快速响应市场需求必须及时发现PAC同实际的偏离,并不断改进,同时也需要PAC能适应客户需求和客观环境的不断变化。但如果一味追随变化,朝令夕改,势必造成生产上的混乱。因此控制计划变动是保证计划可执行程度的重要内容。显然,期望通过不断地调整企业本身的生产资源去适应和匹配不可预测的、动态变化的订单任务是不现实和不可行的。事实上,需要进一步分析产生上述生产系统不平衡和频繁更改现象的原因,很多情况可能是没有系统合理考虑加工资源而造成的。由于企业内外部环境不确定因素的影响,虽然智能型生产系统在一定程度上能缓冲静态作业计划与动态调度间的矛盾,但依然无法从根本上解决计划与调度间的脱节问题。如果将车间内所有班组进行实时调度,由于在普通机床上零件的加工工序不能确保加工时间以及加工质量,加工执行情况必须依赖人工录入的信息,即使按照工艺规定的辅助工时和加工工时进行预先的安排,但普通机床实际的加工结果必须等待人机交互录入后才能进入计算机以及数据库管理系统,因此势必影响后续工序的安排和调度。
(2)不同生产条件下,PAC编程方式也不同。
PAC的编制者可以选择不同的优化目标,对不同的优化目标,又可以采用不同的排序方法,不同的排序规则编排同一作业计划时也将产生不同的排序结果;不同的目标影响调度的具体模式;在不同的制造资源、约束条件、生产规模、生产形式和管理方法下,车间调度问题的调度策略及其数学模型一般不同;不同企业因生产过程不同,其生产组织和管理也有所差异,计划员对现场掌控不同所得出的结果也将不同;即使同样的生产计划经验,同样的设备和人员,所安排的生产计划也略有差异;企业的生产类型和生产组织形式不同,采用的有关生产期限和生产数量的标准即期量标准也将不同;企业性质不同生产结果和方式也不尽相同;按照约束条件去安排,无论是拉式生产,还是推式或混合式生产,其生产方式不一样,计划的安排方式也不一样,不同的编制方式其结果往往差异很大;生产计划还与所处的环境有关系,如果企业周围有着良好的工业环境,距码头近,则计划的方式和生产方式也存在着差别;客户不同安排的结果又不一样;生熟手不同,产生的效率也不同。如果作业分配和排序安排不当,将出现人员或设备窝工,生产周期拉长,急件和缺件不断生产等复杂的问题,只按经验或随意安排作业,导致生产的全面被动乃至恶性循环。另外,PAC编制存在两大问题:第一,在当月PAC尚未执行完毕时,过早地编制下一个月的计划,结果造成当月生产实际完成量与计划量的偏差及用户和市场需求情况的变化,造成计划与生产脱节;第二,在当月PAC全部执行完毕时再编制下一个月的PAC,结果造成生产连续性缺乏必要数量的在制品储备和当月投料、当月加工、当月装配被动的局面。PAC的制订应与企业当前的生产状况相适应,投料过早或过多,各加工中心的在制品数量增加,等待时间延长,导致生产周期增加,系统稳定性变差;投料过少或过晚,系统利用率低,造成产出降低、订单延误。
(3)影响PAC因素的多样性而导致其变动。
影响PAC及其调度有各方面因素,识别这些影响和干扰具有一定的困难。车间制造环境的复杂性、生产加工任务和调度目标的多样性,系统加工任务的动态性,使得PAC和车间调度存在一定的复杂性和困难。由于大量不确定因素的存在,传统的PAC与控制模式存在作业计划与现场调度相脱节的问题,目前PAC的研究与制定大部分逐层进行,往往是上层计划的可行性到下层计划编制实现时才能验证。这样既加大了车间调度的难度,又使作业计划流于形式,生产控制目标难以实现。在PAC编制工作完成以后,付诸生产实施时,由于作业计划考虑的是静态情况,而实际生产过程是动态的,无论编制PAC时考虑多么周密,安排如何具体,也无法预见实际生产过程中的所有变化。PAC将随着市场、加工时间、加工路线等生产影响因素和约束条件的变化而变化,在实施过程中也不是一成不变。在生产中,由于生产能力的变化,前一周期任务的延期完成、废品的产生都可能影响PAC的完成。另外,停机、停工、准备时间的变化,可用原材料的减少等也都是影响PAC完成的因素。尽管制定PAC时已经充分考虑了现有的生产能力,但由于其在实施过程中受到各种因素的影响造成事实情况与计划要求不符或偏离,这种差异主要表现为生产进度和生产数量的不一致;多品种产品的总需求量及其比例的预测与实际情况的差异;特定品种的需求预测和实际情况的差异;订货计划和实际需求情况的差异;计划产量(计划时间)和实际产量(实际时间)的差异;库存量的变动和产品中断发生的差异,此外还有因设备故障和出勤情况变化而造成的工作效率变动。因此,PAC能否得到有效执行,不仅仅取决于该计划是否完善,还取决于对一些不可预见的突发事件的处理,如原材料供应变化、生产任务变化、工件加工质量达不到要求而被迫返工等。在制定PAC时,有可能面临着原料供应、产品需求量、产品价格等都是不确定的,无法提供计划所需材料(比如由于供方失约、原材料短缺等原因),不得不减少甚至停止生产。当出现下列情况时,PAC也要进行调整与修改:市场对产品的需求发生变化;经营方针、目标发生变化;企业微观经济效益、宏观经济效益发生变化和其他宏观控制条件变化;季节性变化;人、财、物等资源供应条件发生变化;专业化、协作者关系及其组织形式发生变化。
(4)外部动态性和内部相对静态的矛盾。
在实际车间调度中,不仅需要考虑管理人员、制造人员的技术水平,刀具、夹具、量具、检具、物料转序等因素,还需考虑产品的投产期、交货期、生产能力、加工顺序、制造设备和原材料的可用性、生产批量、加工工艺路径、成本限制等其他因素,以及生产作业调度和制造资源调度。尽管影响车间调度问题的因素很多,但有些约束条件必须满足,如交货期,生产能力等,而有些只需控制在一定的范围之内,即可把相互矛盾的目标做到相对平衡,如生产成本,这些约束在进行车间调度时可以作为确定性因素处理。实际车间调度问题的难度远超过经典车间调度中的排序问题,其中诸多因素影响调度决策,如市场、技术、人员、资金、经营管理、制造资源。企业生产的内部要素,即企业的生产资源和生产能力,相对来说是确定的、静态的。因此,外部动态性和内部相对静态性二者之间的不匹配和冲突干扰不可避免地成为单件订货型生产系统的固有特性,造成了生产系统的不平衡性,主要表现在两方面:某些时段订单多,任务量大,企业出现某些资源紧张,负荷率大甚至不堪重负,不得不通过频繁大量的加班或外协来完成生产任务;在另一些时段,生产负荷与资源的这种关系可能倒置过来。因此投产批量的设置必须在一个可控的范围内,既不能批量过小导致当前设备利用率过低,也不可以批量过大而导致在制品库存过大,影响到其下道工序的投产时间。在制订作业计划时如果没有考虑系统瓶颈,当出现异常情况,瓶颈发生漂移时,也没有相应的应对措施,就无法实现均衡生产。
(5)PAC和组织管理方式不当。
生产组织管理方式不恰当容易引起生产线能力不平衡,设备维护不到位,因此造成各工段的工作进度不协调,出现等工现象或者堆满了物料等待加工。PAC安排不合理,负荷分布不均衡,无法做到均衡生产,企业的PAC执行率低下。物料的生产和采购期量系统不够健全,物控跟催采购物料进厂状况,在核查时疏忽或责任没到位造成停工待料。而供应商来料不合格、技术资料延迟、采购计划错误、材料标准错误和合同评审程序失效所引致的PAC的时常变更,导致采购部与供应商无法跟上。生产需求的随机性导致生产需求变化和生产瓶颈无法预测时,人工生产排程困难,资源不能充分利用。此外,原材料短缺对PAC带来很大冲击,使企业不能正常安排生产,计划不能按时完成,有些企业为了保证信誉度,保证订单的交货期,不得不以高价购进原材料来维持正常的生产,从而造成经济损失。物料在系统中通过时间太长,设备利用率低,紧急订单得不到及时处理。备料导致无法跟进生产计划而促使计划变动,计划、生产及物料进度不能协调同步进行。物控工作失控造成生产物料不足或过多。销售计划淡旺季预测不准确,造成人员招聘的无计划,影响企业士气,还影响生产效率和资源的利用。客户天天催货,计划部频繁更改出货计划,生产部门时而待料,时而通宵加班等,造成客户抱怨、取消订单甚至索赔。这些由于生产计划的频繁变化所致使的生产现场和生产循环的混乱,严重影响客户满意度。生产经营紊乱引发质量失控造成经常性返工或返修,进而影响PAC的执行。面对频繁的计划变化,生产计划部的工作任务极其艰巨复杂,很难保证计划与控制的质量,生产计划员苦不堪言,加上对实际生产控制缺乏理解,因此常出现所谓的“车间经验”的问题,即忽视目标与实际能力之间的相互关系,导致生产控制恶性循环。如果需要通过加急任务和特别行动才能将最重要的任务按时完成,企业往往采取的措施是进一步加长生产周期,这个循环将会变成一个恶性时间螺旋,它只有在远远高于实际所需的生产周期和更大的偏差水平上才能够稳定下来,从而造成更大的浪费与等待。
(6)调度业务考评办法不合理。
以结果为导向的经济责任制考核办法未体现调度考核职能,它主要考察该单位部门是否完成PAC的各项任务,而对实际生产过程中各项生产指令执行情况以及生产中出现的问题存在不报或延时报告现象没有进行考核,造成车间调度指令经常得不到落实或落实不及时,政令不畅通,影响生产顺利进行。同时,调度在日常检查工作发现工艺过程中存在的问题很难及时纠正,下达的调度指令缺乏“震慑”力,调度室对调度员尚未建立考核办法和相应的考核机制来充分调动调度员工作积极性。
3 PAC的编制流程、方法与调度原则
3.1 PAC的来源及编制流程
编制PAC要解决两方面的问题:一方面保证交货期;另一方面保证企业在生产车间相互衔接。它反映两个主要的变量关系:期与量。期,即计划的时间变量;量,即生产计划的数量。一个典型的制造车间生产活动主要工作流程是:
(1)生产订单由销售订单分解及综合重组而得,它是销售订单与生产之间的中介。计划人员根据原料供应情况、车间设备状况对某一时间段内(如一周、三天等)到达的所有客户订单进行分析,如产品类型、数量、客户重要程度等因素,采用一定的算法,将多个合同进行归并,并根据交货期、设备能力和生产工艺等限制性要求进行最佳组合,使前后工序紧密衔接,减少等待时间。根据交期与资源,对订单进行评估,当出现生产不能满足订单要求时,生产部门需要和销售部门进行信息交流和沟通,最后得出生产订单,即MPS。
(2)PAC依据MPS完工时间,物料需求计划中各零件计划到位时间以及产品的加工次序进行任务分解,然后根据一定的规则,确定各子任务的加工设备,而任务单的开工时间则根据订单下达日期、任务单计划入库日期、相关的工艺信息、生产技术准备工作以及各加工单元的当前加工计划来统一决定,实现PAC有赖于各项工作的落实。在编制出理论计划以后,就形成了各加工单元的负荷。
(3)平衡各加工设备的加工能力与工作负荷,制订派工计划和相关物料准备计划。初步确定若干种可行方案,在计算出各方案的总成本后择优选择,确定加班、转包等生产能力。同时,根据物料、工装等条件及各加工单元的反馈信息,制订出正式可行的作业计划,分配到各工段或班组中,充分利用瓶颈环节生产能力,准时提供零部件,同时尽量使设备负荷均衡并使在制品库存尽量减少,保证生产中心按期完工。车间计划、车间作业、车间调度根据车间生产能力和资源状况信息,为计划资源作优化调度。当生产作业的加工对象不止一种时,为了加快生产进度、缩短加工时间,需要合理地安排生产作业顺序。
(4)车间分配任务有两种方式:一种是将零件的所有加工任务分配到一个工段或班组;另一种是根据各工段或班组设备、人员的特点将零件加工的工序分别分配到不同班组。前一种方式需要班组调度人员同车间调度人员密切协作,以便将不能在本班组加工的工序安排到其他班组或外车间进行加工,后一种方式需要车间的车间调度人员及时了解生产的执行情况,随时根据具体情况重新调度和安排生产。现车间大多数都采用第一种方式进行任务的安排,以方便对班组进行统一考核和人员、生产质量的管理。在复杂的车间里,调度人员接到厂区下达的PAC以后将这些任务分解成零件任务分发到各个工段,由工段调度员根据本工段的当前任务将零件任务分派到各个班组或工人,班组严格遵照生产制造单组织生产。
3.2 PAC日程计划的制定要求
如何对计划进行生产预先设定时间、顺序、不同产品和批量衔接等,是日程计划要明确的事项。企业的生产活动是一个涉及面广而复杂的体系,要使该体系顺畅运作,计划部门需要与销售、研发、生技和资材等相关职能部门合作,经过系统的生产日程计划和安排,为各部门的生产提供依据,确保全面、有序且高效地运作。
(1)生产流程的衔接。
同一件产品在生产流程的时间安排上需要衔接,以保障半成品的顺畅流动,部门与部门之间需保留1/3或半天的缓冲量,以避免出现衔接不上或堆积太多等问题。任何PAC总是在某个时间点上开始执行并跨越某个时段,它总是在前一个计划的基础上(初态)进行调整和修订,故计划问题实际上是再计划,它必须能够适应和兼容生产系统的初态,它还应该为下一个计划留有余地,这就要求计划具有继承性、可扩展性和兼容性。
(2)操作顺序的安排。
在实际生产环境中,操作顺序十分复杂甚至是动态变化的,因不同的设备有不同的加工时间、加工特性(如新设备与旧设备、通用设备与专用设备等),所以加工操作顺序依赖于设备的选择。一个好的作业计划的各种加工操作顺序有高度的弹性。
(3)作业分配的确定。
依据作业日程计划,将作业分配到每个作业者和设备中,同时指派有关部门或人员准备作业。作业分配一般以指令单形式发放,操作员要与所分配的工作相适应,头道工序需要由判断能力强、稳定性好的人员操作,难度系数高的工序应分配给技能熟练的工作操作者,与主流程结合的工序要安排注意力集中且判断能力强的人员操作,此外,人际关系不和谐的作业人员应尽可能分开工作,缺勤率高的员工应安排做辅助性工作。
(4)短缺和富裕的生产能力调整。
由于生产的一次性、经验性及生产系统中诸多意外扰动事件,企业不可能将所接订单任务和剩余生产能力匹配到十分精确的程度,加上客户不愿妥协于企业生产系统的现状而改变交货期,那么在订单确定的交货期条件下,计划期内的所需设备的生产负荷率不可能恰好等于100%。对负荷率超过100%的设备,可以通过对某些零件进行适当、可行的工艺更改或组织外协来转移部分生产负荷,还可通过组织加班来提高设备的剩余生产能力,从而达到降低设备负荷率的目的;对于所有设备负荷率均较低的情况,可以通过将计划的终止期适当提前和降低计划期内的剩余生产能力等途径,达到提高设备的负荷率的目的。
3.3 PAC的编制方法与柔性调度原则
PAC的编制应根据不同生产类型采用不同的编制方法,企业应建立合理的作业计划,实现均衡生产,完成生产任务,进而实现企业的绩效指标有重要作用。PAC中的排产方法主要有正排法、倒排法、平行排产法以及偏置法和覆盖法等。另外企业还可根据实际生产情况,采用固定周期计划法和投产计划法相结合的方法编制PAC,既可以保证企业生产的连续性和稳定性,又能兼顾计划制定的灵活性[5]。多品种中小批量生产企业的PAC管理受许多方面复杂因素的影响,要编制出满意的PAC,不仅要求及时、准确、完整地收集大量的内外部信息,采用先进的计划方法,还需要结合PAC管理决策人员与专家的知识。
在敏捷化、全球制造的新形势下,车间调度研究面临着许多新问题,迫切需要科学的调度方法和调度机制来解决。虽然企业最终采取的排序方式取决于决策部门的排序目标,但完成这些目标,还取决于设备、工艺以及人员的柔性,而获得这种柔性,与作业方法改善、设施规划、缩短作业交货期、制造单元技术和群组技术等相关。因此,柔性车间调度需要注意以下原则:
(1)创建时间原则,即按订单创建时间来排序,其优点是操作简单,缺点在于忽视了数量不同所需的加工时间也不同,同时还忽视了生产的均衡性;
(2)处理时间原则,即优先处理加工时间最短的订单,优点是能有效降低订单的平均等待时间,缺点是忽略了交货时间和设备的利用率;
(3)交货期原则,根据订单的截止期限来排序,即优先执行到期时间最早的订单,此原则表面看可以尽可能地满足交货期限,但实质上忽视了产品之间加工难易程度及所需加工时间;
(4)剩余时间原则,即优先选择剩余处理时间最短的订单来执行,该原则虽提高了系统的整体性能,但可能导致单个订单的执行被延误。
由此,我们可以得出PAC工序的柔性调度规则如表1所示:
由表1调度优化规则,综合某几个调度指标加以平衡,现优化归纳如下:
(1)剩余能力量最大的瓶颈设备先安排;
(2)当瓶颈设备正在加工的负荷量相同时,交货期早的工件优先安排;
(3)当瓶颈设备正在加工的负荷量、工件交货期均相同时,优先安排剩余加工时间最长的工件;
(4)当瓶颈设备正在加工的负荷量、工件交货期、工件剩余加工时间均相同时,优先安排剩余工序数最多的工件;
(5)当瓶颈设备正在加工的负荷量、工件交货期、工件剩余加工时间和工件剩余工序数均相同时,优先安排瓶颈工件;
(6)将等待加工的n个工件,按交货期从小到大排列;交货期相同的工件,按工件剩余加工时间从大到小排列;剩余加工时间相同的工件,按工件剩余工序数从多到少排列;剩余工序数相同的工件,按将要安排的工序的加工时间从大到小的次序排列[6,7]。
4 PAC的评价指标
制造业是一个微观的经济系统,除了以宏观经济系统作为自己的依存环境,还需在产、供、销、储、运等方面搞好内部与外部的协调和配合,才能保证企业的生存和发展,获得良好的经济效益和社会效益。因此,必须用科学的决策手段来制定科学的PAC以保证企业未来的生产经营活动正常、均衡、连续地生产。由于生产过程与生产环境的动态性、生产领域知识的多样性和车间调度影响因素的复杂性,计划人员必须将制造人员、制造资源、约束条件、数学方法、信息技术、生产规模和车间调度方法综合考虑,对车间调度结果进行定量分析与评价,然后根据定量评价结果反过来指导车间调度。
PAC评价的目的是为了判断计划的优劣。但在评价过程中由于评价指标不唯一将带来一系列问题,这些问题可以通过建立“计划围着合同转,生产围着计划转”的体系,以及计划调度对车间领导负责,车间调度对计划调度负责,班组长对车间调度负责,工人对班组长负责的生产控制体系,使各种关系明确,从而为PAC评价的执行提供有力保障。
PAC和车间调度性能目标大致可以归结为3大类:(1)最大能力指标,包括最大生产率、最短生产周期等;(2)生产成本指标,包括最大利润、最小化运行费用、最小投资、库存最小、最大收益等;(3)客户满意度指标,包括最短延迟时间,最小提前或者最小拖后时间等。快速准时的交货要求已影响了这些目标的权重,更加强调交货期、产销率和低库存。PAC指标体系如表2所示。
车间作业调度问题 篇5
生产调度是在一定的时间内,进行可用资源的分配和生产任务的排序,以满足某些指定的性能指标[1]。设备作为重要的生产资源,其可靠性是生产调度方案得以执行的重要保证。为了保障设备持续可用,需要对设备进行必要的计划性维修,如实施预防性维修或基于设备状态的维修策略等。通常在进行生产调度时,往往理想化地假设设备在调度时段内不发生故障,往往导致实际生产过程中设备发生故障或者进行计划性维修时调度难以执行。因此,需要将生产调度和机器设备的维修策略综合考虑,以获得有效可行的生产调度方案[2]。近年来,国内外学者对此问题进行了广泛研究。
金玉兰等[3]假设设备故障服从威布尔分布,维修策略为预防性维修加小修。建立了单台机器车间预防性维修计划和生产调度的多目标联合优化模型,降低了设备故障对生产成本和生产时间的影响。C.Richard Cassady[4]等提出了一个单台机器车间集成预防性维修和单机调度的模型,以工件的最小总加权完工时间为目标,运用全枚举的方法对生产和维修进行集成优化。A.Berrichi等[2]引入可靠性模型指导机器维修,建立了并行机器车间生产与维修集成调度模型。C.S.Wong等[5]假设机器服从最大维修役龄,引入执行预防性维修的时间惩罚和机器的开机准备时间,对塑料生产车间多资源和预防性维修的集成调度问题进行研究。E.Moradi等[6]采用固定周期维修融合“理性策略”的维修方式,引入设备的可用性衡量设备的运行状况,研究了柔性作业车间调度和预防性维修集成调度问题。周炳海等[7]针对流水车间生产与预防性维修集成调度问题,研究了机器最大可利用率目标下预防性维修周期模型,提出了集成启发式的调度算法。Shijin Wan等[8]假设机器故障服从指数分布,维修策略采用固定周期维修策略,对两阶段的混合流水车间生产与维修的集成调度问题展开研究。Hamid Allaoui等[9]假设每台机器在调度时间内有一个不可用的时间段,设计了分支定界算法解决两阶段混合流水车间生产与维修集成调度问题。
以上学者在研究生产与维修的集成调度问题时,主要引入可靠性模型来衡量设备的运行状况,设备加工工件后可靠性降低,经过预防性维修后设备可以恢复如初;维修策略通常为固定周期维修策略或者预防性维修与最小化维修综合考虑的策略。然而,很少考虑机器服役时间对预防维修时长的影响,不能保证预防维修策略的有效执行,容易对生产计划造成影响。
本文引入机器役龄(即执行预防维修前机器的累计作业时间)来衡量设备运行状况,采用基于机器役龄约束的维修策略,同时考虑机器不同役龄下的维修概率和时间,建立基于最大化机器役龄和最小化完工时间的作业与维修计划集成调度模型,并设计了模型求解算法,完成了算例验证。
1 问题描述
本文研究的机器役龄约束的车间作业与维修计划集成调度问题描述如下:给定待加工工件和机器设备,每个工件包括多道工序,每道工序需要在一台给定的机器按照一定的工时定额进行不间断地加工;每台机器在执行预防维修前都可以连续进行加工,采用最大化机器役龄的维修策略保证设备的可靠性。考虑机器工况随着役龄的增长不断退化,致使机器发生故障的概率不断增大,而且故障发生后维修难度增加,同时需要的维修时间也变长。当机器役龄达到某个水平时,机器工况急剧下降必须进行预防维修,如图1所示。本文根据机器的运行参数和历史故障数据设置其最大役龄,即机器需要执行预防性维修前的最大累积运行时间,并且假定执行预防维修后,机器工作能力可以恢复到初始状态,即该机器最大役龄不变。
根据预防维修策略控制的难易程度,图1中设置了两种预防性维修时长与机器役龄之间的函数关系:函数F1表示预防性维修时长与机器役龄之间为三变量分段函数关系,函数F2表示预防性维修时长与机器役龄之间为二次函数关系。在机器役龄早期执行预防性维修,即在远离最大役龄执行维修时,机器的生产能力没有得到充分发挥,增加了维修成本,容易对订单交货期造成延误;如果在机器役龄晚期执行预防性维修,机器的潜在故障已经不断累积,所需维修时间较长,不利于尽快恢复生产。因此,为了避免过早或者过晚执行维修,本文提出了一种作业计划与维修计划集成调度优化模型,采用维修概率与维修时长控制策略,在机器最大役龄约束下,获取最佳的维修时机和时间。
2 模型建立
为了建立机器最大役龄约束的车间生产作业与维修计划的集成调度模型,引入以下符号:
N表示工件数;
K表示机床数;
Ji表示工件i的工序数;
Rk表示机床k的维修次数;
qi,j表示工件i的第j道工序,i=1,2,…,N;j=1,2,…,Ji;
Si,j,k表示工序qi,j在机床k上的开工时间,k=1,2,…,K;
ti,j,k表示工序qi,j在机床k上的加工时间;
Ei,j,k表示工序qi,j在机床k上的完工时间;
Qi,j,k表示工序qi,j在机床k上加工的决策变量:
Wk表示对机床k执行预防维修的决策变量:
∂k表示机床k计划期内的累计工作时间;
∂kM表示机床k的最大役龄,当时,机床必须进行预防维修,维修后∂k=0;
表示机床k工作后如果发生故障需要的维修时间,且该维修是计划期内第mk次维修,mk=0,1,2,…,Rk;
f(∂k)为机床k发生故障的概率密度函数,其概率密度符合正态分布,即:
φ(∂k)表示机床k在累计工作∂k时间后发生故障的概率,则:
Random为随机数Random∈[0,1]。
在集成调度模型中,考虑作业调度的基本优化目标(O1),即最小化最大完工时间,确保生产任务在最短时间内完成;同时要求机床维修时间最短(O2),避免对加工任务造成延误,降低维修成本。故针对文中讨论的问题,建立如下优化目标函数:
其中:
或:
式(3)、式(4)是根据不同的维修控制策略定义的维修时长与机器役龄之间为关系函数,其式(4)中的常数从生产实践中的长期数据统计分析中获得。
模型求解约束如下:
其中,式(6)为工序加工顺序约束,同时保障同一工件的不同工序不能同时加工;式(7)表示任意工序只能在一台机床上加工;式(8)表示每台机床同一时刻只能加工一个工件的一道工序;式(9)表示机器k的累计作业时间不能大于该机床的最大役龄;式(10)表示在满足一定概率条件下对机床k执行预防维修策略。
3 算法求解
以完工时间最小为目标的多工序多机床作业调度问题被公认为是N-P难题。Sun等证明将机器的周期性维修机制纳入调度问题时,仍是N-P难题[10],当维修计划和生产任务被集成调度时,该问题是强N-P难题。本文研究的车间作业与机器维修集成调度问题,不但需要将工件分配给各个机器,同时还需要决定每台机器执行预防性维修任务的最佳时间。因此,需要引入一个有效的算法来解决这个复杂的问题。
由于遗传算法具有显著的并行性和强大的全局寻优能力,适合解决复杂的非结构化问题,被广泛应用于作业车间调度问题的研究。因此,本文引入遗传算法来求解车间作业与机器维修的集成调度问题。该算法的编码解码、交叉变异及精英保留策略的设计如下。
3.1 编码与解码
编码方式直接决定遗传算法的搜索效率。为了便于执行遗传操作,本文采用一种自然数编码方式,染色体长度为,染色体上的基因代表任一工件i,工件i在染色体中出现的次序j对应于该工件的工序qi,j及其加工顺序。因此,生成初始方案时生成随机数i∈,1[N],并满足i在染色体中的出现次数为Ji。
解码时,按照基因顺序确定工件加工工序及在给定机床上的开工时间和完工时间。随后判断工件占用机床的累积工作时间,根据式(10)决策是否执行预防维修,如需维修则根据式(3)或式(4)计算机床维修时间,确定该机床维修的起止时间。
3.2 交叉算子
采用线性顺序的交叉算子,产生新的个体,任取两条染色体,随机生成两个交叉点;截取原染色体中交叉点之间的部分,分别复制给两条新的染色体;排除原染色体中与另一染色体截取部分相同的基因;然后与该截取部分进行基因合并,从而获得两条新染色体。以3工件的交叉运算为例,算法处理原理如图2所示。
3.3 变异算子
变异算子可以使群体进化过程中丢失的个性化基因信息得以恢复,以保持群体中的个体差异性,防止发生成熟前收敛。本文采用倒位变异,任选一条染色体,随机生成两个变异点,然后交换两个变异点对应的编码,即可得到一条新染色体。
3.4 精英保留策略
为了避免丢失种群在迭代的过程中产生的最优解,本文采用了精英保留策略,实施精英保留策略是群体收敛到最优解的一种基本保障。每一代产生的最优解直接复制到交配池,实施交叉与变异。每一代保留的精英个体是根据当前种群的最优解动态更新的。精英保留策略有两个目标:保留每一代种群产生的最优个体;通过将最优解直接复制到交配池,提高了种群的繁殖能力。
4 算例研究
实验算例中有6种工件、4台机器,每种工件有4道工序,工件的4道工序需要分别在4台机器上加工,每种工件只有一件需要加工,工件各道工序的加工时间均匀分布在[1,50]min。工件工序以及对应的加工时间如表1所示。
设4台机器的最大役龄均为80min,考虑机床故障概率与工作运行时间的关系,设维修时长与机器役龄为二次函数关系:
引入基于固定周期维修策略的调度算法作为对比,设定机器每隔80min执行一次预防性维修。
求解算法采用MATLAB编写,设置种群规模为20,迭代代数为800。两种预防性维修策略下的调度结果如表2所示,调度结果分别如图3、图4所示。
相对于固定周期维修策略,采用预防性维修时长与机器役龄成二次函数关系的最大役龄约束维修策略,在保障机床可靠性的同时,可以有效缩短最大完工时间,减少时间约为8.5%。
结果表明,由于固定周期维修策略容易导致生产与维修相互影响和冲突,机器可能会出现长时间处于闲置状态的情况,导致机器的利用率较低。基于机器最大役龄约束的维修策略相对而言,机器执行预防性维修的时间具有一定的灵活性,在维修时机和时长上做到了平衡,机器的利用率得到了提升,维修对生产的影响也有所降低。
5 结束语
设备的可靠运转是保证生产调度得以有效执行的前提条件,为了保障设备的可靠运转,本文考虑机器累计运行时间对设备运行状况的影响,引入基于机器最大维修役龄的预防性维修策略,建立生产与维修的集成调度模型,并设计带精英保留策略的遗传算法,以实例验证了该问题数学模型的正确性和求解算法的有效性。实验结果表明,将生产与维修集成考虑的调度方案相比传统的固定周期维修策略的调度方案,符合设备故障发生规律和设备可靠性要求,能够有效减少生产任务安排与设备维修的时间冲突,将维修更好融入生产过程中,可以进一步提高设备的利用率,减少时间浪费。
摘要：生产过程中作业计划与设备维修计划经常存在着利益冲突,容易造成生产资源闲置和时间成本增加,然而设备的可靠运转是生产作业计划有效执行的重要保障,需要通过定期维修和检测来保证设备的可靠性。据此本文引入基于机器维修役龄的预防性维修策略,将车间作业调度问题和机器预防维修问题进行集成考虑,分析机器累计运行时间对机器预防维修时间及运行状况的影响;以故障概率函数作为实施预防维修策略的控制因子,建立了生产计划与机器维修集成调度模型;并设计了遗传算法进行模型求解,给出了基因编码、交叉变异及精英保留方法;算例结果表明,该方法能够有效减少生产任务安排与设备维修的时间冲突,缩短生产周期,减少时间浪费。
关键词：机器役龄,集成调度,预防性维修
参考文献
[1]黄英杰.基于目标级联法和智能优化算法的车间调度问题研究[D].华南理工大学,2012.
[2]A.Berrichi,F.Yalaoui,L.Amodeo,et al.Bi-Objective Ant Colony Optimization approach to optimize production and maintenance scheduling[J].Computers&Operations Research,2010,37(9):1584-1596.
[3]金玉兰,蒋祖华.预防性维修计划和生产调度的多目标优化[J].哈尔滨工程大学学报,2011,32(9):1205-1209.
[4]C.R.Cassady,E.Kutanoglu.Integrating preventive maintenance planning and production scheduling for a single machine[J].Reliability,IEEE Transactions on,2005,54(2):304-309.
[5]CS Wong,Felix TS Chan,SH Chung.Decision-making on multimould maintenance in production scheduling[J].International Journal of Production Research,2014,52(19):5640-5655.
[6]E.Moradi,S.M.T.Fatemi Ghomi,M.Zandieh.Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem[J].Expert Systems with Applications,2011,38(6):7169-7178.
[7]周炳海,蒋舒宇,王世进,等.集成生产与预防性维护的流水线车间调度算法[J].大连海事大学学报,2007,33(3):32-35.
[8]Shijin Wang,Ming Liu.Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method[J].International Journal of Production Research,2014,52(5):1495-1508.
[9]Hamid Allaoui,Abdelhakim Artiba.Scheduling two-stage hybrid flow shop with availability constraints[J].Computers&Operations Research,2006,33(5):1399-1419.
车间作业调度问题 篇6
关键词：车间作业调度问题,蚁群算法,启发式规则
0引言
车间作业调度问题JSSP (Job Shop Scheduling Problem) 是按一定的时间顺序要求分配资源来完成任务的问题。JSSP是一类复杂且极具代表性的生产调度问题, 它具有约束松弛度紧、约束内联度高和NP-hard等特性。一直以来, 人们普遍尝试采用各种方法来求解JSSP, 如:遗传算法[1]、禁忌搜索[2]、蚁群算法[3]、演化算法[4]和模拟退火[5]等。采用单个方法的调度结果似乎不甚理想, 因而各国学者普遍采用混合方法来求解JSSP问题。这里的“混合”包括两层含义: (1) 将启发式规则融入到现有的求解方法中; (2) 两种或多种方法的有效集成。鉴于此, 本文提出了一种基于启发式规则和蚁群算法的车间作业调度方法。该方法将启发式规则有效地融入到蚁群算法中, 使得该混合方法的优化效率得到极大的改进。
1本文的混合方法
为了有效地求解JSSP, 本文提出了一种基于启发式规则和蚁群算法的混合调度方法。该方法首先采用蚁群算法得到车间作业调度问题的一组可行解, 然后采用一些启发式规则进一步优化这些可行解。该混合方法的计算流程如图1所示。
1.1状态转移规则
在t次迭代时, 蚂蚁k选择工序j的概率公式为:
这里, allowedk表示蚂蚁k在当前位置 (当前时刻的给定机器) 可加工工序的集合;
1.2信息素局部更新规则
信息素是蚂蚁找寻路径的依据, 信息素越多, 找到该路径的概率越大。在JSSP问题中, 排在前面的工序都是优先加工的。为了保障前面工序的优先性, 本文通过公式 (2) 来进行信息素的更新。通过公式 (2) 不难发现对于那些排在前面加工的工序, 蚁群算法给它们追加更多的信息素;使得在构造后续可行方案时, 这些工序能优先加工。同时, 对于那些排在后面加工的工序, 蚁群算法给它们追加较少的信息素;使得在构造后续可行方案时, 这些工序不能被优先加工。通过对信息素局部更新规则的执行, 可以尽可能地保留本次迭代最优解的工序加工顺序。
Δτj=1-log2h/log2H (2)
这里的h表示在第t次迭代的最优可行方案中, 工序j在给定机器上的加工次序, H表示所有任务的最大工序数。
当所有蚂蚁完成当前可行解的构造后, 蚁群算法将按照信息素局部更新规则来改变所有工序上的信息素水平。
τj (t+1) =τj (t) +Δτj (3)
1.3信息素全局更新规则
在蚁群算法中, 为了增加当前最优解被访问的机会, 用公式 (4) 来加大当前最优可行方案的信息素水平 (通过试验发现倍数取3比较合适) 。因此给出信息素全局更新规则如下:在某次迭代中, 如果当前最优可行方案被改进, 蚁群算法将应用公式 (4) 所示的信息素全局更新规则来更新当前最优可行方案上的信息素水平。
Δτj=3 (1-log2h/log2H) (4)
τj (t+1) =τj (t) +Δτj (5)
这里的hh表示在当前最优可行方案中, 工序j在给定机器上的加工次序, HH表示所有任务的最大工序数。
1.4信息素衰退规则
在每次迭代后, 所有工序上的信息素都会发生一定程度的衰减。为了防止算法陷于停滞状态, 蚁群算法将每个工序上的信息素都控制在范围[τmin, τmax]内。
(6)
这里ρ (0<ρ<1) 表示信息素衰减因子。
1.5启发式规则1—关键工序优先
启发式规则“关键工序优先”的主导思想:调整当前可行方案中关键工序 (关键路径上的工序) 的加工顺序, 改进当前可行方案的质量。选择条件:当前方案中存在关键工序, 即此工序是其他工序的前提或对整个工序有重要影响。在实施本规则时, 可考虑按照以下优先顺序改进当前的可行解: (1) 优先安排当前可行方案中的关键工序; (2) 优先安排当前可行方案中原先安排的工序; (3) 优先安排加工时间最短的工序。
1.6启发式规则2—剩余加工时间最长的任务优先
启发式规则“剩余加工时间最长的任务优先”的主导思想:调整当前可行方案中剩余加工时间最长任务的工序的加工顺序, 改进当前可行方案的质量。选择条件:当前方案中存在剩余加工时间最长的任务工序, 即对此工序进行改进可大大提高整个工序方案质量。在实施本规则时, 可考虑按照以下优先顺序改造当前的可行解: (1) 优先安排当前方案中剩余加工时间最长任务的工序; (2) 优先安排当前可行方案中原先安排的工序; (3) 优先安排加工时间最短的工序。
1.7启发式规则3—剩余加工时间最长的机器优先
启发式规则“剩余加工时间最长的机器优先”的主导思想:调整当前可行方案中剩余加工时间最长机器的工序的加工顺序, 改进当前可行方案的质量。选择条件:当前方案中存在剩余加工时间最长机器的工序, 即对此机器工序进行改进可大大提高整个工序方案质量。在实施本规则时, 可考虑按照以下优先顺序改造当前的可行解: (1) 优先安排当前方案中剩余加工时间最长机器的工序; (2) 优先安排当前可行方案中原先安排的工序; (3) 优先安排加工时间最短的工序。
2仿真实例
为了验证本方法的有效性, 我们采用8个不同规模的JSSP标准实例 (见表1) 来验证4种不同的实验方案 (蚁群算法、基于规则1的蚁群算法、基于规则2的蚁群算法和基于规则3的蚁群算法) 。本文所有算法均采用Matlab语言实现, 在内存为256M、CPU为Intel 2.4G的PC中运行。笔者应用每种方案求解每个实例各10次, 取其均值作为最终优化结果。本文蚁群算法中的参数设置如下:α=2、β=3、ρ=0.02、τmax =50、τmin=1、τj (0) =10。算法终止条件为: (1) 当前最优解连续30代内没有被改进; (2) 当前最优解和已知最优解的误差小于0.005; (3) 达到最大迭代次数=max (200, 2倍工序数) 。采用4种实验方案求解8个测试实例的优化结果如表2所示。实验结果表明:将调度规则融入到蚁群算法中, 并不增加混合蚁群算法的总体优化时间;相反, 知识型蚁群算法的优化时间比标准蚁群算法在一定程度上要少。总的来讲, 无论是优化结果还是优化时间, 本文提出的混合蚁群算法都明显优于标准蚁群算法。
3结论
本文的主要创新点:提出了一种基于启发式规则和蚁群算法的车间作业调度方法。该方法将启发式规则有效地融入到蚁群算法中, 使得该混合方法的优化效率得到极大的改进。仿真实例表明, 该方法是可行的、正确的和有效的。
参考文献
[1] GoncalvesJ F, Magalhaes Mendes J J De, Re-Sende M G C.A hybrid genetic algorithm for the job shop scheduling problem [J].European Journal of Operational Research, 2005, 167:77-95.
[2]Pezzella F, Merelli E.A taboo search method guided by shifting bottle-neck for the job shop scheduling problem[J].European Journal of Op-erational Research, 2000, 120:297-310.
[3]Huang K L, Liao C J.Ant colony optimization combined with taboosearch for the job shop scheduling problem[J].Computers and Opera-tions Research, 2007:Article in Press.
[4] Tanev I T, Uozumi T, Morotome Y.Hybrid evolutionary algorithm-based real-world flexible job shop scheduling problem: application service provider approach [J].Applied Soft Computing, 2004, 5:87-100.
车间作业调度问题 篇7
关键词：生产调度,混合流水车间,逆序变换,等价性
0引言
混合流水车间(Hybrid Flow Shop, HFS)调度问题是在流水车间(Flow Shop, FS)调度问题的基础上发展起来的,其特点是所有阶段或部分阶段上存在并行设备。常规HFS调度问题可以描述为n个工件要在s个阶段的流水车间上加工,其中阶段k具有M(k)个同速平行机、且至少有一个阶段存在两台以上的平行机,在满足一系列基本假设和约束条件的基础上去寻找一个调度解使得最大完工时间(makespan)最小。虽然不同的HFS问题不能完全满足常规问题的所有假设和约束,但是也只是在设备加工环境、加工约束和特征、优化准则等方面存在较小的差异。常规HFS问题作为HFS调度问题的 “模板”,其研究成果可以为更加复杂的实际调度问题研究提供基础,受到了学术界和产业界的广泛关注。
由于常规HFS调度问题的NP难特性[1],精确算法[2,3]只能求解很小规模的问题。对于近似求解方法来说,启发式算法[4,5]求解快速,然而其求解质量还有较大的改进空间;元启发式算法[6～10]求解质量较高,通常需要更多的计算资源,难以应用于大规模或者实时性要求高的问题。从已有研究来看,现有的调度算法在求解质量、 求解效率方面仍存在一定的不足,其主要原因在于算法设计的理论基础不够完善,现有的调度算法尚未很好地融入领域知识(domain knowledge)。此外,文献[7]试图通过反例来说明常规HFS问题不具备加工可逆性:对于一个给定的工件排列次序(初始阶段),采用正序、 逆序调度方法可以获得不同的makespan值;然而在给定工件排列次序的情况下,可以生成不同的工件设备指派方案,进而可以得到一系列不同的调度解,该结论并不严谨。因此,本文进一步对常规HFS调度问题的本质特征展开研究,首先通过逆序变换定义了常规HFS调度问题的逆序问题,然后从数学角度证明了两者之间的等价关系,最后给出了一种基于逆序变换进行问题求解的方法,旨在为后续的研究提供理论依据。
1数学模型
1.1符号定义
为了叙述方便,引入下列符号:
J为待加工的工件集合, J ={1,, n};
j为工件编号, j ∈J ;
k为阶段编号, k ∈{1,, s};
m为设备编号;
M(k)为阶段k上的平行机数;
(j,k)为工件j在第k个阶段的操作;
pjk为工件j在阶段k的加工时间;
tjk,cjk为工件j在阶段k的开工时间、完工时间;
Nkm为阶段k上的设备m所加工的操作集合;
Ωk为阶段k上的工件设备指派方案集合,集合的元素满足以下两个条件:
Ω为Ω=Ω1×Ω2×...× Ωs为可行的工件设备指派方案集合,其元素记为ω;
kmπ为为阶段k上的设备m所加工的工件有序集(其中);
π为表示工件的加工顺序方案,其中
Π 为对于给定的工件设备指派方案ω,可行的工件加工顺序方案集合;
S为可行调度解,其集合记为Ψ,不妨记其最大完工时间记为Cmax(S)。
1.2析取图模型
对于给定的工件设备指派方案ω,常规HFS调度问题可以用赋权析取图G =(N, A,E,w) 来表示: N ={0,*, ( j, k) | j, k}是节点集,其中节点(j,k)表示工件j在第k个阶段的操作,而“0”与“*”分别表示整个加工开始的起点和代表全部加工结束的终点;A是合取弧的集合,反映了同一工件的不同操作之间的先后关系,用单向实线来表示;E是析取弧的集合,反映了同一设备上不同工件之间的加工先后关系,同一阶段的任意两个工件之间用双向虚线来连接; w是有向图的权重,其中节点(j,k)的权重为pjk,而节点“0”、“*”和所有弧的权重都为0。
在上述描述中,调度的过程就是将双向箭头用单向箭头代替进而得到E′,使G成为一个无回路的单向图G(N, A, E′, w) ,亦即确定了一个可行的工件加工顺序方案π,该图可以简记为;在满足时序约束、资源约束等的基础上,确定工件的开工时间,进而生成一个可行调度解S。例如,对于一个7个工件3个阶段的常规HFS调度问题,各阶段上的平行机数分别为2、2、3; 已知工件的加工顺序方案 π ,其中 π1 1= ( 1 , 2 , 3 ) ,π1 2= ( 4 , 5 , 6 , 7 ) , π2 1= ( 4 , 6 , 1 , 2 , 3 ) , π2 2= ( 5 , 7 ) ,π31=(6,4,3,2), π32=(1,5), π33=(7),那么对应的如图1所示。由于G(N, A,E′,w)的关键路径长度就是对应工件加工顺序方案 π的最优makespan值,因此在所有的G(N, A, E′, w)中寻找一个具有最小关键路径的无回路单向图就是常规HFS调度问题,即
对于给定的无回路单向图G(N, A,E′,w)亦即确定了工件的加工顺序方案π,根据文献[6]给出的工件完工时间计算公式,可以通过以下递推公式来计算工件的最优开工时间:
其中pj0=0,tj0=0 ( j) ;p0k=0 ,t0k=0 (k )。这样就得到了一个完整的调度解,不妨记为S*,其makespan值为:
2等价逆序变换
定义1:对于一个给定的具有n个工件的常规HFS调度问题,如果另外一个常规HFS问题满足以下两个条件:
其中M(k)和( k)分别表示它们的第k个阶段的平行机数, pjk和jk分别表示工件j在上述两个HFS的第k个阶段的加工时间,那么这两个调度问题分别称为原问题和逆序问题(reverse problem),而通过式(3)、式(4)将原问题转换为逆序问题的过程则称为逆序变换。
对于任意的常规HFS调度问题(原问题),可以根据定义1的逆序变换得到相应的逆序问题。为了证明逆序变换的等价性,下面给出了优化问题的等价性定义。
定义2:如果两个优化问题满足:1)存在一个问题的可行解集合到另外一个问题的可行解集合的映射(不一定是“一对一”的情形);2)任意一个可行解及其 “像”具有相同的目标函数值;那么这两个优化问题是等价的。
引理1:对于原问题的任意一个可行调度解S,记其工件加工顺序方案为 π,那么至少存在逆序问题的一个 s可行调度解,其工件加工顺序方案构造如下:阶段s -k +1上的设备m所加工的 工件有序 集为且这两个调度解具有相同的makespan值。
证明:对于原问题的任意一个可行调度解S,亦即确定了一个无回路单向图G(π),且调度解的makespan值Cmax(S)大于或等于G(π)的关键路径长度。下面,分两种情况进行讨论:
1)如果该调度解的makespan值Cmax(S)等于G(π)的关键路径长度,与文献[11]中的证明方法类似。对于逆序问题的工件加工顺序方案根据递推公式(1)可以计算工件的最优开工时间进而生成一个完整的调度解,其makespan值等于对应有向图的关键路径长度。根据逆序问题的定义及的构成方式,有向图相当于将G(π)中所有弧的箭头反向(逆图),由于此种反向不会改变起点至终点之间的关键路径长度,因此这两个调度解具有相同的makespan值。
2)如果该调度解的makespan值Cmax(S)大于G(π)的关键路径长度,可以给出一种逆序问题调度解的构造方法:首先,对于逆序问题的工件加工顺序方案根据递推公式(1)计算工件的开工时间jk,并记其最后阶段s上完工时间最迟的工件为j';然后,令根据此种方法得到的可行调度解与原问题的可行调度解之间具有相同的makespan值。
综上所述,引理得证。
定理1:原问题及其逆序问题是等价的。
证明:1)令原问题及其逆序问题的可行解集合分别为A、B,现在构造一个从集合A到集合B的映射:
对于任意一个可行调度解S ∈A,记其makespan值为Cmax(S),其工件加工顺序方案为 π 。由引理1的证明过程,我们知道在集合B中都存在唯一的可行调度解与之对应,其工件加工顺序方案工件的开工时间根据递推公式(1)进行计算,并令其最后阶段s上完工时间最迟的工件j'的开工时间为
2 )对于 ∀S ∈A , 其 “ 像 ” 的m ake spa n值为
由定义2,定理得证。
定理2:对于一个可行调度解S,根据引理1构造其“像”,若这两个调度解的makespan值等于对应无回路单向图G(π)的关键路径长度,那么对于G(π)上的任意节点(j,k),满足:
并且当节点(j,k)在关键路径上的时候,等号成立。
s证明:1)明显,为从起点“0”到终点“*”之间的一条路径的长度。由于Cmax(S)等于图中最长路径的长度,因此有
2 )当节点( j , k ) 在关键路径上时,如果我们假定那么在节点(j,k)到节点“*”之间必定有一条 路径 , 它的长度 为满足
由公式(1)的定义可知,代表从“*”到(j,k)之间最长的 路径 , 因此进而 , 我们有这与假定矛盾,因此,等号成立。
由上述两点,定理得证。
定理3:对称定理:逆序问题的逆序是原问题。
3逆序调度方法
由于常规混合流水车间调度问题及其逆序问题的等价性,可以通过原问题的任意调度算法来求解逆序问题,然后经过解的转化来获得原问题的调度解。下面给出此种逆序调度方法的求解框架:
Step1:逆序变换。对于给定的常规HFS调度问题, 根据式(3)、式(4)可以确定逆序问题的相关参数(各阶段的平行机数和加工时间)。
Step2:利用原调度算法求解逆序问题。
Step3:将求得的逆序调度解“映射”回原来的解空间,得到原问题的调度解。即根据引理1,由逆序调度解的加工顺序方案可以得到原问题的一个加工顺序方案π ,然后根据公式(1)来确定工件的开工时间tjk,进而获得原问题的完整调度解。
下面,以启发式算法求解一个10个工件5个阶段的算例j10c5a5[2]为例来进行说明。文献[4]通过仿真实验说明了采用第2种设备指派规则的NEH算法取得了最好的效果,不妨记此种算法为NF,相应的逆序调度算法记为NB。对于该算例,NF算法在步骤1求得工件加工优先级顺序job Order=[5 9 3 8 10 1 2 6 7 4],进一步通过设备指派生成完整的调度解并得到Cmax=126;而通过NB算法求得等价逆序问题的job Order= [4 9 3 8 10 7 6 2 1 5], Cmax=122,并将求得的逆序调度解“映射”回原来的解空间可以得到原问题的解,恰好该调度解为最优解。
4仿真实验
以Carlier和Néron提出的77个Benchmark算例[2]作为测试数据,并根据求解难度将其分成两组:53个易解算例、24个难解算例[3]。本文的算法采用MATLAB语言编写,运行环境为Win8.1、i3-4130(3.40G)/4G的台式机。 为了评价算法的有效性,采用以下3种指标:百分比偏差PD,运行时间CPU,最优比率(求得最优解的算例个数占该算例集算例总数的比率)。
对于这两组算例,分别采用NF、NB以及正逆序相结合的求解算法(记为NFB)独立运行1次,对计算结果进行总结如表1所示。由表1可以看出,NF与NB的平均运行时间非常接近;从平均偏差、最优比率来看, NF优于NB。实际上,由于算例集的规模有限且不具有对称性,不能以此来判断算法的优劣;根据求解结果可以发现,对于不同的算例NF与NB各具优势。与NF、 N B相比,从平均偏差、最优比率这两个指标来看, NFB均有较大幅度的提高。虽然NFB需要付出接近2倍的时间代价才可以获得更好的求解质量,但是其平均运行时间也仅为0.0023s,具有满足实际需求的计算效率。
5结束语
【车间作业调度问题】推荐阅读：
车间调度问题06-02
汽车售后车间作业流程08-23
4S店车间调度员派工基本流程08-11
作业调度07-31
作业调度算法06-23
短作业调度算法06-13
作业车间调度06-10
五金车间现存在的问题08-28
天车与冶炼炉的作业调度05-28
数学作业问题07-20