汇智咨询——扫码关注, 领取更多内部资料PPT 详情咨询请添加客服微信:18576713311 公司电话:0755-86961791 更多干货PPT等你来领 汇智咨询——扫码关注, 领取更多内部资料PPT
第七章 作业排程 前言 作业排程的基本概念 作业排程的特征与限制 单机排程问题 平行机台排程问题 流线型生产之排程问题 零工型生产之排程问题 第七章 作业排程 前言 作业排程的基本概念 作业排程的特征与限制 单机排程问题 平行机台排程问题 流线型生产之排程问题 零工型生产之排程问题 前推与后推排程问题 人员排程问题 结语
系统安装设置(installation)专案 汽车租赁保留(reservation)系统 前言 系统安装设置(installation)专案 半导体制造工厂 汽车组装生产线 汽车租赁保留(reservation)系统 医院中的护士排班问题 生产计划与管理 Chapter 7 作业排程
决定各工作站的工作负荷(work loading) 决定工作之处理顺序(sequencing) 作业排程的基本概念 排程是一种资源分配的决策活动。作业排程(Operations Scheduling)为广义排程中的一种,若在制造业中特别是指制造现场机台与工件间的安排,以下简称排程。 在一般工厂内常见的排程问题中,处理步骤主要可分为两部份。 决定各工作站的工作负荷(work loading) 决定工作之处理顺序(sequencing) 生产计划与管理 Chapter 7 作业排程
作业排程的基本概念 1/2 负荷安排 工作的处理优先级 作业排程的基本概念 1/2 负荷安排 将各项工作分配至各工作站,它决定各工作站该负责之工作,让管理者将制令单安排至各工作站,同时兼顾各工作站间目前的产能负荷情况以及生产线平衡问题,但并未排定各工作站内的工作次序。 工作的处理优先级 又称派工(Dispatching),透过派工法则来决定在线执行顺序。排程可定义成一种短期计划,此计划关系着制造现场的制令单或拟作业之工作的作业顺序和时间配置,此定义说明排程是一序列的排序步骤。 生产计划与管理 Chapter 7 作业排程
作业排程的基本概念 2/2 因此,所有工作的作业先后顺序、先天的技术限制、各个作业的估计时间和各个作业所需之资源产能等,都是构建细部排程时需要考虑的因素。 生产计划与管理 Chapter 7 作业排程
汇智咨询——扫码关注 详情咨询请添加客服微信:18576713311 公司电话:0755-86961791 更多干货PPT等你来领 生产计划与管理 Chapter 7 作业排程
作业排程的特征与限制 制造现场生产结构(Shop Structure) 评估准则(Performance Criteria) 产品结构(Product Structure) 工作中心之产能(Work Center Capacities) 生产计划与管理 Chapter 7 作业排程
单机(single machine)排程问题 独立工作以何顺序分派至一部机台上作业, 以使某一绩效评估指标最佳 定义 ․ n个工作的开始时间均为零 ․作业时间(tj)包含了准备时间(setup time),而 且不受排程顺序的不同而有所影响 ․作业时间(tj)事先已知 ․一旦机器有空马上处理下一等待的工作 ․上机的工作未处理完成前,不能中途停止 假设 生产计划与管理 Chapter 7 作业排程
排程之基本评估指标 1/2 总完工时间(Makespan):所有工作处理完成之完工时间。 作业流程时间(Flowtime):工作在系统中停留之时间。 延误时间(Lateness):工作i完工时间与交期之差异。 延迟时间(Tardiness):工作i完工时间超出交期的时间。 延迟作业数目(Number of tardy jobs): 生产计划与管理 Chapter 7 作业排程
排程之基本评估指标 2/2 平均流程时间(Average flowtime): 平均延误时间(Average lateness): 平均延迟时间(Average tardiness): 最大延误时间(Maximum lateness): 最大延迟时间(Maximum tardiness): 生产计划与管理 Chapter 7 作业排程
单机(single machine)排程问题 最小化平均流程时间。job作业时间越小者排越前面,亦可以使平均延误(迟)时间,平均等候时间最小化。 最短作业时间法则(SPT) 最小化平均加权流程时间。将作业时间除以权重,所得之值越小者排越前面。 加权最短作业时间法则(WSPT) 最大延误(迟)时间最小化。交期越早者排越前面,但是此法会有增加延迟工件数目和增加平均延迟时间的倾向。 最早交期法则(EDD) 最小化延迟工件数目。 Hodgson法则 生产计划与管理 Chapter 7 作业排程
汇智咨询——扫码关注 详情咨询请添加客服微信:18576713311 公司电话:0755-86961791 更多干货PPT等你来领 生产计划与管理 Chapter 7 作业排程
最短作业时间(SPT)法则— 最小化平均流程时间( ) 当n个作业要排至单一机台上时,利用SPT (Shortest Process Time) 法则排序可使得平均流程时间最小化,也就是 。 生产计划与管理 Chapter 7 作业排程
范例 7.1 1/3 给予一组工作集如表 7.6,目标为最小化平均流程时间。 工作 i 作业时间 ti 1 4 2 8 3 7 5 10 6 表 7.6 工作作业时间表 工作 i 作业时间 ti 1 4 2 8 3 7 5 10 6 12 生产计划与管理 Chapter 7 作业排程
范例 7.1 2/3 依SPT派工法则排序,顺序为4-1-8-7-3-2-5-6。其流程时间计算和表7.7所示。 工作 i 流程时间 ti 表 7.7 流程时间计算表 工作 i 流程时间 ti 4 3 1 3+4 8 3+4+5 7 3+4+5+6 3+4+5+6+7 2 3+4+5+6+7+8 5 3+4+5+6+7+8+10 6 3+4+5+6+7+8+10+12 生产计划与管理 Chapter 7 作业排程
范例 7.1 3/3 所以平均流程时间 由上例及图7.3观察,工作流程时间的计算方式为 除了最小化平均流程时间以外,在单机排程问题中SPT法则亦可以最小化平均延误时间、最小化平均等候时间。 5 10 15 20 25 30 35 40 45 50 4 1 8 7 3 2 5 6 生产计划与管理 Chapter 7 作业排程
加权最短作业时间法则 (WSPT)— 最小化加权平均流程时间 当工作附有重要性之属性时,排程人员可给予个别之权重,权重值愈大表示重要性愈大。 WSPT法则即是将作业时间除以权重,所得之值愈小者表示为愈重要之工作,而将它排至顺序的第一位,依此类推。加权平均流程时间的计算方式为 生产计划与管理 Chapter 7 作业排程
最短作业时间 (SPT) 法则— 最小化平均延误时间 ( ) 生产计划与管理 Chapter 7 作业排程
汇智咨询——扫码关注 详情咨询请添加客服微信:18576713311 公司电话:0755-86961791 更多干货PPT等你来领 生产计划与管理 Chapter 7 作业排程
最早交期法则 (EDD Rule)— 最小化最大延误时间 (Lmax) 1955年Jackson提出EDD (Early Due Date) 派工法则,其应用在最小化最大延误时间和最大延迟时间,但是会有增加延迟工作数目和增加平均延迟时间的倾向。 EDD法则排序为交期愈早者排至愈前面,即 生产计划与管理 Chapter 7 作业排程
Hodgson法则:求NT最小, 即最小化延迟工件数目 以EDD法则将所有工作排序为集合,并计算E集合中所有工作的完工时间。假使结果出现没有或者只有一个延迟工作,则停止,此时已达 为最小最佳解。否则进入第二步骤。 Step1 在集合中从头至尾找出第一个延迟作业,假设为k Step2 检视前个工作 (包含第个),将最长作业时间之工作 移至另一集合中 (开始为空集合),其中。 Step3 重新计算集合中所有工作的完工时间。若集合中没有延迟作业,则停止,集合的延迟个数即为最小解。否则回到步骤2。 Step4 生产计划与管理 Chapter 7 作业排程
平行机台(parallel machine) 排程问题 1/2 传统平行机台排程问题就是将n个工作如何安排至m部平行机台的问题。 生产计划与管理 Chapter 7 作业排程
平行机台(parallel machine) 排程问题 2/2 一般平行机台主要可分为二种: Identical parallel machine (等效平行机台): ․所有的机台对于某一个工件的加工速度均相同。 Unrelated parallel machine (无关联平行机台): ․各机台的加工速度皆不同,且以同一机台来说, 不同的工件也会有不同的加工速度。 生产计划与管理 Chapter 7 作业排程
最小化平均流程时间 范例 7.6 Step1:SPT法则 : {6,10,3,7,9,1,8,2,5,4} 工作 i 1 2 3 4 5 6 7 8 9 10 作业时间ti 生产计划与管理 Chapter 7 作业排程
降低总完工时间 范例 7.7 Step1:LPT法则 : {4,5,2,1,8,9,3,7,6,10} Step3:依SPT法则排序机台上工作 工作 i 1 2 3 4 5 6 7 8 9 10 作业时间ti 生产计划与管理 Chapter 7 作业排程
降低最大延迟时间 Step1:EDD法则 : {6,10,1,7,2,8,5,4,3,9} Step2:依序将工作指派至最早闲置之机台 工作i 1 5 8 2 6 9 3 14 4 12 7 11 10 15 作业时间 交期 生产计划与管理 Chapter 7 作业排程
降低延迟工件数目 在探讨单机排程时,我们发现Hodgson方法可使延迟件数最小,现在依此方法应用到平行机台排程上。 利用方法7.5.3指派所有工作。 步骤1 针对每部机台,找出第一个延迟工作,假设发现在机台j的第i个顺位。 步骤2 检查并找出在机台j前i个顺位中作业时间最长者,将它移至机台j的最后顺位,修正更改后工作的完成时间并重复步骤2。 步骤3 生产计划与管理 Chapter 7 作业排程
汇智咨询——扫码关注 详情咨询请添加客服微信:18576713311 公司电话:0755-86961791 更多干货PPT等你来领 生产计划与管理 Chapter 7 作业排程
流线型生产之排程问题 1/3 如何决定n件工作进入系统的处理顺序: 流线型生产之排程问题 1/3 如何决定n件工作进入系统的处理顺序: m部序列机台(m-1机台排在m机台前),每件工作都必须依序通过此m部机台,当某工作在一机台之作业完成后,便依序到下一机台等待处理。 生产计划与管理 Chapter 7 作业排程
流线型生产之排程问题 2/3 琼森法则(Johnson’s rule)-两部序列机台最小化总完工时间。 流线型生产之排程问题 2/3 琼森法则(Johnson’s rule)-两部序列机台最小化总完工时间。 找出所有工作在两部机台上之作业时间ti,1和ti,2两者中最小者。 Step1 假使选出的最小时间在机台1(ti,1),则将所对应的工作排在顺序最早的下一可排空位,继续步骤3。假使选出的最小时间在机台2(ti,2),则将所对应的工作排在顺序最后的下一可排空位,继续步骤3。 Step2 MRP II (p.115) 每个项目的名词定义: 绩效管制报告:可协助管理者衡量计划因实施后的差异,包括交货延误与存货短缺,并可用于评估成本绩效的信息。 将已指派之工作删除,回至步骤1,直到所有工作排完为止。 Step3 生产计划与管理 Chapter 7 作业排程
流线型生产之排程问题 3/3 两部序列机台最小化总完工时间:Johnson’s rule 结果 : { , , , , } 1 4 2 5 流线型生产之排程问题 3/3 两部序列机台最小化总完工时间:Johnson’s rule 结果 : { , , , , } 1 4 2 5 3 生产计划与管理 Chapter 7 作业排程
流线型生产之排程问题范例─7.10 1/3 1 3 5 2 6 8 4 7 9 10 工作i 机台1之作业时间 机台2之作业时间 生产计划与管理 Chapter 7 作业排程
流线型生产之排程问题范例─7.10 2/3 1 3 5 2 6 8 4 7 9 10 工作i 机台1之作业时间 机台2之作业时间 生产计划与管理 Chapter 7 作业排程
流线型生产之排程问题范例─7.10 1/3 最后之顺序为3-1-6-9-5-4-7-10-8-2 流线型生产之排程问题范例─7.10 1/3 最后之顺序为3-1-6-9-5-4-7-10-8-2 生产计划与管理 Chapter 7 作业排程
汇智咨询——扫码关注 详情咨询请添加客服微信:18576713311 公司电话:0755-86961791 更多干货PPT等你来领 生产计划与管理 Chapter 7 作业排程
零工型生产之排程问题 生产计划与管理 Chapter 7 作业排程
零工型生产排程问题 零工型生产系统的派工法则 : 随机法则, FCFS, EDD, SPT, LSF, LWR,……… 生产计划与管理 Chapter 7 作业排程
零工型生产排程问题 一般而言,有限产能排程问题主要可分成下列几种: 以「制令」为主的排程方法 利用订单排序法则决定订单或制令的加工优先级,再按顺序高低逐一安排各制令的详细作业排程。 以「制令」为主的排程方法 (Job-based Scheduling或Order-based Scheduling) 运算逻辑是利用事件导向(Event-Driven)的仿真观念来描述制造系统的实际运作流程。 以「工作中心」为主的排程方法 (Event-based Scheduling) 生产计划与管理 Chapter 7 作业排程
派工法则 1/2 几种常用的派工法则: 随机法则 等候在线的每一等待工作的选择是具相同机率。一般此法将作为与其他方法之比较基础。 派工法则 1/2 几种常用的派工法则: 等候在线的每一等待工作的选择是具相同机率。一般此法将作为与其他方法之比较基础。 随机法则 (Random) 以首先来到等候线的工作为优先 先进先出派工法则 (First Come First Served, FCFS) 以等候线中工作的最早交期者为优先 最早交期派工法则 (Earliest Due Date, EDD) 以等候线中工作的作业时间最短者为优先。 最短作业时间派工法则 (Shortest Processing Time, SPT) 生产计划与管理 Chapter 7 作业排程
派工法则 2/2 最小宽裕时间派工法则 宽裕时间是指交期减掉工作还需在机器上加工完成的时间。以等候线中工作的宽裕时间最短者为优先。 派工法则 2/2 宽裕时间是指交期减掉工作还需在机器上加工完成的时间。以等候线中工作的宽裕时间最短者为优先。 最小宽裕时间派工法则 (Least Slack First, LSF) 以等候线中工作的仍剩余的加工时间最短者为优先。 最小剩余时间派工法则 (Least Work Remaining, LWR) 依照距离到期日剩余时间对剩余加工时间比率,最小者为优先。 关键性比率 (Critical Ratio, CR) 生产计划与管理 Chapter 7 作业排程
范例 7-11─以制令为主的排程方法 1/3 以EDD法则来决定制令的加工优先级 制令 作业顺序与时间 交期 1 范例 7-11─以制令为主的排程方法 1/3 以EDD法则来决定制令的加工优先级 制令 作业顺序与时间 交期 1 A(3)→B(3) →C(2) 10 2 A(5)→C(2) 13 3 B(4)→A(4)→C(2) 12 4 B(3)→C(5)→A(2) 18 5 C(5)→B(4) 14 6 C(2)→A(5)→B(5) 15 顺序 制令 交期 1 10 2 3 12 13 4 5 14 6 15 18 生产计划与管理 Chapter 7 作业排程
汇智咨询——扫码关注 详情咨询请添加客服微信:18576713311 公司电话:0755-86961791 更多干货PPT等你来领 生产计划与管理 Chapter 7 作业排程
范例 7-11─以制令为主的排程方法 2/3 顺序 制令 交期 1 10 2 3 12 13 4 5 14 6 15 18 范例 7-11─以制令为主的排程方法 2/3 顺序 制令 交期 1 10 2 3 12 13 4 5 14 6 15 18 生产计划与管理 Chapter 7 作业排程
范例 7-11─以制令为主的排程方法 3/3 生产计划与管理 Chapter 7 作业排程
范例 7.12 (EDD)─以「工作中心」 为主的排程方法 1/8 制令 作业顺序与时间 交期 1 A(3)→B(3) →C(2) 10 2 A(5)→C(2) 13 3 B(4)→A(4)→C(3) 12 4 B(3)→C(5)→A(2) 18 5 C(5)→B(4) 14 6 C(2)→A(5)→B(5) 15 生产计划与管理 Chapter 7 作业排程
范例 7.12 (EDD)─以「工作中心」 为主的排程方法 2/8 若以T来表示时间轴。当T=0时,此时机台A,B,C均空闲。当开始着手于A机台的排程时,我们所面对的抉择是制令1或制令2,何者排在最前?假设依据EDD派工法则来进行模拟过程,如表分别针对机台A,B,C选定该上机之制令。 机台 可排之制令 派工法则判断 选定之制令 作业时间 A 1,2 D1<D2 1 3 B 3,4 D3<D4 4 C 5,6 D5<D6 5 注:Di 表示制令i 的交期,其中 i=1,2,…,6. 生产计划与管理 Chapter 7 作业排程
范例 7.12 ─派工法则:EDD 3/8 制令 作业顺序与时间 交期 1 A(3)→B(3) →C(2) 10 2 A(5)→C(2) 13 3 B(4)→A(4)→C(3) 12 4 B(3)→C(5)→A(2) 18 5 C(5)→B(4) 14 6 C(2)→A(5)→B(5) 15 生产计划与管理 Chapter 7 作业排程
范例 7.12 ─派工法则:SPT 4/8 制令 作业顺序与时间 交期 1 A(3)→B(3) →C(2) 10 2 A(5)→C(2) 13 3 B(4)→A(4)→C(3) 12 4 B(3)→C(5)→A(2) 18 5 C(5)→B(4) 14 6 C(2)→A(5)→B(5) 15 生产计划与管理 Chapter 7 作业排程
范例 7.12 ─派工法则:FCFS 5/8 生产计划与管理 Chapter 7 作业排程
范例 7.12 ─派工法则:LSF 6/8 生产计划与管理 Chapter 7 作业排程
范例 7.12 ─派工法则:LWR 7/8 生产计划与管理 Chapter 7 作业排程
汇智咨询——扫码关注 详情咨询请添加客服微信:18576713311 公司电话:0755-86961791 更多干货PPT等你来领 生产计划与管理 Chapter 7 作业排程
范例 7.12 ─不同派工法则的绩效表现 8/8 派工法则 评估准则 延迟件数(number of tardy jobs) 总延迟时间(total tardiness) 平均流程时间(mean flow time) 总完工时间(makespan) EDD 3 14 15 22 FCFS 5 17.33 LSF 4 18 16.5 20 SPT 13 15.33 LWR 24 15.5 29 生产计划与管理 Chapter 7 作业排程
前推(Forward)与后推(Backward)排程 由上一小节范例中可发现,排程的方式均是由目前时间点Tnow进行排程活动,即由目前时间点朝未来时间向前看,这样的排程方式称之为前推排程。 前推排程 (Forward Scheduling) 主要是由未来某特定时间点,例如某笔订单的交期,在时间轴上倒推排程。 后推排程 (Backward Scheduling) 生产计划与管理 Chapter 7 作业排程
结论 排程问题存在于各行各业及日常生活中。 制造系统种类极多,且在新的制造技术和制造管理观念持续发展下,随时产生新的排程问题 。 真实制造系统的排程问题其复杂度和困难度均相当高。 生产计划与管理 Chapter 7 作业排程
Q & A 生产计划与管理 Chapter 7 作业排程