《{运营管理}运营管理第11章制造业作业计划与控制》由会员分享，可在线阅读，更多相关《{运营管理}运营管理第11章制造业作业计划与控制（64页珍藏版）》请在金锄头文库上搜索。
1、流水作业排序问题 单件作业排序问题,重点,内容,排序问题的基本概念 流水作业排序问题 单件作业排序问题 生产作业控制,第11章 制造业作业计划与控制,生产作业计划的主要任务是将主生产计划或MRP中的零部件投入出产计划细化，是MRP的具体执行计划，具体、详细地规定了各车间、工段、班组以至每个工作地在较短的时间内（月、旬、周、日、轮班、小时）的生产运作任务。,生产作业计划的内容,作业计划与控制的关系,作业计划： 给生产活动制定详细时间表 生产控制： 以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，保证实现各项各项计划目标。,第一节 排序问题的基本概念,一、名词术语,生产
2、管理,“（编制）作业计划”（Scheduling） “排序”（Sequencing） “派工”（Dispatching） “控制”（Controlling） “赶工”（Expediting）,排序,工件在机器上的加工顺序,（编制）作业计划,工件的加工顺序,加工工件的开始时间,加工工件的完成时间,作业计划的主要问题是确定各台机器上工件的加工顺序,通常情况下都是按最早可能开（完）工时间来编排作业计划的,当工件的加工顺序确定之后，作业计划也就确定了,派工,赶工,属于“调度”范围,“编制作业计划”加工制造发生之前的活动,“调度”是在加工制造发生之后的活动，是发现实生产进度已经偏离预定计划而采取的调配资
3、源的行动 调度的依据是作业计划,描述排序问题的术语,“机器” “工件” “工序” “加工时间”,n个工件经过m台机器加工,“加工路线”,工件加工的工艺过程决定,一般用M1，M2，来表示,“加工顺序”,每台机器加工n个工件的先后顺序,排序问题的复杂性,确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。 例如，考虑32项任务（工件），有32！2.61035 种方案,假定计算机每秒钟可以检查1 billion个顺序, 全部检验完毕需要8.41015 个世纪。 如果只有16个工件, 同样按每秒钟可以检查1 billion个顺序计算, 也需要
4、2/3年。 以上问题还没有考虑其他的约束条件, 如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。 所以，很有必要去寻找一些有效算法，解决管理中的实际问题。,二、假设条件与符号说明,假设条件,l. 一个工件不能同时在几台不同的机器上加工 2. 工件在加工过程中采取平行移动方式 3.不允许中断 4. 每道工序只在一台机器上完成 5.工件数、机器数和加工时间已知，加工时间与加工顺序无关 6.每台机器同时只能加工一个工件,符号,Ji工件i ，i= 1，2，n Mj机器j，j=1，2，m PijJi在Mj上的加工时间，Ji的总加工时间为Pi=pij riJi的到达时间，指J
5、i从外部进入车间，可以开始加工的最早时间 diJi的完工期限 CiJi的完工时间，Ciri +(wij+pij)=ri+Wi+Pi Cmax最长完工时间，Cmax=maxCi,符号,FiJi的流程时间，即工件在车间的实际停留时间，FiCi-ri=Wi+Pi Fmax最长流程时间，Fmax=maxFi Li工件的延迟时间 WijJi在Mj上加工之前的等待时间 WiJi在加工过程中总的等待时间 aiJi的允许停留时间,符号,Li=Ci-di=ri+Pi+Wi-di=(Pi+Wi)-(di-ri)=Fi-ai,当Li0（正延迟），说明Ji的实际完工时间超过了完工期限 当Li0（负延迟），说明Ji提前
6、完工 当Li=0（零延迟），Ji按期完工,Lmax最长延迟时间，Lmax=maxLi,三、排序问题的分类和表示法,分类方法,机器 工件 目标函数,机器,单台机器的排序问题,多台机器的排序问题,工件加工路线,单件作业（Job-Shop）排序问题,流水作业（Flow-shop）排序问题,单件车间排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。 流水车间排序问题的基本特征： 每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。 不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称
7、为排列排序（同顺序排序）。如工件排序为：J1J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。,静态的排序问题 动态的排序问题,单目标排序问题 多目标排序问题,确定型排序问题 随机型排序问题,Conway表示方法,4参数表示法,nm A B,n 工件数 m 机器数 A 车间类型,F 代表流水作业排序问题 P 表示流水作业排列排序问题 G 表示一般单件作业排序问题 m1 A 空白,B 目标函数,第二节 流水作业排序问题,基本特征,工件的加工路线都一致,工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工,对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致,流水作
8、业排列排序问题,“同顺序”排序问题,所有工件在各台机器上的加工顺序都相同,排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解,对于仅有2台和3台机器的特殊情况，排列排序问题下的最优解一定是相应流水作业排序问题的最优解,一、最长流程时间Fmax的计算,nmPFmax,目标函数最长流程时间最短,最长流程时间加工周期,从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间,Fmax等于排在末位的工件在车间的停留时间，等于一批工件的最长完工时间Cmax,设n个工件的加工顺序为S=（S1，S2，Sn）,Si 排第i位加工的工件的代号,
9、表示工件Si在机器Mk上的完工时间,表示工件Si在Mk上的加工时间,k=1，2，m i=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项任务在两台机器的排序问题Scheduling n Jobs on Two Machines n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。,两台机器排
10、序问题的目标,两台机器排序的目标是使最大完成时间（总加工周期）Fmax最短。 Fmax的含义见如下的甘特图(Gantt Chart)。,多台机器排序的目标一般也是使最大完成时间（总加工周期） Fmax最短。,1954年Johnson提出 用ai 表示Ji在M1 上的加工时间，用bi 表示Ji在M2 上的加工时间。每个工件都按M1 M2的路线加工。 Johnson指出，若min(ai, bj)min(aj, bi),则Ji应排在Jj之前。 按上关系式可以确定每两个工件的相对位置，从而可以得到n个工件的完整的顺序 Johnson算法： 从加工时间矩阵中找出最短的加工时间 若它出现在M1上，则其对应
11、的工件应尽可能往前排；若它出现在M2上，则其对应的工件应尽可能往后排 划去已排序工件并重复上述步骤直至排完,例11.2 求表11-3所示的6/2/F/Fmax问题的最优解,表11-3 加工时间矩阵,将工件2排第1位 2 将工件3排第6位 2 3 将工件5排第2位 2 5 3 将工件6排第3位 2 5 6 3 将工件4排第5位 2 5 6 4 3 将工件1排第4位 2 5 6 1 4 3,最优加工顺序为S=（2，5，6，l，4，3） 最优顺序下的Fmax=28,Johnson法则2,将所有aibi的工件按ai值不减的顺序排成一个序列A 将所有aibi的工件按bi值不增的顺序排成一个序列B 将A放
12、到B之前，就构成了最优加工顺序,序列A为（2，5，6，1） 序列B为（4，3） 最优顺序为（2，5，6，l；4，3）,应用Johnson法则求得的最优顺序中任意去掉一些工件时，余下的工件仍构成最优顺序,Johnson 法则只是一个充分条件，不是必要条件,不符合这个法则的加工顺序，也可能是最优顺序,两台机器排序问题算法的扩展(Extension to Three Machines),一般情况下当机器数为3台以上时，就很难找到最优解了 但是，对于n个工件由三台机器流水作业时，在满足某些条件后可以采用Johnsons Law解决问题。 设：A、B、C为三台机器，如果工件在三台机器上的加工时间满足以下
13、条件，则可以转化为两台机器的排序问题： min Ai=max Bi or min Ci = max Bi 定义：Ai = Ai+ Bi , Bi = Bi +Ci 例: 考虑以下问题. 5个工件由3台机器加工, 作业时间见下表. 求: 总加工周期最短的作业顺序。,解: 检查上表, 发现: min Ai = 4 max Bi = 6 min Ci = 6 因此,满足以上条件, 建立两台机器的作业时间表:,应用Johnson法则，得出： 总加工周期为：,三、n/m/P/Fmax问题的启发式算法,对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法,对于一般的流水车间排列排序问题,分
14、支定界法,启发式算法,求一般nmPFmax问题近优解（Near optimal solution）的启发式算法,（一）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+
15、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
16、）个加工顺序，取其中优者。,具体做法,按,和,合并组成新的“机器”,l=1,2,m-1,合并(m-1)次，得到(m-1)个n/2/F/Fmax问题,用Johnson算法求（m-1）次加工顺序，取其中最好的结果,L1，按Johnson算法得到加工顺序(1，2，3，4)，Fmax28 L2，按Johnson算法得到加工顺序(2，3，1，4)， Fmax29 取顺序(1，2，3，4）为最优顺序。,四、相同零件不同移动方式下加工周期的计算,排序问题针对的是不同的零件，如果n个零件相同，则没有排序问题。 零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。 零件在加工过程中可以采用三种典型的移动方式： 顺序移动 平行移动 平行顺序移动,第三节 单件作业排序问题,每个工件都有其独特的加工路线，工件没有一定的流向 单件作业的排序问题是最一般的排序问题，也是最复杂的一种排序问题 R.w.Conway 作业计划理论（Theory of Scheduling）,一、问题的描述,
