第9章排序与统筹方法.ppt

第九章 排序与统筹方法 §1 车间作业计划模型 车间作业计划是指一个工厂生产工序的计划和安排。 一、一台机器、n个零件的排序问题 二、两台机器、n个零件的排序问题 §1 车间作业计划模型 一、一台机器、n个零件的排序问题 例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。 应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？ §1 车间作业计划模型 §1 车间作业计划模型 §1 车间作业计划模型 二、两台机器、n个零件 例2. 某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如下表所示。 　　应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？ §1 车间作业计划模型 解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的。如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。 图 12-1 从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。 为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。 §1 车间作业计划模型 寻找例2的最优解：我们在上表中找到所列出的最短加工时间是0.25,它是第二道工序磨床加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五位，并在表中划去零件2 所在行。如表中红色线条所示。 §1 车间作业计划模型 接着，我们又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把磨床加工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把表中的零件1所在的行划去。如表中黄色线条所示。 §1 车间作业计划模型 下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表中蓝色线条所示。 §1 车间作业计划模型 同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故把零件3排在第二位上，同时把零件3所在的行划去。如表中黑色线条所示。 §1 车间作业计划模型 这样就得到了最优加工顺序：5，3，4，1，2。 §1 车间作业计划模型 从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部任务总的时间最短的排序算法。 步骤1: 在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所需时间， 步骤2: 当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量靠后。 步骤3: 在表上划去零件j的所在行，回到步骤1。 §1 车间作业计划模型 思考题： 　　m台机器n个零件的排序问题如何解决？ §2 统筹方法 统筹法又称网络计划法。它是以网络图反映、表达计划安排，据以选择最优工作方案，组织协调和控制生产（项目）的进度（时间）和费用（成本），使其达到预定目标，获得更佳经济效益的一种优化决策方法。 1957年，美国化学公司Du Pont的M.R.Walker与Rand通用电子计算机公司的J.E.Kelly为了协调公司内部不同业务部门的工作, 共同研究出关键路线方法（简记作CPM）.首次把这一方法用于一家化工厂的筹建，结果筹建工程提前两个月完成.随后又把这一方法用于工厂的维修，结果使停工时间缩短了47个小时，当年就取得节约资金达百万元的要观效益。 1958年，美国海军武器规划局特别规划室研制含约3000项工作任务的北极星导弹潜艇计划，参与的厂商达11000多家。为了有条不紊地实施如此复杂的工作，特别规划室领导人W.Fazar积极支持与推广由专门小组创建的计划评审技术（简记作PERT）。结果研制计划提前两个完成，取得了极大的成功。 CPM在民用企业与PERT在军事工业中的显著成效,自然引起了普遍的重视。