汽车4维修系统调度问题的协调与优化

汽车4维修系统调度问题的协调与优化

1动态柔性加工车间调度模型及其改进后的再调度2004年，ibm和美国竞争力委员会首次提出了服务科学的概念。在他们的大力支持下，国内外科学家积极响应。郭重庆、国家自然科学基金委员会交通管理部的郭重庆、刘作义教授等在科学研究方面做了笔记。服务系统调度问题属于服务科学研究的范畴。目前,针对汽车4S店维修服务系统调度问题的理论研究还比较少,4S店的车间管理人员通常是结合任务的紧急程度和设备的繁忙状况等因素,依据经验预估任务的完成时间,进行任务的作业排序。这即不利于提高企业资源利用率,也难以满足客户需求。因此,该研究具有理论和现实价值。汽车4S店维修服务系统调度问题的基本形式可以描述为动态柔性加工车间调度问题(FlexibleJobShopSchedulingProblem,FJSP)。FJSP问题是对经典加工车间调度问题(JobShopSchedulingProblem,JSP)的扩展,由于问题的复杂性,目前对此类问题的研究集中在应用启发式算法求解静态问题上。但是汽车4S店维修服务系统存在:任务不确定、无法库存以及任务的作业时窗缺乏柔性等特征,使得其调度更具动态性。再调度是解决动态调度问题的有效方式,众多学者研究了再调度策略及其应用。但是再调度将一个FJSP问题变成多个,进一步增加了问题的求解难度。Goldratt(1984)提出约束理论,简称TOC(theoryofconstraints),指出瓶颈是制约系统朝着目标前进的主要因素,决定了整个系统的性能,通过把管理重点放到瓶颈环节,简化非瓶颈环节,能有效地提升管理效率。目前,已经有学者研究如何将约束理论运用于生产调度和供应链管理等领域,并取得较好的结果。但是,现有研究多针对制造系统,很少有涉及动态的服务系统。本文试图在已有研究的基础上,针对汽车4S店维修服务系统的柔性调度特性进行问题的分解简化,通过缓冲设置与管理协调瓶颈与非瓶颈加工中心,并设计再调度策略实现问题的动态求解。2数量质量描述中,下标j表示任务(j=1,2,…,n,n表示任务的数量);上标i表示工作中心(i=1,2,…,l,l表示工作中心的数量);上标h表示工作中心i中的一台并行异速机(h=1,2,…,mi,mi表示工作中心i中并行异速机的数量)。2.1任务2:每台设备未加工一项任务假设1:每项任务在每个加工中心只选择一台设备加工一次。假设2:任一时刻每台设备只加工一项任务。假设3:每项任务按照预定的工艺路径依次通过各加工中心。假设4:在整个服务系统中只存在一个瓶颈加工中心。假设5:任务在设备开始加工则不允许中断。2.2这个问题的基本描述采用三元组α/β/γ方法,对4S店维修服务系统与制造系统调度问题的共性进行基本描述。2.2.1车辆维修保养汽车4S店维修服务系统中包含多个串行加工中心(包括:机电、钣金、油漆和美容等)。车辆维修保养任务要按照事先预定的加工路线,顺序通过上述加工中心,每个加工中心有多台设备可供选择。整体而言,该系统相当于柔性加工车间,符合FJSP调度模型。2.2.2任务响应约束任务具有提交时间rj、工期dj、权重ωj、作业时间pj和设备能力Mj等约束,具体如下:①时间窗约束完成一辆汽车的维修保养任务,要满足作业提交时间rj和工期dj约束。②准备时间约束sjg准备时间sjg是指设备连续完成任务j和g的过程中需要的整理调试时间,它受任务作业顺序的影响。例如,对车辆进行喷漆,前后车辆颜色相同则准备时间短,否之则准备时间长。③能力约束Mj设备能力约束由任务性质和设备适用性决定,例如车辆擦刮后需要打磨喷漆和烘干,由于受损面积和位置不同,决定了不同任务适用的设备存在差异。2.2.3绩效目标iii域与制造系统的调度目标相类似,汽车维修服务系统设备的调度也要满足制造时间和工作的最终期限等调度目标。2.3问题描述针对汽车4S店维修服务系统与制造系统调度问题的差异,进行汽车4S店维修服务系统调度问题的特性描述。2.3.1薄层加工汽车4S店维修服务系统与一般的FJSP调度模型相比存在明显的瓶颈加工中心。由于汽车4S店维修车间的烤漆房价格贵,任务在该设备上的作业时间长,利用率高,钣喷加工中心成为整个汽车4S店维修服务系统的瓶颈环节。2.3.2作业时窗的柔性汽车4S店维修服务系统中任务的动态性比制造系统更强,具体表现为以下几个方面:①作业时窗缺乏柔性制造系统的库存准备为任务的作业时窗提供了缓冲。而汽车维修服务系统,只有在客户将车辆送至现场,发出工单后,才能开始作业,没有预先的库存准备,因此其作业时窗缺乏柔性。②任务具有实时性由于客户到达时间是实时的,使得任务提交时间不确定,任意时刻都可能出现任务要及时安排,因此工作任务具有实时性,要实行动态调度。2.3.3任务权重的确定使客户满意是服务业经营管理的关键。从时间上讲,就是确保任务的预期完成时间,减小滞后,特别是重要任务的滞后。因此,汽车4S店维修服务系统的调度目标是最小化加权滞后时间和∑ωjTj,式中ωj表示任务的权重,体现了任务j的重要程度;Tj=max(Cj-dj,0),表示任务滞后时间,Cj表示任务j离开系统的实际时间。2.4任务系统约束综上所述,汽车4S店维修服务系统调度问题可设计为存在明显瓶颈,以最小化加权滞后时间和为目标,受多约束限制的动态FJSP问题。其数学模型如下:Μinn∑j=1ωjΤj(1)Min∑j=1nωjTj(1)s.t.Tj=max(dj-Cj,0)(2)Cihjihj-rij≥pihj+sihjg/(i,j)∈N/(3)x1hj≥rj/(i,j)∈N/(4)xkhj-xihj≥pihj+sihjg/(i,j)→(k,j)∈A/(5)xihj-xihg≥pihg+sihjgorxihg-xihj≥pihj+sihjg/i∈L,h∈Mi/(6)xihj≥0/(i,j)∈N/(7)模型中,决策变量xihj表示操作(ih,j)的起始时间;L表示工作中心集合,Mi表示工作中心i中的机器集合;N表示任务集合;Cihj表示任务j在工作中心i中机器h上的完工时间;A为线路约束(i,j)→(k,j)集合,表示任务j在工作中心加工的先后顺序。式(1)为目标函数,式(2)-式(7)为约束条件。其中:式(2)度量了任务j的延迟时间;式(3)保证任务j的所有工序都能够完成;式(4)确保任务j开始作业的时间满足任务提交时间约束;式(5)为操作约束,确保任务j在不同工作中心的加工顺序;式(6)为机器约束,保证在同一台机器上加工的不同任务之间存在先后排序;式(7)保证每道加工工序的时间大于0。3非瓶颈加工中心优化调度流程约束理论将优化的重点聚焦到瓶颈环节,首先松弛非瓶颈加工中心的能力约束,调度最难安排的瓶颈设备,接着安排非瓶颈设备,然后协调各子问题,以获得可行调度。3.1分解、简化和建模3.1.1加工中心、瓶颈后加工中心的加工以瓶颈为核心,在瓶颈加工中心前后设置缓冲能确保瓶颈环节任务的连续性和及时性,据此汽车4S店维修服务系统调度问题可分解为:瓶颈前(机电、钣金)加工中心、瓶颈(钣喷)加工中心和瓶颈后(洗车、美容)加工中心三个部分。如图1所示:图中:pbbj=b-1∑i=1pij+sij表示任务j在瓶颈前各加工中心的作业与准备时间和,TBin表示输入缓冲,rbj表示瓶颈加工中心的提交时间,pbj表示瓶颈加工中心的作业时间,sbj表示瓶颈加工中心的准备时间,dbj表示瓶颈加工中心的工期,TBout表示输出缓冲,pabj=l∑i=b+1pij+sij表示瓶颈后各加工中心的作业与准备时间和。3.1.2非瓶颈加工中心的机器能力约束非瓶颈环节的加工能力无限大,且在瓶颈加工中心前后设置有缓冲,则非瓶颈加工中心的机器能力约束可以松弛。FJSP问题的求解简化为对瓶颈环节并行异速机的求解问题。3.1.3子问题建模动态调度问题根据约束理论,瓶颈决定系统的节奏,最小化任务在整个系统的滞后时间就是最小化任务在瓶颈环节的滞后时间。同时,瓶颈环节存在资源短缺,在调度中要提高资源的利用率。据此,瓶颈加工中心的调度问题可设计为包含最小化的制造期(Cmax)与最小化加权滞后时间和(∑ωjTj)的多目标,受到多约束限制的并行机动态调度问题(Qm|rj|θ1∑wjTj+θ2Cmax)。非瓶颈加工中心的调度问题可设计为带任务提交时间和交货期限制的并行机动态调度问题(Qm|rj|Lmax)。加工中心任务到达时间和工业进展瓶颈加工中心提交时间如式(8),工期如式(9);瓶颈前加工中心任务到达时间如式(10),工期如式(11);瓶颈后加工中心任务到达时间如式(12),工期如式(13)。式中tbj和cbj分别表示瓶颈加工中心调度结果的开始时间和完工时间。rbj=rj+pbbj+TBin(8)dbj=dj-pabj-TBout(9)rbbj=rj(10)dbbj=tbj-TBin(11)rabj=cbj(12)dabj=dj(13)3.2瓶颈不是瓶颈加工中心的协调3.2.1缓冲设计Daniel提出动态缓冲的长度是瓶颈前或瓶颈后作业时间和的倍数。结合经验数据,为确保瓶颈环节加工任务不间断,在瓶颈(钣喷)加工中心前设置输入缓冲(TBin=2Pbbj);为确保瓶颈环节任务及时完成,不拖延工期,在瓶颈(钣喷)加工中心后设置输出缓冲(TBout=Pabj)。3.2.2简单的调度规则预调度以瓶颈(钣喷)加工中心为核心。首先运用动态调度规则获得问题的初始解,接着运用智能搜索算法迭代寻优;非瓶颈加工中心加工能力大于需求,且只需满足提交时间和工期要求,可以运用简单的调度规则快速求解。调度结果中:任务j在瓶颈前(机电、钣金)加工中心实际完工时间用cbbj表示;在瓶颈后(洗车、美容)加工中心的实际开始时间用tabj表示。通过协调上述结果变量可实现汽车4S店维修服务系统的调度。3.2.3缓冲管理应用如果瓶颈前工序不能在期望的完工时间内完成,则可能造成瓶颈和瓶颈前加工中心作业在时间轴上的迭代,使得调度不可行。对于瓶颈后加工中心,rabj=cbj,这使得调度不存在时间轴上的迭代,所以缓冲管理的重点是输入缓冲区。通过在瓶颈与非瓶颈加工中心间的缓冲管理可有效缓解这种时间上的迭代,如图2所示。忽略区,cbbj∈[rj+pbbj,rj+2pbbj],落入此区域的任务在重调度时可忽略,只需将新任务插入其中即可,如果有大量任务落入此区域,可考虑缩短输入缓冲。警示区,cbbj∈[rj+2pbbj,rbj],落入此区域的任务要关注,如果该任务在瓶颈加工中心上的作业开始时间tbj发生变化则需要重新计算其指数,进行重排。冻结区,cbbj∈[rbj,tbj],任务落入此区域则需要冻结其在瓶颈加工中心前的作业时段,确保该任务能按时执行,如果有大量任务落入此区域,则需要延长各任务的工期,并重新设计输入缓冲。重排区,cbbj≥tbj,对落入此区域的任务,需要进行重新调度,调整瓶颈加工中心的到达时间和完工时间,随后根据新的调度结果重新设定非瓶颈加工中心的到达时间和工期。4再规划策略设计设计再调度策略包括重调度时刻的确定和各子问题再调度方法的选择两个方面。4.1局部重调度局部重调度采用基于任务(车辆)的混合策略进行重调度,即在周期性调度的基础上,当特定事件发生时也要引发重调度。如图3所示。横坐标表示任务(车辆)序号,W(l)表示第l个预测窗口,预测窗口内有L(l)个车辆。重调度时刻有两种情况:情况一,周期性重调度,每次执行局部最优调度中的k个车辆,并将完成这k个车辆的时刻作为重调度时刻;情况二,特定事件(包括:紧急车辆到达、车辆延迟、优先权变化等)发生时。滚动窗口内最多有k个车辆,且滚动窗口内的车辆数小于预测窗口内的车辆数,即L(l)>k。4.2车辆集、监控方法对瓶颈加工中心采取完全重调度,即任意重调度时刻t,对未加工的所有车辆集进行调度。对瓶颈前加工中心采取部分重调度,即:仅重调度直接和间接受干扰的任务,具体可用缓冲区管理中的再调度方法。对瓶颈后加工中心采取右移再调度,即推迟车辆的加工直到调度可行,调度顺序保持不变。5测试结果与分析通过现场调研,日常情况下,开业期在2-10年的汽车4S店维修车间每天的任务数量范围为[20,130],其中需要进行油漆工序的任务占总数的20%-30%,可以使用预喷房和烤灯的任务占油漆任务数的30%-50%。瓶颈资源烤漆房的数量范围为,预喷房的数量范围为,烤灯的数量范围为。烤漆房的作业时间pAj在区间中均匀分布,预喷房的作业时间pBj在区间[0.5,1]中均匀分布;各项作业的权重在区间中正态分布;非瓶颈工位上任务的加工时间服从[0.3,1]的均匀分布;任务到达时间rj服从[0,8]的离散均匀分布;为了避免预期完成时间dj设置过松或过紧,令dj=rj+λ∑p,∑p表示任务总的作业时间和,任务在每个工序的作业时间可用任务在该工序不同设备上的平均作业时间表示,λ在区间中均匀分布。本文运用几种调度规则(先到先加工FCFS,最短加工时间先加工SPT,最早交货期限先加工EDD)对所有设备进行完全重调度。并将本文所述算法记作DBR进行仿真比较。以10个任务为滚动窗口,用n×m[D(m1),B(m2)]标志每个组别,其中n表示任务数,m表示油漆设备的数量,D和B分别表示烤漆房和预喷房,括号内的m1,m2表示对应资源的数量,每组产生10个样本。采用以