搜索
-780-第三十二章作业计划排序的理论与方法是编制车间作业计划的基础。本章将介绍排序问题的基本概念，重点介绍流水作业排序问题。§1流水车间调度问题1.1排序问题的基本概念1.1.1名词术语在生产管理中，常用到“编制作业计划”（Scheduling）、“排序”（Sequencing）、“派工”（Dispatching）、“控制”（Controlling）和“赶工”（Expediting）这些名词。一般说来，编制作业计划与排序不是同义语。排序只是确定工件在机器上的加工顺序。而编制作业计划，则不仅包括确定工件的加工顺序，而且还包括确定机器加工每个工件的开始时间和完成时间。因此，只有作业计划才能指导每个工人的生产活动。由于编制作业计划的主要问题是确定各台机器上工件的加工顺序，而且，在通常情况下都是按最早可能开(完)工时间来编排作业计划的。因此，当工件的加工顺序确定之后，作业计划也就确定了。所以，人们常常不加区别地使用“排序”与“编制作业计划”这两个术语。在本章里，讲排序的时候就暗指相应的作业计划是最早时间作业计划。只有在需要的时候，才将这两个术语区别使用。“派工”是按作业计划的要求，将具体生产任务安排到具体的机床上加工，属于我们经常说的“调度”范围。“赶工”是在实际进度已落后于计划进度时采取的行动，也属于“调度”范围。“调度”是实行控制所采取的行动。“编制作业计划”是加工制造发生之前的活动；“调度”是在加工制造发生之后的活动。调度的依据是作业计划。比如，火车时刻表是一种作业计划，火车发生晚点，就要进行调度。调度是一种现场指挥。描述排序问题的名词术语来自加工制造行业。为了和惯用的名词术语保持一致，本书仍使用“机器”、“工件”、“工序”和“加工时间”等术语来描述各种不同的排序问题。但要注意，它们已不限于本来的含义。这里所说的“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者”；工件则代表“服务对象”。工件可以是单个零件，也可以是一批相同的零件。假定有n个工件要经过m台机器加工。“加工路线”是工件加工的工艺过程决定的，它是工件加工在技术上的约束。比如，某工件要经过车、铣、占、磨的路线加工，我们可以用4321,,,MMMM来表示。一般地，可用mMMM,,,21L来表示加工路线。“加工顺序”则表示每台机器加工n个工件的先后顺序，是排序要解决的问题。1.1.2假设条件与符号说明为了便于分析研究，建立数学模型，有必要对排序问题提出一些假设条件。①一个工件不能同时在几台不同的机器上加工。②工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。③不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。④每道工序只在一台机器上完成。⑤工件数、机器数和加工时间已知，加工时间与加工顺序无关。⑥每台机器一次只能加工一个工件。-781-在下面的讨论中，如不作特别说明，都是遵循以上假设条件的。下面对有关符号进行说明。iJ：工件i，ni,,2,1L=；jM：机器j，mj,,2,1L=；ijt：iJ在jM上的加工时间，iJ的总加工时间为∑==mjijitT1；ijh：iJ在jM上的等待时间，iJ的总等待时间为∑==mjijihH1；ir：iJ的到达时间，指iJ从外部进入车间，可以开始加工的最早时间；id：iJ的完工期限；ijc：iJ在jM上的完工时间；iC：iJ的完工时间，iiimjijijiiTHrthrC++=++=∑=1)(；maxC：最长完工时间，}{max1maxinicC≤≤=；iF：iJ的流程时间，即工件在车间的实际停留时间，iiiiiTHrCF+=−=；maxF：最长流程时间，}{max1maxiniFF≤≤=；iL：工件的延迟时间，iiidCL−=；当0iL（正延迟），说明iJ的实际完工时间超过了完工期限；当0iL（负延迟），说明iJ提前完工；当0=iL（零延迟），iJ按期完工。maxL：最长延迟时间，}{max1maxiniLL≤≤=。1.1.3排序问题的分类和表示法排序问题有不同的分类方法。最常用的分类方法是按机器、工件和目标函数的特征分类。按机器的种类和数量不同，可以分成单台机器的排序问题和多台机器的排序问题。对于多台机器的排序问题，按工件加工路线的特征，可以分成单件作业(Job-shop)排序问题和流水作业(Flow-shop)排序问题。工件的加工路线不同，是单件作业排序问题的基本特征；而所有工件的加工路线完全相同，则是流水作业排序问题的基本特征。按工件到达车间的情况不同，可以分成静态的排序问题和动态的排序问题。当进行排序时，所有工件都已到达，可以一次对它们进行排序，这是静态的排序问题；若工件是陆续到达，要随时安排它们的加工顺序，这是动态的排序问题。按目标函数的性质不同，也可划分不同的排序问题。譬如，同是单台机器的排序，目标是使平均流程时间最短和目标是使误期完工工件数最少，实质上是两种不同的排序问题。按目标函数的情况，还可以划分为单目标排序问题与多目标排序问题。以往研究的排序问题，大都属于单目标排序问题，而对多目标排序问题则很少研究。另外，按参数的性质，可以划分为确定型排序问题与随机型排序问题。所谓确定型排序问题，指加工时间和其它有关参数是已知确定的量；而随机型排序问题的加工时间和有关参数为随机变量。这两种排序问题的解法本质上不同。由机器、工件和目标函数的不同特征以及其它因素上的差别，构成了多种多样的排序问题。对于本节要讨论的排序问题，我们将用Conway等人提出的方法来表示。这个-782-方法只用4个参数就可以表示大多数不同的排序问题。4参数表示法为：BAmn///其中,n－工件数；m－机器数；A－车间类型，在A的位置若标以“F”，则代表流水作业排序问题。若标以“P”，则表示流水作业排列排序问题。若标以“G”，则表示一般单件作业排序问题。当1=m，则A处为空白。因为对于单台机器的排序问题来说，无所谓加工路线问题，当然也就谈不上是流水作业还是单件作业的问题了。B－目标函数，通常是使其值最小。有了这4个符号，就可以简明地表示不同的排序问题。例如，max//3/CPn表示n个工件经3台机器加工的流水作业排列排序问题，目标函数是使最长完工时间maxC最短。1.2流水作业排序问题流水作业排序问题的基本特征是每个工件的加工路线都一致。在流水生产线上制造不同的零件，遇到的就是流水作业排序问题。我们说加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。如果某些工件不经某些机器加工，则设相应的加工时间为零。一般说来，对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。但本节要讨论的是一种特殊情况，即所有工件在各台机器上的加工顺序都相同的情况。这就是排列排序问题。流水作业排列排序问题常被称作“同顺序”排序问题。对于一般情形，排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解；对于仅有2台和3台机器的特殊情况，可以证明，排列排序问题下的最优解一定是相应流水作业排序问题的最优解。本节只讨论排列排序问题。1.2.1最长流程时间maxF的计算本节所讨论的是max///FPmn问题，目标函数是使最长流程时间最短。最长流程时间又称作加工周期，它是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零（0=ir，ni,,2,1L=），所以maxF等于排在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时间maxC。设n个工件的加工顺序为},,,{21nsssSL=，其中is为排第i位加工的工件的代号。以ksic表示工件is在机器kM上的完工时间，ksit表工件is在kM上的加工时间，ni,,2,1L=；mk,,2,1L=，则ksic可按以下公式计算：1111sstc=kskskstcc1111,+=−，mk,,2L=（1）1111iiissstcc+=−，ni,,2L=（2）ksksksksiiiitccc+=−−},max{1,1，ni,,2L=，mk,,2L=（3）当0=ir，ni,,2,1L=时，最大流程时间为-783-msncF=max（4）当由式（3）得出msnc时，maxF就求得了。在熟悉以上计算公式之后，可直接在加工时间矩阵上从左到右计算完工时间。下面以一例说明。例1有一个max//4/6FP问题，其加工时间如表1所示。当按顺序,2,5,1,6(=S)3,4加工时，求maxF。表1加工时间矩阵i1234561it4231422it4567453it5875554it424331解：按顺序S＝(6,1,5,2,4,3)列出加工时间矩阵，如表2所示。按式（1）～（3）进行递推，将每个工件的完工时间标在其加工时间的后面。对于第一行第一列，只需把加工时间的数值作为完工时间标在加工时间的后面。对于第一行的其它元素，使用迭代公式（1），只需从左到右依次将前一列后面的数字加上计算列的加工时间，将结果填在计算列加工时间的后面。对于从第二行到第m行，第一列的算法相同，使用迭代公式（2），只要把上一行后面的数字和本行的加工时间相加，将结果填在本行加工时间的后面；从第2列到第n列，使用迭代公式（3），则要从本行前一列后面数字和本列上一行后面数字中取大者，再和本列加工时间相加，将结果填在本列加工时间的后面。这样计算下去，最后一行最后一列的后面数字，即为msnc，也是maxF。计算结果如表2所示。本例46max=F。表2顺序S下的加工时间矩阵i6152431it2，24，64，102，121，133，162it5，74，114，155，207，276，333it5，125，175，228，305，357，424it1，134，213，252，323，384，46计算的Matlab程序如下：clc,cleart=[423142456745587555424331]';s=[615243];st=t(s,:);%提出指定顺序的时间矩阵[n,m]=size(st);c(1,:)=cumsum(st(1,:));%计算c的第一行c(2:n,1)=c(1,1)+cumsum(st(2:n,1));%计算c的第一列的除第1个元素外其它元素-784-fori=2:nfork=2:mc(i,k)=max(c(i-1,k),c(i,k-1))+st(i,k);endendds=c'%显示计算结果Fmax=ds(end)%显示最后一个元素1.2.2max//2/FFn问题的最优算法对于以最大流程时间为目标的两台机器流水车间问题称为Johnson问题，其最优调度由著名的Johnson规则确定。Johnson规则的基本思想为后来m台机器问题的启发式算法提供了基础。假定有n个工件，在第一台机器和第二台机器上的加工时间分别为1it，ni,,1L=和2it，ni,,1L=，最优调度由如下规则给出：Johnson规则：如果},min{},min{1221jijitttt≤，则最优调度中工件i排在工件j之前。最优顺序可以直接利用Johnson规则通过两个工序之间的检查来构造。Johnson算法可以描述为:步骤1：令}|{21iittiU≤=，}|{21iittiV=；步骤2：对U中的工件按1it非减顺序调度；步骤3：对V中的工件按2it非增顺序调度；步骤4：有序集U放到V之前构成工件的最优加工顺序。例2求表3所示的max//2/8FF问题的最优解。表38工件问题的实例i123456781it521763752it26256721本例的解构造如下：步骤1：工件集}6,5,3,2{=U和}8,7,4,1{=V；步骤2：U中的工件调度为工件i：32651it：1236步骤3：V中的工件调度为工件i：47181it：5221步骤4：最优顺序为)8,1,7,4,5,6,2,3(。计算的Matlab程序如下：clc