《第11章 制造业作业计划与控制》由会员分享，可在线阅读，更多相关《第11章 制造业作业计划与控制（62页珍藏版）》请在金锄头文库上搜索。
1、华中科大管理学院陈荣秋马士华,1,第11章 制造业作业计划与控制Scheduling and Controlling for Manufacturing,11.1 作业计划问题的基本概念 11.2 流水作业排序问题 11.3 单件作业的排序问题 11.4 生产作业控制,华中科大管理学院陈荣秋马士华,2,11.1作业计划问题的基本概念,编制作业计划要解决的问题 编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。 由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。,华中科大管理学院陈荣秋马士华,3,11
2、.1作业计划问题的基本概念（续）,11.1.1 有关的名词术语 编制作业计划或排程(Scheduling) 排序(Sequencing) 派工(Dispatching) 控制(Controlling) 赶工(Expediting) “调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动，属于计划范畴。,华中科大管理学院陈荣秋马士华,4,11.1.1有关名词术语（续）,“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者”。 “零件”代表“服务对象”。零件
3、可以是单个零件，也可以是一批相同的零件。 “加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束 。 “加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题。,华中科大管理学院陈荣秋马士华,5,11.1.2 假设条件与符号说明,假设条件 一个工件不能同时在几台不同的机器上加工。 工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。 不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。 每道工序只在一台机器上完成。 工件数、机器数和加工时间已知，加工时间与加工顺序无关。 每台机器同时只能加工一个工件。,
4、华中科大管理学院陈荣秋马士华,6,11.1.2 假设条件与符号说明（续）,符号说明 Ji工件i，i1,2,n。 Mj机器j，j1,2,m。 pijJi在Mj上的加工时间，Ji的总加工时间为Pipij riJi的到达时间，或准备就绪时间，指Ji从外部进入车间，可以开始加工的最早时间。 diJi的完工期限。 CiJi的完工时间, Ciri(wij+ pij) = ri+Wi+Pi. Cmax最长完工时间, Cmaxmax Ci .,华中科大管理学院陈荣秋马士华,7,11.1.2 假设条件与符号说明（续）,FiJi的流程时间，即工件在车间的实际停留时间, FiCI-riWi+Pi. Fmax最长流程
5、时间，Fmaxmax Fi . Li工件延迟时间，LiCidi riPi.+ Widi (Pi.+ Wi)(di -ri)Fiai. 当Li0 (正延迟)，说明Ji的实际完工时间超过了完工期限； 当Li0(负延迟)，说明Ji提前完工；当Li0(零延迟)，Ji按期完工。 Lmax最长延迟时间，Lmaxmax Li .,华中科大管理学院陈荣秋马士华,8,11.2 流水作业排序问题,流水车间(Flow shop):工件的加工路线都一致，典型的如流水线 11.2.1 最长流程时间的计算 11.2.2 两台机器排序问题的最优算法 11.2.3 多台机器排序问题的启发式算法 11.2.4相同零件、不同移动
6、方式下加工周期的计算,华中科大管理学院陈荣秋马士华,9,11.2.1 最长流程时间的计算,工件代号i,1 4 6 3 5 2,Pi1 4 5 3 4 8 6 Pi2 3 9 1 3 7 5 Pi3 7 6 8 2 5 9 Pi4 5 6 3 9 2 4,4 9 12 16 24 30,7 18 19 22 31 36,14 24 32 34 39 48,19 30 35 44 46 52,华中科大管理学院陈荣秋马士华,10,11.2.2 两台机器排序问题的 最优算法,约翰森法则 如果Min(ai, bj) Min (aj, bi),则工件i应该排在工件j之前。 约翰森算法 （1）从加工时间矩阵
7、中找出最短加工时间； （2）若最短加工时间出现在机器M1 上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2 上，则对应工件应该尽可能往后排。,华中科大管理学院陈荣秋马士华,11,11.2.2 两台机器排序问题的 最优算法（续）,然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。 （3）若所有工件都已排序，停止。否则，转步骤（1）。,华中科大管理学院陈荣秋马士华,12,将工件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
8、6 1 4 3 最优加工顺序为S=(2,5,6,1,4,3), Fmax =28,I 1 2 3 4 5 6,Ai 5 1 8 5 3 4 Bi 7 2 2 4 7 4,11.2.2 两台机器排序问题的 最优算法（续）,华中科大管理学院陈荣秋马士华,13,11.2.2 两台机器排序问题的 最优算法（续） Johnson算法的改进,1. 将所有ai bi的工件按ai值不减的顺序排成一个序列A； 2. 将aibi的工件按bi值不增的顺序排成一个序列B； 3. 将A放到B之前，就构成了一个最优加工顺序。,华中科大管理学院陈荣秋马士华,14,11.2.2 两台机器排序问题的 最优算法（续） 举例,工件
9、号 1 2 3 4 5 6,ai 5 1 8 5 3 4,bi 7 2 2 4 7 4,工件最优顺序：2 5 6 1 4 3,1 3 4 5 5 8 2 7 4 7 4 2,4 8 13 18 26,3 11 15 22 26 28,ai,bi,最优顺序下的加工周期为28,华中科大管理学院陈荣秋马士华,15,11.2.3 多台机器排序问题的 启发式算法,关键工件法 1. 计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C； 2. 对于余下的工件，若pi1pim则按pi1不减的顺序排成一个序列Sa ,若pi1pim 则按pim不增的顺序排成一个序列Sb; 3. 顺序（Sa,C,Sb）即
10、为所求顺序。,华中科大管理学院陈荣秋马士华,16,11.2.3 多台机器排序问题的 启发式算法（续） 举例,工件i 1 2 3 4,Pi1 2 1 6 3 Pi2 4 8 2 9 Pi3 5 4 8 2,11 13 16 14,C,Sa (2,1),Sb(4),所求顺序： （2,1,3,4）,华中科大管理学院陈荣秋马士华,17,11.2.4 相同零件不同移动方 式下加工周期的计算,当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同 三种典型的移动方式 顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工 平行移动方式：单个零件加工完成后，立即移动到下道工序加工 平行顺序移动方
11、式：两者混合,华中科大管理学院陈荣秋马士华,18,顺序移动方式,华中科大管理学院陈荣秋马士华,19,设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为 （分钟/件），i=1.2n. 则该批零件的加工周期为：,顺序移动方式（续）,华中科大管理学院陈荣秋马士华,20,平行移动方式,华中科大管理学院陈荣秋马士华,21,平行移动方式（续）,零件平行移动的加工周期 为：,为最长单件工序时间,华中科大管理学院陈荣秋马士华,22,平行顺序移动方式,特点：既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。如图所示：
12、,华中科大管理学院陈荣秋马士华,23,平行顺序移动方式（续）,平行顺序移动加工周期计算,华中科大管理学院陈荣秋马士华,24,11.3 单件作业排序问题,11.3.1 任务分配问题 11.3.2 单件作业排序问题的描述 11.3.3 优先派工准则 11.3.4 求解一般n/m/G/Fmax问题的启发式方法,华中科大管理学院陈荣秋马士华,25,11.3.1 任务分配问题,有4个零件可以分配给4台机器加工，其所需加工时间如图所示。即，零件1分配给机器1加工，需要9个时间单位；分配给机器2加工 ，需要7个时间单位；分配给机器3加工，需,要3个时间单位；分配给机器4加工，需要5个时间单位，等等。如果有n
13、个零件要分配给n台机器加工，则有n!种不同的分配方案。通过匈牙利算法可以较方便地找到最优分配方案。,华中科大管理学院陈荣秋马士华,26,11.3.1 任务分配问题（续）,匈牙利算法 (1)从加工时间(费用)矩阵每一行所有元素减去该行最小的元素，使每行至少出现一个零元素。 (2)从实施第(1)步得到的矩阵中的每一列所有元素减去该列最小的元素，使每列至少出现一个零元素。 (3)从实施第(2)步得到的矩阵中，划出能覆盖尽可能多的零元素的直线，如果线条数等于矩阵的行数，则已找到最优矩阵，转第(6)步；否则，转第(4)步。,华中科大管理学院陈荣秋马士华,27,11.3.1 任务分配问题（续）,(4)从矩
14、阵中未被线条穿过的元素中减去这些元素中的最小数，并将这个最小数加到直线交叉的元素上，其余元素不变。 (5)重复步骤(3)和步骤(4)，直到获得最优矩阵。 （6）从仅有一个零的行或列开始，找出零元素对应的分配方案，每行和每列仅能确定一个元素，最后使每行和每列都有一个零元素。零元素对应的就是最优分配方案。,华中科大管理学院陈荣秋马士华,28,M1 M2 M3 M4,J1 J2 J3 J4,9 7 3 5 3 7 8 12 11 7 4 6 8 7 4 6 11 13 10 6,(a),M1 M2 M3 M4,J1 J2 J3 J4,6 4 0 2 0 1 5 4 0 2 4 3 0 5 7 4 0 1 0 2,(b),11.3.1 任务分配问题（续）,行最小数,列最小数,华中科大管理学院陈荣秋马士华,29,M1 M2 M3 M4,J1 J2 J3 J4,3 0
