版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
作业排程前言作业排程的基本概念作业排程的特征与限制单机排程问题平行机台排程问题流线型生产之排程问题零工型生产之排程问题前推与后推排程问题人员排程问题结语前言半导体制造工厂汽车组装生产线汽车租赁保留(reservation)系统医院中的护士排班问题系统安装设置(installation)专案作业排程的基本概念排程是一种资源分配的决策活动。作业排程(OperationsScheduling)为广义排程中的一种,若在制造业中特别是指制造现场机台与工件间的安排,以下简称排程。在一般工厂内常见的排程问题中,处理步骤主要可分为两部份。决定各工作站的工作负荷(workloading)决定工作之处理顺序(sequencing)作业排程的基本概念1/2将各项工作分配至各工作站,它决定各工作站该负责之工作,让管理者将制令单安排至各工作站,同时兼顾各工作站间目前的产能负荷情况以及生产线平衡问题,但并未排定各工作站内的工作次序。又称派工(Dispatching),透过派工法则来决定在线执行顺序。排程可定义成一种短期计划,此计划关系着制造现场的制令单或拟作业之工作的作业顺序和时间配置,此定义说明排程是一序列的排序步骤。负荷安排工作的处理优先级作业排程的基本概念2/2因此,所有工作的作业先后顺序、先天的技术限制、各个作业的估计时间和各个作业所需之资源产能等,都是构建细部排程时需要考虑的因素。作业排程的特征与限制制造现场生产结构(ShopStructure)评估准则(PerformanceCriteria)产品结构(ProductStructure)工作中心之产能(WorkCenterCapacities)单机(singlemachine)排程问题․
n个工作的开始时间均为零․作业时间(tj)包含了准备时间(setuptime),而且不受排程顺序的不同而有所影响․作业时间(tj)事先已知․一旦机器有空马上处理下一等待的工作․上机的工作未处理完成前,不能中途停止假设․单机排程是最基本的排程问题,其定义为n件独立工作以何顺序分派至一部机台上作业,以使某一绩效评估指标最佳定义排程之基本评估指标1/2作业流程时间(Flowtime):工作在系统中停留之时间。延误时间(Lateness):工作i完工时间与交期之差异。总完工时间(Makespan):所有工作处理完成之完工时间。延迟时间(Tardiness):工作i完工时间超出交期的时间。延迟作业数目(Numberoftardyjobs):排程之基本评估指标2/2平均流程时间(Averageflowtime):平均延误时间(Averagelateness):平均延迟时间(Averagetardiness):最大延误时间(Maximumlateness):最大延迟时间(Maximumtardiness):单机(singlemachine)排程问题n件独立工作以何顺序分派至一部机台上作业,以使某一绩效评估指标最佳。最小化平均流程时间。job作业时间越小者排越前面,亦可以使平均延误(迟)时间,平均等候时间最小化。最短作业时间法则(SPT)最小化平均加权流程时间。将作业时间除以权重,所得之值越小者排越前面。加权最短作业时间法则(WSPT)最大延误(迟)时间最小化。交期越早者排越前面,但是此法会有增加延迟工件数目和增加平均延迟时间的倾向。最早交期法則(EDD)
最小化延迟工件数目。Hodgson法则当n个作业要排至单一机台上时,利用SPT(ShortestProcessTime)法则排序可使得平均流程时间最小化,也就是。最短作业时间(SPT)法则—
最小化平均流程时间(
)范例7.11/3给予一组工作集如表7.6,目标为最小化平均流程时间。表7.6工作作业时间表工作i作业时间ti142837435106127685范例7.12/3依SPT派工法则排序,顺序为4-1-8-7-3-2-5-6。其流程时间计算和表7.7所示。表7.7流程时间计算表工作i流程时间ti4313+483+4+573+4+5+633+4+5+6+723+4+5+6+7+853+4+5+6+7+8+1063+4+5+6+7+8+10+12范例7.13/3所以平均流程时间由上例及图7.3观察,工作流程时间的计算方式为
除了最小化平均流程时间以外,在单机排程问题中SPT法则亦可以最小化平均延误时间、最小化平均等候时间。4187325605101520253035404550加权最短作业时间法则(WSPT)—
最小化加权平均流程时间当工作附有重要性之属性时,排程人员可给予个别之权重,权重值愈大表示重要性愈大。WSPT法则即是将作业时间除以权重,所得之值愈小者表示为愈重要之工作,而将它排至顺序的第一位,依此类推。加权平均流程时间的计算方式为最短作业时间(SPT)法则—
最小化平均延误时间(
)单机排程问题之目标若为最小化平均延误时间,SPT法则排序可得最佳解,即最早交期法则(EDDRule)—
最小化最大延误时间(Lmax)1955年Jackson提出EDD(EarlyDueDate)派工法则,其应用在最小化最大延误时间和最大延迟时间,但是会有增加延迟工作数目和增加平均延迟时间的倾向。EDD法则排序为交期愈早者排至愈前面,即Hodgson法则:求NT最小,
即最小化延迟工件数目以EDD法则将所有工作排序为集合,并计算E集合中所有工作的完工时间。假使结果出现没有或者只有一个延迟工作,则停止,此时已达为最小最佳解。否则进入第二步骤。Step1在集合中从头至尾找出第一个延迟作业,假设为kStep2检视前个工作(包含第个),将最长作业时间之工作移至另一集合中(开始为空集合),其中。Step3重新计算集合中所有工作的完工时间。若集合中没有延迟作业,则停止,集合的延迟个数即为最小解。否则回到步骤2。Step4平行机台(parallelmachine)
排程问题1/2传统平行机台排程问题就是将n个工作如何安排至m部平行机台的问题。平行机台(parallelmachine)
排程问题2/2一般平行机台主要可分为二种:Unrelatedparallelmachine(无关联平行机台):․各机台的加工速度皆不同,且以同一机台来说,
不同的工件也会有不同的加工速度。Identicalparallelmachine(等效平行机台):․所有的机台对于某一个工件的加工速度均相同。最小化平均流程时间范例7.6Step1:SPT法则:{6,10,3,7,9,1,8,2,5,4}Step2:依序将工作指派至最早闲置之机台工作i12345678910作业时间ti5638723542降低总完工时间范例7.7Step1:LPT法则:{4,5,2,1,8,9,3,7,6,10}Step2:依序将工作指派至最早闲置之机台Step3:依SPT法则排序机台上工作工作i12345678910作业时间ti5638723542降低最大延迟时间Step1:EDD法则:{6,10,1,7,2,8,5,4,3,9}Step2:依序将工作指派至最早闲置之机台作业时间交期工作i158269331448125711625738851094151027降低延迟工件数目在探讨单机排程时,我们发现Hodgson方法可使延迟件数最小,现在依此方法应用到平行机台排程上。利用方法7.5.3指派所有工作。步骤1针对每部机台,找出第一个延迟工作,假设发现在机台j的第i个顺位。步骤2检查并找出在机台j前i个顺位中作业时间最长者,将它移至机台j的最后顺位,修正更改后工作的完成时间并重复步骤2。步骤3流线型生产之排程问题1/3如何决定n件工作进入系统的处理顺序:m部序列机台(m-1机台排在m机台前),每件工作都必须依序通过此m部机台,当某工作在一机台之作业完成后,便依序到下一机台等待处理。流线型生产之排程问题2/3琼森法则(Johnson’srule)-两部序列机台最小化总完工时间。找出所有工作在两部机台上之作业时间ti,1和ti,2两者中最小者。Step1假使选出的最小时间在机台1(ti,1),则将所对应的工作排在顺序最早的下一可排空位,继续步骤3。假使选出的最小时间在机台2(ti,2),则将所对应的工作排在顺序最后的下一可排空位,继续步骤3。Step2将已指派之工作删除,回至步骤1,直到所有工作排完为止。Step3流线型生产之排程问题3/3两部序列机台最小化总完工时间:Johnson’srule结果:{,,,,}14253流线型生产之排程问题范例─7.101/3工作i机台1之作业时间机台2之作业时间13526232847656665975483296810104流线型生产之排程问题范例─7.102/3
工作i机台1之作业时间机台2之作业时间13526232847656665975483296810104流线型生产之排程问题范例─7.101/3最后之顺序为3-1-6-9-5-4-7-10-8-2零工型生产之排程问题零工型生产排程问题零工型生产系统的派工法则:随机法则,FCFS,EDD,SPT,LSF,LWR,………零工型生产排程问题一般而言,有限产能排程问题主要可分成下列几种:利用订单排序法则决定订单或制令的加工优先级,再按顺序高低逐一安排各制令的详细作业排程。以「制令」为主的排程方法(Job-basedScheduling或Order-basedScheduling)运算逻辑是利用事件导向(Event-Driven)的仿真观念来描述制造系统的实际运作流程。以「工作中心」为主的排程方法(Event-basedScheduling)派工法则1/2几种常用的派工法则:以首先来到等候线的工作为优先先进先出派工法则(FirsteFirstServed,FCFS)以等候线中工作的最早交期者为优先最早交期派工法则(EarliestDueDate,EDD)等候在线的每一等待工作的选择是具相同机率。一般此法将作为与其他方法之比较基础。随机法则(Random)以等候线中工作的作业时间最短者为优先。最短作业时间派工法则(ShortestProcessingTime,SPT)派工法则2/2以等候线中工作的仍剩余的加工时间最短者为优先。最小剩余时间派工法则(LeastWorkRemaining,LWR)宽裕时间是指交期减掉工作还需在机器上加工完成的时间。以等候线中工作的宽裕时间最短者为优先。最小宽裕时间派工法则(LeastSlackFirst,LSF)依照距离到期日剩余时间对剩余加工时间比率,最小者为优先。关键性比率(CriticalRatio,CR)范例7-11─以制令为主的排程方法1/3以EDD法则来决定制令的加工优先级顺序制令交期111023123213451456156418制令作业顺序与时间交期1A(3)→B(3)→C(2)102A(5)→C(2)133B(4)→A(4)→C(2)124B(3)→C(5)→A(2)185C(5)→B(4)146C(2)→A(5)→B(5)15范例7-11─以制令为主的排程方法2/3顺序制令交期111023123213451456156418范例7-11─以制令为主的排程方法3/3范例7.12(EDD)─以「工作中心」
为主的排程方法1/8制令作业顺序与时间交期1A(3)→B(3)→C(2)102A(5)→C(2)133B(4)→A(4)→C(3)124B(3)→C(5)→A(2)185C(5)→B(4)146C(2)→A(5)→B(5)15范例7.12(EDD)─以「工作中心」
为主的排程方法2/8若以T来表示时间轴。当T=0时,此时机台A,B,C均空闲。当开始着手于A机台的排程时,我们所面对的抉择是制令1或制令2,何者排在最前?假设依据EDD派工法则来进行模拟过程,如表分别针对机台A,B,C选定该上机之制令。机台可排之制令派工法则判断选定之制令作业时间A1,2D1<D213B3,4D3<D434C5,6D5<D655注:Di
表示制令i的交期,其中i=1,2,…,6.范例7.12─派工法则:EDD3/8制令作业顺序与时间交期1A(3)→B(3)→C(2)102A(5)→C(2)133B(4)→A(4)→C(3)124B(3)→C(5)→A(2)185C(5)→B(4)146C(2)→A(5)→B(5)15范例7.12─派工法则:SPT4/8制令作业顺序与时间交期1A(3)
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学二年级道德与法治《小水滴的诉说》情境化活动教学设计
- 初中地理八年级交通运输业二阶三阶提升教学设计
- 初中九年级数学教学设计:相似三角形性质定理一的深度探究与创新应用
- 初中科学七年级下册项目化学习自制酸奶教学设计
- 初中七年级道德与法治“法治与改革相互促进”教学设计
- 初中生物学中考专题复习教学设计:生命的起源与生物进化脉络梳理
- 初中数学九年级沪教版第30章投影与视图考点易错教学设计
- 小学六年级综合实践活动《身边的能源》教学设计
- 八年级数学下册平均数中位数众数课堂训练教学设计
- 初中九年级语文中考命题作文十二题精准预测教学设计
- 圣诞超市促销活动策划方案
- 入团日常培养考察谈话记录范文
- 厂务运维管理办法
- 电信转正考试题库及答案
- T/CHES 105-2023 T/CHAS 090-2023医院节水管理规范
- 2024年秋新沪教牛津版英语三年级上册课件 Unit 6 第1课时
- 早产儿低体重儿护理课件
- JB-T 7072-2023 水轮机调速器及油压装置 系列型谱
- JBT 14645-2023 低温装置用密封垫片 (正式版)
- (高清版)JTGT 3650-01-2022 公路桥梁施工监控技术规程
- 国内外A2O工艺处理城市污水技术研究现状及展望
评论
0/150
提交评论