运营管理制造业作业计划与控制(PPT 65页).ppt

流水作业排序问题单件作业排序问题,重点,内容,排序问题的基本概念流水作业排序问题单件作业排序问题生产作业控制,第11章制造业作业计划与控制,生产作业计划的主要任务是将主生产计划或MRP中的零部件投入出产计划细化，是MRP的具体执行计划，具体、详细地规定了各车间、工段、班组以至每个工作地在较短的时间内（月、旬、周、日、轮班、小时）的生产运作任务。,生产作业计划的内容,作业计划与控制的关系,作业计划：给生产活动制定详细时间表生产控制：以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，保证实现各项各项计划目标。,第一节排序问题的基本概念,一、名词术语,生产管理,“（编制）作业计划”（Scheduling）“排序”（Sequencing）“派工”（Dispatching）“控制”（Controlling）“赶工”（Expediting）,排序,工件在机器上的加工顺序,（编制）作业计划,工件的加工顺序,加工工件的开始时间,加工工件的完成时间,作业计划的主要问题是确定各台机器上工件的加工顺序,通常情况下都是按最早可能开（完）工时间来编排作业计划的,当工件的加工顺序确定之后，作业计划也就确定了,派工,赶工,属于“调度”范围,“编制作业计划”加工制造发生之前的活动,“调度”是在加工制造发生之后的活动，是发现实生产进度已经偏离预定计划而采取的调配资源的行动调度的依据是作业计划,描述排序问题的术语,“机器”“工件”“工序”“加工时间”,n个工件经过m台机器加工,“加工路线”,工件加工的工艺过程决定,一般用M1，M2，来表示,“加工顺序”,每台机器加工n个工件的先后顺序,排序问题的复杂性,确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪。如果只有16个工件,同样按每秒钟可以检查1billion个顺序计算,也需要2/3年。以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。,二、假设条件与符号说明,假设条件,l.一个工件不能同时在几台不同的机器上加工2.工件在加工过程中采取平行移动方式3.不允许中断4.每道工序只在一台机器上完成5.工件数、机器数和加工时间已知，加工时间与加工顺序无关6.每台机器同时只能加工一个工件,符号,Ji工件i，i=1，2，nMj机器j，j=1，2，mPijJi在Mj上的加工时间，Ji的总加工时间为Pi=pijriJi的到达时间，指Ji从外部进入车间，可以开始加工的最早时间diJi的完工期限CiJi的完工时间，Ciri+(wij+pij)=ri+Wi+PiCmax最长完工时间，Cmax=maxCi,符号,FiJi的流程时间，即工件在车间的实际停留时间，FiCi-ri=Wi+PiFmax最长流程时间，Fmax=maxFiLi工件的延迟时间WijJi在Mj上加工之前的等待时间WiJi在加工过程中总的等待时间aiJi的允许停留时间,符号,Li=Ci-di=ri+Pi+Wi-di=(Pi+Wi)-(di-ri)=Fi-ai,当Li0（正延迟），说明Ji的实际完工时间超过了完工期限当Li0（负延迟），说明Ji提前完工当Li=0（零延迟），Ji按期完工,Lmax最长延迟时间，Lmax=maxLi,三、排序问题的分类和表示法,分类方法,机器工件目标函数,机器,单台机器的排序问题,多台机器的排序问题,工件加工路线,单件作业（Job-Shop）排序问题,流水作业（Flow-shop）排序问题,单件车间排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。流水车间排序问题的基本特征：每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。,静态的排序问题动态的排序问题,单目标排序问题多目标排序问题,确定型排序问题随机型排序问题,Conway表示方法,4参数表示法,nmAB,n工件数m机器数A车间类型,F代表流水作业排序问题P表示流水作业排列排序问题G表示一般单件作业排序问题m1A空白,B目标函数,第二节流水作业排序问题,基本特征,工件的加工路线都一致,工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工,对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致,流水作业排列排序问题,“同顺序”排序问题,所有工件在各台机器上的加工顺序都相同,排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解,对于仅有2台和3台机器的特殊情况，排列排序问题下的最优解一定是相应流水作业排序问题的最优解,一、最长流程时间Fmax的计算,nmPFmax,目标函数最长流程时间最短,最长流程时间加工周期,从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间,Fmax等于排在末位的工件在车间的停留时间，等于一批工件的最长完工时间Cmax,设n个工件的加工顺序为S=（S1，S2，Sn）,Si排第i位加工的工件的代号,表示工件Si在机器Mk上的完工时间,表示工件Si在Mk上的加工时间,k=1，2，mi=1，2，n,按以下公式计算,(11.1),k=1,2,m;i=1,2,n,当ri=0，i=1,2,n时,Fmax=,例11.1有一个64PFmax问题，其加工时间如表111所示。当按顺序S=(6,1,5,2,4,3)加工时，求Fmax。,表11-l加工时间矩阵,表112顺序S下的加工时间矩阵,二、n/2/F/Fmax问题的最优算法,n项任务在两台机器的排序问题SchedulingnJobsonTwoMachinesn个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。,两台机器排序问题的目标,两台机器排序的目标是使最大完成时间（总加工周期）Fmax最短。Fmax的含义见如下的甘特图(GanttChart)。,多台机器排序的目标一般也是使最大完成时间（总加工周期）Fmax最短。,1954年Johnson提出用ai表示Ji在M1上的加工时间，用bi表示Ji在M2上的加工时间。每个工件都按M1M2的路线加工。Johnson指出，若min(ai,bj)=maxBiorminCi=maxBi定义：Ai=Ai+Bi,Bi=Bi+Ci例:考虑以下问题.5个工件由3台机器加工,作业时间见下表.求:总加工周期最短的作业顺序。,解:检查上表,发现:minAi=4maxBi=6minCi=6因此,满足以上条件,建立两台机器的作业时间表:,应用Johnson法则，得出：总加工周期为：,三、n/m/P/Fmax问题的启发式算法,对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法,对于一般的流水车间排列排序问题,分支定界法,启发式算法,求一般nmPFmax问题近优解（Nearoptimalsolution）的启发式算法,（一）Palmer法,按斜度指标排列工件的启发式算法,工件斜度指标,k=1,2,n,m为机器数；pik为工件i在Mk上的加工时间,按照各工件不增的顺序排列工件，可得出令人满意的顺序,(11.4),例11.3有一个43FFmax问题，其加工时间如表115所示，用Palmer法求解,表115加工时间矩阵,解：对于本例，式（114）变成,k=1,2,3,=-pk1+pk3,=-p11+p13=-1+4=3,=-p21+p23=-2+5=3,=-p31+p33=-6+8=2,=-p41+p43=-3+2=-1,按不增的顺序排列工件，得到加工顺序（l,2,3,4）和（2,l,3,4）,这两个顺序都是最优顺序,Fmax28,（二）关键工件法,步骤,（1）计算每个工件的总加工时间Pi=pij，找出加工时间最长的工件C（j=m），将其作为关键工件。（2）对于余下的工件，若pi1pim，则按pi1不减的顺序排成一个序列Sa；若pi1pim，则按pim不增的顺序排列成一个序列Sb。（3）顺序（Sa，C，Sb）即为所求顺序。,表11-6用关键工件法求解,总加工时间最长的为3号工件,（三）CDS法,把Johnson算法用于一般的nmPFmax问题，得到（m-1）个加工顺序，取其中优者。,具体做法,按,和,合并组成新的“机器”,l=1,2,m-1,合并(m-1)次，得到(m-1)个n/2/F/Fmax问题,用Johnson算法求（m-1）次加工顺序，取其中最好的结果,L1，按Johnson算法得到加工顺序(1，2，3，4)，Fmax28L2，按Johnson算法得到加工顺序(2，3，1，4)，Fmax29取顺序(1，2，3，4）为最优顺序。,四、相同零件不同移动方式下加工周期的计算,排序问题针对的是不同的零件，如果n个零件相同，则没有排序问题。零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。零件在加工过程中可以采用三种典型的移动方式：顺序移动平行移动平行顺序移动,第三节单件作业排序问题,每个工件都有其独特的加工路线，工件没有一定的流向单件作业的排序问题是最一般的排序问题，也是最复杂的一种排序问题R.w.Conway作业计划理论（TheoryofScheduling）,一、问题的描述,对于一般单件作业排序问题,描述一道工序，要用3个参数：i,j和k,i表示工件代号j表示工序号k表示完成工件i的第j道工序的机器的代号,用（i,j,k）来表示工件i的第j道工序是在机器k上进行的这样一件事用加工描述矩阵描述所有工件的加工要求。,加工描述矩阵D,加工描述矩阵D的每一行描述一个工件的加工每一列的工序序号相同行表示不同的工件；列表示不同的工序。,单件作业排序问题(n/m/G/Fmax),加工描述矩阵D：每一行描述一个工件的加工，每一列的工序序号相同。加工时间矩阵T：与D相对应。,单件作业排序问题(n/m/G/Fmax),加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。,单件作业排序问题(n/m/G/Fmax),用方块图表示：,二、一般n/m/G/Fmax问题的启发式算法,对于一般的n/m/G/Fmax排序问题,分支定界法或整数规划法,是无效算法,启发式算法是求解一般单件车间排序问题使用最多的方法,（一）两种作业计划的构成,半能动作业计划（Semi-activeschedule）,各工序都按最早可能开（完）工时间安排的作业计划,能动作业计划（Activeschedule）,任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业划,无延迟作业计划（Non-delayschedule）,没有任何延迟出现的能动作业计划,延迟,有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序,能动作业计划和无延迟作业计划的生成方法,将每安排一道工序称作一“步”,设,Stt步之前已排序工序构成的部分作业计划Ot第t步可以排序的工序的集合TkOt中工序Ok的最早可能开工时间TkOt中工序Ok的最早可能完工时间,1.能动作业计划的构成步骤,（1）设t=l，S1为空集，O1为各工件第一道工序的集合（2）求T*=minTk，并求出T*出现的机器M*。如果M*有多台，则任选一台（3）从Ot中挑出满足以下两个条件的工序Oj：需要机器M*加工，且TjT*（4）将确定的工序Oj放入St，从Ot冲消去Oj，并将Oj的紧后工序放入Ot，使t=t+1（5）若还有未安排的工序，转步骤（2）；否则，停止,得到加工顺序矩阵：,2.无延迟作业计划的构成步骤,（1）设t=1，S1为空集，O1为各工件第一道工序的集合（2）求T*=minTk，并求出T*出现的机器M*。如果M*有多台；则任选一台（3）从Ot中挑出满足以下两个条件的工序Oj：需要机器M*加工，且Tj=T*（4）将确定的工序Oj放入St，从Ot中消去Oj，并将Oj的紧后工序放入Ot，使t=t+1（5）若还有未安排的工序，转步骤；否则，停止,得到加工顺序矩阵：,（二）三类启发式算法,能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。,1.优选调度法则,能动作业计划与无延迟作业什划的构成步骤时，其中第（3）步的两个条件一般都有多个工序可以满足。按什么样的准则来选择可安排的工序，对作业计划的优劣有很大影响优先调度法则,1.优选调度法则,SPT(ShortestProcessingTime)法则：优先选择加工时间最短的工序。FCFS(FirstComeFirstServed)法则：优先选择最早进入可排工序集合的工件。EDD(EarliestDueDate)法则：优先选择完工期限紧的工件。MWKR(MostWorkRemaining)法则：优先选择余下加工时间最长的工件。LWKR(LeastWorkRemaining)法则：优先选择余下加工时间最短的工件。MOPNR(MostOperationsRem