第十章作业计划

第十章作业计划教材第11章P2871第十章作业计划教学目的：了解车间作业管理的主要工作了解作业排序的目标与分类掌握制造业作业排序的一般方法与数学方法2学习内容编制生产作业计划的实质作业计划编制的相关概念2台机器排序问题的最优算法n/m/P/Fmax的启发式算法指派问题及其启发式算法3？MRP后企业该干什么通过MRP确定各车间的零部件投入出产计划，从而将全厂性的产品出产计划变成了各车间的生产任务。各车间要完成生产任务还必须将零部件投入出产计划转化为车间生产作业计划，将计划安排到具体的机器和个人。因而牵涉到任务分配和作业排序问题。4任务分配问题假定甲单位有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成A、B、C、D、E五项任务，每个员工完成每项工作所需要耗费的工作时间不同。问：员工与任务之间应当如何进行配置，才能保证完成工作任务的时间最短？5123？从哪一项工作开始4.5小时8.5小时4.5小时拟稿时间5小时7小时8小时审稿时间作业排序问题61车间作业管理的工作内容核实MRP产生的计划清单检查物料、能力、工具等的可用性下达生产订单说明零件加工工序顺序和时间监控在制品生产与车间生产相关的其它工作72生产作业计划

2.1编制生产作业计划的实质-1将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题，包括确定零部件产品的加工顺序，加工任务的分配和加工每件零件开始时间和完成时间的确定。82.2有关的名词术语排序确定零件在机器上的加工顺序。调度作业计划编制之后实施生产控制采取的一切行动。派工在作业计划制定后，按照作业计划要求，将具体的生产任务分配到具体的机床和工人。92.3排程的基本要求一个好的排程能满足什么要求?完成时间最短设备使用率最大化在制品库存量最小等待时间最少对于这些要求衡量的标准是什么?成本与利润

每件工作的平均完成时间设备运行的时间百分比系统的平均库存数量平均延迟天数102.4排程问题的分类-1按机器种类和数量分类单台机器的排序问题多台机器的排序问题单件作业排序问题(Job-Shop)－零件加工路线不同流水作业排序问题(Flow-Shop)－所有零件的加工路线完全相同112.4排程问题的分类-2按工件到达车间的情况不同静态排序问题－所有零件都已到达，一次排序动态排序问题－零件陆续到达，随时排序按参数的性质确定型排序问题－加工时间等参数为已知量随机型排序问题－加工时间等参数为随机变量12零件数机器数车间类型目标函数N个零件经过3台设备加工的流水作业排列排序问题，目标函数是使最长完工时间C最短F：流水线作业排序问题

P：流水线作业排列排序问题

G：一般单件作业排序问题

B：目标函数，通常是使其最小2.5排序问题的四参数表示方法-Conway133作业排序的一般方法－－甘特图

3.1概述甘特图（Ganttchart）又叫横道图、条状图(Barchart)。它是以图示的方式通过活动列表和时间刻度形象地表示出任何特定项目的活动顺序与持续时间。它是在第一次世界大战时期发明的，以亨利·L·甘特先生的名字命名，他制定了一个完整地用条形图表示进度的标志系统。由于甘特图形象简单，在简单、短期的项目中，甘特图都得到了最广泛的运用。14甘特图153.2甘特图的含义-1甘特图内在思想简单，基本是一条线条图，横轴表示时间，纵轴表示活动(项目)，线条表示在整个期间上计划和实际的活动完成情况。它直观地表明任务计划在什么时候进行，及实际进展与计划要求的对比。管理者由此极为便利地弄清一项任务(项目)还剩下哪些工作要做，并可评估工作是提前还是滞后，亦或正常进行。是一种理想的控制工具。163.2甘特图的含义-2甘特图包含以下三个含义：1、以图形或表格的形式显示活动；2、现在是一种通用的显示进度的方法；3、构造时应包括实际日历天和持续时间，并且不要将周末和节假日算在进度之内。173.3两种基本形式的甘特图作业进度图表示一项工作的计划开始日期、计划完成日期以及现在的进度。机器图描述不同工作在每一台机器上的工作次序，也可用来管理生产进度。18SMTWTFSDayJobJobAJob

BJobCRepairUsedtomonitorjobprogressTodayGanttSchedulingChart注明：计划使用时间实际工作进度19UsedtodescribetheworksequenceoneachmachineGanttMachineChartWorkCenterMTWThFSheetMetalJob

