制造业作业计划与控制(3)课件

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个顺序计算, 也需要2/3年。以上问题还没有考虑其他的约束条件

4、, 如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。二、假设条件与符号说明 假设条件 l. 一个工件不能同时在几台不同的机器上加工 2. 工件在加工过程中采取平行移动方式3.不允许中断4. 每道工序只在一台机器上完成 5.工件数、机器数和加工时间已知，加工时间与加工顺序无关 6.每台机器同时只能加工一个工件 符号 Ji工件i ，i= 1，2，n Mj机器j，j=1，2，m PijJi在Mj上的加工时间，Ji的总加工时间为Pi=pij riJi的到达时间，指Ji从外部进入车间，可以开始加工的最早时间 diJi的

5、完工期限 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提前完工当Li=0（零延迟），Ji按期完工 Lmax最长延迟

6、时间，Lmax=maxLi 三、排序问题的分类和表示法 分类方法 机器 工件 目标函数 机器 单台机器的排序问题 多台机器的排序问题 工件加工路线 单件作业（Job-Shop）排序问题 流水作业（Flow-shop）排序问题 单件车间排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。流水车间排序问题的基本特征：每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1J3J2，则表示所有

7、机器都是先加工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位加工的工件的代号 表示工件Si在机器Mk上的完工时间 表示工件Si在Mk上的加工时间 k=1，2，m

9、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。i123456pi1423142pi 2456745pi 3587555pi 4424331表11-l 加工时间矩阵 i615243pi12246410212113316pi 257411415520727633pi 3512517522830535742pi 4113421325232338446表112 顺序S下的加工时间矩阵 二、n/2/F/ Fma

10、x问题的最优算法n项任务在两台机器的排序问题Scheduling n Jobs on Two Machinesn个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。机器1到达系统工件的集合离开系统（机器）J1J2J3Jn机器2两台机器排序问题的目标两台机器排序的目标是使最大完成时间（总加工周期）Fmax最短。 Fmax的含义见如下的甘特图(Gantt Chart)。多台机器排序的目标一般也是使最大完成时间（总加工周期） Fmax最短。Fmax 时间 机器 A B在机器A上的作业时间总加工周期1954年Johnson提出用ai 表示Ji在M1 上的加工时间，用bi 表示Ji在M2 上的加工

11、时间。每个工件都按M1 M2的路线加工。 Johnson指出，若min(ai, bj)=max Bior min Ci = max Bi 定义：Ai = Ai+ Bi , Bi = Bi +Ci例: 考虑以下问题. 5个工件由3台机器加工, 作业时间见下表. 求: 总加工周期最短的作业顺序。 1 2 3 4 5机器A 44 913 821 627 532机器B 59 619 223 330 436机器C 817 1029 635 742 1153 解: 检查上表, 发现: min Ai = 4 max Bi = 6 min Ci = 6因此,满足以上条件, 建立两台机器的作业时间表: 1 2

12、3 4 5机器A 9 15 10 9 9机器B 13 16 8 10 15 1 4 5 2 3机器A 44 610 515 924 832机器B 59 313 419 630 234机器C 817 724 1135 1045 651应用Johnson法则，得出：总加工周期为：三、n/m/P/Fmax问题的启发式算法 对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法 对于一般的流水车间排列排序问题 分支定界法 启发式算法 求一般nmPFmax问题近优解（Near optimal solution）的启发式算法 （一）Palmer法 按斜度指标排列工件的启发式算法 工件斜度指标

13、 k=1,2,n m为机器数；pik为工件i在Mk上的加工时间 按照各工件 不增的顺序排列工件，可得出令人满意的顺序 (11.4)例11.3 有一个43FFmax问题，其加工时间如表115所示，用Palmer法求解 i1234pi11263pi28429pi34582表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） 这两个

14、顺序都是最优顺序 Fmax28 （二）关键工件法 步骤 （1）计算每个工件的总加工时间Pi=pij，找出加工时间最长的工件C（j=m），将其作为关键工件。 （2）对于余下的工件，若pi1pim，则按pi1不减的顺序排成一个序列Sa；若pi1pim，则按pim不增的顺序排列成一个序列Sb。 （3）顺序（Sa，C，Sb）即为所求顺序。 i1234pi11263pi28429pi34582pi13111614表11-6 用关键工件法求解 总加工时间最长的为3号工件 （三）CDS法 把Johnson算法用于一般的nmPFmax问题，得到（m-1）个加工顺序，取其中优者。 具体做法 按和合并组成新的“机

15、器”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个零件相同，则没有排序问题。零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。零件在加工过程中可以采用三种典型的移动方式：顺序移动平行移动平行顺序移动第三节 单件作业排序问题 每个工件都

16、有其独特的加工路线，工件没有一定的流向单件作业的排序问题是最一般的排序问题，也是最复杂的一种排序问题 R.w.Conway 作业计划理论（Theory of Scheduling）一、问题的描述 对于一般单件作业排序问题 描述一道工序，要用3个参数：i,j和k i表示工件代号j表示工序号k表示完成工件i的第j道工序的机器的代号 用（i,j,k）来表示工件i的第j道工序是在机器k上进行的这样一件事 用加工描述矩阵描述所有工件的加工要求。加工描述矩阵D 加工描述矩阵D的每一行描述一个工件的加工 每一列的工序序号相同 行表示不同的工件；列表示不同的工序。单件作业排序问题(n/m/G/ Fmax)D=

17、1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=4 6 35 7 4加工描述矩阵D：每一行描述一个工件的加工，每一列的工序序号相同。加工时间矩阵T：与D相对应。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,3单件作业排序问题(n/m/G/ Fmax)加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,3T=4 6 35 7 41,1,1

18、2,1,31,2,32,2,11,3,22,3,2M1M2M3单件作业排序问题(n/m/G/ Fmax)用方块图表示：二、一般n/m/G/Fmax问题的启发式算法 对于一般的n/m/G/Fmax排序问题 分支定界法或整数规划法 是无效算法 启发式算法是求解一般单件车间排序问题使用最多的方法 （一）两种作业计划的构成 半能动作业计划（Semi-active schedule） 各工序都按最早可能开（完）工时间安排的作业计划 能动作业计划（Active schedule） 任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业划 无延迟作业计划（Non-delay schedule） 没

19、有任何延迟出现的能动作业计划 延迟 有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序 能动作业计划和无延迟作业计划的生成方法 将每安排一道工序称作一“步” 设 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

20、，从Ot冲消去Oj，并将Oj的紧后工序放入Ot，使t=t+1 （5）若还有未安排的工序，转步骤（2）；否则，停止 得到加工顺序矩阵：S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3237738132. 无延迟作业计划的构成步骤 （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）若还有未安排的工序，转步骤；否则，停止 得到加工顺序矩阵：S=1,1,1 2,2,12,3,2 1,3,22,1,3 1,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3237731213（二）三类启发式算法能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。一