排序问题

第8章 制造业作业计划与控制,8.1 排序的基本概念 8.2 流水作业计划问题 8.3 单件作业排序问题,8.1 排序的基本概念,排序与编制作业计划 编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。 工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间； 医院要安排病人手术，为此要安排手术室、配备手术器械、手术医师和护士； 学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课。 排序，给出零部件在一台或一组设备上加工的先后顺序的工作。 在编制作业计划过程中,有一个问题需要管理人员注意，即投入生产过程的作业顺序的安排。 编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。,确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。 例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1 billion个顺序, 全部检验完毕需要8.41015个世纪. 如果只有16个工件, 同样按每秒钟可以检查1 billion个顺序计算, 也需要2/3年. 以上问题还没有考虑其他的约束条件, 如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。 所以，很有必要去寻找一些有效算法，解决管理中的实际问题。,排序问题的分类 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 根据加工路线的特征 单件车间排序(Job Shop) 流水型排序(Flow Shop) 根据工件到达系统的情况 静态排序 动态排序 根据参数的性质 确定型排序 随机型排序 根据要实现的目标 单目标排序 多目标排序,排序问题的一般假设 为便于分析研究，建立数学模型，除非特别说明，本课程对排序问题有如下假设： 一个工件不能同时在几台机器上加工 工件在加工过程中采取平行移动方式，即上一道工序完工后，立即送下道工序加工 不允许中断，当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件 每道工序只在一台机器上完成 工件数、机器数和加工时间已知，加工时间与加工顺序无关 每台机器同时只能加工一个工件,排序常用的符号 Ji-工件i，i=1,2,n Mj-机器j，j=1,2,m di-工件i的交货期 Pij-工件i在机器j上加工时间, 系统内有Pi=jPij Wij-工件i在机器j的等待时间, 系统内有Wi=jWij Ci-工件i的完成时间, 在工件都已到达的情况下, Ci= Pi+ Wi Fi-工件i的流程时间，在工件都已到达的情况下, Fi= Pi+ Wi Li-工件i的延误时间, Li= Ci- di . Li0 延误 Ti-工件i的延期量, Ti=max0, Li Ei-工件i提前完成的时间,排序问题的表示方法 排序问题常用四个符号来描述: n/m/A/B 其中, n-工件数； m-机器数； A-车间类型, F=流水型排序 P=排列排序 G=一般类型,即单件型排序 B-目标函数,8.2 流水作业计划问题,流水线是流水车间(Flow shop) 典型的代表，每个零件的加工路线都一致。 只要加工路线一致：M1, M2, M3，., Mm,不要求每个零件都经过每台机器加工，如果某些工件不经过某些机器加工，则设相应的加工时间为零即可。 一般来说，对于流水车间的排序问题，工件在不同的机器上的加工顺序不尽相同。 排列排序问题：所有工件在各机器上的加工顺序都是相同的。 最长流程时间Fmax又称作加工周期,最长流程时间Fmax 又称作加工周期 设n个工件的加工顺序为S=(s1,s2,sn)，Cj(si)为工件si在机器Mj上的完工时间，psij表示工件在Mj上的加工时间，则可按下式计算Cj(si) C1(si) C1(si-1)+ psi1 Cj(si)maxCj-1(si), Cj(si-1)+ psij Fmax= Cm(sn) 这是个递推公式，从j=1,i=1开始，最后可以得到Fmax,加工周期为46,表8-2 顺序S下的加工时间矩阵,【例8-1】6/4/p/ Fmax问题，当按顺序S( 6,1,5,2,4,3)加工时，求Fmax。,表8-1 加工时间矩阵,2,6,10,12,13,16,7,12,13,11,15,20,27,33,17,22,30,35,42,21,25,32,38,46,n/2/F/Fmax问题的含义 n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。,图8-1 n/2/F/Fmax系统,n/2/F/Fmax问题的目标,n/2/F/Fmax问题的目标是使最大完成时间（总加工周期）Fmax最短。 Fmax的含义见如下的甘特图(Gantt Chart)。,多台机器排序的目标一般也是使最大完成时间（总加工周期） Fmax最短。,图8-2 n/2/F/Fmax问题,n/2/F/Fmax问题的算法 一个优化算法就是著名的约翰逊法(Johnsons Law)。其具体求解过程分为4个步骤： (1)列出所有工件在两台设备上的作业时间。 (2)找出作业时间最小者。 (3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。 (4)排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)，直到所有工件都安排完毕。,【例8-2】某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。,加工周期为30,解：由约翰逊法可知，表中最小加工时间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得： J4 - * - * - * - * 去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备2上的，所以应将对应的工件J1排在最后一位，即： J4 - * - * - * - J1 再去掉J1，在剩余的J2、J3、J5中重复上述步骤，求解过程为： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 当同时出现多个最小值时，可从中任选一个。最后得 J4 - J2 - J3- J5 - J1 经计算，初始作业顺序的总加工周期是30，用约翰逊法排出的作业顺序总加工周期是26，显然后者的结果优于前者。,问题算法的扩展(Extension to Three Machines),一般情况下，当机器数为3台以上时，就很难找到最优解了。 但是，对于n个工件由三台机器流水作业时，在满足某些条件后可以采用Johnsons Law解决问题。 设：A、B、C为三台机器，如果工件在三台机器上的加工时间满足以下条件，则可以转化为两台机器的排序问题： min Ai=max Bi or min Ci = max Bi 定义：Ai = Ai+ Bi , Bi = Bi +Ci,【例8-3】考虑以下问题： 5个工件由3台机器加工, 作业时间见下表。 求: 总加工周期最短的作业顺序。,解: 检查上表, 发现: min Ai = 4 max Bi = 6 min Ci = 6 因此,满足以上条件, 建立两台机器的作业时间表:,表8-4 加工时间矩阵,应用Johnson法则，得出： 总加工周期为：,表8-5 两台机器的加工时间矩阵,表8-6 三台机器的加工时间矩阵,一般n/m/P/Fmax问题近优解的启发式算法,一般采用启发式算法(Heuristics)解决这类问题。 关键工件法,步骤1 计算 ,找出其中最大者，定义为关键工件JC。,步骤2 除JC外，将满足ti1tim的工件，按ti1值的大小，从小到大排在JC的前面。,步骤3 除JC外，将满足ti1tim的工件，按tim值的大小，从大到小排在JC的后面。,步骤4 除JC外，将满足ti1=tim的工件，排在JC的前面或者后面。,步骤5 如有多个方案，可再加比较，从中选优。,【例8-4】关键工件法举例,找出关键工件：工作负荷最大的40，对应的是工件6，所以JC=J6,确定排在关键工件前面的工件：满足步骤2条件的有J4, J5, 所以有J4 J5 J6 ,确定排在关键工件后面的工件：满足步骤3条件的有J2, J3, 所以有 J6 J2 J3,满足步骤4条件的有J1, 所以有 J6 J1， 或者J1 J6,最后有：J4 J5 J6 J1 J2 J3 ， 或者 J4 J5 J1 J6 J2 J3,8.3 单件作业排序问题,加工描述矩阵和加工时间矩阵,无延迟作业计划的构成,我们称每安排一道工序称作一“步”，设 Stt步之前已排序工序构成的部分作业计划； Ot 第t步可以排序的工序的集合； Tk Ot 中工序Ok的最早可能开工时间； Tk Ot 中工序Ok的最早可能完工时间。,无延迟作业计划的构成步骤:, 设t1，S1为空集，O1为各工件第一道工序的集合。 求T*minTk，并求出T*出现的机器M*。如果M*有多台，则任选一台。 从Ot中挑出满足以下两个条件的工序Oj：需要机器M*加工，且TjT*。 将确定的工序Oj放入St，从 Ot 中消去Oj，并将Oj的紧后工序放入 Ot ，使tt1。 若还有未安排的工序，转步骤；否则，停止。,例【8-5】,表8-7 2/3/G/Fmax的无延迟作业计划,图8-3 无延迟作业计划,优先派工法则,在介绍无延迟作业计划的构成步骤时，其中第步的两个条件一般都有多个工序可以满足。按什么样的准则来选择可安排的工序，对作业计划的优劣有很大影响。为了得到所希望的作业计划，人们提出了很多优先调度法则，按优先调度法则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。 迄今，人们已提出了100多个优先调度法则，其中主要的有下8个： SPT(Shortest Processing Time)法则 优先选择加工时间最短的工序。 FCFS(First Come First Served)法则 优先选择最早进入可排工序集合的工件。,优先派工法则(续), EDD(Earliest Due Date)法则 优先选择完工期限紧的工件。 MWK