生产计划与调度培训课程

1、生产计划与调度生产计划与调度Production Planning and Scheduling浙江大学系统工程研究所浙江大学系统工程研究所OUTLINEProduction Scheduling1. 离散制造过程离散制造过程(APS)2. 流程工业（间歇与连续）流程工业（间歇与连续）3. 生产调度数学模型生产调度数学模型4. 调度问题调度问题优化方法优化方法5. 智能调度方法智能调度方法离散制造过程生产调度离散制造过程生产调度生产控制的主要内容是作业计划与动态调整，它称为车间调度问题。包括两个方面：n其一为静态调度，产生一个初始调度；n其二为意外事件发生后，进行调度的修改与调整即动态调度。

2、nMRP II内主要采用启发式规则进行作业调度与优先级控制，提供一个建议的作业计划，在订单下达时，包括开工日期与完工日期，但已考虑了时间余量，因此，车间调度有一定的缓冲余地。n执行中的意外即动态调度可由车间进行有限的局部调度，但当其影响到生产计划时，只能反馈至计划部门，由计划部门统一调整。 车间作业调度的特点车间作业调度的特点n离散制造过程中，工件生产时间较短，工件切换加工成本离散制造过程中，工件生产时间较短，工件切换加工成本低但库存成本很高。低但库存成本很高。 n主要解决多个产品对设备的争用问题。主要解决多个产品对设备的争用问题。n目的在于寻找最优的设备加工任务次序，使得等待时间与目的在于寻

3、找最优的设备加工任务次序，使得等待时间与切换时间最小。切换时间最小。(1) 单机调度问题单机调度问题(2) 并行机调度问题并行机调度问题(3) Job-shop调度问题调度问题(4) Flow-shop调度问题调度问题(5) Open-shop调度问题调度问题给定一个工件的集合给定一个工件的集合P和一个机器的集合和一个机器的集合M每个工件包括多道工序每个工件包括多道工序 Ji=Pi1 . Pik 每台设备可以多个加工任务每台设备可以多个加工任务JMi=J(1) . J(li) 约束：约束：n顺序约束：同一个产品的有序工序对必须在前一工序完成后才能顺序约束：同一个产品的有序工序对必须在前一工序完

4、成后才能开始开始n占用约束：每台机床同一时间只能加工一个产品的某个工序，占用约束：每台机床同一时间只能加工一个产品的某个工序，每每道工序需要在一台给定的机器上非间断地加工一段时间道工序需要在一台给定的机器上非间断地加工一段时间Job-shop问题问题 决策：工序分配给机器上某个时间段决策：工序分配给机器上某个时间段目标：总加工时间最短的调度目标：总加工时间最短的调度ijkJijkSijkTJob-shop问题问题A设备设备B设备设备C设备设备D设备设备任务任务1任务任务nJSP是一类满足任务配置和顺序约束要求的资源分配问题，是最困难是一类满足任务配置和顺序约束要求的资源分配问题，是最困难的组合

5、优化问题之一。的组合优化问题之一。生产的柔性：生产的柔性：设备使用的柔性设备使用的柔性设备安排的柔性设备安排的柔性调度决策内容包括：调度决策内容包括：分配决策分配决策(工件的加工次序工件的加工次序)时间决策时间决策(工件的各工序的加工时间工件的各工序的加工时间)路径决策路径决策(工件的工序的设备分配工件的工序的设备分配) Flow-shop调度问题调度问题 n个工件在个工件在m台机器上加工，一个工件分为台机器上加工，一个工件分为n道工序，每道工序道工序，每道工序要求不同的机器加工。要求不同的机器加工。n个工件在个工件在m台机器上的加工顺序相同，工件在机器上的加工台机器上的加工顺序相同，工件在机

6、器上的加工时间是给定。时间是给定。问题目标：求个工件在机器上最优的加工顺序，使最大流程时问题目标：求个工件在机器上最优的加工顺序，使最大流程时间最小。间最小。 M1M2M3M4P1P2设备设备产品产品流水车间调度问题，常用流水车间调度问题，常用 表示，即个表示，即个n工件工件/m台机器台机器/流水车间流水车间/最大流程时间最大流程时间。max/cFmnFlow-shop问题示例问题示例假设有假设有A、B、C、D四种零件，都需要进行先车后铣，其加工时间四种零件，都需要进行先车后铣，其加工时间如表所示。如表所示。零件名称零件名称车床工时（时）车床工时（时）铣床工时（时）铣床工时（时）A A1515

