生产管理_Charpt_08_作业排序.pptVIP

生产与运作管理 作业排序 第七章 作业排序 基本概念 最长流程时间 n/2/F/Fmax问题的算法 一般n/m/P/ Fmax问题的启发式算法 一、基本概念 1、排序 排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。 排序中常用的几个概念 工件（Job）：服务对象； 机器（Machine、Processor）：服务者。 所以，作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。 如可用（1，6，5，4，3，2）表示加工顺序： J1—J6—J5—J4—J3—J22。 2、作业计划（Scheduling） 作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。 如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。 3、排序问题的分类与表示 1）单台机器与多台机器的排序问题。 2）流水车间与单件车间排序问题。 流水车间排序问题的基本特征： 每个工件的加工路线都一样。如车—铣—磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车—磨，有的为铣—磨。 不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1—J3—J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。 单件车间排序问题的基本特征： 每个工件都有其独特的加工路线，工件没有一定的流向。 3）表示方法 一般正规的表示方法为：n/m/A/B n：工件数；m：机器数； A：车间类型（F、P、G）；B：目标函数 4）一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。 二、最长流程时间 最长流程时间（加工周期）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。 假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。 计算Fmax的几个假定条件： 机器M1不会发生空闲； 对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。 三、n/2/F/Fmax问题的算法 Johnson算法： 假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1—M2的路线加工。 Johnson算法的步骤： 从加工时间矩阵中找出最短的加工时间 若最短时间出现在M1上，则对应的工件尽可能往前排 若最短时间出现在M2上，则对应的工件尽可能往后排 若最短时间有多个，则任选一个 划去已排序的工件 若所有工件都已排序，则停止，否则重复上述步骤 四、一般n/m/P/ Fmax问题的启发式算法 对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。 关键工件法的步骤： 计算Pi=? Pij ，找出Pi最长的工件，将之作为关键工件C。 对其余工件，若Pi1≤Pim ，则按Pi1不减的顺序排成序列SA。若Pi1 Pim ，则按Pim不增的顺序排成序列SB。 顺序（SA，C，SB）即为近优解。 车间作业管理 车间作业管理的信息源 计划文件数据概要 作业排序的十大优先规则 作业排序的评价 排序问题的分类与表示法 N个作业单台工作中心的排序 N个作业两台工作中心排序 N个作业n台工作中心排序 N个作业m台工作中心排序 车间作业控制的定义和主要功能 生产工序类型和计划方法 类型 产品 特征 通常的计划方法 单一工序 大批量生产 中等批量生产 小批量生产 化工产品、钢、金属、液体产品等 汽车、电话、摩托车、家用设施 工业用品、最终消费品 定做的或标准的设备、专用仪器等 全自动化，产品中劳动力成本低，设施专用于一种产品 自动化装备，半自动化传动装置或移动装配线 成组技术单元，专业化小工厂 按生产功能组织的机器中心，通用设备换装时间相当长等 有限符合，前向排序，机器有限 生产线有限负荷，前向排序，机器有限，准时化生产 无限负荷，前向排序，有限调度控制，常劳动力有限但有时机器有限 无限负荷，前向排序， 车间作业排序的目标 满足交货期 极小化提前期 极小化准备时间或成本 极小化在制品