第十一二章制造服务作业计划与控制

第11章车间作业计划与控制重难点：---作业计划问题的基本概念---流水车间作业计划问题：1、加工周期的计算2、两台机器排序问题的最优算法---生产作业控制层次性：---年度生产计划---零部件投入出产计划---车间生产作业计划（班组、各工作地、各工人的任务）第1节作业计划问题的基本概念１.1作业计划的含义与作用作业计划(Scheduling):是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。Scheduling：编制作业计划或安排日程（时间表）排序(sequencing)：确定零件在机器上的加工顺序作业计划：不仅包括确定零件的加工顺序，还包括加工任务的分配和加工每个零件的开始时间和完成时间；派工(dispatching)：在作业计划制定后，按作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的车床和工人；赶工(expediting)：在实际进度已经落后于计划进度时采取的行动；编制作业计划的目的：满足交货期要求(MeetDueDates)使在制品库存最小使平均流程时间最小(Minimizetheaverageflowtimethroughthesystem)提供准确的工件状态信息提高机器/工人的时间利用率减少调整准备时间(Reducesetuptimes)使生产和人工成本最低1.2作业计划的种类大量生产类型的作业计划成批生产类型的作业计划单件小批生产类型作业计划另外，还有其他分类：车间作业计划(JobFloorscheduling)人力计划(PersonnelScheduling)设施计划(FacilitiesScheduling)车辆调度计划(VehicleScheduling)供应商计划(VendorScheduling)工程项目计划(ProjectScheduling)动态计划和静态计划(DynamicversusStaticScheduling)1.3制定作业计划的影响因素•工件到达的方式•车间内机器的数量•车间拥有的人力资源•工件移动方式•不同调度准则的评价•1.4作业计划与控制的关系•作业计划：给生产活动制定详细时间表•生产控制：以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，保证实现各项各项计划目标。第2节排序的基本概念(Sequencing)2.1排序与编制作业计划的差别上面讲了编制作业计划的问题.在编制作业计划过程中,有一个问题需要管理人员注意,即投入生产过程的作业顺序的安排.·作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。·排序，给出零部件在一台或一组设备上加工的先后顺序的工作。所以,编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪.如果只有16个工件,同样按每秒钟可以检查1billion个顺序计算,也需要2/3年.以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。2.2排序问题的分类•根据机器数的多少：单台机器的排序问题/多台机器的排序问题•根据加工路线的特征：单件车间排序(JobShop)流水型排序(FlowShop)：每个零件都顺序地经过流水线上的不同机器进行加工，即：加工路线一样•根据工件到达系统的情况：静态排序/动态排序•根据参数的性质：确定型排序/随机型排序•根据要实现的目标：单目标排序/多目标排序2.3排序常用的符号Ji----工件i，i=1,2,....ndi----工件i的交货期Pi----工件i的加工时间,,pij----工件i在机器j上的加工时间,j=1,…,mmjijipP1mjijiwW1Wi----工件i在系统内的等待时间,,wij----工件i在机器j前的等待时间,j=1,…,mCi----工件i的完成时间,在工件都已到达的情况下,Ci=Pi+WiFi----工件i的流程时间，在工件都已到达的情况下,Fi=Pi+WiLi----工件i的延误时间,Li=Ci-di,Li=0按期或完成提前；Li0延误Ti----工件i的延期量,Ti=max{0,Li}Ei----工件i提前完成的时间2.4排序问题的表示方法排序问题常用四个符号来描述:n/m/A/Bn-----工件数；m-----机器数；A----车间类型,F：流水作业排序问题P：流水作业排列排序问题G：一般单件作业排序：每一工件都有其独特的加工路线B-----目标函数2.5编制作业计划问题的一些假设：•1、一个零件不能同时在几台不同的机器上加工；•2、零件在加工过程中采取平行移动方式，即当上道工序完工后立即送下道工序加工；•3、不允许中断：一个零件一旦开始加工，必须一直加工到完成，不得中间插入其他零件加工；•4、每道工序只能在一台机器上完成；•5、零件数、机器数和加工时间已知；•6、每台机器同时只能加工一个零件；第3节单台机器的排序问题3.1单台机器排序问题n个工件全部经由一台机器处理J1J2J3Jn机器到达系统工件的集合离开系统（机器）3.2常见单台机器排序问题的目标函数1)平均流程时间最短FnFiin_11为n个零件经由一台机器的平均流程时间。定义:FnFiin_11目标函数MIN:2）最大延期量最小TTimaxmax定义:为最大延期量。目标函数minmaxT根据排序目标的不同，可以选择不同的排序规则，有时又称为确定优先权(Priorities)。常见的优先权规则(Priorityrules)有：SPT---ShortestProcessTime,EDD---EarliestDueDateFCFS---FirstComeFirstServedCR---CriticalRate等,分别用于解决不同的问题。3.3求平均流程时间最短的排序问题•求平均流程时间最短的作业顺序，采用SPT原则。按工件加工时间的长短，按不减的顺序从小到大安排各项作业。•例：一个车间有一台加工中心，现有5个工件需要该机器加工。相关的加工时间和要求完成时间（交货期）如下表所示，求平均流程时间最短的作业顺序。J1J2J3J4J5加工时间11293112交货期6145313332解：根据SPT原则，得出：J4-J5-J1-J2-J3有关项目的计算：发生延迟发生延迟加工时间完成时间交货期延迟J411330J523320J11114610J2294345031743143J3FnFiin_/.1135527013.4求最大延期量最小的排序问题•求最大延期量最小的作业顺序采用EDD原则。EDD(EarliestDueDate):Jobsaresequencedinincreasingorderoftheirduedates.•例：借用上面的例子，求最大延期量最小的作业顺序。解：根据EDD原则，得出：J3-J5-J4-J2-J1加工时间完成时间交货期延迟J33131310J5233321J4134331J229634518J111746113平均延迟=33/5=6.6FnFiin_/.123554701Tmax=18进一步考虑：在最大延期量不变的情况下，如何使平均流程时间缩短？如果想同时满足这两个目标，就是多目标排序。第4节n项任务在两台机器的排序问题4.1两台机器排序问题的含义n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。机器1到达系统工件的集合离开系统（机器）J1J2J3Jn机器24.2两台机器排序问题的目标•两台机器排序的目标是使最大完成时间（总加工周期）Fmax最短。Fmax的含义见如下的甘特图(GanttChart)。•多台机器排序的目标一般也是使最大完成时间（总加工周期）Fmax最短。Fmax时间机器AB在机器A上的作业时间总加工周期4.3两台机器排序问题的算法（重点）实现两台机器排序的最大完成时间Fmax最短的目标，一优化算法就是著名的约翰逊法(Johnson’sLaw)。其具体求解过程如下例所示（或见课本P210例11-2）。约翰逊法解决这种问题分为4个步骤：(1)列出所有工件在两台设备上的作业时间。(2)找出作业时间最小者。(3)如果该最小值是在设备1上，将对应的工件排在前面；如果该最小值是在设备2上，则将对应的工件排在后面。(4)排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)，直到所有工件都安排完毕。例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。工件在两台设备上的加工时间工件编号J1J2J3J4J5设备A36715设备B28643解：由约翰逊法可知，表5-8中最小加工时间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得：J4-*-*-*-*去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备2上的，所以应将对应的工件J1排在最后一位，即：J4-*-*-*-J1再去掉J1，在剩余的J2、J3、J5中重复上述步骤，求解过程为：J4-*-*-J5-J1J4-J2-*-J5-J1J4-J2-J3-J5-J1当同时出现多个最小值时，可从中任选一个。最后得J4-J2-J3-J5-J1(a)J1-J2-J3-J4-J530AB26AB(b)J4-J2-J3-J5-J1可以看出，初始作业顺序的总加工周期是30，用约翰逊法排出的作业顺序总加工周期是26，显然后者的结果优于前者。4.4两台机器排序问题算法的扩展(N)一般情况下，当机器数为3台以上时，就很难找到最优解了。但是，对于n个工件由三台机器流水作业时，在满足某些条件后可以采用Johnson’sLaw解决问题。设：A、B、C为三台机器，如果工件在三台机器上的加工时间满足以下条件，则可以转化为两台机器的排序问题：minAi=maxBiorminCi=maxBi定义：A’i=Ai+Bi,B’i=Bi+Ci例:考虑以下问题.5个工件由3台机器加工,作业时间见下表.求:总加工周期最短的作业顺序.12345机器A44913821627532机器B59619223330436机器C81710296357421153解:检查上表,发现:minAi=4maxBi=6minCi=6因此,满足以上条件,建立两台机器的作业时间表:应用Johnson法则，得出：１－４－５－２－３总加工周期为：12345机器A’9151099机器B’13168101514523机器A44610515924832机器B59313419630234机器C817724113510456514.5m(m3)台机器排序问题的算法（N）•一般采用启发式算法(Heuristics)解决这类问题。•关键工件法步骤1计算,找出其中最大者，定义为关键工件JC。mjijp1步骤2除JC外，将满足pi1p1m的工件，按ti1值的大小，从小到大排在JC的前面。步骤3除JC外，将满足pi1p1m的工件，按tim值的大小，从大到小排在JC的后面。步骤4除JC外，将满足pi1=p1m的工件，排在JC的前面或者后面。步骤5如有多个方案，可再加比较，从中选优。•关键工件法举例J1J2J3J4J5J6机器1pi15541210机器2pi25553610机器3pi3833474机器4pi4282156机器5pi55212810总和252315112840找出关键工件：工作负荷最大的40，对应的是工件6，所以JC=J6确定排在关键工件前面的工件：满足步骤2条件的有J4,J5,所以有J4–J5–J6–确定排在关键工件后面