7、4 4B B8 81010C C6 65 5D D12127 7合计合计41412626(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 问题中各个产品的生产路径相同，产品加工工序的顺序与设备

8、的顺序对应，因而某个设备的加工任务顺序就表示产品的加工顺序。 Job-shop问题中各个产品的加工路线并不相同，设备上加工任务与总的加工任务矩阵无对应关系，即使产品数量与设备数量确定，也不能确定所有的加工任务，存在路径选择问题。 对于Flow-shop，若给定某一个产品生产次序，则可以计算出所有工序的完成时间以及等待时间，而对于Job-shop，由于它存在路径选择问题，即使给定产品生产次序，也无法计算。 实际调度问题实际调度问题n“因为瓶颈工序在不断变化，我们如何知道瓶颈在那里？”n“能否自动分配工序？ 自动调配人力，设备能力？”n“在插入急单时，能否自动根据目标重排计划，一些定单自动延迟，一

9、些定单自动提前？”n“能否对采购延迟，生产的延迟， 设备的故障， 人员的效率等意外快速响应，及自动进行模拟，调整？”ERP作业计划作业计划ERP(MRPII)制定作业计划的方法一般包括以下几个步骤：1、确定批量；2、计算提前期；3、安排优先权，安排作业计划；4、根据能力限制调整作业计划，再重复前三个步骤。按预先制定的提前期，用无限能力计划法编制作业计划。APS先进计划调度先进计划调度基于约束理论能够处理生产类型和工序约束自动的，可视化的作业计划TOC约束理论一约束理论一n“约束资源”， “瓶颈”n约束资源决定企业有效产出与库存企业有效产出受到企业的生产能力和市场的需求量的制约n“非约束”应与“

10、约束”同步库存水平只要能维持“约束”上的物流连续稳定即可n“非约束”的利用程度不由其本身决定，而是由系统的“约束”决定的。 n“约束”上一个小时的损失则是整个系统的一个小时的损失。 n“非约束”节省的一个小时无益于增加系统有效产出。APS约束类型约束类型 n资源约束 a，单一资源 b，无限资源 c，并发资源 d，共享资源 e，可调整共享资源 n顺序约束 n库存约束 n特别约束 APS计划算法一计划算法一n有限能力计划有限能力计划 a，算法顺序计划b，向前顺序计划c，向后顺序计划b，双向计划或瓶颈计划 n基于模拟的计划基于模拟的计划 基于模拟规则产生一个优化的计划 APS计划算法计划算法二二向前

11、顺序计划固定了开始时间，决定结束时间，也许会违反完成日期。 向后顺序计划固定结束时间，决定开始时间，产生一个不会延迟的计划，然而，计划也许有不可行的开始时间。双向计划或瓶颈计划，先安排约束资源上加工的关键件的生产进度计划，以约束资源为基准，把约束资源之前、之间、之后的工序分别按拉动、工艺顺序、推动的方式排定，并进行一定优化，接下来编制非关键件的作业计划。特点：与ERP不同，瓶颈算法顺序计划中的提前期是批量、优先权和其它许多因素的函数，是编制作业计划产生的结果。启发式规则启发式规则 n主要的优点是启发式规则往往利用与该问题相关的知识，因此，在通常情况下能够在较短的时间内得到较好方案。 n启发式规

12、则无法分析与判断其方案的质量。APS中的启发式规则中的启发式规则1、 预先确定任务的参数类规则 如升序定单属性值，优先级 、反向优先级 2、 最小化任务延迟类规则 如先到先服务3、 最小化任务流程时间类规则 适用于最小时间的控制，提高工时利用率。如完成日期 4、 最大设备能力类规则 适用于是计划设备效率来最大化整个设备的生产能力。如闲散时间 5、 定制规则流程工业调度特点流程工业调度特点产品配方、产品混合、物料平衡等问题需要考虑主产品、副产品、协产品、半成品循环和回流热蒸汽、冷冻水、压缩空气、水、电等动力能源辅助系统也应纳入调度生产调度生产调度流程工业中生产过程的柔性是靠改变各装置间的物流分配

13、和生产装置的工作点来实现的，必须由先进的在线优化、控制技术来保证。n静态调度：它考虑工厂生产资源优化分配，属于在确定性环境下静态组合优化问题；n动态调度：它是在生产过程出现各种动态变化因素时进行的再调度。 静态调度静态调度n主要的决策变量为：各个操作的开始时间，持续时间、执行的单元设备，以及容量。n调度期变化范围为23天至26月。受到单元设备的操作周期、产品的生产周期以及原料准备所需的时间影响。联系：n产品生产率和产品质量指标直接由调度下达至先进控制。n先进控制将生产过程的状态、过程模型的参数的更新反馈至生产调度。 动态调度动态调度n动态调度又称再调度：处理突发事件，如某项生产控制指标超出临界

14、值，设备的故障、资源突然短缺以及能源供应中断等。它在生产过程中出现的意外事件进行，保证生产的平稳进行。n动态调度依据生产计划和实际工况响应进行调度，与静态调度不同，需要考虑实时性。 n动态生产调度对生产运行控制的性能具有重大影响，但大规模的具有工业意义的动态生产调度问题由于其复杂性，单纯依靠人（即使是有经验的生产调度人员）来解决已被实践经验证明是不现实的。最优调度问题描述最优调度问题描述给定：生产过程的工艺、设备及全部相关信息；一个感兴趣的时间段；用户定单及原料到货信息或生产计划信息决定：每个设备单元的操作时间（例如，在感兴趣的时间段内设备在每个时刻执行哪个任务）；工厂的物料流。使得：目标函数

15、最优。生产过程的约束 约束条件：生产调度受到诸多因素的限制，一般有：产品的投产期，交货期（完成期），生产能力，加工顺序，加工设备和原料的可用性，批量大小，加工路径，成本限制等，这些都是所谓的约束条件。硬约束与软约束：硬约束是必须要满足的，如交货期，生产能力等，而软约束只需达到一定的满意度即可，如生产成本等。这些约束一般情况是确定的，在进行调度时大都作为确定性因素考虑。不确定性因素：设备故障，原料供应变化，生产任务变化等非正常情况，都是事先不能预见的，大都作为不确定性因素考虑。Scheduling modelConstraintsTime relations start(A)+p(A)=end(

16、A) sequencing BA end(B)start(A) Resource capacity constraints unary resource (activities cannot overlap) AB BA end(A)start(B) end(B)start(A)BA优化目标优化目标 生产调度的性能指标可以是成本最低、库存费用最少（减少流动资金占用）、生产周期最短、生产切换最少、设备利用率最高、三废最少等。生产调度的性能指标大致可以归结为三类： n最大能力指标n成本指标 n客户满意度指标 间歇型生产过程调度间歇型生产过程调度n间歇型生产过程适用于中小批量且产出价值较高的产品。

17、一般是由一些通用型的设备组成，通过对设备、原材料等资源的共享，在同一组设备上实现多种产品的生产，并且可以实现较为复杂的合成过程。n间歇型生产过程的灵活性，对生产调度提出了更高的要求。 由于设备可由多项流程共享，工艺描述与设备描述是不同且独立的，在设备管理的同时还亟需工艺管理。为了在特定的时间段上将设备分配给特定的工艺流程，调度成为最重要的功能。中间贮罐协调工序间差异中间贮罐协调工序间差异中间贮罐： 某些需要较长加工时间的工序成为生产过程的瓶颈，它属于时间瓶颈。为解决瓶颈问题，往往在工序间加入中间贮罐，使得上、下游的物料流分离，协调工序间生产能力、加工时间差异。 中间贮罐并不能够完全地解决时间与

18、能力瓶颈。 由于中间产品往往具有不稳定的特点，它在加工完成后，必须立即由下一道工序加工，而不允许等待。导致了工序间存在大量的空闲时间，降低了设备的使用率和生产率，中间存储策略中间存储策略不同性质的化工产品(中间品)具有不同的中间存储策略： NIS无限存储策略 FIS有限存储策略 NIS无中间存储 ZW零等待策略 MIS混合存储策略成品与原料一般为无限存储，不稳定中间品必须采用ZW策略，而稳定中间品可采用FIS(有限能力的贮罐)或NIS(设备自身存储)。 连续型流程工业生产调度连续型流程工业生产调度n连续型生产过程适合于固定的大批量产品的生产，其特点是生产过程工艺流程基本不变，物料流是连续的。n

19、物流与能源流的连续、操作任务连续执行是连续过程的本质特点。n连续过程的特点为其物料(中间品)可以为多个工序使用，并生产不同的产品，调度问题的目的在于合理调配物料，使之能够获得最大的经济效益。n由于关键中间品的生产能力存在瓶颈，可称为有限能力下最大利润问题。 连续型流程工业生产调度连续型流程工业生产调度调度方法：优化目标在于充分利用有限的生产能力进行物料的调配与平衡。 由于产品的变化是由装置加工方案和工艺操作条件决定的，生产过程的一定限度内的柔性是靠改变各装置间物流的分配和改变装置运行的工作点即工艺操作参数来实现的。前者通过生产调度系统来确定，后者则通过操作优化，由先进控制来保证。实时性要求：由

20、于生产是在连续不断的进行之中，调度问题也随着生产流程的变化而变化，在时间上要求调度决策迅速及时，与生产流程保持同步，要求滞后时间在一定的域值范围之内。Scheduling Problems Type IOne machineMultiple machine (Single-stage)Scheduling Problems Type IIMulti-stageMulti-purposeS310%90%HeatS460%Reaction 3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1Heat过程调度类型过程调度类型生产过程生产调

21、度问题可按其产品生产工艺的相似程度分为两类：多产品(Multi-Stage)过程，类似于Flowshop 整个生产过程分为若干个生产阶段，每个阶段内包括若干个并行生产设备，每个产品都需要顺序经过所有的生产阶段。多用途(Multi-Purpose) 过程调度。类似于Jobshop 各个产品的生产工艺不相同，同一产品生产存在多个备选生产路径，其生产路途并不是预先确定的，可以通过设备的组织安排来调整，因此其调度问题比多产品过程更复杂。 ExampleABB1CABC原生产过程中，A加工时间1h，B加工时间4h，C加工时间2h，原来每批次循环时间为4小时，现增加一个设备B1，批次循环时间降为2小时；A

22、工序上的等待时间减少了2h ，C设备上空闲时间由原来的2小时降为零 0 4 5 6 7 8 9 10 11 0 4 5 6 7 8 9Scheduling Problems PropertyDifferent Constraints Sequence (in)dependent setup times Release/due timesDifferent Objective Functions Maximize throughput over a fixed period of time Minimize completion time (makespan) for a given set o

23、f ordersScheduling in Chemical Industry Manufacturing Industry Chemical Industry Order Single unit (e.g. car) Variable amount of chemical (e.g. 1.5 ton of sulfur acid) Production Assembly/addition of parts Mixing of intermediate chemicals in various ratios Variable batch sizesRecycle streams, batch

24、splitting/mixingDifferent storage policies; shared storage tanksUtilities (cooling water, steam, etc.)S310%90%HeatS460%Reaction 3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1HeatState-Task Network (STN) RepresentationS3HeatReaction11h2hSeparationS4S1S2Reaction23hS5S62hReaction 3S71hSTN网是一

25、个具有两类节点的有向图，分别表示状态与任务，状态指生产过程的各种物料，而任务表示物料从一种状态转换至另一状态的操作，通过各个状态的存储能力属性来表示各种中间存储策略。 State-Task Network (STN) RepresentationBsA2=BsA4=20S140%25%S3S260%S475%BIA,S1,2=8BOA,S3,4=5BIA,S2,2=12BOA,S4,4=15State-Task Network (STN) RepresentationInventoryS2S30 1 2 3 4 5 6 Time (h) Reactor 1Reactor 2Reactor 3C

26、olumnHeating Reaction 1Reaction 2Reaction 3Separation0 1 2 3 4 5 6 Time (h)优化调度模型优化调度模型时间表示方式时间表示方式 Kondili, Pantelides & Sargent (1993); Shah, Pantelides & Sargent (1993): STN - Discrete Pantelides (1994): RTN - DiscreteGeneral framework for handling wide range of scheduling problems. MILP

27、with many binaries.Zhang & Sargent (1995); Mockus & Reklaitis (1999): STN/RTN - ContinuousSchilling & Pantelides (1996): RTN - ContinuousGeneral MINLP formulation for design and scheduling. Reduces to MILP for fixed recipes.Ierapetritou & Floudas (1998): STN Continuous Event-Based Fo

28、rmulationNew continuous-time representation with different events for each process unit.Cerda and Mendez (2000); Rodriguez et al. (2001); Lee et al. (2001); Castro et al. (2001)Special cases: No batch splitting/mixing, no resource constraints other than units.优化调度模型优化调度模型时间表示方式 n标准时间分布(UDM)， 以所有的工厂任

29、务的最短操作时间为划分标准等分时间，并假定所有操作(生产任务开始、约束、资源的变化、设备失效等)均发生在各时间段的边界上。非标准连续时间分布(NUDM)，将时间表达为连续变量，时间段的划分为非均匀方式，时间段的个数与长度非预先确定，它可以在整个调度期内的任意一点开始。离散事件表示，不存在时间段的划分，直接以任务和设备上事件的开始、结束时间来表示。Fixed time pointsFixed time intervalVariable time pointsVariable time intervals No common time intervalsTime Representations -

30、Discrete Time Representation2 hr1 hr 30 min3 hrT = 30 minT1T2T3 Approximations often needed Constant processing timesT1T2T30 1 2 3 4 5 6 7 8 t (hr)2 hr1 hr 40 min3 hrT = 20 min0 1 2 3 4 5 6 7 8 t (hr) T1 T2 T3 Time Representations -Continuous Time Representation No approximations needed Accounts for

31、 variable processing times Fewer time periods Fewer variables & constraints Duration and number of time periods unknown T1 T2 T3 T1T2T30 1 2 3 4 5 6 7 8 t (hr)Continuous Time Representation ITime Representations - Event-Based Representation T1T2T30 1 2 3 4 5 6 7 8 t (hr)122233Event-Based Represe

32、ntation 决策变量为设备事件分配与任务事件分配在某一事件上使用逻辑约束使得若任务事件发生，必然使得某个设备事件发生。此方法避免使用时间分配变量模型为MILP优化模型，但需要预先估算事件的个数。 时间表达方式差异时间表达方式差异UDM直观，简单，将调度水平分成的等间隔时间段。问题可以表示为一个多时段的MILP模型。但模型规模与加工时间有关，可能产生计算复杂性问题。NUDM直接通过使用连续变量来表示所有事件（如：任务的开始和结束）的发生时间，而不是分布在每个人为分成的等间隔时间段上，从而达到减少变量的数目的目的。问题最后表示为MINLP，模型较为复杂。模型规模与加工时间无关。在事件数目远小于

33、时间段数目时，NUDM的性能明显优于UDM。COMPUTATIONAL EFFICIENCYAvoid time partitioningFew time intervalsAvoid big-M constraintsNo utility constraintsGENERALITYRecycle streamsBatch splitting/mixingDifferent storage policiesUtility constraintsExample1Given:the time horizonthe available units and storage tanks, and the

34、ir capacitiesthe available utilities (steam, cooling water)the production recipe (mass balance coefficients, utility requirements)the prices of raw materials and final productsDetermine:the sequence and the timing of tasks taking place in each unitthe batch size of tasks (i.e. the processing time an

35、d the allocated resources)the amount of raw materials purchased and final products soldExample2Maximize Production over a fixed time horizonExample2-RemarkExample3Unlimited StorageFinite StorageNo Intermediate StorageZero-WaitCooling WaterLow Pressure SteamHigh Pressure SteamDifferent Storage Polici

36、es Utility ConstraintsExample3-ResultBinaries: 249 Nodes:690 Continuous: 1,711 CPU sec: 22.7 Constraints 3,382Equipment Gantt Chart -Utility Consumption Graph基于基于UDMUDM的调度优化模型的调度优化模型,.,2 , 1, ),(qnERSRQTfMaxiltiktijtin0),(iltiktijtisERSRQTH0),(iltiktijtisERSRQTG0),(iltiktijtisERSRQTD),.,2 , 1 (Ht基于基

37、于UDMUDM的调度优化模型的调度优化模型Assignment Constraints Calculation of duration and finish time of task i Mass balances Utility Constraint Tightening Constraints 计划调度优化方法数学规划计划调度优化方法数学规划数学规划理论包括：排队网络方法(Queing Network)线性规划(Linear Programming, LP)非线性规划(Non-linear Programming, NLP)动态规划(Dynamical Programming, DP)混合

38、整数线性规划(Mixed Integer Linear Programming , MILP)工业中的应用最为广泛的是混合整数规划。计划调度优化方法数学规划计划调度优化方法数学规划优点：主要优点是其全局优化的观点，对所有的分配与次序决策都同时做出，能够有效地评价方案的质量。对于凸问题能够得到全局最优解。即使求解过程在达到到最佳解之前终止，对于凸问题也能够得到达到全局最优解的范围，能够有效地评价方案的质量。缺点：尽管通用算法很有效，但也往往不能在可行时间内得到一个可行解。必须针对特定问题，开发和使用特殊的算法。而且问题发生轻微变化后，原先的算法就可能失效。用户必须将问题抽象为形式化的模型。相同的

39、问题可以描述为不同的模型 。 计划调度优化方法人工智能计划调度优化方法人工智能n生产过程是高维对象，采用规划模型求解调度问题，随着维数的增加，计算量呈指数增长。n为了提高求解效率、减少计算工作量，提出了不少基于规则的优化方法。对于提高计算效率起到了重要的作用；n采用人工智能的方法 (如各种搜索的方法、专家系统的方法等) 对于解决具体的调度问题，不仅可以简化问题，而且能获得合乎实际的满意解。 运筹学和人工智能融合运筹学和人工智能融合 两类方法采用了不同的模型，不同的术语，各有其特点，但都未能真正解决调度与计划决策问题。由于生产环境的动态性，生产领域知识的多样性，调度问题的复杂性，必须将人、数学方

40、法和信息技术结合起来研究生产领域的管理调度问题。 注重算法在实际问题中的应用，以及实际调度与计划问题的解决。 分解Basic Decomposition IdeaCompared to “manufacturing” problems:1. Unknown type and number of batches (tasks); unknown assignments of tasks to units2. Mixing of intermediates; variable batch-size and processing time There are good algorithms for

41、problems with fixed type and number of tasks and fixed assignments Decompose problem in two subproblems1. Determine type and number of tasks and assignments of units to tasks2. Solve reduced problem with an efficient, problem-specific algorithm 分解Basic Decomposition IdeaAlgebra x1+2x2+2x3= 62x1+ x2

42、+ x3= 63x2+4x3= 7 x3+3x4+ x5= 8 x4+2x5= 8 x 1 = 2 x 2 = 1 x 3 = 1 x 4 = 2 x5=3Optimization M2M2 M1 Underdetermined Many solutions Solve (S1) & (S2) many timesSolution time: 2 (M1) 210 = 1024 sec(M1) & (M2) 25+25= 64 sec 1st Subproblem (M1): Mathematical Programming MILP 2nd Subproblem (M2):

43、Constraint Programming Modeling and Solution Paradigms Mathematical Programming Well known & widely applied Efficient algorithms for moderately sized problems (branch-and bound, cutting planes) Search is based on solution of relaxed problems Constraint Programming New Modeling and Solution Parad

44、igm Developed in early 90s in AI Very effective for classes of optimization problemsHighly constrained (feasibility) problems; some scheduling problems Special “constructs” and constraints for classes of problems Constructs:activity X, unary resource Y Constraints: X requires Y(GLOBAL)A B, A B(LOGIC

45、) Highly Expressive Effective local search Search is based on constraint propagation Mathematical vs. Constraint ProgrammingConstraint Programming Fast algorithms for special problems Computationally effective for highly constrained, feasibility and machine sequencing problems Not effective for opti

46、mization problems with complex structure and many feasible solutions Mathematical Programming Intelligent search strategy but computationally expensive for large problems Computationally effective for optimization problems with many feasible solutions Not effective for feasibility problems and machi

47、ne sequencing problems MAIN IDEA Decompose problem into two parts Use MP for high-level optimization decisions Use CP for low-level sequencing decisions Proposed Strategy ProductionZ*Upper boundFeasible solution0 2 4 6 8 10Iterations Fix no/type of tasks and assignment decisions Problem is highly co

48、nstrained: suitable for CP If feasible, obtain lower bound Add integer cut and continue until bounds converge Express problem in an aggregated MP form Use MP to identify potentially good solutions Fix no/type of tasks, assignment of tasks to units Fix no/type of tasks and assignment decisions Proble

49、m is highly constrained: suitable for CP If feasible, obtain lower bound Add integer cut and continue until bounds converge Solve MIP Master Problemmax productions.t. RELAXATIONObtain UBSolve CP Sub problemmax productions.t. ALL CONSTRAINTS w/ fixed no/type of tasksObtain LB Solve MIP Master Problem

50、max productions.t. RELAXATION Obtain UB Fix no/type of tasks,assignment to units Add integer cuts Fix no/type of tasks and assignment decisions Problem is highly constrained: suitable for CP If feasible, obtain lower bound Add integer cut and continue until bounds convergeProposed Formulation Solve

51、MIP Master Problemmax productions.t. RELAXATIONObtain UBCP Sub problem(CP)max productions.t. ALL CONSTRAINTS w/ fixed no/type of tasksObtain LB MIP Master Problem(MP)max productions.t. SOME CONSTRAINTS Obtain UB Fix no/type of tasks,assignment to units Add integer cuts Tasks ActivitiesUnits Unary Re

52、sources Utilities Discrete Resources States Reservoirs Zic = 1 if batch c of task i is carried out Integer Cuts INTsCSCciZZsBBSSciZBBZBjMSZDssicicicicIiticicOitsicMAXiicicMINijIicicic |, , 10)(Generalization of Decomposition Framework I Multipurpose Batch Plant S310%90%HeatS460%Reaction 3S740%Separa

53、tionReaction1Reaction3Reaction270%30%S5S6S2S1HeatMaster MIP Problem CP Sub problemZic = 1 if batch c of task i is carried out Bic = batch size of batch c of task i Ss = inventory level of state s ciMSendciTaskscisStateBconsumesciTaskscisStateBconsumesciTaskcirUtilityRrequiresciTaskcjIijjUnitrequires

54、ciTaskFPsdBciBRciBBBicspisiscisicicsOicsiciiicMAXiicMINi, ., , , ,),(, , , , INTsCSFPsdSsBBSSciZBBZBjESTSTMSZDssssicicIiticicOitsicMAXiicicMINijIicjjicic , 0)(Generalization of Decomposition Framework - General Multi-stage PlantMaster MIP Problem CP Sub problemZic = 1 if batch c of task i is carried

55、 out Bic = batch size of batch c of task i Ss = inventory level of state s ciMSendciTaskscisStateBconsumesciTaskscisStateBconsumesciTaskcjIijjUnitrequiresciTaskFPsdBciBBBicsisicsOicsMAXiicMINi, ., 1 , 1 ,),(, , , INTsCSFPsdSsBBSSciZBBZBjESTSTMSZDssssicicicicsicMAXiicicMINijIicjjicic 11, 0)(T10T20T11

56、T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32 Generalization of Decomposition Framework - Multi-stage Plant: demand in ordersMaster MIP Problem CP Sub problem Fixed batches & batch-sizes Drop c index, B variables Task(order,stage,unit): i(o,k,j) Add assignment constraint kZj

57、oMSendjkoTaskkojkoTaskpreceedjkoTaskkZjojUnitrequiresjkoTaskokjokj, 1|, ., , 1, , 1|, ,)()(, 1)( kJjokjjOokkokjokjkoZkJjESTSTMSXDT10T20T11T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32Generalization of Decomposition Framework: Single-stageMaster MIP Problem CP Sub problem 1|, .,1

58、|, , ., .,okokooZjkoMSendjkoTaskZjkojUnitrequiresjoTaskjodendjoTaskjorstartjoTask)()( 1 maxmaxkJjojjOooOooOoojojoZjrdXDGeneralization of Decomposition Framework IIUse problem-specific algorithm to solve sub problem (not necessarily CP) Minimization of cost of multi-stage problem for orders with rele

59、ase and due timesN orders have to be processed sequentially on K stages, where each stage consists of Mk units. Each order i has release ri and due di time that have to be met, and a processing cost cij and processing time ptij when processed on unit j. The objective is to minimize the sum of proces

60、sing costs subject to meeting the release and due times. Subproblem is a traditional OR problem (job-shop problem) There are efficient algorithmsUse Shifting Bottleneck Procedure (Adams and Balas, 1988) to solve the sub problem Master Problem: AssignmentSub problem: Sequencing Generalization of Decomposition Framework IVMILP SolverMaster