AJobFMechanicalJobDJobGElectricalJobBJobHPaintingJobCJobEJobI注明设备空闲时间203.4甘特图的优点图形化概要，通用技术，易于理解；中小型项目一般不超过30项活动；有专业软件（微软项目管理软件(MicrosoftProject）支持，无须担心复杂计算和分析。213.5甘特图的不足甘特图事实上仅仅部分地反映了项目管理的三重约束（时间、成本和范围），因为它主要关注进程管理（时间）；软件的不足。尽管能够通过项目管理软件描绘出项目活动的内在关系，但是如果关系过多，纷繁芜杂的线图必将增加甘特图的阅读难度；224流水车间作业计划问题

4.1加工周期的计算-1n个不同的零件要按相同的加工路线经过m台机器加工，目标是使这批零件的加工周期最短，这种流水车间作业排序问题是本节所讨论的n/m/P/Fmax问题。加工周期又称为最长流程时间，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。234.1加工周期的计算-2按给出的顺序S列出加工时间矩阵。将每个零件的完工时间标在其右上角。对于第一行第一列的元素其完工时间为自身加工时间；对于第一行的其它元素，只需从左到右依次将上一列的数值加上计算列的加工时间；对于第一列的其它元素，只需从上到下依次将上一行的数值加上计算行的加工时间；对于其它元素则要从本行前一列右上角数字和本列上一行的右上角数字中取大者，加上元素的加工时间。最后一行的最后一列右上角数字，即为加工周期。24i123456Pi1423142Pi2456745Pi3587555Pi4424331例：有一个6/4/P/Fmax问题，其加工时间如下表，当按照顺序S=（6，1，5，2，4，3）加工时，求Fmax25i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi411342132523233844626123？从哪一项工作开始4.5小时8.5小时4.5小时拟稿时间5小时7小时8小时审稿时间27优先规则：Johnson规则列好时间表，从中选最小；若在第一列，将其排在首；若在第二列，将其排在尾。J1J2J3J412n/2/P/Fmax4.22台机器排序问题的最优算法28

工作中心1工作中心2工作数据输入时间（h）核对时间（h）A2.51.7B3.82.6C1.91.0D1.83.029工作中心1工作中心2A2.502.5B6.3CD1.810ABC9.9D3.013iABCDPi1.810Pi8.91.09.93.01330工作数据输入时间（h）核对时间（h）A2.51.7B3.82.6C1.91.0D1.83.0——C排序方案：31工作数据输入时间（h）核对时间（h）A2.51.7

B3.82.6D1.83.0——C排序方案：——A32工作数据输入时间（h）核对时间（h）B3.82.6D1.8

3.0——C排序方案：——AD——33——C排序方案：——AD——B工作中心1工作中心2D1.801.8B5.6AC1.910D

3.04.83.8BA9.9C1.01134工作中心1工作中心2D1.801.8B5.6AC1.910D

3.04.83.8BA9.9C1.011新排序方案：D—B—A—C工作中心1工作中心2A2.502.5B6.3CD1.810ABC9.9D3.013原方案：D—B—A—C35123？从哪一项工作开始4.5小时8.5小时4.5小时拟稿时间5小时7小时8小时审稿时间36工作拟稿时间（h）审稿时间（h）A84.5B58.5C74.5试求1、最优排序方案B—C—A2、不同排序方案下的Fmax/B—A—C24.52637Palmer法（帕尔默法）关键工件法CDS法Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi345824.3一般n/m/P/Fmax问题的启发式算法384.3.1Palmer法1965年，帕尔默（D.S.Palmer）指出按斜度指标排列零件的启发式算法。计算零件的斜度指标按照各零件不增的顺序排列零件39Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi3458212得到加工工序Fmax＝28（1，2，3，4）或（2，1，3，4）404.3.2关键零件法（陈荣秋）计算最长加工时间的工件C（j=m）对余下工件，若，按不减顺序排成Sa若，按不增顺序排成Sb顺序（Sa，C，Sb）即所求41Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi34582Pi13111614123424.3.3CDS法－穷举法-1坎贝尔（Campbell）、杜德克（Dudek）、史密斯（Smith）三人提出了一个启发式算法。是Johnson算法解一般n/m/P/Fmax的运用。对加工时间和用Johnson算法求m-1次加工顺序，求其中最好。434.3.3CDS法－穷举法-2穷举法的操作步骤如下：取首末两道工序，用约翰逊法排序，求Fmax取首两道工序的和及尾两道工序的和，用约翰逊法排序，求Fmax取首三道工序的和及尾三道工序的和，用约翰逊法排序，求Fmax以此类推，直到所有的（m-1）种都考虑后，比较得到的Fmax，找出其中最小的为最优。44Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi34582i1234L=1Pi11263Pi34582L=2Pi1+Pi296812Pi2+Pi31291011L=1,(1,2,3,4)L=2,(2,3,1,4)45i1234Pi11/12/36/93/12Pi28/94/132/159/24Pi34/135/188/262/28L=1,(1,2,3,4)i2314Pi12/26/81/93/12Pi24/62/108/189/27Pi35/118/194/232/29L=2,(2,3,1,4)465单件车间作业计划问题单件车间作业计划问题是十分复杂的一种作业计划问题。它不仅包括排序问题，还包括任务分配问题。475.1任务分配问题-1

－指派问题（AssignmentProblem）在编制生产作业计划分配生产任务时，会碰到这样的问题：有若干项任务，要分配给若干小组或人去完成，由于每个人或小组完成各项任务的效率不同，应如何分配才能发挥每个小组或个人的优势，使完成任务总的效率最高呢？把零件分配给工人或机器加工，将区域分配给销售人员，将出故障的机器分配给维修小组都是任务分配问题。48AB

CD

泌尿科心脏病科整形外科产科指派问题（AssignmentProblem）495.1任务分配问题（指派问题）-2一种求解特殊的可将任务或工作分配给相应的资源的线性规划模型的方法重要特征：一件工作（一个服务对象）仅分配给一个服务者《运筹学》清华大学出版社2001年134第五章整数规划第5节指派问题505.2匈牙利法

5.2.1概述匈牙利法（TheHungarianmethodofassignment）是由匈牙利数学家考尼格（Konig）提出的，因此得名。目标成本最小或利润最大515.2匈牙利法

5.2.2步骤行减最小，列减最小。最少直线盖住表中所有零。直线数＝行列数则到第4)步，否则到第3）步未盖住数减最小，将最小加到直线相交处，重复2)最佳分配出现在表中零位置。525.2匈牙利法

