生产计划与调度

生产计划与调度ProductionPlanningandScheduling浙江大学系统工程研究所OUTLINE－ProductionScheduling1.离散制造过程(APS)2.流程工业（间歇与连续）3.生产调度数学模型4.调度问题优化方法5.智能调度方法离散制造过程生产调度生产控制的主要内容是作业计划与动态调整，它称为车间调度问题。包括两个方面：其一为静态调度，产生一个初始调度；其二为意外事件发生后，进行调度的修改与调整即动态调度。MRPII内主要采用启发式规则进行作业调度与优先级控制，提供一个建议的作业计划，在订单下达时，包括开工日期与完工日期，但已考虑了时间余量，因此，车间调度有一定的缓冲余地。执行中的意外即动态调度可由车间进行有限的局部调度，但当其影响到生产计划时，只能反馈至计划部门，由计划部门统一调整。车间作业调度的特点离散制造过程中，工件生产时间较短，工件切换加工成本低但库存成本很高。主要解决多个产品对设备的争用问题。目的在于寻找最优的设备加工任务次序，使得等待时间与切换时间最小。(1)单机调度问题(2)并行机调度问题(3)Job-shop调度问题(4)Flow-shop调度问题(5)Open-shop调度问题给定一个工件的集合P和一个机器的集合M每个工件包括多道工序Ji={Pi1…..Pik}每台设备可以多个加工任务JMi={J(1)…..J(li)}约束：顺序约束：同一个产品的有序工序对必须在前一工序完成后才能开始占用约束：每台机床同一时间只能加工一个产品的某个工序，每道工序需要在一台给定的机器上非间断地加工一段时间Job-shop问题决策：工序分配给机器上某个时间段目标：总加工时间最短的调度ijkJijkSijkTJob-shop问题A设备B设备C设备D设备任务1任务nJSP是一类满足任务配置和顺序约束要求的资源分配问题，是最困难的组合优化问题之一。生产的柔性：设备使用的柔性设备安排的柔性调度决策内容包括：分配决策(工件的加工次序)时间决策(工件的各工序的加工时间)路径决策(工件的工序的设备分配)Flow-shop调度问题n个工件在m台机器上加工，一个工件分为n道工序，每道工序要求不同的机器加工。n个工件在m台机器上的加工顺序相同，工件在机器上的加工时间是给定。问题目标：求个工件在机器上最优的加工顺序，使最大流程时间最小。M1M2M3M4P1P2设备产品流水车间调度问题，常用表示，即个n工件/m台机器/流水车间/最大流程时间。max///cFmnFlow-shop问题示例假设有A、B、C、D四种零件，都需要进行先车后铣，其加工时间如表所示。零件名称车床工时（时）铣床工时（时）A154B810C65D127合计4126(D,1,1)(C,1,1)(A,1,1)(B,1,1)0152341(D,2,2)(C,2,2)(A,2,2)0193833(B,2,2)15234829M1（车床）M2（铣床）甘特图调度结果甘特图(A,1,1)(C,1,1)B,1,1)(D,1,1)082041(D,2,2)(C,2,2)(A,2,2)0204132(B,2,2)18274526M1（车床）M2（铣床）优化调度结果：调度问题不同特点Flow-shop问题中各个产品的生产路径相同，产品加工工序的顺序与设备的顺序对应，因而某个设备的加工任务顺序就表示产品的加工顺序。Job-shop问题中各个产品的加工路线并不相同，设备上加工任务与总的加工任务矩阵无对应关系，即使产品数量与设备数量确定，也不能确定所有的加工任务，存在路径选择问题。对于Flow-shop，若给定某一个产品生产次序，则可以计算出所有工序的完成时间以及等待时间，而对于Job-shop，由于它存在路径选择问题，即使给定产品生产次序，也无法计算。实际调度问题“因为瓶颈工序在不断变化，我们如何知道瓶颈在那里？”“能否自动分配工序？自动调配人力，设备能力？”“在插入急单时，能否自动根据目标重排计划，一些定单自动延迟，一些定单自动提前？”“能否对采购延迟，生产的延迟，设备的故障，人员的效率等意外快速响应，及自动进行模拟，调整？”ERP作业计划ERP(MRPII)制定作业计划的方法一般包括以下几个步骤：1、确定批量；2、计算提前期；3、安排优先权，安排作业计划；4、根据能力限制调整作业计划，再重复前三个步骤。按预先制定的提前期，用无限能力计划法编制作业计划。APS先进计划调度基于约束理论能够处理生产类型和工序约束自动的，可视化的作业计划TOC约束理论一“约束资源”，“瓶颈”约束资源决定企业有效产出与库存企业有效产出受到企业的生产能力和市场的需求量的制约“非约束”应与“约束”同步库存水平只要能维持“约束”上的物流连续稳定即可“非约束”的利用程度不由其本身决定，而是由系统的“约束”决定的。“约束”上一个小时的损失则是整个系统的一个小时的损失。“非约束”节省的一个小时无益于增加系统有效产出。APS约束类型资源约束a，单一资源b，无限资源c，并发资源d，共享资源e，可调整共享资源顺序约束库存约束特别约束APS计划算法一有限能力计划a，算法顺序计划b，向前顺序计划c，向后顺序计划b，双向计划或瓶颈计划基于模拟的计划基于模拟规则产生一个优化的计划APS计划算法二向前顺序计划固定了开始时间，决定结束时间，也许会违反完成日期。向后顺序计划固定结束时间，决定开始时间，产生一个不会延迟的计划，然而，计划也许有不可行的开始时间。双向计划或瓶颈计划，先安排约束资源上加工的关键件的生产进度计划，以约束资源为基准，把约束资源之前、之间、之后的工序分别按拉动、工艺顺序、推动的方式排定，并进行一定优化，接下来编制非关键件的作业计划。特点：与ERP不同，瓶颈算法顺序计划中的提前期是批量、优先权和其它许多因素的函数，是编制作业计划产生的结果。启发式规则主要的优点是启发式规则往往利用与该问题相关的知识，因此，在通常情况下能够在较短的时间内得到较好方案。启发式规则无法分析与判断其方案的质量。APS中的启发式规则1、预先确定任务的参数类规则如升序定单属性值，优先级、反向优先级2、最小化任务延迟类规则如先到先服务3、最小化任务流程时间类规则适用于最小时间的控制，提高工时利用率。如完成日期4、最大设备能力类规则适用于是计划设备效率来最大化整个设备的生产能力。如闲散时间5、定制规则流程工业调度特点产品配方、产品混合、物料平衡等问题需要考虑主产品、副产品、协产品、半成品循环和回流热蒸汽、冷冻水、压缩空气、水、电等动力能源辅助系统也应纳入调度生产调度流程工业中生产过程的柔性是靠改变各装置间的物流分配和生产装置的工作点来实现的，必须由先进的在线优化、控制技术来保证。静态调度：它考虑工厂生产资源优化分配，属于在确定性环境下静态组合优化问题；动态调度：它是在生产过程出现各种动态变化因素时进行的再调度。静态调度主要的决策变量为：各个操作的开始时间，持续时间、执行的单元设备，以及容量。调度期变化范围为2－3天至2－6月。受到单元设备的操作周期、产品的生产周期以及原料准备所需的时间影响。联系：产品生产率和产品质量指标直接由调度下达至先进控制。先进控制将生产过程的状态、过程模型的参数的更新反馈至生产调度。动态调度动态调度又称再调度：处理突发事件，如某项生产控制指标超出临界值，设备的故障、资源突然短缺以及能源供应中断等。它在生产过程中出现的意外事件进行，保证生产的平稳进行。动态调度依据生产计划和实际工况响应进行调度，与静态调度不同，需要考虑实时性。动态生产调度对生产运行控制的性能具有重大影响，但大规模的具有工业意义的动态生产调度问题由于其复杂性，单纯依靠人（即使是有经验的生产调度人员）来解决已被实践经验证明是不现实的。最优调度问题描述给定：生产过程的工艺、设备及全部相关信息；一个感兴趣的时间段；用户定单及原料到货信息或生产计划信息决定：每个设备单元的操作时间（例如，在感兴趣的时间段内设备在每个时刻执行哪个任务）；工厂的物料流。使得：目标函数最优。生产过程的约束约束条件：生产调度受到诸多因素的限制，一般有：产品的投产期，交货期（完成期），生产能力，加工顺序，加工设备和原料的可用性，批量大小，加工路径，成本限制等，这些都是所谓的约束条件。硬约束与软约束：硬约束是必须要满足的，如交货期，生产能力等，而软约束只需达到一定的满意度即可，如生产成本等。这些约束一般情况是确定的，在进行调度时大都作为确定性因素考虑。不确定性因素：设备故障，原料供应变化，生产任务变化等非正常情况，都是事先不能预见的，大都作为不确定性因素考虑。SchedulingmodelConstraints•Timerelationsstart(A)+p(A)=end(A)sequencingBAend(B)≤start(A)•Resourcecapacityconstraintsunaryresource(activitiescannotoverlap)AB∨BAend(A)≤start(B)∨end(B)≤start(A)BA优化目标生产调度的性能指标可以是成本最低、库存费用最少（减少流动资金占用）、生产周期最短、生产切换最少、设备利用率最高、三废最少等。生产调度的性能指标大致可以归结为三类：最大能力指标成本指标客户满意度指标间歇型生产过程调度间歇型生产过程适用于中小批量且产出价值较高的产品。一般是由一些通用型的设备组成，通过对设备、原材料等资源的共享，在同一组设备上实现多种产品的生产，并且可以实现较为复杂的合成过程。间歇型生产过程的灵活性，对生产调度提出了更高的要求。由于设备可由多项流程共享，工艺描述与设备描述是不同且独立的，在设备管理的同时还亟需工艺管理。为了在特定的时间段上将设备分配给特定的工艺流程，调度成为最重要的功能。中间贮罐协调工序间差异中间贮罐：某些需要较长加工时间的工序成为生产过程的瓶颈，它属于时间瓶颈。为解决瓶颈问题，往往在工序间加入中间贮罐，使得上、下游的物料流分离，协调工序间生产能力、加工时间差异。中间贮罐并不能够完全地解决时间与能力瓶颈。由于中间产品往往具有不稳定的特点，它在加工完成后，必须立即由下一道工序加工，而不允许等待。导致了工序间存在大量的空闲时间，降低了设备的使用率和生产率，中间存储策略不同性质的化工产品(中间品)具有不同的中间存储策略：NIS无限存储策略FIS有限存储策略NIS无中间存储ZW零等待策略MIS混合存储策略成品与原料一般为无限存储，不稳定中间品必须采用ZW策略，而稳定中间品可采用FIS(有限能力的贮罐)或NIS(设备自身存储)。连续型流程工业生产调度连续型生产过程适合于固定的大批量产品的生产，其特点是生产过程工艺流程基本不变，物料流是连续的。物流与能源流的连续、操作任务连续执行是连续过程的本质特点。连续过程的特点为其物料(中间品)可以为多个工序使用，并生产不同的产品，调度问题的目的在于合理调配物料，使之能够获得最大的经济效益。由于关键中间品的生产能力存在瓶颈，可称为有限能力下最大利润问题。连续型流程工业生产调度调度方法：优化目标在于充分利用有限的生产能力进行物料的调配与平衡。由于产品的变化是由装置加工方案和工艺操作条件决定的，生产过程的一定限度内的柔性是靠改变各装置间物流的分配和改变装置运行的工作点即工艺操作参数来实现的。前者通过生产调度系统来确定，后者则通过操作优化，由先进控制来保证。实时性要求：由于生产是在连续不断的进行之中，调度问题也随着生产流程的变化而变化，在时间上要求调度决策迅速及时，与生产流程保持同步，要求滞后时间在一定的域值范围之内。SchedulingProblemsTypeIOnemachineMultiplemachine(Single-stage)SchedulingProblemsTypeIIMulti-stageMulti-purposeS310%90%Hea