5作业计划与控制11.13

第5章作业计划与控制

OperationsSchedulingandControlling排序问题的基本概念单台机器的排序问题多台机器的排序问题生产作业控制编制作业计划要解决的问题任务分配：每个工人、每个工作地的日生产任务编制作业计划（Scheduling）：将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题工厂：对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间医院：安排病人手术——安排手术室、配备手术器械、手术医师和护士学校：安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课项目计划管理：作业计划生产排序：通过排序方法编制生产计划，提高生产效率5.1排序的基本概念

作业计划与排序是一回事么？作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。排序，给出零部件在一台或一组设备上加工的先后顺序的工作。编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。根据排序规则对每一个到达的工件安排作业顺序工作地工件排队等待加工来自上游工作地的工件加工完毕的工件流向下一工作地排序的概念生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。目的：提高设备或工作中心的效率、减少在制品占用量、缩短生产周期、保证按期交货作业排序（sequencing）的目标作业排序是解决各个生产层次中生产任务的加工顺序问题，既包括哪个生产任务先投产，哪个生产任务后投入，还包括在同一设备上不同工件的加工顺序。作业排序（sequencing）：确定工件在设备上的加工顺序。作业计划（scheduling）：不仅包括确定工件的加工顺序，还包括确定设备加工每个工件的开始时间和结束时间。排序的目标：如何在尽可能满足各种约束条件的情况下，给出一个令人满意的排序方案。一、有关的名词术语排序(Sequencing)：确定零件在机器上的加工顺序编制作业计划(Scheduling)：加工制造发生之前的活动（火车时刻表）。包括确定加工顺序、加工任务的分配和加工每个零件的开始和完成时间调度：作业计划编制后实施生产控制所采取的一切行动（火车运行的安排，发生晚点后的处理）派工（Dispatching）：在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人赶工（Expediting）：在实际进度已落后于计划进度时采取的行动控制（Controlling）：机器：表示“服务者”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元零件：代表“服务对象”。可以是单个零件，也可以是一批相同的零件加工路线：零件加工经过不同机器构成的路线。（某零件要经过车、铣、占、磨的路线加工，我们可以用M1,M2,M3,M4来表示）加工顺序：表示每台机器加工n个零件的先后顺序，是排序要解决的问题4参数表示法R.W.Conway等人在《TheoryofScheduling》中提出的表示方法，该方法只用4个参数就可以表示大多数不同的排序问题。即：

n/m/A/Bn──零件数m──机器数A──作业类型在A的位置若标以“F”，则代表流水作业排序问题若标以“P”，则表示流水作业排列排序问题若标以“G”，则表示一般单件作业排序问题当m＝1，则A处为空白，因为对于单台机器的排序问题来说，无所谓加工路线问题B──目标函数，通常是使其值最小例：二、排序常用的符号

Ji----工件i，i=1,2,....ndi----工件i的交货期Pi----工件i的加工时间,,pij----工件i在机器j上的加工时间,j=1,…,mWi----工件i在系统内的等待时间,,wij----工件i在机器j前的等待时间,j=1,…,m

Ci----工件i的完成时间,在工件都已到达的情况下,Ci=Pi+WiFi----工件i的流程时间，在工件都已到达的情况下,Fi=Pi+WiLi----工件i的延误时间,Li=Ci-di,Li<=0按期或完成提前；Li>0延误Ti----工件i的延期量,Ti=max{0,Li}Ei----工件i提前完成的时间作业排序的基本分析

1、作业排序的一般假设：（1）一台设备不得同时加工两个或两个以上的任务；（2）一个任务不能同时在几台设备上加工；（3）每个任务必须按照工艺顺序进行加工。

2、作业排序所需的有关生产信息：任务Ji在第j个工序Oij（j=1,2,…，Ni，i=1,2,…，M）在相应的设备上Mij（i,j=1,2,…N）上所需要的加工时间为tij，Ji的可能开始时刻为ri和应完工的交货期di。

3、作业排序的一般结论：

平均流程时间的最优排序方案对于平均完工时间、平均延迟以及平均等待时间也是最优的。但是这一结论对于Fmax和其他最大值目标是不成立的。排序问题分类按机器单台机器排序问题多台机器排序问题单件作业排序问题流水线作业排序问题按零件到达车间的情况静态的排序问题动态的排序问题按目标函数的性质分类按参数确定型排序问题随机型排序问题三、排序问题的分类单台机器的排序问题

n个工件全部经由一台机器处理

J1J2J3Jn机器到达系统工件的集合离开系统（机器）

为实现任务总等待时间最短的目标，保证尽可能多的对象早日加工出来，加速资金周转，只需根据最短加工时间准则对加工对象排序即可。n项任务在两台机器的排序问题

n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。机器1到达系统工件的集合离开系统（机器）J1J2J3Jn机器211.2流水作业排序问题流水线是流水车间(Flowshop)典型的代表，每个零件的加工路线都一致。只要加工路线一致：M1，M2,

M3，…..，Mm,不要求每个零件都经过每台机器加工流水线加工方式一、最长流程时间Fmax的计算最长流程时间又称作加工周期（1）问题的描述和表示描述：n个不同零件要按相同的加工路线经过m台机器加工，目标是使这批零件的加工周期最短（加工路线确定，对不同的零件，根据目标求各个零件的加工次序）表示

