生产与运作管理 11 作业计划与控制

生产与运作管理11作业计划与控制11作业计划与控制OPERATIONSCHEDULINGANDCONTROL111排序问题112流水作业排序问题113单件作业排序问题114生产作业控制115服务业的作业计划111排序问题生产任务的最终落实MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务，才算落到实处将任务安排到工作地，牵涉到任务分配和作业排序问题作业排序（SEQUENCING）的目标作业排序是解决各个生产层次中生产任务的加工顺序问题，既包括哪个生产任务先投产，哪个生产任务后投入，还包括在同一设备上不同工件的加工顺序。作业排序（SEQUENCING）确定工件在设备上的加工顺序。作业计划（SCHEDULING）不仅包括确定工件的加工顺序，还包括确定设备加工每个工件的开始时间和结束时间。排序的目标如何在尽可能满足各种约束条件的情况下，给出一个令人满意的排序方案。编制作业计划要解决的问题SCHEDULING编制作业计划或安排日程计划时间表编制作业计划（SCHEDULING）将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题工厂对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间医院安排病人手术安排手术室、配备手术器械、手术医师和护士学校安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课项目计划管理作业计划有关的名词术语排序SEQUENCING确定零件在机器上的加工顺序编制作业计划SCHEDULING加工制造发生之前的活动（火车时刻表）。包括确定加工顺序、加工任务的分配和加工每个零件的开始和完成时间调度作业计划编制后实施生产控制所采取的一切行动（火车运行的安排，发生晚点后的处理）派工（DISPATCHING）在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人赶工（EXPEDITING）在实际进度已落后于计划进度时采取的行动控制（CONTROLLING）机器表示“服务者”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元零件代表“服务对象”。可以是单个零件，也可以是一批相同的零件加工路线零件加工经过不同机器构成的路线。（某零件要经过车、铣、占、磨的路线加工，我们可以用M1,M2,M3,M4来表示）加工顺序表示每台机器加工N个零件的先后顺序，是排序要解决的问题有关的符号说明P298作业排序问题的分类1、制造业和服务业中两种基本形式的排序（1）劳动力排序主要是确定人员何时工作；（2）生产作业排序主要是将不同的工件安排在不同的设备上，或安排不同的人员做不同的工作。2、生产作业排序的分类（1）按设备数量分类单件车间排序问题（JOBSHOP）加工路线不同流水车间排序问题（FLOWSHOP）所有工件的加工路线相同。单台设备排序问题多台设备排序问题（2）按工件到达车间的情况分类静态排序动态排序确定性动态排序随机性动态排序（3）按目标函数的性质分类单目标排序多目标排序（4）按目标的不同又可划分为不同的排序问题如使平均流程时间最短的排序、使总流程时间最短的排序、使平均误期时间最短的排序、使最大平均误期时间最短的排序问题等。影响生产作业排序的因素1、生产任务的到达方式静态到达（成批到达）生产计划人员将一段时间内的订单汇总，一起安排生产作业计划。动态到达在一段时间内按某种统计分布规律到达，即生产随到随安排。2、车间中的设备种类和数量3、车间中的人员数量在特定的生产操作人员数量少于设备数量的情况下，尤其是服务系统，生产操作人员成为排序时必须考虑的关键资源。4、生产任务在车间的流动模式分流水车间（定流车间）、单件车间（随机路线车间）、混合式加工车间。作业计划的评价标准任务完成的程度设备利用的程度达到企业整体目标的程度由于可操作性的缘故，通常对作业计划的评价集中在任务完成的程度方面。常见的有（1）总流程时间FMIN最短；（2）平均流程时间最短；指一批工件实际生产周期或加工周期的平均值；（4）平均延迟或平均延迟最短；（5）平均在制品占用量最小；（76）总调整时间最小。除了上述标准之外，还有延期罚款最小、生产费用最小、总利润最大、设备利用率最大等。（3）最大延迟LMAX或最大误期TMAX最短；延迟指工件的实际完成时间与预定的交货期之间的差额。这里既包括实际完成时间比预定的交货期晚，即通常意义下的延误，也包括实际完成时间比预定的交货期早的情况。误期指通常意义下的延误。作业排序的基本分析1、作业排序的一般假设（1）一台设备不得同时加工两个或两个以上的任务；（2）一个任务不能同时在几台设备上加工；（3）每个任务必须按照工艺顺序进行加工。2、作业排序所需的有关生产信息任务JI在第J个工序OIJ（J1,2,，NI，I1,2,，M）在相应的设备上MIJ（I,J1,2,N）上所需要的加工时间为TIJ，JI的可能开始时刻为RI和应完工的交货期DI。3、作业排序的一般结论平均流程时间的最优排序方案对于平均完工时间、平均延迟以及平均等待时间也是最优的。但是这一结论对于FMAX和其他最大值目标是不成立的。4参数表示法RWCONWAY等人在THEORYOFSCHEDULING中提出的表示方法，该方法只用4个参数就可以表示大多数不同的排序问题。即N/M/A/BN零件数M机器数A作业类型在A的位置若标以“F”，则代表流水作业排序问题若标以“P”，则表示流水作业排列排序问题若标以“G”，则表示一般单件作业排序问题当M1，则A处为空白，因为对于单台机器的排序问题来说，无所谓加工路线问题B目标函数，通常是使其值最小例作业排序的优先调度规则作业排序问题非常复杂，大多属于NP（NEAROPTIMALSOLUTION）难题，至今还没有研究出有效的解析求解方法。因此，大多数排序算法采用优先调度规则（优先安排哪一个任务的规则）解决生产对设备需求发生的冲突。常见优先调度规则有（1）FCFS（FIRSTCOMEFIRSTSERVED）规则优先选择排队等待的任务中最早进入的任务；（2）SPT（SHORTESTPROCESSINGTIME）法则优先选择加工时间最短的任务；该规则能有效地缩短任务的流程时间，提高设备利用率，降低在制品占用量。（3）EDD（EARLIESTDUEDATE）规则优先选择加工期限最早的任务；（4）SST（SMALLESTSLACKTIME）规则优先选择松弛时间最短的工件。松弛时间是指在不影响交货的条件下，完成任务的机动时间。该规则与EDD规则类似，但更能反映任务的紧迫程度。（1033）式中ST松弛时间；DD（DUEDATE）交货时间；CDCURRENTDATE当前日期；LI剩余工序的加工周期（不含等待时间）。（5）MWKR（MOSTWORKREMAINING）规则优先选择余下加工时间最长的任务；（6）SCR（SMALLESTCRITICALRATIO）规则优先选择关键比最小的任务。关键比（CR）为任务允许停留时间和任务剩余工序加工时间之比。（1034）（7）LWKR（LEASTWORKREMAINING）规则优先选择余下加工时间最短的任务；（8）MOPNR（MOSTOPERATIONSREMAINING）规则优先选择余下工序最多的任务；（9）RANDOM规则随机地挑选任务。局部优先规则决定任务的优先分配顺序仅以单个设备队列中的任务所代表的信息为依据，例SPT、EDD、FCFS等规则。优先调度规则全局优先规则决定任务的优先分配顺序不仅考虑正在排序的设备的情况，还要考虑到其他设备的有关信息，例SCR、MWKR、LWKR，以及MOPNR等规则。有时，需采用优先规则的组合进行排序。例SPTMWRKRANDOM，含义是首先选用SPT规则选择下一个待加工的任务；若同时有多个任务被选中，则采用MWRK规则再次选择；若仍有多个任务被选中，最后采用RANDOM从中随机选择一个作为下一个待加工的任务。作业排序方法（一）单设备排序问题1定理1对于单设备排序问题，SPT规则使平均加工时间最小。2定理2对于单设备排序问题，EDD规则使最大延迟LMAX或最大延误TMAX最短。例1015个工件J1J2J3J4J5的单机作业排序问题的有关资料见下表14682023交货期45173作业时间J5J4J3J2J1工件号07000误期T076197延迟L2013841结束时间149520开始时间20614238交货期75431作业时间J2J4J5J1J3工件排序00000误期T33421延迟L20171065结束时间1811760开始时间23201486交货期37415作业时间J1J2J5J3J4工件排序表109采用SPT规则计算工件排序表1010采用EDD规则计算工件排序3定理3如果对于某单设备排序问题，存在使TMAX为0的工件排序方案，则在交货期比考虑中的工件的作业时间之和大的工件中，将作业时间最大的工件安排在最后位置，如此反复进行，可得到使最小的最优工件顺序。用定理3对例101的计算,见表1011。00000误期T011407延迟L2013961结束时间1410720开始时间20142368交货期74351作业时间J2J5J1J4J3工件排序表1011采用定理3计算工件排序4、加工前设备调整的两个原则（1）如果各工件的调整时间与排序无关，可将其与实际加工时间合并，作为工件的作业时间来考虑即可；（2）如果各工件的调整时间与排序相关，可用总处理时间作为评价准则。（1135）式中S（I1）I在第I个工件加工结束后，再开始第I个工件加工所需调整时间；式中第2项与排序无关，使第1项最小的排序就是最优排序方案。此问题相当于巡回销售商（TRAVELINGSALESMAN）问题,可用分支定界法求解。112流水作业排序问题流水线是流水车间FLOWSHOP典型的代表，每个零件的加工路线都一致。只要加工路线一致M1，M2,M3，MM,不要求每个零件都经过每台机器加工最长流程时间FMAX的计算最长流程时间又称作加工周期6/4/P/FMAX问题，当按顺序S6,1,5,2,4,3加工时，求FMAX加工周期为46N/2/F/FMAX问题的最优算法JOHNSON算法从加工时间矩阵中找出最短的加工时间。若最短的加工时间出现在M1上，则对应的零件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个若所有零件都已排序，停止。否则，转步骤。求最优顺序算法步骤的改进把JOHNSON算法作些改变，改变后的算法按以下步骤进行将所有AIBI的零件按AI值不减的顺序排成一个序列A。将所有AIBI的零件按BI值不增的顺序排成一个序列B。将A放到B之前，就构成了最优加工顺序序列A为2，5，6，1，序列B为4，3，构成最优顺序为2，5，6，1，4，3，与JOHNSON算法结果一致。JOHNSON法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例112顺序2，5，6，4，1，3不符合JOHNSON法则，但它也是一个最优顺序对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。对于一般的流水车间排列排序问题，可以用分支定界法。求一般N/M/P/FMAX问题近优解NEAROPTIMALSOLUTION的启发式算法关键零件法CDS法关键零件法求近优解举例CDS法CAMPBELLDUDEKSMITH提出了一个启发式算法,简称CDS法把JOHNSON算法用于一般的N/M/P/FMAX问题，得到1个加工顺序，取其中优者当1时，按JOHNSON算法得到加工顺序1，2，3，4当2时，得到加工顺序2，3，1，4。对于顺序2，3，1，4，相应的FMAX29取顺序1，2，3，4为最优顺序。当1时，按JOHNSON算法得到加工顺序1，2，3，4；当2时，得到加工顺序2，3，1，4。对于顺序2，3，1，4，相应的FMAX29。所以，取顺序1，2，3，4。我们已经知道，这就是最优顺序。113单件作业排序问题加工描述矩阵和加工时间矩阵无延迟作业计划NONDELAYSCHEDULE的构成称每安排一道工序称作一“步”，设STT步之前已排序工序构成的部分作业计划；OT第T步可以排序的工序的集合；TKOT中工序OK的最早可能开工时间；TKOT中工序OK的最早可能完工时间。无延迟作业计划的构成步骤设T1，S1为空集，O1为各工件第一道工序的集合。求TMINTK，并求出T出现的机器M。如果M有多台，则任选一台。从OT中挑出满足以下两个条件的工序OJ需要机器M加工，且TJT。将确定的工序OJ放入ST，从OT中消去OJ，并将OJ的紧后工序放入OT，使TT1。若还有未安排的工序，转步骤；否则，停止。优先派工法则在介绍无延迟作业计划的构成步骤时，其中第步的两个条件一般都有多个工序可以满足。按什么样的准则来选择可安排的工序，对作业计划的优劣有很大影响。按优先调度法则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。迄今，人们已提出了100多个优先调度法则，其中主要的有下8个SPTSHORTESTPROCESSINGTIME法则优先选择加工时间最短的工序。FCFSFIRSTCOMEFIRSTSERVED法则优先选择最早进入可排工序集合的工件EDDEARLIESTDUEDATE法则优先选择完工期限紧的工件。MWKRMOSTWORKREMAINING法则优先选择余下加工时间最长的工件。LWKRLEASTWORKREMAINING法则优先选择余下加工时间最短的工件。MOPNRMOSTOPERATIONSREMAINING法则优先选择余下工序数最多的工件。SCRSMALLESTCRITICALRATIO法则优先选择临界比最小的工件。临界比为工件允许停留时间与工件余下加工时间之比。RANDOM法则随机地挑一个工件随机抽样法用穷举法或分支定界法求一般单件车间排序问题的最优解时，实际上比较了全部能动作业计划；采用优先调度法则求近优解时，只选择了一种作业计划。随机抽样法介于这两个极端之间。它从全部无延迟作业计划之中抽样，得出多个作业计划，从中选优。应用随机抽样法时，实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划。概率调度法随机抽样法是从K个可供选择的工序以等概率方式挑选，每个工序被挑选的概率为1K，这种方法没有考虑不同工序的特点，有一定盲目性。例如，在构在无延迟作业计划的第步有3道工序，A、B和C可挑选，这3道工序所需的时间分别为3，4和7。如果按RANDOM法则，每道工序挑选上的概率都是13；如果按SPT法则，则只能挑选工序A。现按目标函数的要求，选择了SPT法则。按概率调度法，将这3道工序按加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率，比如A、B和C的挑选概率分别为614、514和314。114生产作业控制生产作业控制的原因和条件不同生产类型生产控制的特点生产控制115服务业的作业计划服务业运作的特点服务交付系统服务特征矩阵服务交付系统管理中的问题影响需求类型的策略处理非均匀需求的策略服务交付系统（SERVICEDELIVERYSYSTEM）服务交付系统与生产系统类似对谁提供服务，目标市场提供何种服务，服务产品即成套服务（SERVICEPACKAGE）在何处提供服务,服务台如何提供服务如何保证服务质量服务特征矩阵快餐洗车租车干洗零售公共汽车无线电和电视电影动物园博物馆学校航空公司美容美发草坪维护房屋油漆出租车餐馆搬家公司外科医生牙医汽车修理代理人器具修理包租飞机顾客化程度服务的复杂程度高低高低IIIIIIIV服务交付系统管理中的问题顾客参与的影响顾客参与影响服务运作实现标准化，从而影响服务效率。为使顾客感到舒适、方便和愉快，也会造成服务能力的浪费。对服务质量的感觉是主观的。顾客参与的程度越深，对效率的影响越大。但是顾客参与是必然趋势预测是长期的、产量导向的预测是短期的，时间导向的预测通过库存调节，可使能力处于平均水平为避免销售缺货，能力按尖峰考虑能力计划固定的产出允许计件工资可变的产出要求计时工资工资时间定额标准紧服务时间取决于一起顾客需求，时间定额标准松时间定额标准质量标准一般是可测量的，固定的质量标准在公众的眼中，易变化质量控制第一线工人只需要技术技能第一线的工人组成服务的主要部分，要求他们能很好地与公众交往工人的技能晚交货和产均衡都是可能的存货不可存储，均衡生产导致生意损失生产计划顾客主要关心完工时间顾客参与作业计划编作业计划顾客并不参与主要的加工过程生产阶段对顾客有直接的影响工艺设计顾客不在服务环境中，产品可规定较少的属性环境和实体产品决定了服务的性质产品设计设施应该提高生产率设施必须满足顾客的体力和精神需要设施布置生产运作可能靠近供应商，便于运输或劳动力易获的地方1生产运作必须靠近顾客选址顾客参与程度低的系统顾客参与程度高的系统生产活动服务交付系统管理中的问题减少顾客参与影响的办法通过服务标准化减少服务品种通过自动化减少同顾客的接触将部分操作于顾客分离影响需求类型的策略固定时间表对于处于服务特征矩阵第III部分的服务业采用，如航班、车次固定使用预约系统对于处于服务特征矩阵第I和II部分的服务业采用，如牙医推迟服务家用电器故障修理为低峰时的需求提供优惠电话夜间半价处理非均匀需求的策略转移需求可减少需求的不均匀性，但不能消除处理非均匀需求的策略改善人员班次安排利用半时工作人员（钟点工）由顾客选择不同的服务利用外单位设施雇佣多技能工人采用生产线方法随机服务系统研究排队现象有助于确定服务能力，控制队长，发挥发挥设施能力随机服务系统的构成最简单的随机服务系统随机服务系统的构成输入过程到达率单位时间内顾客到达的数量排队规则先来先服务（FCFS,优先服务，随机服务，成批服务等服务设施服务台的数量、服务时间等随机服务系统的构成结构类型单队，单阶段多队，单阶段单队，多阶段随机服务系统的结构类型多队，多阶段混合式最简单的随机服务系统最简单的随机服务系统是单队单阶段，按FIFS规则的等待制系统设到达率服从泊松分布，则单位随机到达X个顾客的概率为式中，E为自然对数的底，E271828X0,1,2,3,；其它要用到的符号为最简单的随机服务系统例某医院急诊室有一个外科医生全日工作。急诊病人的到达率服从泊松分布，外科医生的服务率服从负指数分布。问1该外科医生平均有多少时间在救护病人2急诊病人平均等多久才能得到治疗最简单的随机服务系统例某医院急诊室有一个外科医生全日工作。急诊病人的到达率服从泊松分布，外科医生的服务率服从负指数分布。问1该外科医生平均有多少时间在救护病人2急诊病人平均等多久才能得到治疗解已知人员班次计划人员班次安排涉及人力资源的具体使用既要考虑工作需要，又要保证员工每周2天休息人员班次计划，一般以周为计划的时间单位。采取周一至周日的表示法，一周内有5天平常日和2天周末日。每个工人每天只能分配一个班次，不同天可以被分配到不同种类的班次，如白班、晚班、夜班等。周末休息频率用A/B表示在任意连续B周内，工人有A周在周末休息。人员班次计划的分类按班次计划的特点个人班次（INDIVIDUALSCHEDULE）公共班次COMMONSCHEDULE班次的种类单班次和多班次工人的种类全职与兼职参数的性质确定型或随机型班次问题单班次问题特点每天只有一个班次的工人当班，是最简单、最基本的班次问题可作为某些特殊的多班次问题的合理近似求解单班次问题的思想和方法，对建立求解一般的人员班次问题的方法能提供一些启示。求解班次计划设某单位每周工作7天，每天一班，平常日需要N人，周末需要N人。求在以下条件下的班次计划（1）保证工人每周有两个休息日；（2）保证工人每周的两个休息日为连休；（3）除保证条件（1）外，连续2周内，每名工人有一周在周末休息。（4）除保证条件（2）以外，连续2周内，每名工人有一周在周末休息。设WI为条件（I）下最少的工人数；X为大于等于X的最小整数；X在作业计划中表示休息日。求解班次计划（1）条件（1），每周休息2天。对条件（1），所需劳动力下限为W1MAXN,N2N/5（N,N,5N2N/5三个中的最大植）求解步骤安排W1N名工人在周末休息；对余下的N名工人从1到N编号，1号至N号工人周一休息；安排紧接着的W1N名工人第二天休息，这里，工人1紧接着工人N；如果5W15N2N，则有多余的休息日供分配，此时可按需要调整班次计划，只要保证每名工人一周休息两天，平日有N人当班即可。例N5,N8，求班次安排。解W1MAX8,528/59987654321日六五四三二一日六五四三二一工人号条件1下的班次计划条件（2），每周连休2天。对条件（2），所需劳动力下限为W2MAXN,N2N/5，2N2N/3求解步骤为计算W2，给W2