作业计划与排序.ppt

第7章 作业计划与排序Operations Scheduling and Sequencing 本章的主要内容 作业计划 (Scheduling) 排序 (Sequencing) 车间生产控制 （ Shop-Floor Control ） 第一节 作业计划的目的和要求 一、编制生产作业计划的目的 1、生产作业计划以生产计划(MRP)为基础，在时间上进一步细分为日、小时。在空间上将生产任务分配到车间、班组或设备甚至到个人； 2、通过编制生产作业计划，使生产任务与各种资源（设备能力、工时、原燃材料等）之间进一步综合平衡； 一、在制品定额法 在制品定额法，是一种利用预先制订的在制品定额，来协调和规定各车间投入量和出产量的方法。 这种方法适用于大批量生产企业。 第三节 排序的基本概念 一、 排序与编制作业计划的区别 排序---确定零部件在一台或一组设备上加工的先后顺序的工作。 作业计划---安排零部件的出产数量和投入时间及出产时间。 二、 排序问题的分类 根据机器数的多少 单台机器的排序问题 ：多个工件在一台机器上加工 多台机器的排序问题 ：多个工件在多台机器上加工 根据加工路线的特征（多台机器的排序问题） 单件车间排序 ：工件加工路线不同(Job Shop) 流水型排序 : 工件加工路线相同 (Flow Shop) 根据工件到达系统的情况 静态排序 :排序时工件已全部到达 动态排序 :排序时工件陆续到达 根据参数的性质 确定型排序 ：加工时间等参数已知 随机型排序 根据要实现的目标 单目标排序 ：平均流程时间最短或误期工件最少等 多目标排序 三、 排序常用的符号 Ji----工件i，i=1,2,....n di----工件i的交货期 Pi----工件i的加工时间, , pij----工件i在机器j上的加工时间,j=1,…,m 排序问题的表示方法： 排序问题常用四个符号来描述: n/m/A/B 其中, n-----工件数； m-----机器数； A----车间类型, F=流水型排序 （路线相同） G=单件车间排序（路线不同） m=1时A空白 B-----目标函数 12/3/F/F----12个工件/3台设备/流水线/流程时间最短 四、单台机器排序问题 （n/1/ /B) n个工件全部经由一台机器处理 1、 常见单台机器排序问题的目标函数 1) 平均流程时间最短 根据排序目标的不同，可以选择不同的排序规则，又称为确定零件加工的优先权。 常见的排序规则： SPT---Shortest Process Time, 优先选择加工时间最短的工件 EDD---Earliest Due Date 优先选择交货期紧的工件 FCFS---First Come First Served 按工件到达的先后顺序 CR---Critical Rate 优先选择临界比最小的工件 CR=（交货期-当前日期）/剩余加工时间 2 求平均流程时间最短的排序问题 求平均流程时间最短的作业顺序，采用SPT原则。 按工件加工时间的长短，从小到大安排作业。 例：一台加工中心，现有5个工件需要该机器加工。相关的加工时间和要求完成时间（交货期）如下表所示，求平均流程时间最短的作业顺序。 解：根据SPT原则，得出： J4 -J5 -J1 -J2 -J3 有关项目的计算： 3 求最大延期量最小的排序问题 求最大延期量最小的作业顺序采用EDD原则。 例：同上面的例子，按延期量(完工日期-交货期）大小，从小到大排序。 解：根据EDD原则，得出 J3 -J5 -J4-J2 -J1 作业题 五、 n项任务在两台机器的排序问题 1、两台机器排序问题的含义(n/2/F/Fmax) n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。 2、两台机器排序问题的目标 两台机器排序的目标是使生产周期Fmax最短。 Fmax的含义见如下图。 3、两台机器排序问题的算法 约翰逊法(Johnson’s Law)， 约翰逊法解决这种问题分为4个步骤： (1)列出所有工件在两台设备上的作业时间。 (2)找出作业时间最小者。 (3)如果该最小值是在设备1上，将对应的工件排在前面，如果该