（2）求解加工周期

加工周期是指第一个零件在第一台机器上开始加工到最后一个零件在最后一台机器上完成加工为止，所需要的时间假设，n个零件的加工顺序为S=(S1,S2……,Sn)Si为排在i位加工的零件代号CkSi表示零件Si在机器Mk上的完工时间PSik表示零件Si在Mk上的加工时间k=1,2,3,……,m，i=1,2,3,……,n总加工周期的计算方法工件在两台设备上的加工时间工件编号J1J2J3J4J5设备A36715设备B28643例:在设备A和B上安排5个工件的加工任务，每项任务的作业时间如下表所示。求:该顺序的总加工周期Fmax。图解法：30AB0表格法工件编号J1J2J3J4J5设备A3369716117522设备B25817623427330Fmax=306/4/p/Fmax问题，当按顺序S＝(6,1,5,2,4,3)加工时，求Fmax.

加工周期为46（1）描述和表示描述：n个零件经过2台机器加工，使加工周期最短的流水作业排序问题表示（2）求解方法Johnson算法二、2台机器的排序问题求解算法n/2/F/Fmax问题的最优算法Johnson算法：

(1)列出所有工件在两台设备上的作业时间。(2)找出作业时间最小者。(3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。(4)排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)，直到所有工件都安排完毕。例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。工件在两台设备上的加工时间工件编号J1J2J3J4J5设备A36715设备B28643

求最优顺序算法步骤的改进把Johnson算法作些改变，改变后的算法按以下步骤进行：①将所有ai≤bi的零件按ai值不减的顺序排成一个序列A。②将所有ai＞bi的零件按bi值不增的顺序排成一个序列B。③将A放到B之前，就构成了最优加工顺序

序列A为(2，5，6，1)，序列B为(4，3)，构成最优顺序为(2，5，6，1，4，3)，与Johnson算法结果一致。

Johnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例11-2顺序(2，5，6，4，1，3)不符合Johnson法则，但它也是一个最优顺序

对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。对于一般的流水车间排列排序问题，可以用分支定界法。一般的流水车间排列排序问题如想求得精确解可用分支界定法，但计算量比较大，以至于计算机也无法求解，因此常用一些启发式算法求近似解

（一）Palmer法按零件的斜度指标排列零件的启发式算法零件的斜度指标三、一般n/m/P/Fmax问题的启发式算法按照各零件λi不增的顺序排列零件，可得出令人满意的顺序，如果排列的结果有多个，可以通过计算Fmax，取其中最优Fmax对应的排序作为排序结果。例，有一个4/3/F/Fmax问题，其加工时间如下表所示，试用Palmer法求解

Plamer法解：计算λi按照Palmer计算公式步骤1计算,找出其中最大者，定义为关键工件JC。步骤2除JC外，将满足pi1<=pim的工件，按ti1值的大小，从小到大排在JC的前面。步骤3除JC外，将满足pi1>pim的工件，按tim值的大小，从大到小排在JC的后面。步骤4如有多个方案，可再加比较，从中选优。（二）关键工件法

关键工件法举例J1J2J3J4J5J6机器1pi15541210机器2pi25553610机器3pi3833474机器4pi4282156机器5pi55212810总和252315112840找出关键工件：工作负荷最大的40，对应的是工件6，所以JC=J6确定排在关键工件前面的工件：满足步骤2条件的有J4,J5,J1，所以有J4–J5–J1-J6–确定排在关键工件后面的工件：满足步骤3条件的有J2,J3,所以有–J6–J2–J3最后有：J4–J5–J1–J6–J2–J3

关键零件法求近优解举例第三节单件作业计划问题一、任务分配问题二、单间作业排序问题三、优先派工法则一、任务分配问题把零件分配给工人或机器加工，将区域分配给销售人员，将出故障的机器分配给维修小组等，都是任务分配问题。求解任务分配问题的目标是使任务与资源得到最佳匹配。匈牙利算法1、将每行的元素减去行中的最小元素，如果某列中没有出现0元素，再将该列元素减去列中的最小元素。2、测试是否已达到最佳分配组合。求出能够穿越所有0的最小线数，如果此数等于矩阵的阶，直接进入第4步。否则继续第3步。3、将没有被直线覆盖的元素减去其中的最小元素，并将各直线交点上的元素加上该最小元素。然后返回第2步。4、进行分配：从0元素最少的行或列开始，选择一个0，然后划去同行和同列的其他0。如此反复进行，直到所有0元素都被选择或划去为止。例：根据给定数据，求解各项作业与机器的最佳分配。机器ABCD工作18624工作2671110工作33576工作4510129解：1、行作业与列作业：保证每行每列都有0存在。机器ABCD工作16300工作20052工作30141工作404722、用最少的直线划去所有0元素。机器ABCD工作16300工作20052工作30141工作404723、将剩余元素减去其中的最小元素1，并将各直线交点的元素加上1。机器ABCD工作17400工作20041工作30130工作40461机器ABCD工作17400工作20041工作30130工作404614、用最少的直线划去所有0元素。5、分配机器ABCD工作17400工作20041工作30130工作40461所选0元素的数目等于4，故试分配成功。分配方案如下：分