《生产与运作管理制造业作业计划概述.ppt》由会员分享，可在线阅读，更多相关《生产与运作管理制造业作业计划概述.ppt（40页珍藏版）》请在金锄头文库上搜索。
1、华中科大管理学院陈荣秋马士华,1,第11章 制造业作业计划与控制Scheduling and Controlling for Manufacturing,11.1 作业计划问题的基本概念 11.2 流水作业排序问题 11.3 单件作业的排序问题 11.4 生产作业控制,华中科大管理学院陈荣秋马士华,2,11.1作业计划问题的基本概念,编制作业计划要解决的问题 编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。 由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。,华中科大管理学院陈荣秋马士华,3,11
2、.1作业计划问题的基本概念（续）,有关的名词术语 编制作业计划或日程安排(Scheduling) 排序(Sequencing) 派工(Dispatching) 控制(Controlling) 赶工(Expediting) “调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动,华中科大管理学院陈荣秋马士华,4,11.1作业计划问题的基本概念（续）,“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者” “零件”代表“服务对象”。零件可以是单个零件，也可以
3、是一批相同的零件 “加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束 “加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题,华中科大管理学院陈荣秋马士华,5,11.2 流水作业排序问题,流水车间(Flow shop):工件的加工路线都一致，典型的如流水线 11.2.1 最长流程时间的计算 11.2.2 两台机器排序问题的最优算法 11.2.3 多台机器排序问题的启发式算法,华中科大管理学院陈荣秋马士华,6,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
4、 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,华中科大管理学院陈荣秋马士华,7,11.2.2 两台机器排序问题的 最优算法,约翰森法则 如果Min(ai, bj) Min (aj, bi),则工件i应该排在工件j之前。 约翰森算法 （1）从加工时间矩阵中找出最短加工时间； （2）若最短加工时间出现在机器M1 上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2 上，则对应工件应该尽可能往后排。,华中科大管理学院陈荣秋马士华,8,11.2.2
5、两台机器排序问题的 最优算法（续）,然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。 （3）若所有工件都已排序，停止。否则，转步骤（1）。,华中科大管理学院陈荣秋马士华,9,将工件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,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 两台机器排序问题的 最
6、优算法（续）,华中科大管理学院陈荣秋马士华,10,11.2.2 两台机器排序问题的 最优算法（续） Johnson算法的改进,1. 将所有ai bi的工件按ai值不减的顺序排成一个序列A； 2. 将aibi的工件按bi值不增的顺序排成一个序列B； 3. 将A放到B之前，就构成了一个最优加工顺序。,华中科大管理学院陈荣秋马士华,11,11.2.2 两台机器排序问题的 最优算法（续） 举例,工件号 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 1
7、1 15 22 26 28,ai,bi,最优顺序下的加工周期为28,华中科大管理学院陈荣秋马士华,12,11.2.3 多台机器排序问题的 启发式算法,关键工件法 1. 计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C； 2. 对于余下的工件，若pi1pim则按pi1不减的顺序排成一个序列Sa ,若pi1pim 则按pim不增的顺序排成一个序列Sb; 3. 顺序（Sa,C,Sb）即为所求顺序。,华中科大管理学院陈荣秋马士华,13,11.2.3 多台机器排序问题的 启发式算法（续） 举例,工件i 1 2 3 4,Pi1 2 1 6 3 Pi2 4 8 2 9 Pi3 5 4 8 2,1
8、1 13 16 14,C,Sa (2,1),Sb(4),所求顺序： （2,1,3,4）,华中科大管理学院陈荣秋马士华,14,11.2.4 相同零件不同移动方 式下加工周期的计算,当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同 三种典型的移动方式 顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工 平行移动方式：单个零件加工完成后，立即移动到下道工序加工 平行顺序移动方式：两者混合,华中科大管理学院陈荣秋马士华,15,顺序移动方式,华中科大管理学院陈荣秋马士华,16,设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟
9、），零件在i道工序的单件工时为 （分钟/件），i=1.2n. 则该批零件的加工周期为：,顺序移动方式（续）,华中科大管理学院陈荣秋马士华,17,平行移动方式,工序,1,2,3,4,时间,加工周期,华中科大管理学院陈荣秋马士华,18,平行移动方式（续）,零件平行移动的加工周期 为：,华中科大管理学院陈荣秋马士华,19,平行顺序移动方式,特点：既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。如图所示：,时间,工序,1,2,3,4,加工 周期,华中科大管理学院陈荣秋马士华,20,平行顺序移动方式（续）,平行顺序移动加工周期计算,华中科大管理学院陈荣秋马士华,21,11.3 单件作业排序问
10、题,11.3.1 问题的描述 11.3.2 两种作业计划的构成 11.3.3 求解一般n/m/G/Fmax问题的启发式方法,华中科大管理学院陈荣秋马士华,22,11.3.1 问题的描述,D=,1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2,T=,2 4 1 3 4 5,加工描述矩阵D和加工时间矩阵T对应,华中科大管理学院陈荣秋马士华,23,11.3.2 两种作业计划的构成,符号说明 每安排一道工序称为一“步” St:t步之前已排序工序构成的部分作业计划； Ot:t步可排序工序的集合； Tk为Ot中工序Ok的最早可能开始时间； Tk为Ot中工序Ok的最早可能完成时间。,华
11、中科大管理学院陈荣秋马士华,24,11.3.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）若还有未安排的工序，转步骤（2）；否则，停止。,华中科大管理学院陈荣秋马士华,25,能动作业计划的构成,华中科大管理学院陈荣秋马士华,26,能动作业计划的甘特图,2,3,2,1,1,1
12、 2,2,1,1,3,2,2,1,3 1,2,3,3 7,7 8 13,2 3 7,0,时间,机器,M1,M2,M3,华中科大管理学院陈荣秋马士华,27,11.3.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）若还有未安排的工序，转步骤（2）；否则，停止。,华中科大
13、管理学院陈荣秋马士华,28,无延迟作业计划的构成,华中科大管理学院陈荣秋马士华,29,无延迟作业计划的甘特图,2,3,2,1,1,1 2,2,1,2,1,3 1,2,3,3 7,7 12 13,2 3 7,0,时间,机器,M1,M2,M3,1,3,2,华中科大管理学院陈荣秋马士华,30,11.3.3 三类启发式算法,（1）优先调度法则 构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划 计算量小 已经提出100多种优先调度法则,华中科大管理学院陈荣秋马士华,31,优先调度法则 FCFS（first come, first s
14、erved）选择最早进入可排序集合的工序 SPT( shortest processing time）选择加工时间最短的工序 EDD（earliest due date）选择完工期限最紧的工序 SCR(smallest critical ratio)选择临界比最小的工件 MWKR(most work remaining)选择余下加工时间最长的工件 LWKR(least work remaining)选择余下加工时间最短的工件 MOPNR(most operations remaining)选择余下工序数最多的工件 RANDOM 随机挑选一个工件 Rush,华中科大管理学院陈荣秋马士华,32,11.3.3 三类启发式算法（续）,（2）随机抽样法 从全部能动计划或无延迟计划中随机抽样，得出
