《生产作业排序》由会员分享，可在线阅读，更多相关《生产作业排序（47页珍藏版）》请在金锄头文库上搜索。
1、1 1第八章生产作业排序2 2第一节第一节 排序的根本概念排序的根本概念 (Sequencing) 1.1概念作业排序：就是在指在有限的人力、资源设备上，安排多项工作任务，规定其执行的时间和顺序，使得预定的目标得以实现。3 3第一节第一节 排序的根本概念排序的根本概念 (Sequencing) 1.2排序与编制作业方案的差异1作业方案是安排零部件作业、活动的出产数量、设备及人工使用、投入时间及出产时间。2作业排序，给出零部件在一台或一组设备上加工的先后顺序的工作。所以,编制作业方案与排序的概念和目的都是不同的。但是，编制作业方案的主要工作之一就是要确定出最正确的作业顺序。4 4确定出最正确的作
2、业顺序容易吗？5 5确定出最正确的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。例如，考虑32项任务工件，有32！2.61035种方案,假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪.如果只有16个工件,同样按每秒钟可以检查1billion个顺序计算,也需要2/3年.以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。6 6第一节第一节 排序的根本概念排序的根本概念 (Sequencing
3、) 1.3排序问题的根本假设和常用符号的含义1.3.1根本假设对于生产作业的排序问题不管是流水型或者是非流水型，一般都是通过生产生活中总结的经验，科学的建立模型来求解作业排序问题，这样就需要有一定的环境或者说是架设问题。1一个工件不能够同时在几个机器上加工；2工件的加工时间是确定的，并且与投产顺序无关；7 73每个设备同时只能够加工一个工件不考虑工位组合机床4工件的工艺过程是固定的，一种工件不能够有多种加工工艺即便是有，在加工过程或者是说，在加工手册中之能够使用一种5每台设备支能够胜任一道工序加工，不能够加工多道工序，即不考虑一对多的关系，比方数控机床6一个工件在加工过程之中，不能够终端插入其
4、他的工件的加工。当让这些假设条件也并非是固定不变的，在这里仅仅是针对现在所讲的集中排序类型和模型而言。8 8 排序常用的符号排序常用的符号Ji-工件i，i=1,2,.n di-工件i的交货期 Pi-工件i的加工时间, pij-工件i在机器j上的加工时间,j=1,mWi-工件i在系统内的等待时间,wij-工件i在机器j前的等待时间,j=1,m9 9 Ci-工件i的完成时间,在工件都已到达的情况下, Ci= Pi+ Wi Fi-工件i的流程时间，在工件都已到达的情况下, Fi= Pi+ Wi Li-工件i的延迟时间, Li= Ci- di , Li0 延迟 Ti-工件i的延误, Ti=max0,
5、Li Ei-工件i提前完成的时间1010目标函数在这里目标函数是指我们所建立的生产作业函数其对生产作业进行排序的目的是什么，不同的目的构成了不同的目标函数，针对同一作业进行排序，不同的目标函数排序出来的结果会是截然不同的。1已按时交货为目标这类目标函数主要有平均延迟时间：平均延误时间：最大延误时间：2以工件的完工时间和工件的流程时间为目标函数最长完工时间：最长流程时间：平均完工时间：平均流程时间：11113在制品库存WIP。一个工件正从一个工作地移向另一个，由于一些原因被拖延加工，正在被加工或放置于零件库中，都可被看作是在制品库存。它是在途库存的一个例子，但其物料工程是制造出来的，而不是购置来
6、的。这种度量标准可以用工件个数、其货币价值或可供给的周数来表示。4总库存。方案入库量和现有库存量的总和为总库存量。5利用率。用一台机器和一个工人的有效生产时间占总工作时间的百分比来表示。1212 排序问题的分类排序问题的分类根据机器数的多少单台机器的排序问题多台机器的排序问题根据加工路线的特征单件车间排序(JobShop)流水型排序(FlowShop)1313根据工件到达系统的情况静态排序动态排序根据要实现的目标单目标排序多目标排序1414 排序问题的表示方法排序问题的表示方法排序问题常用四个符号来描述:n/m/A/B其中,n-工件数；m-机器数；A-车间类型,F=流水型排序P=流水型同顺序排
7、序G=一般类型,即单件型排序B-目标函数1515第第二二节节 单台机器的排序问题单台机器的排序问题2.1 单台机器排序问题单台机器排序问题n个工件全部经由一台机器处理J1J2J3Jn机器到达系统工件的集合离开系统机器1616一台设备有n项任务，如何安排作业顺序才能取得较好的经济效益？衡量效益的指标通常有：1完成任务的时间总和最短；2按期交货的作业工程最多；3任务总的拖期天数最少。通常情况下，这些指标不能同时到达最优，那么根据任务的需要，以单工程标作为优先原那么进行作业排序。17172.2 常见单台机器排序问题的目标函数常见单台机器排序问题的目标函数1)平均流程时间最短为n个零件经由一台机器的平
8、均流程时间。定义:目标函数MIN:2最大延期量最小定义:为最大延期量。目标函数1818根据排序目标的不同，可以选择不同的排序规那么，有时又称为确定优先权(Priorities)。常见的优先权规那么(Priorityrules)有：SPT-ShortestProcessTime,EDD-EarliestDueDateFCFS-FirstComeFirstServed.等,分别用于解决不同的问题。19192.3 求平均流程时间最短的排序问题求平均流程时间最短的排序问题求平均流程时间最短的作业顺序，采用SPT原那么。按工件加工时间的长短，按不减的顺序从小到大安排各项作业。例：一个车间有一台加工中心，
9、现有5个工件需要该机器加工。相关的加工时间和要求完成时间交货期如下表所示，求平均流程时间最短的作业顺序。J1J2J3J4J5加工时间11293112交货期61453133322020解：根据SPT原那么，得出：J4-J5-J1-J2-J3有关工程的计算：加工时间完成时间交货期延迟J411330J523320J11114610J2294345031743143J321212.4 求最大延期量最小的排序问题求最大延期量最小的排序问题求最大延期量最小的作业顺序采用EDD原那么。EDD(EarliestDueDate):Jobsaresequencedinincreasingorderoftheird
10、uedates.例：借用上面的例子，求最大延期量最小的作业顺序。解：根据EDD原那么，得出：J3-J5-J4-J2-J1加工时间完成时间交货期延迟J33131310J5233321J4134331J229634518J1117461132222平均延迟=33/5=6.6=18进一步考虑：在最大延期量不变的情况下，如何使平均流程时间缩短？如果想同时满足这两个目标，就是多目标排序。2323第第三三节节 n项任务在两台机器的排序问题项任务在两台机器的排序问题Scheduling n Jobs on Two Machines3.1 两台机器排序问题的含义两台机器排序问题的含义n个工件都必须经过机器1和
11、机器2的加工，即工艺路线是一致的。 机器1到达系统工件的集合离开系统（机器）J1J2J3Jn机器224243.2 两台机器排序问题的目标两台机器排序问题的目标两台机器排序的目标是使最大完成时间总加工周期Fmax最短。Fmax的含义见如下的甘特图(GanttChart)。多台机器排序的目标一般也是使最大完成时间总加工周期Fmax最短。Fmax 时间 机器AB在机器A上的作业时间总加工周期25253.3 两台机器排序问题的算法两台机器排序问题的算法 实现两台机器排序的最大完成时间实现两台机器排序的最大完成时间Fmax最短的目标，一最短的目标，一优化算法就是著名的约翰逊法优化算法就是著名的约翰逊法(
12、Johnsons Law)。其具体。其具体求解过程如下例所示。求解过程如下例所示。 约翰逊法解决这种问题分为约翰逊法解决这种问题分为4个步骤：个步骤： (1)列出所有工件在两台设备上的作业时间。列出所有工件在两台设备上的作业时间。 (2)找出作业时间最小者。找出作业时间最小者。 (3)如果该最小值是在设备如果该最小值是在设备1上，将对应的工件排在前面，上，将对应的工件排在前面，如果该最小值是在设备如果该最小值是在设备2上，那么将对应的工件排在后面。上，那么将对应的工件排在后面。 (4)排除已安排好的工件，在剩余的工件中重复步骤排除已安排好的工件，在剩余的工件中重复步骤(2)和和(3)，直到所有
13、工件都安排完毕。，直到所有工件都安排完毕。 2626例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。工件在两台设备上的加工时间工件编号J1J2J3J4J5设备A36715设备B286432727解：由约翰逊法可知，表5-8中最小加工时间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规那么，应将对应的工件4排在第一位，即得：J4-*-*-*-*去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备2上的，所以应将对应的工件J1排在最后一位，即：J4-*-*-*-J1再去掉J1，在剩余的J
14、2、J3、J5中重复上述步骤，求解过程为：J4-*-*-J5-J1J4-J2-*-J5-J1J4-J2-J3-J5-J1当同时出现多个最小值时，可从中任选一个。最后得J4-J2-J3-J5-J12828(a)J1-J2-J3-J4-J530AB26AB(b)J4-J2-J3-J5-J1可以看出，初始作业顺序的总加工周期是30，用约翰逊法排出的作业顺序总加工周期是26，显然后者的结果优于前者。29293.4 两台机器排序问题算法的扩展两台机器排序问题算法的扩展(Extension to Three Machines)一般情况下，当机器数为3台以上时，就很难找到最优解了。但是，对于n个工件由三台机
15、器流水作业时，在满足某些条件后可以采用JohnsonsLaw解决问题。设：A、B、C为三台机器，如果工件在三台机器上的加工时间满足以下条件，那么可以转化为两台机器的排序问题：minAi=maxBiorminCi=maxBi定义：Ai=Ai+Bi,Bi=Bi+Ci例:考虑以下问题.5个工件由3台机器加工,作业时间见下表.求:总加工周期最短的作业顺序.303012345机器A44913821627532机器B59619223330436机器C81710296357421153解:检查上表,发现:minAi=4maxBi=6minCi=6因此,满足以上条件,建立两台机器的作业时间表:3131应用Jo
16、hnson法那么，得出：总加工周期为：12345机器A9151099机器B13168101514523机器A44610515924832机器B59313419630234机器C8177241135104565132323.5 m(m 3)台机器排序问题的算法台机器排序问题的算法一般采用启发式算法(Heuristics)解决这类问题。关键工件法1 1按工序汇总个零件的加工工作量，定义加工工作量最大的工序为关键工按工序汇总个零件的加工工作量，定义加工工作量最大的工序为关键工序；序；2 2比较各零件首尾两道工序的大小比较各零件首尾两道工序的大小, ,并把全部零件分成三组，首并把全部零件分成三组，首
17、尾尾 分在分在第一组；首尾第一组；首尾 分在第二组分在第二组 首首 尾尾 分在第三组分在第三组3 3各组零件分别对组内零件进行排序；各组零件分别对组内零件进行排序；第一组第一组 每一零件分别将关键工序之前的各工序相加，按总和数值递增排列每一零件分别将关键工序之前的各工序相加，按总和数值递增排列第三组第三组 每一零件分别将关键工序之后的各工序相加，按总和数值递减排列每一零件分别将关键工序之后的各工序相加，按总和数值递减排列第二组第二组 当第一组零件少于第三组，按第一组规那么排，否那么按第三组规当第一组零件少于第三组，按第一组规那么排，否那么按第三组规那么排。那么排。4 4 全部零件按分组顺序排列
18、。全部零件按分组顺序排列。3333关键工件法举例J1J2J3J4J5J6机器1pi15541210机器2pi25553610机器3pi3833474机器4pi4282156机器5pi55212810总和252315112840找出关键工件：工作负荷最大的40，对应的是工件6，所以JC=J6确定排在关键工件前面的工件：满足步骤2条件的有J4,J5,所以有J4J5J6确定排在关键工件后面的工件：满足步骤3条件的有J2,J3,所以有J6J2J3满足步骤4条件的有J1,所以有J6J1，或者J1J6最后有：J4J5J6J1J2J3，或者J4J5J1J6J2J33434非流水型排序一般的非流水型排序问题，
19、每个工件有其独立的工艺路线。需要三个参数描述：i工件号j工序号k加工i工件j工序的机器代号3535加工矩阵D描述非流水型的排序问题用加工矩阵D来描述1,1,11,2,31,3,2i,j,kD=2,1,32,2,12,3,3每行描述一个零件的每到工序加工情况第2个工件第1道工序在第3个设备上加工3636时间矩阵T473T=568每行描述一个工件，每列描述一道工序3737加工顺序矩阵S1,1,12,2,1S=1,3,22,3,2i,j,k2,1,31,2,3每行描述每台机器的加工顺序情况第2个零件第1道工序在第3台设备上加工3838一n/2/G/Fmax排序借鉴约翰逊法那么：1、将n个工件分为四个
20、集合1只有一道工序，且这道工序在M1上加工的工件归属A集合2只有一道工序，且这道工序在M2上加工的工件归属B集合3有两道工序，且第一道工序在M1上加工，第二道工序在M2上加工，的工件归属AB集合3有两道工序，且第一道工序在M2上加工，第二道工序在M1上加工，的工件归属BA集合39392、对于AB集合中的工件，安约翰逊法那么排序，得顺序SAB；对于BA集合中的工件，安约翰逊法那么排序，得顺序SBA；对于A和B集合中的工件可以按照任何顺序编排，分别得到顺序SA和SB。3、在机器M1上工件按SABSASBA顺序加工。在机器M2上按SBASBSAB顺序加工。4040例工件号工件号12345678910
21、第1工序设备M1M2M1M1M2M2M1M1M2M2工时691274810957第2工序设备M2M1M2M2M1M2M1工时812710711104141例工件工件号号第一工序第一工序第一工序第一工序第一工序第一工序第一工序第一工序总工总工时时交货交货期期设备工时设备 工时 设备 工时设备工时J1M15M25M37M432028J2M27M14M31M461828J3M32M16M43M271825J4M34M24M16M4216264242生产过程生产过程 的组织的组织生产过程的生产过程的 空间组织空间组织生产过程的生产过程的 时间组织时间组织设施选址设施选址设施布置设施布置零件的移动方式零件的移动方式作业排序作业排序4343甘特图有两种根本形式的甘特图：1作业进度图，表示一项工作的方案开始日期、方案完成日期、现在的进度；2机器图，描述不同工作在每一台机器上的工作次序。4444例：汽车零件制造公司加工三种零件A、B、CA滞后于方案；B按方案完成；C超前于方案。45454646假设：截止到4月26日，零件A还不能完工，其装配线就要停工，因此需更新甘特图。A按方案完成；B和C将延期完工。4747