5.2.3示例假定甲单位有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成A、B、C、D、E五项任务，每个员工完成每项工作所需要耗费的工作时间，如表1所示。请求出：员工与任务之间应当如何进行配置，才能保证完成工作任务的时间最短？53员工任务甲乙丙丁戊A10591811B131961214C32445D189121715E116141910表1各员工完成任务时间汇总表单位：小时54解：1.以各个员工完成各项任务的时间构造矩阵1。1059181113196121432445189121715116141910矩阵1552．对矩阵1进行行约减，即每一行数据减去本行数据中的最小数，得矩阵2。5041367130681022390386508134矩阵2563．检查矩阵2，若矩阵2各行各列均有“0”，则跳过此步，否则进行列约减，即每一列数据减去本列数据中的最小数，得矩阵3。4041136130450020080363408111矩阵3574．从含“0”最多的行或列开始画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住，得矩阵4。4041136130450020080363408111矩阵4585．数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步，若“盖0”线的数目小于矩阵得维数则进行数据转换，本例属于后一种情况，应进行转换，操作步骤如下：（1）找出未被“盖0”线覆盖的数中的最小值例中

＝1。（2）将未被“盖0”线覆盖住的数减去。（3）将“盖0”线交叉点的数加上。59本例结果见表2－10矩阵5。3041025130340130070352308100矩阵5606．重复4步和5步（计算过程见矩阵5a和矩阵5b），直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表矩阵6。3041025130340130070352308100矩阵5a6100472213004046034032200870矩阵5b00472213004046034032200870矩阵6627.求最优解。对n维矩阵，找出不同行、不同列的n个“0”，每个“0”的位置代表一对配置关系，具体步骤如下：（1）先找只含有一个“0”的行（或列），将该行（或列）中的“0”打“√”。（2）将带“√”的“0”所在列（或行）中的“0”打“”。（3）重复（1）步和（2）步至结束。若所有行列均含有多个“0”，则从“0”的数目最少的行或列中任选一个“0”打“√”。6300472213004046034032200870矩阵7√√√√√64其结果如矩阵7所示，即员工甲负责任务A，员工乙负责任务D，员工丙负责任务B，员工丁负责任务C，员工戊负责任务E，参照表1各员工完成任务时间汇总表，得出表2所示的员工配置最终结果。65员工任务甲乙丙丁戊A10B6C4D9E10表2各员工配置最终结果

单位：小时665.3一般n/m/G/Fmax问题的启发式算法

5.3.1基本法则-1先到先服务原则（FCFS）：按照订单到达的先后顺序进行加工。交货期最早原则（EDD）：按照交货期由早到晚的顺序进行加工。后到先服务原则（LCFS）：后到的订单放在先到的上面，操作员在操作的时候会先加工上面的订单。FirstcomefirstserveEarliestduedateLastcomefirstserve675.3一般n/m/G/Fmax问题的启发式算法

5.3.1基本法则-2最短加工时间准则（SPT）：优先安排加工时间最短的任务。最短松弛时间准则（SST）：按照松弛时间有短到长进行