第九章 流水作业的排序问题.ppt
《第九章 流水作业的排序问题.ppt》由会员分享,可在线阅读,更多相关《第九章 流水作业的排序问题.ppt(43页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第九章第九章流水作业的排序问题流水作业的排序问题9.1 9.1 排序问题概述排序问题概述9.2 9.2 流水作业排序问题流水作业排序问题9.1 9.1 排序问题概述排序问题概述一、排序问题的基本概念一、排序问题的基本概念排序是确定工件(零部件)在一台或一组设备排序是确定工件(零部件)在一台或一组设备上加工的先后顺序。上加工的先后顺序。在一定约束条件下,寻找总加工时间最短的安在一定约束条件下,寻找总加工时间最短的安排产品加工顺序的方法,就是生产作业排序。排产品加工顺序的方法,就是生产作业排序。例如,考虑例如,考虑32项任务(工件),有项任务(工件),有32!2.6 1035种方案种方案,假定计算
2、机每秒钟可以检假定计算机每秒钟可以检查查1billion个顺序个顺序,全部检验完毕需要全部检验完毕需要8.4 1015个世纪个世纪.如果只有如果只有16个工件个工件,同样按每秒钟可以检查同样按每秒钟可以检查1billion个顺序计算个顺序计算,也需要也需要2/3年年.以上问题还没有考虑其他的约束条件以上问题还没有考虑其他的约束条件,如机如机器、人力资源、厂房场地等,如果加上这些器、人力资源、厂房场地等,如果加上这些约束条件,所需要的时间就无法想象了。约束条件,所需要的时间就无法想象了。所以,很有必要去寻找一些有效算法,解决所以,很有必要去寻找一些有效算法,解决管理中的实际问题。管理中的实际问题
3、。假设条件假设条件1.一个工件不能同时在几台不同的机器上加工。一个工件不能同时在几台不同的机器上加工。2.工工件件在在加加工工过过程程中中采采取取平平行行移移动动方方式式,即即当当上上一一道道工工序完工后,立即送下道工序加工。序完工后,立即送下道工序加工。3.不不允允许许中中断断。当当一一个个工工件件一一旦旦开开始始加加工工,必必须须一一直直进进行到完工,不得中途停止插入其它工件。行到完工,不得中途停止插入其它工件。4.每道工序只在一台机器上完成。每道工序只在一台机器上完成。5.工工件件数数、机机器器数数和和加加工工时时间间已已知知,加加工工时时间间与与加加工工顺顺序无关。序无关。6.每台机器
4、同时只能加工一个工件。每台机器同时只能加工一个工件。排序常用的符号排序常用的符号 Ji-Ji-工件工件i i,i=1,2,.ni=1,2,.n。Mj Mj-机器机器j j,j j1 1,2 2,m.m.pijpij-工件工件JiJi在机器在机器MjMj上的加工时间上的加工时间,j=1,j=1,m,m Pi-Pi-工件工件J Ji i的加工时间;的加工时间;di-di-工件工件J Ji i 的完工期限;的完工期限;Ci-Ci-工件工件J Ji i 的完成时间;的完成时间;Fi-Fi-工件工件J Ji i 的流程时间的流程时间,即工件在车间的实际停留即工件在车间的实际停留时间时间,在工件都已到达的
5、情况下在工件都已到达的情况下,Fi=Pi+WiFi=Pi+Wi Wi-工件工件Ji在加工过程中总的等待时间在加工过程中总的等待时间 Li-Li-工工件件J Ji i 的的延延误误时时间间,Li=Li=Ci-Ci-di di,Li=0 Li0 Li0 延误延误 Fmax-Fmax-最长流程时间,最长流程时间,FmaxFmaxmaxFimaxFi二、排序问题的分类和表示法二、排序问题的分类和表示法1、排序问题的分类:、排序问题的分类:(1)根据机器数的多少根据机器数的多少单台机器的排序问题单台机器的排序问题多台机器的排序问题多台机器的排序问题(2)根据加工路线的特征根据加工路线的特征单件作业排序单
6、件作业排序(JobShop):工件加工路线不同工件加工路线不同流水作业排序流水作业排序(FlowShop):所有:所有工件加工路线完全相同工件加工路线完全相同(3)根据工件到达系统的情况根据工件到达系统的情况静态排序:静态排序:进行排序时,所有工件都已到达,可以一次对他们排序进行排序时,所有工件都已到达,可以一次对他们排序动态排序:动态排序:工件陆续到达,要随时安排他们的加工顺序工件陆续到达,要随时安排他们的加工顺序(4)根据参数的性质)根据参数的性质确定型排序:确定型排序:指加工时间和其他参数是已知确定的量指加工时间和其他参数是已知确定的量随机型排序:随机型排序:指加工时间和有关参数为随机变
7、量指加工时间和有关参数为随机变量(5)根据要实现的目标)根据要实现的目标单目标排序单目标排序多目标排序多目标排序2、排序问题的表示法排序问题的表示法排序问题常用四个符号来描述排序问题常用四个符号来描述:n/m/A/B其中其中,n-工件数;工件数;m-机器数;机器数;A-车间类型;车间类型;F流水作业排序,流水作业排序,P流水作业排列排序流水作业排列排序G一般类型一般类型,即单件型排序即单件型排序B-目标函数目标函数9.2流水作业排序问题流水作业排序问题一、一、最长流程时间最长流程时间Fmax的计算的计算工件工件Si在机器MK 上的完工时间为CKSi工件工件Si在机器MK 上的加工时间为PSiK
8、 C1Si=C1Si-1+PSi1 CKSi=max C(k-1)Si(k-1)Si,CkSi-1kSi-1+PSikSik举例:有一个举例:有一个6/4/p/Fmax问题,其加工时间如下问题,其加工时间如下表所示。当按顺序表所示。当按顺序S(6,1,5,2,4,3)加工时,求加工时,求Fmax。i1 2 3 4 5 6Pi1Pi2Pi3pi44 2 3 1 4 24 5 6 7 4 55 8 7 5 5 54 2 4 3 3 1i6 1 5 2 4 3Pi1Pi2Pi3pi422 4 6 410 212 113 31657 4 11 415 520 727 633512 517 5 22 8
9、 30 535 742 113 4 21 325 2 32 338 446二、两台机器排序问题二、两台机器排序问题两台机器排序的目标是使最大完成时间(总两台机器排序的目标是使最大完成时间(总加工周期)加工周期)Fmax最短最短。实现两台机器排序的最大完成时间实现两台机器排序的最大完成时间Fmax最短最短的目标,一优化算法就是著名的约翰逊法的目标,一优化算法就是著名的约翰逊法(JohnsonsLaw)。其具体求解过程如下例其具体求解过程如下例所示。所示。约翰逊贝尔曼法则约翰逊贝尔曼法则约翰逊法解决这种问题分为约翰逊法解决这种问题分为4个步骤:个步骤:(1)列出所有工件在两台设备上的作业时间。列出
10、所有工件在两台设备上的作业时间。(2)找出作业时间最小者。找出作业时间最小者。(3)如如果果该该最最小小值值是是在在设设备备1上上,将将对对应应的的工工件件排排在在前前面面,如如果果该该最最小小值值是是在在设设备备2上上,则则将对应的工件排在后面。将对应的工件排在后面。(4)排除已安排好的工件,在剩余的工件中排除已安排好的工件,在剩余的工件中重复步骤重复步骤(2)和和(3),直到所有工件都安排完,直到所有工件都安排完毕。毕。举例举例ABAB两台设备完成两台设备完成6 6个零件的加工任务,每个工个零件的加工任务,每个工件在设备上的加工时间如下表所示。求总加件在设备上的加工时间如下表所示。求总加工
11、周期最短的作业顺序。工周期最短的作业顺序。J1J2J3J4J5J6机器机器A A518534机器机器B B722474机器机器工件工件编编号号求解过程求解过程由由约约翰翰逊逊法法可可知知,表表中中最最小小加加工工时时间间值值是是1个个时时间间单单位位,出出现现在在设设备备1上,根据约翰逊法的规则,应将对应的工件上,根据约翰逊法的规则,应将对应的工件2排在第一位,即得:排在第一位,即得:J2-*-*-*-*-*去去掉掉J2,在在剩剩余余的的工工件件中中再再找找最最小小值值,最最小小值值是是2个个时时间间单单位位,它它是出现在设备是出现在设备2上,所以应将对应的工件上,所以应将对应的工件J3排在最
12、后一位,即:排在最后一位,即:J2-*-*-*-*J3再去掉再去掉J3,在剩余的在剩余的J1、J4、J5、J6中重复上述步骤,求解过程为:中重复上述步骤,求解过程为:J2J5-*-*-*-J3J2J5J6-*-*J3J2J5J6-*-J4J3J2J5J6J1-J4J3当同时出现多个最小值时,可从中任选一个。当同时出现多个最小值时,可从中任选一个。J2J5J6-J1-J4J3或或J2J5J1-J6-J4J3i2 5 6 1 4 3Pi1Pi211 34 48 513 518 82623 7 11 415 722 426 228i2 5 1 6 4 3Pi1Pi211 34 59 413 518
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九章 流水作业的排序问题 第九 流水作业 排序 问题
限制150内