第十一章制造业作业计划与控制生产任务的最终落实编制作业计划要解决的问题第一节排序问题的基本概念“机器”，可以是工厂里的各种机床，也可以是维修工人，表示“服务者”“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题有关符号三、排序问题的分类根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序4参数法四、作业排序方案的评价标准3.在制品库存（WIP）在制品是对介于原材料和成品之间的生产过程中的产品的称谓。一个工件正从一个工作地移向另一个，由于一些原因被拖延加工，正在被加工或放置于零件库中，都可以看作在制品库存。4.利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示。五、优先调度规则常用的优先顺序规则：一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化[例]一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间。下表显示了周一上午的情况，顾客的取货时间用从周一上午开始，还有多少工作小时来计算。机壳加工次序机壳加工次序优先调度法则第二节流水作业排序问题一、最长流程时间Fmax的计算例有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序S=（6，1，5，2，4，3）加工时，求Fmax。i二、两台机器排序问题【例】求如表所示的6/2/F/Fmax问题的最优解。【例题】任务A,3.0【例题】1.将所有ai≤bi的工件按ai值不减的顺序排成一个序列A；2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。练习任务三、一般n/m/P/Fmax问题的启发式算法（一）Palmer法例有一个4/3/F/Fmax问题，其加工时间如下表所示，试用帕尔默法求最优顺序。（二）关键零件法i例题（三）CDS法m=2时，l=1,加工时间分别为pi1和pi2；m=3时，l=1,2,加工时间分别为：（1）l=1，pi1和pi3（2）l=2,pi1+pi2和pi2+pi3m=4时，l=1，2，3，加工时间分别为：（1）l=1,pi1和pi4（2）l=2，pi1+pi2和pi3+pi4（3）l=3，pi1+pi2+pi3和pi2+pi3+pi4ii用Palmer法、关键工件法和CDS法求以下4/4/P/Fmax问题的最优解，并比较三种方法的结果。四、相同零件、不同移动方式下加工周期的计算（一）顺序移动方式设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为ti（分钟/件），i=1.2…n。则该批零件的加工周期为：（二）平行移动方式零件平行移动的加工周期为：（三）平行顺序移动方式具体做法平行顺序移动加工周期计算[例]已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟。求三种移动方式下的加工周期。解：T顺=4×（10+5+15+10）=160分钟T平=（10+5+15+10）+（4-1）×15=85分钟T平顺=4×（10+5+15+10）-（4-1）×（5+5+10）=100分钟比较项目第三节单件作业排序问题1、指派问题的形式表述给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务设n个人被分配去做n件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i个人去做第j件工作的的效率为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？典型问题问：如何分配，能使所需的总时间最少？建立模型4、指派问题的匈牙利解法例2有甲、乙、丙、丁四个工人，要分别派他们完成四项不同的任务，分别记作A、B、C、D。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？11.3.2问题的描述11.3.3两种作业计划的构成符号说明每安排一道工序称为一“步”{St}:t步之前已排序工序构成的部分作业计划；{Ot}:t步可排序工序的集合；Tk为{Ot}中工序Ok的最早可能开始时间；T’k为{Ot}中工序Ok的最早可能完成时间。（一）能动作业计划的构成步骤例有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：能动作业计划的构成能动作业计划的甘特图（二）无延迟作业计划构成步骤