第7章 作业计划与控制

1第7章作业计划与控制OperationsSchedulingandControlling27.1基本概念3生产计划的层次4编制作业计划要解决的问题工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课。。。5编制作业计划要解决的问题编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。6常用的符号7排序问题的分类8排序问题的分类FlowShop9排序问题的分类JobShopWorkCenter1WorkCenter2WorkCenter3WorkCenter4JobAJobB10排序问题的表示方法117.2流水车间作业计划问题12加工周期的计算13加工周期的计算14加工周期的计算例11-1152台机器排序问题的最优算法Johnson算法162台机器排序问题的最优算法例11-217练习计算题1（P311）18一般n/m/P/Fmax问题的启发式算法Palmer法CDS法197.3单件车间作业计划问题20任务分配问题在生产运作管理工作中，管理人员经常面临的一个问题是：如何根据有限的资源(人力、物力、财力等)，进行工作任务分配，以达到降低成本或提高经济效益的目的。如：有A、B、C、D四门课程，上课的老师可以从甲、乙、丙、丁四名老师中选择，不同的老师上不同的课程，其费用是不同的，并且规定，每人只讲一门课程，每门课程只需要一人讲授。问：如何安排，才能使总的上课费用最低？又如：运输任务的分配问题。有n条航线的运输任务指派给n艘船去完成，不同的船完成不同的航线其运输成本不同。要求每条船完成一条航线，并且一条航线只能由一条船去完成。如何分配任务，才能使总的费用最小？。。。这类问题是常见的任务分配问题，也叫指派问题，它的目标是如何进行合理的任务分配，使总的费用最小。21任务分配问题任务分配问题可以用一般的整数规划求解方法进行求解。但是，整数规划问题的求解也是非常困难的，到目前为止，还缺乏统一的求解方法。本课程采用匈牙利法求解任务分配问题。22匈牙利法求解任务分配问题可以证明，对于分配问题，在其费用矩阵Cij中，各行、各列均减去一个常数，Cij改变以后的最优解，仍为原问题的最优解。利用这个性质，通过对Cij的行、列进行加减常数的计算，把一些矩阵元素变为0，在Cij为0的元素上进行分解，就可得到原问题的最优解。该方法应用了匈牙利数学家Konig矩阵性质定理，因此这种方法被称为匈牙利法。23第一步：使指派问题的系数矩阵，经变换，在各行各列中都出现0元素。为此分如下两步进行：1.将系数矩阵的每行元素减去该行的最小元素；2.再从所得的系数矩阵中，将每列减去该列的最小元素。（若该行或列已有0元素，则就不必计算）第二步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立0元素。令这直线数为l。若ln，则说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第三步；若l=n，则已得到最优解，为此转第四步。匈牙利法求解任务分配问题24第三步：对于上述矩阵进行行变换的目的是增加0元素。为此，在没有被直线覆盖的部分中找出最小元素，然后在没有被直线覆盖各元素中都减去该最小元素，并将这个最小数加到直线交叉的元素上，其余元素不变。这样得到的新系数矩阵与原问题具有相同最优解。由此若能得到n个独立的0元素，则已得到最优解，为此转第四步；否则返回到第二步重复进行。第四步：进行指派以寻求最优解。为此按如下4个分步骤进行：1.从只有一个0元素的行（列）开始，给这个0元素加圈，记为。然后划去所在的列（行）的其它0元素，记为。这表示该列所代表的任务已指派完，不必再考虑别人。2.给只有一个0元素的列的0元素加圈，记为；然后划去所在行的0元素，记为。3.重复进行（1）、（2）两步，直到所有0元素都被圈出和划掉为止。4.若元素的数目m等于矩阵的阶数n,那么这个指派问题的最优解已得到。匈牙利法求解任务分配问题25任务分配问题例11-5（P297）26练习求如下系数矩阵所对应的任务分配问题16151211151416151716121312109727答案最优任务分配方案为：x13=x22=x34=x41=1，最优值为48。287.4生产作业控制29实行生产作业控制的原因生产计划和生产作业计划在实施过程中由于以下原因，往往造成实施情况与计划要求偏离加工时间估计不准确。随机因素的影响。加工路线的多样性。企业环境的动态性。。。。30实行生产作业控制的条件要有一个标准。标准就是生产计划和生产作业计划。要取得实际生产进度与计划偏离的信息。要能采取纠正偏差的行动。31不同生产类型生产控制的特点单件小批生产对于单件小批生产，排队时间是主要的，它大约占工件加工提前期的80-95%。排队时间越长，在制品库存就越高。如果能够控制排队时间，也就控制了工件在车间的停留时间。要控制排队时间，实际是控制排队队长的问题。因此，如何控制排队的队长，是生产控制要解决的主要问题。32不同生产类型生产控制的特点大量大批生产大量大批生产的产品是标准化的，通常采用流水线或自动线的组织方式生产。因此，控制问题比较简单。