第九章 作业计划与排序

null第九章 作业 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 与排序第九章 作业计划与排序西北工业大学管理学院 车阿大 ache@nwpu.edu.cn 13032977687第九章 作业计划与排序第九章 作业计划与排序第一节 制造业作业计划与排序 第二节 服务业作业计划与排序第一节 制造业作业计划与排序第一节 制造业作业计划与排序作业计划与排序的基本概念 作业排序的优先准则 作业优化排序方法 作业计划与排序的基本概念作业计划与排序的基本概念作业计划与排序问题的举例 名词与术语 假设条件 排序问题的分类作业计划与排序问题的举例一般来说，凡是有多个不同的任务要完成，就有作业计划，作业排序问题。作业计划与排序问题的举例nullBCD2.53.81.91.81.72.61.03.0数据输入时间（小时）核对时间（小时）A工作工作中心1工作中心2null——C排序 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ：——AD——BBCD2.53.81.91.81.72.61.03.0数据输入时间（小时）核对时间（小时）A工作工作中心1工作中心2null——C新排序方案：——AD——B原方案：——D——CA——B名词与术语名词与术语作业排序（Sequencing）：确定工件在机器上的加工顺序 编制作业计划（Scheduling）：确定工件的加工顺序，以及机器加工每个工件的开始时间和完成时间 尽管作业排序与作业计划有区别，但人们在使用时又常不加区别的混用 名词与术语名词与术语机器、工件：广义。排序最早应用于制造业，现扩展到服务业。 凡是提供服务的：机器 ，具体可以是机床、工人、码头 凡是接受服务的：工件 工序：工件经过机器的先后顺序假设条件假设条件一个工件不能同时在几台不同的机器上加工 工件在加工过程中采用平行移动方式（无等待） 工件开始加工后，完工前不能插入其它工件 每道工序只在一台机器上完成 工件数、机器数和加工时间已知，且与加工顺序无关 每台机器同时只能加工一个工件排序问题的分类排序问题的分类* 1、按排序的对象分类劳动力作业排序：确定人员何时工作（服务业） 生产作业排序：将不同工件安排在不同的设备上（制造业）2、按加工设备的种类和数量不同分类单台设备排序：多种工件在一台设备 多台设备排序：多种工件在多台设备3、按加工路线的特征不同分类流水型排序：N个工件经过M个工序，所有工件 工艺 钢结构制作工艺流程车尿素生产工艺流程自动玻璃钢生产工艺2工艺纪律检查制度q345焊接工艺规程 顺序都相同 非流水型排序：N个工件经过M个工序，工件工艺顺序不完全都相同排序问题的分类排序问题的分类4、按工件到达车间的情况不同分类静态排序：排序时，所有工件都已经到达，一次性进行排序。 动态排序：排序时，工件陆续到达，需要随时安排加工顺序。5、按目标函数的性质不同（排序追求目标的不同）多目标排序 单目标排序作业排序的优先准则作业排序的优先准则给工件赋予优先权时所遵循的准则称为优先准则。（1）先到先服务准则（FCFS）（First Come First Served ） 按工件到达车间的先后顺序安排加工，先到先加工。（2）后到先服务准则（LCFS）（Last Come First Served ） 作业排序的优先准则作业排序的优先准则（3）最短加工时间准则（SPT）（Shortest Processing Time） 加工顺序按加工时间，从短到长排列。 可使工件加工的平均流程时间最短。 （4）最早交货期准则（EDD）（Earliest Due Date） 按交货期早晚，从早到晚排序。 使最大交货拖期量最小。 （5）随机安排准则：随机地选择一个工件进行加工。 作业排序的优先准则作业排序的优先准则以上准则各有特点 先到先服务准则：对工件比较公平 最短加工时间准则：使工件平均流程时间最短，减少在制品占用量 最早交货期准则使最大交货拖期量最小。 作业排序时选择那一种优先准则，应根据排序的目标来确定。作业优化排序方法作业优化排序方法单一设备排序 两个设备排序 多个设备排序 单一设备排序单一设备排序单一设备排序:N个工件在一台设备上加工的作业排序 流程时间（完工时间）：从被加工对象投入开始，到被加工完为止所用全部时间。 最大流程时间：从被加工对象投入开始，到最后一个零件被加工完为止的时间。 单一设备：最大流程时间固定，与排序无关。 单一设备优化排序的评价标准（追求目标）通常为： 平均流程时间最小、最大交货拖期量最小或为0 单一设备排序方法（1）先到先服务准则（FCFS） （2）最短加工时间（SPT）准则 优点：可使平均流程时间最小。减少在制品占用量，减少流动资金占用。 缺点：由于未考虑交货期，可能发生交货期延迟现象。 （3）最早交货期（EDD）准则 优点：最大交货拖期量最小，保证交货期，减少拖期罚款。 缺点：平均流程时间有所增加。单一设备排序方法5件薄金属板加工工作在爱佳克斯公司的长滩工作中心等待分配。它们的生产时间和到期时间如下表所示。要根据FCFS、SPT、EDD来决定其操作顺序。每件工作按其来到顺序标一字母。5件薄金属板加工工作在爱佳克斯公司的长滩工作中心等待分配。它们的生产时间和到期时间如下表所示。要根据FCFS、SPT、EDD来决定其操作顺序。每件工作按其来到顺序标一字母。举例nullFCFS规则有以下效率测算结果： （a）平均流程时间=总流程时间/工件数 =77/5=15.4（天） （b）使用率=总加工时间/总流程时间 =28/77=36.4% （c）系统中平均工件数=总流程时间/总加工时间 =77/28=2.75（件） （d）平均拖期量=总拖期量/工件数 =11/5=2.2（天）1.按FCFS规则排序的结果是A-B-C-D-EnullSPT效率指标测算结果如下： （a）平均流程时间=65/5=13（天） （b）使用率=28/65=43.1% （c）系统中平均工作数=65/28=2.32（件） （d）平均拖期量=9/5=1.8（天） 2.按SPT规则排序的结果是B-D-A-C-E。null 3.按EDD规则排序结果为B-A-D-C-E。EDD效率指标计算结果为： （a）平均流程时间=68/5=13.6（天） （b）使用率=28/68=41.2% （c）系统中平均工作数=68/28=2.42（件） （d）平均拖期量=6/5=1.2（天）null 以上三个规则的结果总结如下:练习练习J1 J2 J3 J4 J5 加工时间交货期 28 25 13 8 19 4 8 2 6 5下表所示为5种零件的单工序排序问题，试分别用FCFS准则、 SPT准则、 EDD准则进行排序，并计算各种排序下的完工时间、平均流程时间、平均拖期量？两个设备排序两个设备排序: N个工件在两台设备上加工的流水型排序 流水型： N个工件加工的工艺顺序都相同 N个工件总加工周期：从第一个工件在第一台设备上加工开始，到最后一个工件在第二台设备上加工完为止的时间。 两台设备流水型排序的目标：使总加工周期最短。 常用的排序方法：Johnson法。两个设备排序Johnson法的步骤Johnson法的步骤（1）列出所有工件在两台设备的作业时间 （2）找出作业时间最小者 （3）如果该最小值在设备1上，将对应工件排在前面；如果前该最小值在设备2上，将对应工件排在后面 （4）排除已安排好的工件，在剩余的工件中重复步骤（2）、（3），直到所有工件都安排完毕 Johnson法示例Johnson法示例BCD2.53.81.91.81.72.61.03.0数据输入时间（小时）核对时间（小时）A工作工作中心1工作中心2nullBCD2.53.81.91.81.72.61.03.0数据输入时间（小时）核对时间（小时）A工作——C排序方案：nullBD2.53.81.81.72.63.0数据输入时间（小时）核对时间（小时）A工作——C排序方案：——AnullBD3.81.82.63.0数据输入时间（小时）核对时间（小时）工作——C排序方案：——AD——nullBD3.81.82.63.0数据输入时间（小时）核对时间（小时）工作——C排序方案：——AD——B练习6零件在2台设备上流水加工，工序时间见下表，试排出加工顺序使总加工周期最短，并求此时总加工周期？J1 J2 J3 J4 J5 J6M1 M2 4 3 2 3 5 1 6 8 9 12 7 10练习多个设备排序多个设备排序: N个工件在多台设备上加工的流水型排序 常用的排序方法： Palmer法 关键工件法 CDS法多个设备排序nullCDS 法4个工件在3台机器上排序l=1,2,…，m-1对加工时间 和 用Johnson算法 求m－1次加工顺序，求其中最好nulll=1,2,…，m-1对加工时间 和 用Johnson算法 求m－1次加工顺序，求其中最好L=1, (1,2,3,4)L=2, (2,3,1,4)CDS 法第二节 服务业作业计划第二节 服务业作业计划 服务业运作的特点 随机服务系统 人员班次计划 服务业运作的特点 服务业运作的特点 服务交付系统 服务交付系统管理中的问题 影响需求类型的策略 处理非均匀需求的策略服务交付系统服务交付系统服务交付系统指提供何种服务，在何处提供服务和对谁提供服务 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 服务交付系统指确定服务交付系统的结构及其运行方式。具体包括确定目标市场、确定服务产品及其运营方式 对服务交付系统的管理需要特别注意服务与有形产品的形成与消费等方面的差异 服务交付系统管理中的问题服务交付系统管理中的问题顾客参与的影响 顾客参与影响服务运作的标准化，从而影响服务的效率 为使顾客感到舒适、方便和愉快，可能造成服务能力的浪费 对服务质量的感觉是主观的 顾客参与的程度越深，对效率的影响越大服务交付系统管理中的问题（续）服务交付系统管理中的问题（续）减少顾客参与影响的方法 通过服务的标准化减少服务品种 通过自动化减少同顾客的接触 将部分操作与顾客分离 设置一定的库存。主要针对服务套装（成套服务）中的有形产品部分。影响需求的策略影响需求的策略 固定时间表 使用预约系统 使用预订系统 按一定规则推迟交货 为低峰时的需求提供优惠处理非均匀需求的策略处理非均匀需求的策略改善人员班次安排 利用半时工作人员 让顾客自己选择服务水平 利用外单位的设施和设备 雇佣多技能员工 顾客自我服务 采用生产线方法随机服务系统随机服务系统一些典型的随机服务系统一些典型的随机服务系统排队系统 顾 客 服务台 服 务 电话系统 电话呼叫 电话总机 接通呼叫或取消呼 叫 售票系统 购票旅客 售票窗口 收款、售票 设备维修 出故障的设备 修理工 排除设备故障 防空系统 进入阵地的敌机 高射炮 瞄准、射击直至敌机被 击落或离开 排队的队可以是有形的也可以是无形的。如：几个旅客同时打电话订购车票。 顾客和服务员可以是人也可以是物。如：打字员桌子上等待打字的稿件；要求着陆的飞机等都可视为排队系统中的顾客。服务员分别为打字员和飞机着陆的跑道。排队情况的特征排队情况的特征一群顾客到达具有一个或几个服务员的服务机构。在顾客到达机构的时候，可能立即受到服务，也可能因服务员繁忙而在队伍中等待直到获得服务为止，当顾客获得服务后便离开系统。随机服务系统的描述随机服务系统的描述顾客和顾客总体 顾客到达模式 服务机构与服务时间 排队规则（先来现服务等）顾客和顾客总体顾客和顾客总体顾客:任何一种需要系统对其服务的实体，它可以是人，也可以是零件、机器等物 顾客总体：指潜在的顾客总数 具有大的潜在顾客的系统中，顾客源一般假定为无限顾客到达模式顾客到达模式指顾客按照怎样的规律到达系统 一般用顾客相继到达的时间间隔来描述 顾客到达模式 确定性：顾客相继到达的时间间隔是预先确定的或固定的 随机性：顾客相继到达的时间间隔是随机的，不确定的。它一般用概率分布来描述，最常见的随机到达模式为泊松分布服务机构与服务时间服务机构与服务时间服务机构：同一时刻有多少服务台提供服务，服务台之间的布置和关系是如何的 服务时间：指服务台为顾客服务的时间，可以是确定的，也可以是随机的，后者更为常见。 对随机服务时间，一般采用概率分布来描述排队规则排队规则指顾客按照什么样的次序与规则接受服务，常见的排队规则有： 先进先出FIFO 后进先出LIFO 按优先级服务PR 最短处理时间先服务SPT 衡量系统有效性的指标衡量系统有效性的指标服务台的利用率＝平均服务时间/平均到达时间 顾客平均等待时间和逗留时间 平均队长和与系统中平均顾客数 忙期(闲期) 平均队长与系统中顾客数平均队长与系统中顾客数平均队长Lq：正在排队的顾客数。 系统中顾客数L=等待服务的顾客数（即队伍中的顾客数）+正被服务的顾客数平均等待时间与逗留时间平均等待时间与逗留时间平均等待时间Wq ：顾客在系统中平均等待服务的时间即在队伍中平均等待的时间 平均逗留时间W ：顾客在系统中的平均停留时间，即一个顾客在进入系统到服务完成的整个时间 逗留时间=等待时间+服务时间忙期(闲期)忙期(闲期)忙期：服务台全部处于非空闲状态的时间段，否则为非忙期 闲期：服务台全部处于非空闲状态的时间段随机服务系统的计算机仿真法(1)随机服务系统的计算机仿真法(1) 仿真模型 -实体&事件 -顾客&到达 -服务&离开 -系统状态 -系统内顾客数 k -到达事件-〉k+1 -离开事件-〉k -1 -空闲状态 -服务空闲时间 …随机变量决策变量到达间隔 X11, X12, …服务时间 X21, X22, …平均服务 时间 D3窗口数 D1=1等待线数 D2=1{{运行指标 Y L Lq W Wq 随机服务系统的计算机仿真法(2)随机服务系统的计算机仿真法(2)基于离散概率模型的到达间隔与服务时间的生成随机服务系统的计算机仿真法(3)随机服务系统的计算机仿真法(3)基于仿真模型的排队系统行为生成(时间单位：分)随机服务系统的计算机仿真法(4)随机服务系统的计算机仿真法(4)基于系统行为统计 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 生成排队系统运行指标 -平均到达间隔=所有到达间隔之和/(到达人数-1) -平均服务时间=总服务时间/顾客总数 -顾客在队列中的平均等待时间(Wq) = 在队列中等待的总时间/在队列中等待的总人数 -顾客在系统中的平均逗留时间(W) = 在系统中逗留的总时间/顾客总数 -在队列中等待的顾客数的平均(Lq) -在系统中的顾客数的平均(L) -服务空闲的概率=服务总空闲时间/仿真总时间 随机服务系统的手工仿真案例随机服务系统的手工仿真案例某银行储蓄处只有一个服务窗口，假设顾客按泊松分布随机到达，对每个顾客的服务时间也服从泊松分布，表1给出了服从泊松分布的5个顾客到达时间间隔和需要的服务时间。顾客到达时，若服务员正忙，则在队列中等待，服务完毕后顾客即离开系统。假定上一个顾客的服务完毕时刻即为下一个顾客的服务开始时刻。定义顾客到达为事件1，顾客离开为事件2。 随机服务系统的手工仿真案例随机服务系统的手工仿真案例随机服务系统的手工仿真案例 性能评估随机服务系统的手工仿真案例 性能评估服务台利用率ρ=平均服务时间/平均到达时间间隔=3.4/3.54=96% ； 顾客平均等待时间=1.8； 顾客平均逗留时间=5.2 平均队列长度=(0×3.2+0×3.8+0×3.9+0×2.3+1×1.2+0×0.4+1×2.9+2×0.9+1×3.1+0×2.4)/24.1=0.37； 平均顾客数=(0×3.2+1×3.8+0×3.9+1×2.3+2×1.2+1×0.4+2×2.9+3×0.9+2×3.1+1×2.4)/24.1=1.1 空闲期 7.1，忙期17.1人员班次计划人员班次计划人员班次计划指兼顾企业生产需要和员工休息及工作时间两方面要求的前提下，合理安排员工的工作班次（工作日/休息日顺序），使职工数量最少。 常用术语 安排班次的企业部门单位通称部门，被安排的对象通称工人 安排时间以周为时间单位，用周一至周日表示 单班次问题指一天只安排一个班次 多班次问题指一天安排多个班次，如白班、晚班、夜班 周末信息频率A/B指在任意连续B周内，工人有A周在周末休息 R(i,j),表示第i天第j班次所需工人数量,N表示总的人力需求,W表示所需劳动力下限人员班次计划的分类人员班次计划的分类按班次计划的特点分 个人班次计划(固定/非循环班次计划,每个工人沿用特定的工作日/休息日顺序,与他人无关) 公共班次计划(循环班次计划,每隔若干周,每名工人的计划就重复一次) 按每天的班次数分:单班次问题和多班次问题 按工人的种类分 全职排班、全职与兼职排班、多种向下替代排班 按参数的性质分 确定型人员排班和随机型人员排班。确定型人员排班问题指人力需求和其它有关参数已知、固定单班次问题单班次问题特点 最简单、最基本 可作为某些特殊多班次问题的合理近似 为一般人员班次问题的求解提供启示 情形条件（每周工作7天，每天一班，正常需要N人，周末需要n人） （1） 保证工人每周有两个休息日 （2） 保证工人每周的两个休息日为连休 （3） 保证条件（1） 之外，连续2周内每名工人有1周在周末休息 （4）保证条件（2） 之外，连续2周内每名工人有1周在周末休息单班次问题—情形（1） 单班次问题—情形（1） 求解步骤 安排[W1 -n]名工人在周末休息 对余下的n名工人从1到n编号，1号到[W1 -N]号工人周一休息 安排紧接着的[W1 -N]名工人第二天休息（工人1紧接着工人n） 如果5 W1 >5N+2n，则有多余的休息日供分配，可按需要调整班次计划所需劳动力下限为：单班次问题—情形（2） 单班次问题—情形（2） 求解步骤 计算W2 ，给W2名工人编号 取k=max{0,2N+n-2W2}; 1号到k号工人(五,六)休息，k+1~2k号工人(日,一)休息，接下来的[W2-n-k]号工人(六,日)休息; 对余下的工人按(一,二)， (二,三)， (三,四)， (四,五)的顺序安排连休，保证有N名工人在平常日当班W2-k≥n; W2-k≥N所需劳动力下限为：单班次问题—情形（3） 单班次问题—情形（3） 求解步骤 计算W3 ，将[W3 -2n]名工人安排周末休息 将余下的2n名工人等分成A、B两组，A组工人第一周周末休息， B组工人第二周周末休息 按情形  的步骤3、4给A组工人分配第二周的休息日。如果5 W3 >5N+2n，可以安排1至 [W3 -N]号工人周五休息，不足部分按周五、周四到周一的顺序安排休息日 B组的n名工人第一周班次计划与A组的第一周班次计划相同所需劳动力下限为：单班次问题—情形（4）单班次问题—情形（4）求解步骤 将W4 名工人分成A、B两组，A组[W4 /2]工人第一周周末休息， B组( W4 - [W4 /2])工人第二周周末休息 取k=max{0,4N+2n-4W4}， A组中k/2名工人(五2,六2)休息， k/2名工人(日2,一1)休息； B组中k/2名工人(五1,六1)休息， k/2名工人(日1,一2)休息 在保证平常日有N名、周末有n名工人当班的前提下，对A组余下人员按下列顺序安排连休日： (六2,日2)， (四2,五2)， (三2,四2)， (二2,三2)， (一2,二2)；对B组余下人员按下列顺序安排连休日： (六1,日1)， (四1,五1)， (三1,四1)， (二1,三1)， (一1,二1)所需劳动力下限为：