作业计划与控制OperationschedulingandControl.ppt

shanghai, 2019/7/10, Cao Min,Nr. 1,11 作业计划与控制 (Operation scheduling and Control),11.1 排序问题 11.2 流水作业排序问题 11.3 单件作业排序问题 11.4 生产作业控制 11.5 服务业的作业计划,shanghai, 2019/7/10, Cao Min,Nr. 2,11.1 排序问题,生产任务的最终落实 MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务 各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务，才算落到实处 将任务安排到工作地，牵涉到任务分配和作业排序问题,shanghai, 2019/7/10, Cao Min,Nr. 3,作业排序（sequencing）的目标,作业排序是解决各个生产层次中生产任务的加工顺序问题，既包 括哪个生产任务先投产，哪个生产任务后投入，还包括在同一设备上 不同工件的加工顺序。,排序的目标：如何在尽可能满足各种约束条件的情况下，给出一 个令人满意的排序方案。,shanghai, 2019/7/10, Cao Min,Nr. 4,编制作业计划要解决的问题,Scheduling：编制作业计划或安排日程计划(时间表) 编制作业计划（ Scheduling ）：将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题 工厂：对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间 医院：安排病人手术安排手术室、配备手术器械、手术医师和护士 学校：安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课 项目计划管理：作业计划,shanghai, 2019/7/10, Cao Min,Nr. 5,有关的名词术语,排序(Sequencing) ：确定零件在机器上的加工顺序 编制作业计划(Scheduling)：加工制造发生之前的活动（火车时刻表）。包括确定加工顺序、加工任务的分配和加工每个零件的开始和完成时间 调度：作业计划编制后实施生产控制所采取的一切行动（火车运行的安排，发生晚点后的处理） 派工（ Dispatching ）：在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人 赶工（ Expediting ）：在实际进度已落后于计划进度时采取的行动 控制（ Controlling ）： 机器：表示“服务者”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元 零件：代表“服务对象”。可以是单个零件，也可以是一批相同的零件 加工路线：零件加工经过不同机器构成的路线。（某零件要经过车、铣、占、磨的路线加工，我们可以用M1,M2,M3,M4来表示） 加工顺序：表示每台机器加工n个零件的先后顺序，是排序要解决的问题,shanghai, 2019/7/10, Cao Min,Nr. 6,有关的符号说明,P298,shanghai, 2019/7/10, Cao Min,Nr. 7,作业排序问题的分类 1、制造业和服务业中两种基本形式的排序： （1）劳动力排序：主要是确定人员何时工作； （2）生产作业排序：主要是将不同的工件安排在不同的设备上， 或安排不同的人员做不同的工作。 2、生产作业排序的分类： （1）按设备数量分类：,单件车间排序问题（job-shop）: 加工路线不同 流水车间排序问题（flow-shop）: 所有工件的加工路线相同。,shanghai, 2019/7/10, Cao Min,Nr. 8,（2）按工件到达车间的情况分类,（3）按目标函数的性质分类：,单目标排序,多目标排序,（4）按目标的不同又可划分为不同的排序问题：如使平均流程时间 最短的排序、使总流程时间最短的排序、使平均误期时间最短的 排序、使最大平均误期时间最短的排序问题等。,shanghai, 2019/7/10, Cao Min,Nr. 9,影响生产作业排序的因素 1、生产任务的到达方式,2、车间中的设备种类和数量,3、车间中的人员数量 在特定的生产操作人员数量少于设备数量的情况下，尤其是服务 系统，生产操作人员成为排序时必须考虑的关键资源。,4、生产任务在车间的流动模式 分流水车间（定流车间）、单件车间（随机路线车间）、混合式 加工车间。,shanghai, 2019/7/10, Cao Min,Nr. 10,作业计划的评价标准 任务完成的程度 设备利用的程度 达到企业整体目标的程度 由于可操作性的缘故，通常对作业计划的评价集中在任务完成的程度方面。常见的有：,（1）总流程时间 Fmin最短；,（2）平均流程时间,最短；,指一批工件实际生产周期或加工周期的平均值；,shanghai, 2019/7/10, Cao Min,Nr. 11,（4）平均延迟,或平均延迟,最短；,（5）平均在制品占用量最小；,（6）总调整时间最小。,除了上述标准之外，还有延期罚款最小、生产费用最小、 总利润最大、设备利用率最大等。,（3）最大延迟Lmax或最大误期 Tmax 最短； 延迟指工件的实际完成时间与预定的交货期之间的差额。这里既包括实际完成时间比预定的交货期晚，即通常意义下的延误，也包括实际完成时间比预定的交货期早的情况。 误期指通常意义下的延误。,shanghai, 2019/7/10, Cao Min,Nr. 12,作业排序的基本分析 1、作业排序的一般假设： （1）一台设备不得同时加工两个或两个以上的任务； （2）一个任务不能同时在几台设备上加工； （3）每个任务必须按照工艺顺序进行加工。,2、作业排序所需的有关生产信息： 任务Ji在第j个工序Oij （j=1,2, ，Ni ，i=1,2, ，M）在相应的设备上Mij （i,j =1,2,N）上所需要的加工时间为tij ， Ji的可能开始时刻为ri和应完工的交货期di 。,3、作业排序的一般结论： 平均流程时间的最优排序方案对于平均完工时间、平均延迟以及平均等待时间也是最优的。但是这一结论对于Fmax和其他最大值目标是不成立的。,shanghai, 2019/7/10, Cao Min,Nr. 13,4参数表示法,R.W.Conway等人在Theory of Scheduling中提出的表示方法，该方法只用4个参数就可以表示大多数不同的排序问题。即： n /m /A /B n 零件数 m 机器数 A 作业类型 在A的位置若标以“F”，则代表流水作业排序问题 若标以“P”，则表示流水作业排列排序问题 若标以“G”，则表示一般单件作业排序问题 当m1，则A处为空白，因为对于单台机器的排序问题来说，无所谓加工路线问题 B目标函数，通常是使其值最小 例：,shanghai, 2019/7/10, Cao Min,Nr. 14,作业排序的优先调度规则 作业排序问题非常复杂，大多属于NP（Near Optimal solution）难题，至今还没有研究出有效的解析求解方法。因此，大多数排序算法采用优先调度规则（优先安排哪一个任务的规则）解决生产对设备需求发生的冲突。常见优先调度规则有：,（1）FCFS（First Come First Served）规则：优先选择排队等待的任 务中最早进入的任务；,（2）SPT（Shortest Processing Time）法则：优先选择加工时间最短 的任务；该规则能有效地缩短任务的流程时间，提高设备利 用率，降低在制品占用量。,（3）EDD（Earliest Due Date）规则：优先选择加工期限最早的任务；,shanghai, 2019/7/10, Cao Min,Nr. 15,（4）SST（Smallest Slack Time）规则：优先选择松弛时间最短的工件。 松弛时间是指在不影响交货的条件下，完成任务的机动时间。 该规则与EDD规则类似，但更能反映任务的紧迫程度。,（10-33）,式中：ST松弛时间； DD（Due Date）交货时间； CD(Current Date)当前日期； L i 剩余工序的加工周期（不含等待时间）。,（5）MWKR（Most Work Remaining）规则：优先选择余下加工时间 最长的任务；,shanghai, 2019/7/10, Cao Min,Nr. 16,（6）SCR（Smallest Critical Ratio）规则：优先选择关键比最小的任务。 关键比（CR）为任务允许停留时间和任务剩余工序加工时间之比。,（10-34）,（7）LWKR（Least Work Remaining）规则：优先选择余下加工时间 最短的任务；,（8）MOPNR（Most Operations Remaining）规则：优先选择余下工序 最多的任务；,（9）RANDOM规则：随机地挑选任务。,shanghai, 2019/7/10, Cao Min,Nr. 17,局部优先规则：决定任务的优先分配顺序仅以单个设备队列中的任务所代表的信息为依据，例SPT、EDD、FCFS等规则。,优先调度规则,全局优先规则：决定任务的优先分配顺序不仅考虑正在排序的设备的情况，还要考虑到其他设备的有关信息，例SCR、MWKR、LWKR，以及MOPNR等规则。,有时，需采用优先规则的组合进行排序。 例：SPT+MWRK+RANDOM，含义是首先选用SPT规则选择下一个待加 工的任务；若同时有多个任务被选中，则采用MWRK规则再次选择；若 仍有多个任务被选中，最后采用RANDOM从中随机选择一个作为下一 个待加工的任务。,shanghai, 2019/7/10, Cao Min,Nr. 18,作业排序方法 （一）单设备排序问题,1.定理 1 对于单设备排序问题，SPT规则使平均加工时间最小。,2.定理 2 对于单设备排序问题，EDD规则使最大延迟Lmax或最大延 误Tmax最短。,例10-1: 5个工件J1-J2-J3-J4-J5的单机作业排序问题的有关资料见下表：,shanghai, 2019/7/10, Cao Min,Nr. 19,表10-9 采用SPT规则计算工件排序,表10-10 采用EDD规则计算工件排序,shanghai, 2019/7/10, Cao Min,Nr. 20,3.定理 3 如果对于某单设备排序问题，存在使Tmax为0的工件排序方 案，则在交货期比考虑中的工件的作业时间之和大的工件中，将 作业时间最大的工件安排在最后位置，如此反复进行，可得到使 最小的最优工件顺序。,用定理3对例10-1的计算,见表10-11。,shanghai, 2019/7/10, Cao Min,Nr. 21,表10-11 采用定理3计算工件排序,shanghai, 2019/7/10, Cao Min,Nr. 22,4、加工前设备调整的两个原则： （1）如果各工件的调整时间与排序无关，可将其与实际加工时 间合并，作为工件的作业时间来考虑即可； （2）如果各工件的调整时间与排序相关，可用总处理时间作为评 价准则。,（11-35）,式中：S（i-1）i在第i个工件加工结束后，再开始第i个工件加工所 需调整时间； 式中第2项与排序无关，使第1项最小的排序就是最优排序方案。此问题相当于巡回销售商（traveling salesman）问题,可用分支定界法求解。,shanghai, 2019/7/10, Cao Min,Nr. 23,shanghai, 2019/7/10, Cao Min,Nr. 24,11.2 流水作业排序问题,流水线是流水车间(Flow shop) 典型的代表，每个零件的加工路线都一致。 只要加工路线一致：M1， M2, M3，Mm,不要求每个零件都经过每台机器加工,shanghai, 2019/7/10, Cao Min,Nr. 25,最长流程时间Fmax的计算,最长流程时间又称作加工周期 6/4/p/ Fmax问题，当按顺序S( 6,1,5,2,4,3)加工时，求Fmax.,shanghai, 2019/7/10, Cao Min,Nr. 26,加工周期为46,shanghai, 2019/7/10, Cao Min,Nr. 27,n/2/F/Fmax问题的最优算法,Johnson算法： 从加工时间矩阵中找出最短的加工时间。 若最短的加工时间出现在M1上，则对应的零件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个 若所有零件都已排序，停止。否则，转步骤。,shanghai, 2019/7/10, Cao Min,Nr. 28,求最优顺序,shanghai, 2019/7/10, Cao Min,Nr. 29,算法步骤的改进,把Johnson算法作些改变，改变后的算法按以下步骤进行： 将所有aibi的零件按ai值不减的顺序排成一个序列A。 将所有aibi的零件按bi值不增的顺序排成一个序列B。 将A放到B之前，就构成了最优加工顺序,shanghai, 2019/7/10, Cao Min,Nr. 30,序列A为 (2， 5，6，1)，序列B为(4，3)，构成最优顺序为 (2，5，6，1， 4，3)，与Johnson算法结果一致。,shanghai, 2019/7/10, Cao Min,Nr. 31,Johnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例11-2顺序(2，5，6，4，1，3)不符合Johnson法则，但它也是一个最优顺序 对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。 对于一般的流水车间排列排序问题，可以用分支定界法。,shanghai, 2019/7/10, Cao Min,Nr. 32,求一般n/m/P/ Fmax问题近优解 (Near optimal solution)的启发式算法,关键零件法 CDS法,shanghai, 2019/7/10, Cao Min,Nr. 33,关键零件法求近优解举例,shanghai, 2019/7/10, Cao Min,Nr. 34,CDS法,Campbell-Dudek-Smith提出了一个启发式算法,简称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)为最优顺序。,shanghai, 2019/7/10, Cao Min,Nr. 35,当1时，按Johnson算法得到加工顺序(1，2，3，4)； 当2时，得到加工顺序(2，3，1，4)。对于顺序(2，3，1， 4)，相应的Fmax29。所以，取顺序(1，2，3，4)。我们已经知道，这就是最优顺序。,shanghai, 2019/7/10, Cao Min,Nr. 36,11.3 单件作业排序问题,加工描述矩阵和加工时间矩阵,shanghai, 2019/7/10, Cao Min,Nr. 37,无延迟作业计划(non-delay schedule)的构成,称每安排一道工序称作一“步”，设 Stt步之前已排序工序构成的部分作业计划； Ot 第t步可以排序的工序的集合； Tk Ot 中工序Ok的最早可能开工时间； Tk Ot 中工序Ok的最早可能完工时间。,shanghai, 2019/7/10, Cao Min,Nr. 38,无延迟作业计划的构成步骤:, 设t1，S1为空集，O1为各工件第一道工序的集合。 求T*minTk，并求出T*出现的机器M*。如果M*有多台，则任选一台。 从Ot中挑出满足以下两个条件的工序Oj：需要机器M*加工，且TjT*。 将确定的工序Oj放入St，从 Ot 中消去Oj，并将Oj的紧后工序放入 Ot ，使tt1。 若还有未安排的工序，转步骤；否则，停止。,shanghai, 2019/7/10, Cao Min,Nr. 39,shanghai, 2019/7/10, Cao Min,Nr. 40,优先派工法则,在介绍无延迟作业计划的构成步骤时，其中第步的两个条件一般都有多个工序可以满足。按什么样的准则来选择可安排的工序，对作业计划的优劣有很大影响。按优先调度法则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。 迄今，人们已提出了100多个优先调度法则，其中主要的有下8个： SPT(Shortest Processing Time)法则 优先选择加工时间最短的工序。 FCFS(First Come First Served)法则 优先选择最早进入可排工序集合的工件 EDD(Earliest Due Date)法则 优先选择完工期限紧的工件。 MWKR(Most Work Remaining)法则 优先选择余下加工时间最长的工件。 LWKR(Least Work Remaining)法则 优先选择余下加工时间最短的工件。 MOPNR(Most Operations Remaining)法则 优先选择余下工序数最多的工件。 SCR(Smallest Critical Ratio)法则 优先选择临界比最小的工件。临界比为工件允许停留时间与工件余下加工时间之比。 RANDOM法则 随机地挑一个工件,shanghai, 2019/7/10, Cao Min,Nr. 41,随机抽样法,用穷举法或分支定界法求一般单件车间排序问题的最优解时，实际上比较了全部能动作业计划；采用优先调度法则求近优解时，只选择了一种作业计划。 随机抽样法介于这两个极端之间。 它从全部无延迟作业计划之中抽样，得出多个作业计划，从中选优。 应用随机抽样法时，实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划。,shanghai, 2019/7/10, Cao Min,Nr. 42,概率调度法,随机抽样法是从k个可供选择的工序以等概率方式挑选，每个工序被挑选的概率为1k，这种方法没有考虑不同工序的特点，有一定盲目性。 例如，在构在无延迟作业计划的第步有3道工序，A、B和C可挑选，这3道工序所需的时间分别为3，4和7。如果按RANDOM法则，每道工序挑选上的概率都是13；如果按SPT法则，则只能挑选工序A。现按目标函数的要求，选择了SPT法则。按概率调度法，将这3道工序按加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率，比如A、B和C的挑选概率分别为614、514和314。,shanghai, 2019/7/10, Cao Min,Nr. 43,11.4 生产作业控制,生产作业控制的原因和条件 不同生产类型生产控制的特点 生产控制,shanghai, 2019/7/10, Cao Min,Nr. 44,11.5 服务业的作业计划,服务业运作的特点 服务交付系统 服务特征矩阵 服务交付系统管理中的问题 影响需求类型的策略 处理非均匀需求的策略,shanghai, 2019/7/10, Cao Min,Nr. 45,服务交付系统（service delivery system）,服务交付系统 与生产系统类似 对谁提供服务，目标市场 提供何种服务，服务产品即成套服务（service package） 在何处提供服务, 服务台 如何提供服务 如何保证服务质量,shanghai, 2019/7/10, Cao Min,Nr. 46,服务特征矩阵,顾客化程度,服务的复杂程度,高,低,高,低,I,III,II,IV,shanghai, 2019/7/10, Cao Min,Nr. 47,服务交付系统管理中的问题,顾客参与的影响 顾客参与影响服务运作实现标准化，从而影响服务效率。 为使顾客感到舒适、方便和愉快，也会造成服务能力的浪费。 对服务质量的感觉是主观的。 顾客参与的程度越深，对效率的影响越大。 但是顾客参与是必然趋势,shanghai, 2019/7/10, Cao Min,Nr. 48,shanghai, 2019/7/10, Cao Min,Nr. 49,服务交付系统管理中的问题,减少顾客参与影响的办法 通过服务标准化减少服务品种 通过自动化减少同顾客的接触 将部分操作于顾客分离,shanghai, 2019/7/10, Cao Min,Nr. 50,影响需求类型的策略,固定时间表 对于处于服务特征矩阵第III部分的服务业采用，如航班、车次固定 使用预约系统 对于处于服务特征矩阵第I和II部分的服务业采用，如牙医 推迟服务 家用电器故障修理 为低峰时的需求提供优惠 电话夜间半价,shanghai, 2019/7/10, Cao Min,Nr. 51,处理非均匀需求的策略,转移需求可减少需求的不均匀性，但不能消除 处理非均匀需求的策略 改善人员班次安排 利用半时工作人员（钟点工） 由顾客选择不同的服务 利用外单位设施 雇佣多技能工人 采用生产线方法,shanghai, 2019/7/10, Cao Min,Nr. 52,随机服务系统,研究排队现象有助于确定服务能力，控制队长，发挥发挥设施能力 随机服务系统的构成 最简单的随机服务系统,shanghai, 2019/7/10, Cao Min,Nr. 53,随机服务系统的构成,输入过程 到达率：单位时间内顾客到达的数量 排队规则 先来先服务（FCFS),优先服务，随机服务，成批服务等 服务设施 服务台的数量、服务时间等,shanghai, 2019/7/10, Cao Min,Nr. 54,随机服务系统的构成结构类型,单队，单阶段,多队，单阶段,单队，多阶段,shanghai, 2019/7/10, Cao Min,Nr. 55,随机服务系统的结构类型,多队，多阶段,混合式,shanghai, 2019/7/10, Cao Min,Nr. 56,最简单的随机服务系统,最简单的随机服务系统是单队单阶段，按FIFS规则的等待制系统 设到达率服从泊松分布，则单位随机到达x个顾客的概率为：,式中，e为自然对数的底，e=2.71828;,x=0,1,2,3,；,shanghai, 2019/7/10, Cao Min,Nr. 57,其它要用到的符号为：,最简单的随机服务系统,例：某医院急诊室有一个外科医生全日工作。急诊病人的到达率服从泊松分布，外科医生的服务率服从负指数分布。问：(1)该外科医生平均有多少时间在救护病人？(2)急诊病人平均等多久才能得到治疗？,shanghai, 2019/7/10, Cao Min,Nr. 58,最简单的随机服务系统,例：某医院急诊室有一个外科医生全日工作。急诊病人的到达率服从泊松分布，外科医生的服务率服从负指数分布。问： (1)该外科医生平均有多少时间在救护病人？ (2)急诊病人平均等多久才能得到治疗？,解：,已知,shanghai, 2019/7/10, Cao Min,Nr. 59,人员班次计划,人员班次安排涉及人力资源的具体使用 既要考虑工作需要，又要保证员工每周2天休息 人员班次计划，一般以周为计划的时间单位。 采取周一至周日的表示法，一周内有5天平常日和2天周末日。 每个工人每天只能分配一个班次，不同天可以被分配到不同种类的班次，如白班、晚班、夜班等。 周末休息频率用A/B表示：在任意连续B周内，工人有A周在周末休息。,shanghai, 2019/7/10, Cao Min,Nr. 60,人员班次计划的分类,按班次计划的特点 个人班次（individual schedule） 公共班次(common schedule) 班次的种类 单班次和多班次 工人的种类 全职与兼职 参数的性质 确定型或随机型班次问题,shanghai, 2019/7/10, Cao Min,Nr. 61,单班次问题,特点 每天只有一个班次的工人当班，是最简单、最基本的班次问题 可作为某些特殊的多班次问题的合理近似 求解单班次问题的思想和方法，对建立求解一般的人员班次问题的方法能提供一些启示。,shanghai, 2019/7/10, Cao Min,Nr. 62,求解班次计划,设某单位每周工作7天，每天一班，平常日需要N人，周末需要n人。求在以下条件下的班次计划: （1）保证工人每周有两个休息日； （2）保证工人每周的两个休息日为连休； （3）除保证条件（1）外，连续2周内，每名工人有一周在周末休息。 （4）除保证条件（2）以外，连续2周内，每名工人有一周在周末休息。 设Wi 为条件（i）下最少的工人数；x为大于等于x的最小整数；X在作业计划中表示休息日。,shanghai, 2019/7/10, Cao Min,Nr. 63,求解班次计划（1）,条件（1），每周休息2天。 对条件（1），所需劳动力下限为 W1max n,N+2n/5 （N, n, (5N+2n)/5三个中的最大植） 求解步骤： 安排W1n名工人在周末休息； 对余下的n名工人从1到n编号，1号至N号工人周一休息； 安排紧接着的W1N名工人第二天休息，这里，工人1紧接着工人n； 如果5W15N+2n，则有多余的休息日供分配，此时可按需要调整班次计划，只要保证每名工人一周休息两天，平日有N人当班即可。,shanghai, 2019/7/10, Cao Min,Nr. 64,例：N=5,n=8，求班次安排。 解： W1max 8,5+28/59,条件1下的班次计划,shanghai, 2019/7/10, Cao Min,Nr. 65,条件（2），每周连休2天。 对条件（2），所需劳动力