资源描述：
《排序问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第8章制造业作业计划与控制8.1排序的基本概念8.2流水作业计划问题8.3单件作业排序问题18.1排序的基本概念排序与编制作业计划编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间；医院要安排病人手术，为此要安排手术室、配备手术器械、手术医师和护士；学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课。排序，给出零部件在一台或一组设备上加工的先后顺序的工作。在编制作业计划过程中,有一个问题需要管理人员注意，即投入生产过程的作业顺序的安排。编制作业计划与排序的概
2、念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。2确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪.如果只有16个工件,同样按每秒钟可以检查1billion个顺序计算,也需要2/3年.以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。
3、3排序问题的分类根据机器数的多少单台机器的排序问题多台机器的排序问题根据加工路线的特征单件车间排序(JobShop)流水型排序(FlowShop)根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序根据要实现的目标单目标排序多目标排序4排序问题的一般假设为便于分析研究，建立数学模型，除非特别说明，本课程对排序问题有如下假设：一个工件不能同时在几台机器上加工工件在加工过程中采取平行移动方式，即上一道工序完工后，立即送下道工序加工不允许中断，当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件每道工序只在一台机器上完成工件数、机器数和加工时间已知，加工时间与加
4、工顺序无关每台机器同时只能加工一个工件5排序常用的符号Ji----工件i，i=1,2,....nMj----机器j，j=1,2,....mdi----工件i的交货期Pij----工件i在机器j上加工时间,系统内有Pi=∑jPijWij----工件i在机器j的等待时间,系统内有Wi=∑jWijCi----工件i的完成时间,在工件都已到达的情况下,Ci=Pi+WiFi----工件i的流程时间，在工件都已到达的情况下,Fi=Pi+WiLi----工件i的延误时间,Li=Ci-di.Li<=0按期或完成提前；Li>0延误Ti----工件i的延期量,Ti=max{0,Li}Ei----工件i提前完成的
5、时间6排序问题的表示方法排序问题常用四个符号来描述:n/m/A/B其中,n-----工件数；m-----机器数；A----车间类型,F=流水型排序P=排列排序G=一般类型,即单件型排序B-----目标函数78.2流水作业计划问题流水线是流水车间(Flowshop)典型的代表，每个零件的加工路线都一致。只要加工路线一致：M1,M2,M3，….,Mm,不要求每个零件都经过每台机器加工，如果某些工件不经过某些机器加工，则设相应的加工时间为零即可。一般来说，对于流水车间的排序问题，工件在不同的机器上的加工顺序不尽相同。排列排序问题：所有工件在各机器上的加工顺序都是相同的。最长流程时间Fmax又称作加
6、工周期8最长流程时间Fmax又称作加工周期设n个工件的加工顺序为S=(s1,s2,…,sn)，Cj(si)为工件si在机器Mj上的完工时间，psij表示工件在Mj上的加工时间，则可按下式计算Cj(si)C1(si)＝C1(si-1)+psi1Cj(si)＝max{Cj-1(si),Cj(si-1)}+psijFmax=Cm(sn)这是个递推公式，从j=1,i=1开始，最后可以得到Fmax9加工周期为46iPi1Pi2Pi3Pi4表8-2顺序S下的加工时间矩阵【例8-1】6/4/p/Fmax问题，当按顺序S＝(6,1,5,2,4,3)加工时，求Fmax。i123456Pi1423142Pi24
7、56745Pi3587555Pi4424331表8-1加工时间矩阵62551144545445322582417533367426101213167121311152027331722303542212532384610n/2/F/Fmax问题的含义n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。机器1到达系统工件的集合离开系统J1J2J3…Jn机器2图8-1n/2/F/Fmax系统11n/2/F
