搜索
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不同生产类型生产控制的特点大量大批生产大量大批生产的产品是标准化的，通常采用流水线或自动线的组织方式生产。因此，控制问题比较简单。