生产计划与调度

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

MRPII内主要采用启发式规则进行作业调度与优先级控制，提供一个建议的作业计划，在订单下达时，包括开工日期与完工日期，但已考虑了时间余量，因此，车间调度有一定的缓冲余地。执行中的意外即动态调度可由车间进行有限的局部调度，但当其影响到生产计划时，只能反馈至计划部门，由计划部门统一调整。

车间作业调度的特点离散制造过程中，工件生产时间较短，工件切换加工成本低但库存成本很高。 主要解决多个产品对设备的争用问题。目的在于寻找最优的设备加工任务次序，使得等待时间与切换时间最小。(1)单机调度问题(2)并行机调度问题(3)Job-shop调度问题(4)Flow-shop调度问题(5)Open-shop调度问题给定一个工件的集合P和一个机器的集合M每个工件包括多道工序Ji={Pi1…..Pik}

每台设备可以多个加工任务JMi={J(1)…..J(li)}约束：顺序约束：同一个产品的有序工序对必须在前一工序完成后才能开始占用约束：每台机床同一时间只能加工一个产品的某个工序，每道工序需要在一台给定的机器上非间断地加工一段时间Job-shop问题

决策：工序分配给机器上某个时间段目标：总加工时间最短的调度Job-shop问题A设备B设备C设备D设备任务1任务nJSP是一类满足任务配置和顺序约束要求的资源分配问题，是最困难的组合优化问题之一。生产的柔性：设备使用的柔性设备安排的柔性调度决策内容包括：分配决策(工件的加工次序)时间决策(工件的各工序的加工时间)路径决策(工件的工序的设备分配)

Flow-shop调度问题

n个工件在m台机器上加工，一个工件分为n道工序，每道工序要求不同的机器加工。n个工件在m台机器上的加工顺序相同，工件在机器上的加工时间是给定。问题目标：求个工件在机器上最优的加工顺序，使最大流程时间最小。

M1M2M3M4P1P2设备产品流水车间调度问题，常用表示，即个n工件/m台机器/流水车间/最大流程时间。Flow-shop问题示例假设有A、B、C、D四种零件，都需要进行先车后铣，其加工时间如表所示。零件名称车床工时（时）铣床工时（时）A154B810C65D127合计4126甘特图调度结果甘特图(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月。受到单元设备的操作周期、产品的生产周期以及原料准备所需的时间影响。联系：产品生产率和产品质量指标直接由调度下达至先进控制。先进控制将生产过程的状态、过程模型的参数的更新反馈至生产调度。动态调度动态调度又称再调度：处理突发事件，如某项生产控制指标超出临界值，设备的故障、资源突然短缺以及能源供应中断等。它在生产过程中出现的意外事件进行，保证生产的平稳进行。动态调度依据生产计划和实际工况响应进行调度，与静态调度不同，需要考虑实时性。动态生产调度对生产运行控制的性能具有重大影响，但大规模的具有工业意义的动态生产调度问题由于其复杂性，单纯依靠人（即使是有经验的生产调度人员）来解决已被实践经验证明是不现实的。最优调度问题描述给定：生产过程的工艺、设备及全部相关信息；一个感兴趣的时间段；用户定单及原料到货信息或生产计划信息决定：每个设备单元的操作时间（例如，在感兴趣的时间段内设备在每个时刻执行哪个任务）；工厂的物料流。使得：目标函数最优。生产过程的约束

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

start(A)+p(A)=end(A)

sequencingB<<Aend(B)≤start(A)Resourcecapacityconstraints

unaryresource(activitiescannotoverlap)A<<B∨B<<Aend(A)≤start(B)∨end(B)≤start(A)BA优化目标

生产调度的性能指标可以是成本最低、库存费用最少（减少流动资金占用）、生产周期最短、生产切换最少、设备利用率最高、三废最少等。生产调度的性能指标大致可以归结为三类：最大能力指标成本指标客户满意度指标

间歇型生产过程调度间歇型生产过程适用于中小批量且产出价值较高的产品。一般是由一些通用型的设备组成，通过对设备、原材料等资源的共享，在同一组设备上实现多种产品的生产，并且可以实现较为复杂的合成过程。

间歇型生产过程的灵活性，对生产调度提出了更高的要求。由于设备可由多项流程共享，工艺描述与设备描述是不同且独立的，在设备管理的同时还亟需工艺管理。为了在特定的时间段上将设备分配给特定的工艺流程，调度成为最重要的功能。中间贮罐协调工序间差异中间贮罐：

某些需要较长加工时间的工序成为生产过程的瓶颈，它属于时间瓶颈。为解决瓶颈问题，往往在工序间加入中间贮罐，使得上、下游的物料流分离，协调工序间生产能力、加工时间差异。中间贮罐并不能够完全地解决时间与能力瓶颈。由于中间产品往往具有不稳定的特点，它在加工完成后，必须立即由下一道工序加工，而不允许等待。导致了工序间存在大量的空闲时间，降低了设备的使用率和生产率，中间存储策略不同性质的化工产品(中间品)具有不同的中间存储策略：NIS无限存储策略FIS有限存储策略NIS无中间存储ZW零等待策略MIS混合存储策略成品与原料一般为无限存储，不稳定中间品必须采用ZW策略，而稳定中间品可采用FIS(有限能力的贮罐)或NIS(设备自身存储)。连续型流程工业生产调度连续型生产过程适合于固定的大批量产品的生产，其特点是生产过程工艺流程基本不变，物料流是连续的。物流与能源流的连续、操作任务连续执行是连续过程的本质特点。连续过程的特点为其物料(中间品)可以为多个工序使用，并生产不同的产品，调度问题的目的在于合理调配物料，使之能够获得最大的经济效益。由于关键中间品的生产能力存在瓶颈，可称为有限能力下最大利润问题。连续型流程工业生产调度调度方法：

优化目标在于充分利用有限的生产能力进行物料的调配与平衡。由于产品的变化是由装置加工方案和工艺操作条件决定的，生产过程的一定限度内的柔性是靠改变各装置间物流的分配和改变装置运行的工作点即工艺操作参数来实现的。前者通过生产调度系统来确定，后者则通过操作优化，由先进控制来保证。实时性要求：由于生产是在连续不断的进行之中，调度问题也随着生产流程的变化而变化，在时间上要求调度决策迅速及时，与生产流程保持同步，要求滞后时间在一定的域值范围之内。SchedulingProblemsTypeIOnemachineMultiplemachine(Single-stage)SchedulingProblemsTypeIIMulti-stageMulti-purposeS310%90%HeatS460%Reaction3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1Heat过程调度类型生产过程生产调度问题可按其产品生产工艺的相似程度分为两类：多产品(Multi-Stage)过程，类似于Flowshop整个生产过程分为若干个生产阶段，每个阶段内包括若干个并行生产设备，每个产品都需要顺序经过所有的生产阶段。多用途(Multi-Purpose)过程调度。类似于Jobshop各个产品的生产工艺不相同，同一产品生产存在多个备选生产路径，其生产路途并不是预先确定的，可以通过设备的组织安排来调整，因此其调度问题比多产品过程更复杂。ExampleABB1CABC原生产过程中，A加工时间1h，B加工时间4h，C加工时间2h，原来每批次循环时间为4小时，现增加一个设备B1，批次循环时间降为2小时；A工序上的等待时间减少了2h，C设备上空闲时间由原来的2小时降为零0１２３45678910110１２３456789SchedulingProblemsPropertyDifferentConstraints•Sequence(in)dependentsetuptimes•Release/duetimesDifferentObjectiveFunctions•Maximizethroughputoverafixedperiodoftime•Minimizecompletiontime(makespan)foragivensetofordersSchedulinginChemicalIndustryVariablebatchsizesRecyclestreams,batchsplitting/mixingDifferentstoragepolicies;sharedstoragetanksUtilities(coolingwater,steam,etc.)S310%90%HeatS460%Reaction3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1HeatState-TaskNetwork(STN)RepresentationS3HeatReaction11h2hSeparationS4S1S2Reaction23hS5S62hReaction3S71hSTN网是一个具有两类节点的有向图，分别表示状态与任务，状态指生产过程的各种物料，而任务表示物料从一种状态转换至另一状态的操作，通过各个状态的存储能力属性来表示各种中间存储策略。

State-TaskNetwork(STN)RepresentationBsA2=BsA4=20S140%25%S3S260%S475%BIA,S1,2=8BOA,S3,4=5BIA,S2,2=12BOA,S4,4=15State-TaskNetwork(STN)RepresentationInventoryS2S30123456Time(h)Reactor1Reactor2Reactor3ColumnHeatingReaction1Reaction2Reaction3Separation0123456Time(h)优化调度模型－时间表示方式Kondili,Pantelides&Sargent(1993);Shah,Pantelides&Sargent(1993):STN-DiscretePantelides(1994):RTN-DiscreteGeneralframeworkforhandlingwiderangeofschedulingproblems.MILPwithmanybinaries.Zhang&Sargent(1995);Mockus&Reklaitis(1999):STN/RTN-ContinuousSchilling&Pantelides(1996):RTN-ContinuousGeneralMINLPformulationfordesignandscheduling.ReducestoMILPforfixedrecipes.Ierapetritou&Floudas(1998):STN–ContinuousEvent-BasedFormulationNewcontinuous-timerepresentationwithdifferenteventsforeachprocessunit.CerdaandMendez(2000);Rodriguezetal.(2001);Leeetal.(2001);Castroetal.(2001)Specialcases:Nobatchsplitting/mixing,noresourceconstraintsotherthanunits.优化调度模型－时间表示方式标准时间分布(UDM)，以所有的工厂任务的最短操作时间为划分标准等分时间，并假定所有操作(生产任务开始、约束、资源的变化、设备失效等)均发生在各时间段的边界上。非标准连续时间分布(NUDM)，将时间表达为连续变量，时间段的划分为非均匀方式，时间段的个数与长度非预先确定，它可以在整个调度期内的任意一点开始。离散事件表示，不存在时间段的划分，直接以任务和设备上事件的开始、结束时间来表示。FixedtimepointsFixedtimeintervalVariabletimepointsVariabletimeintervals

NocommontimeintervalsTimeRepresentations-DiscreteTimeRepresentation2hr1hr30min3hr∆T=30minT1T2T3ApproximationsoftenneededConstantprocessingtimesT1T2T3012345678t(hr)2hr1hr40min3hr∆T=20min012345678t(hr)TimeRepresentations-ContinuousTimeRepresentationNoapproximationsneededAccountsforvariableprocessingtimesFewertimeperiods⇒Fewervariables&constraintsDurationandnumberoftimeperiodsunknownT1T2T3012345678t(hr)ContinuousTimeRepresentationITimeRepresentations-Event-BasedRepresentation

T1T2T301 2 34 5678t(hr)122233Event-BasedRepresentation

决策变量为设备事件分配与任务事件分配在某一事件上使用逻辑约束使得若任务事件发生，必然使得某个设备事件发生。此方法避免使用时间分配变量模型为MILP优化模型，但需要预先估算事件的个数。时间表达方式差异UDM直观，简单，将调度水平分成的等间隔时间段。问题可以表示为一个多时段的MILP模型。但模型规模与加工时间有关，可能产生计算复杂性问题。NUDM直接通过使用连续变量来表示所有事件（如：任务的开始和结束）的发生时间，而不是分布在每个人为分成的等间隔时间段上，从而达到减少变量的数目的目的。问题最后表示为MINLP，模型较为复杂。模型规模与加工时间无关。在事件数目远小于时间段数目时，NUDM的性能明显优于UDM。COMPUTATIONALEFFICIENCYAvoidtimepartitioningFewtimeintervalsAvoidbig-MconstraintsNoutilityconstraintsGENERALITYRecyclestreamsBatchsplitting/mixingDifferentstoragepoliciesUtilityconstraintsExample1Given:thetimehorizontheavailableunitsandstoragetanks,andtheircapacitiestheavailableutilities(steam,coolingwater)theproductionrecipe(massbalancecoefficients,utilityrequirements)thepricesofrawmaterialsandfinalproductsDetermine:thesequenceandthetimingoftaskstakingplaceineachunitthebatchsizeoftasks(i.e.theprocessingtimeandtheallocatedresources)theamountofrawmaterialspurchasedandfinalproductssoldExample2MaximizeProductionoverafixedtimehorizonExample2-RemarkExample3UnlimitedStorageFiniteStorageNoIntermediateStorageZero-WaitCoolingWaterLowPressureSteamHighPressureSteamDifferentStoragePolicies–UtilityConstraintsExample3-ResultBinaries:249Nodes:690Continuous:1,711CPUsec:22.7 Constraints3,382EquipmentGanttChart-UtilityConsumptionGraph基于UDM的调度优化模型基于UDM的调度优化模型AssignmentConstraints

Calculationofdurationandfinishtimeoftaski

Massbalances

UtilityConstraint

TighteningConstraints

计划调度优化方法－数学规划数学规划理论包括： 排队网络方法(QueingNetwork) 线性规划(LinearProgramming,LP) 非线性规划(Non-linearProgramming,NLP) 动态规划(DynamicalProgramming,DP) 混合整数线性规划(MixedIntegerLinearProgramming,MILP)

工业中的应用最为广泛的是混合整数规划。计划调度优化方法－数学规划优点：主要优点是其全局优化的观点，对所有的分配与次序决策都同时做出，能够有效地评价方案的质量。对于凸问题能够得到全局最优解。即使求解过程在达到到最佳解之前终止，对于凸问题也能够得到达到全局最优解的范围，能够有效地评价方案的质量。缺点：

尽管通用算法很有效，但也往往不能在可行时间内得到一个可行解。必须针对特定问题，开发和使用特殊的算法。而且问题发生轻微变化后，原先的算法就可能失效。用户必须将问题抽象为形式化的模型。相同的问题可以描述为不同的模型。

计划调度优化方法－人工智能生产过程是高维对象，采用规划模型求解调度问题，随着维数的增加，计算量呈指数增长。为了提高求解效率、减少计算工作量，提出了不少基于规则的优化方法。对于提高计算效率起到了重要的作用；采用人工智能的方法(如各种搜索的方法、专家系统的方法等)对于解决具体的调度问题，不仅可以简化问题，而且能获得合乎实际的满意解。

运筹学和人工智能融合

两类方法采用了不同的模型，不同的术语，各有其特点，但都未能真正解决调度与计划决策问题。由于生产环境的动态性，生产领域知识的多样性，调度问题的复杂性，必须将人、数学方法和信息技术结合起来研究生产领域的管理调度问题。注重算法在实际问题中的应用，以及实际调度与计划问题的解决。分解BasicDecompositionIdeaComparedto“manufacturing”problems:1.Unknowntypeandnumberofbatches(tasks);unknownassignmentsoftaskstounits2.Mixingofintermediates;variablebatch-sizeandprocessingtime

Therearegoodalgorithmsforproblemswithfixedtypeandnumberoftasksandfixedassignments

Decomposeproblemintwosubproblems1.Determinetypeandnumberoftasksandassignmentsofunitstotasks2.Solvereducedproblemwithanefficient,problem-specificalgorithm分解BasicDecompositionIdeaAlgebra

x1+2x2+2x3=62x1+x2+x3=63x2+4x3 =7x3+3x4+x5=8x4+2x5=8

x1=2x2=1x3=1x4=2x5=3Optimization

M2M2M1Underdetermined⇒Manysolutions⇒Solve(S1)&(S2)manytimesSolutiontime:2

(M1)→210=1024sec(M1)&(M2)→25+25=64sec1stSubproblem(M1):MathematicalProgramming→MILP

2ndSubproblem(M2):ConstraintProgrammingModelingandSolutionParadigms

MathematicalProgrammingWellknown&widelyappliedEfficientalgorithmsformoderatelysizedproblems(branch-andbound,cuttingplanes)SearchisbasedonsolutionofrelaxedproblemsConstraintProgrammingNewModelingandSolutionParadigm•Developedinearly90’sinAI•VeryeffectiveforclassesofoptimizationproblemsHighlyconstrained(feasibility)problems;someschedulingproblemsSpecial“constructs”andconstraintsforclassesofproblems•Constructs: activityX,unaryresourceY•Constraints:XrequiresY (GLOBAL)A→

B,A∨

B (LOGIC)⇒

HighlyExpressive⇒

EffectivelocalsearchSearchisbasedonconstraintpropagation

Mathematicalvs.ConstraintProgrammingConstraintProgramming

Fastalgorithmsforspecialproblems

Computationallyeffectiveforhighlyconstrained,feasibilityandmachinesequencingproblems

Noteffectiveforoptimizationproblemswithcomplexstructureandmanyfeasiblesolutions

MathematicalProgramming

Intelligentsearchstrategybutcomputationallyexpensiveforlargeproblems

ComputationallyeffectiveforoptimizationproblemswithmanyfeasiblesolutionsNoteffectiveforfeasibilityproblemsandmachinesequencingproblemsMAINIDEA

Decomposeproblemintotwoparts

UseMPforhigh-leveloptimizationdecisions

UseCPforlow-levelsequencingdecisions

ProposedStrategy

ProductionZ*×××××UpperboundFeasiblesolution0246810Iterations

Fixno/typeoftasksandassignmentdecisions

Problemishighlyconstrained:suitableforCP

Iffeasible,obtainlowerbound

Addintegercutandcontinueuntilboundsconverge•ExpressprobleminanaggregatedMPform

•UseMPtoidentifypotentiallygoodsolutions

•Fixno/typeoftasks,assignmentoftaskstounits

•Fixno/typeoftasksandassignmentdecisions

•Problemishighlyconstrained:suitableforCP•Iffeasible,obtainlowerbound•Addintegercutandcontinueuntilboundsconverge

SolveMIPMasterProblemmaxproductions.t.RELAXATIONObtainUBSolveCPSubproblemmaxproductions.t.ALLCONSTRAINTSw/fixedno/typeoftasksObtainLB

SolveMIPMasterProblemmaxproductions.t.RELAXATIONObtainUB

Fixno/typeoftasks,assignmenttounits

Addintegercuts

Fixno/typeoftasksandassignmentdecisions

Problemishighlyconstrained:suitableforCP

Iffeasible,obtainlowerbound

AddintegercutandcontinueuntilboundsconvergeProposedFormulation

SolveMIPMasterProblemmaxproductions.t.RELAXATIONObtainUBCPSubproblem(CP)maxproductions.t.ALLCONSTRAINTSw/fixedno/typeoftasksObtainLB

MIPMasterProblem(MP)maxproductions.t.SOMECONSTRAINTS

ObtainUB

Fixno/typeoftasks,assignmenttounits

Addintegercuts

Tasks ⇒

ActivitiesUnits ⇒

UnaryResourcesUtilities⇒

DiscreteResourcesStates ⇒

Reservoirs

Zic=1ifbatchcoftaskiiscarriedout

IntegerCuts

GeneralizationofDecompositionFrameworkIMultipurposeBatchPlant

S310%90%HeatS460%Reaction3S740%SeparationReaction1Reaction3Reaction270%30%S5S6S2S1HeatMasterMIPProblem

CPSubproblemZic=1ifbatchcoftaskiiscarriedoutBic

=batchsizeofbatchcoftaski

Ss

=inventorylevelofstates

GeneralizationofDecompositionFramework-GeneralMulti-stagePlantMasterMIPProblem

CPSubproblemZic=1ifbatchcoftaskiiscarriedoutBic

=batchsizeofbatchcoftaski

Ss

=inventorylevelofstates

T10T20T11T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32GeneralizationofDecompositionFramework-Multi-stagePlant:demandinorders

MasterMIPProblem

CPSubproblemFixedbatches&batch-sizesDropcindex,BvariablesTask→(order,stage,unit):i→(o,k,j)

AddassignmentconstraintT10T20T11T21T30T31F1F2F3S10S20S30S11S21S31P1P2P3T10T20T30T11T21T31T12T22T32GeneralizationofDecompositionFramework:Single-stageMasterMIPProblem

CPSubproblemGeneralizationofDecompositionFrameworkIIUseproblem-specificalgorithmtosolvesubproblem(notnecessarilyCP)

Minimizationofcostofmulti-stageproblemfororderswithreleaseandduetimesNordershavetobeprocessedsequentiallyonKstages,whereeachstageconsistsofMkunits.Eachorderihasreleaserianddueditimethathavetobemet,andaprocessingcostcijandprocessingtimeptijwhenprocessedonunitj.Theobjectiveistominimizethesumofprocessingcostssubjecttomeetingthereleaseandduetimes.

SubproblemisatraditionalORproblem(job-shopproblem)⇒ThereareefficientalgorithmsUseShiftingBottleneckProcedure(AdamsandBalas,1988)tosolvethesubproblemMasterProblem:AssignmentSubproblem:SequencingGeneralizationofDecompositionFrameworkIVMILPSolverMaster(MP)Subproblem(SP)ProgramControlIntegerCut1IntegerCut2IntegerCut3ConstraintProgrammingShiftingBottleneckProcedurePreprocessing1Preprocessing2Preprocessing3ProgramControlMaster(MP)

Subproblem(SP)Data•PlantConfiguration•Units,tasks,states•Yields,massfractions•Processingtimes•Setuptimes,costs•Release/duetimes

IntegratedFramework

智能方法－约束规划highlyeffectivetechnologythatusesdomainreductionandconstraintpropagationtoefficientlysolveproblemsthatarehighlycombinatorialwithhighlylogicalcontent.Theseproblemsareusuallydifficultorimpossibletorepresentwithlinearexpressions.Constraintprogrammingusesinformationcontainedintheproblemto“prune”thesearchspace,rapidlyidentifyingfeasiblesolutions.

约束规划－Constraintprogramming

约束规划的前提是有效地收缩搜索空间与求解一个可行的或最优的方案同样重要。 约束规划适合于实现柔性化，高效率的调度系统。通过为约束传播者封装不同的算法，能把适合特定的问题的求解算法考虑进去，使得柔性成为可能。约束规划适合于处理含有大量约束的调度与再调度问题。

约束规划－收缩Domainfiltering

…Da={1,2},Db={1,2,3}…a<bValue1canbesafelyremovedfromDb.Constraintsareusedactivelytoremoveinconsistenciesfromtheproblem.Arcconsistency

约束规划－搜索Consistencytechniquesare(usually)incomplete.Weneedasearchalgorithmtoresolvetherest!depth-firstsearchassignavaluetothevariablepropagate=maketheproblemlocallyconsistentbacktrackuponfailure…Xin1..5≈X=1∨X=2∨X=3∨X=4∨X=5Ingeneral,searchalgorithmresolvesremainingdisjunctions!X=1∨X≠1(standardlabeling)X<3∨X≥3(domainsplitting)X<Y∨X≥Y(variableordering)constraintsatisfactiontreesearchalgorithmswhilenotsolvedandnotinfeasible

docheckconsistencyifadeadendisdetectedthentrytoescapefromdeadendelseselectvariableselectvalueforvariableendifendwhileThealgorithmCheckConsistencyprocCheckConsistencyForwardCheck;whiledomainshavechangeddo2-ConsCheck;SequencingCheck;RCPCheck;endwhileendproc智能方法-遗传算法

遗传算法是一种随机搜索算法，能够在比较短的时间在解空间的不同区域内搜索。由于它一次产生一组方案，它也适合于使用并行处理。方案的质量因为成本函数上的界限不能获得，所以估价起来有困难。算法的收敛速度很难预测。智能方法－Agent自主性：根据自己的需要，自主地控制其行为合作性：可与其他Agent交互协商，通过合作共同完成感应性：可以主动而有选择地观察外部环境，及时采取动作存在性：不断观察环境，更新内态，选择并执行相应的动作MAS是由若干具有一个或多个目标的Agent按照一定的信息关系、控制关系以及问题求解能力的分布模式而组成的，是一个松散耦合的Agent网络，其内部Agent之间的组织结构可灵活改变。“针对时间而设计(design-to-time)”的实时Agent调度方案ExPlanTechExPlanTech–aproductionplanningsystemwithafunctionalityto:estimatingduedatesandresourcesrequirementsprovidingaprojectplanimplementingre-planningMultiAgentsystem(MAS)MultiAgentsystem(MAS)operator:aninstanceoftheppaandpmaclasses–projectconfigurationanddecomposition,managementoftheoverallprojectworkshop:aninstanceofthepaclass–schedulingandresourceallocationonadepartmentorCNCmachinedatabaseagent:aninstanceofthepaclass–anintegrationagent,integratesExPlanTechwithfactoryERPmaterialagent:aninstanceofthepaclass–integratesanMRP-materialresourceplanningsystemSpecialvisualizationandusermanipulationmeta-agent仿真模拟

仿真模拟提供对全部任务，次序,先后和时间选择决定的结果的直接观察，能够以较低的计算成本对方案进行快速而详细的分析。仿真模拟的方法能够用来测试用户提出的各种候选方案。如果它与一个较为粗略但却快速的调度求解方法结合，通过不断的重复仿真与求解，从而能够实现在线调度。

SupplyChainCustomers

Retailers

Distributioncenters

Warehouses/Assemblypoints

ProductionFacilities

MaterialFlow

OrderFlow

SchedulingwithinSupplyChainI

Excesscapacity:Changeoverto“idle”sometimesveryexpensive(e.g.furnaces,mills)Heavily-loadedplants:Includebacklogcosts(usuallyasmultipleofholdingcost)LongplanninghorizonsProductionTargets

Deliveriesonlyatspecifieddates

Highpeaksindemand(productiontargets)MajorTrade-off:ChangeoverCostvs.InventoryCost024681012(months)SchedulingwithinSupplyChainIIMinimizationofcostoveralongtimehorizonwithduedates

ExistingModelsinChemELiterature

MathematicalProgrammingModels(95%)•Maximizationofproduction;minimizationofmakespan•Shorttimehorizons•Veryexpensivewhenaccountforduedates

OtherModels(5%)•Minimizationofmakespan•Shorttimehorizons•DuedateseffectivelyaddressedResearchObjective:DevelopefficientmodelsforSupplyChainLongtimehorizons;duedatesAccountfortransportation&holdingcostsatdownstreamnodes(?)Accountfordemanduncertainty(?)

FutureDirections

1.UsesophisticatedsolutiontechniquesforMIPmodels

• Newcuttingplanes

• Specializedbranchingtechniquesforcardinalityconstraints

• Exploitnetworkstructureofsupplychains

• Lagrangeandecomposition

2.Hierarchicaldecompositionschemes:planning–schedulingsubproblems

• PlanningMIPmaster–SchedulingCPsubproblem

• PlanningaggregateMIPmaster–SchedulingdetailedMIPsubproblem

3.Rollinghorizonapproaches

• Productiontargetsdeterminedbyplanningproblem

• Detailedschedulingfor2weeks;implementoneweek;reschedulefor2weeksAnyQuestion?Example-制药发酵过程调度Example－流程种子罐、培养罐与发酵罐均为间歇操作，菌种在种子罐与培养罐的培养时间一般为20-30小时和70-80小时，在发酵罐内需要的发酵时间则较长，一般为6-7天左右，因此它是主要的瓶颈工序。提炼工序在发酵放罐后才开始运行，属于连续操作，其能力大于发酵能力。

Example－车间设备Example－STNExample－任务设备Example－STN参数存储任务名称任务编码消耗材料比例T_nameT_idT_materialT_propChar(20)IntegerIntegernumber(4,2)任务名称任务编码产出材料产出工时产出比例T_nameT_idT_productT_protimeT_propChar(20)IntegerintegerNumber(10,2)Number(4,2)任务名称任务编码消耗资源比例T_nameT_idT_engeryT_propChar(20)IntegerIntegernumber(4,2)设备名称设备编码任务编码加工时间最大能力最小能力M_nameM_idT_idM_tasktimeM_maxM_minChar(20)Integerintegernumber(10,2)number(10,2)number(10,2)调度期产品名称产品编码需求数量价格S_numP_nameT_idP_requiredP_priceIntegerchar(20)integerNumber(10,2)Number(10,2)Example－STN描述语言Example－模型存在？所有违反库存约束物料集合所有违反需求产品集合存在？随机选取集合中某一物料随机选取该物料某一任务随机选取执行该任务某一设备随机选取该任务某一发生时刻随机选取任务集合中某一任务随机选取执行该任务某一设备随机选取该任务某一发生时刻随机选取集合中某一元素随机选取生产该产品的某一任务随机选取执行该任务某一设备随机选取该任务某一发生时刻低于需求？删除该产品对应的任务删除该物料对应的任务低于库存？返回返回返回返回返回Example－算法CP优化软件－ILOGOPLStudioAmodelinglanguage－ViaILOGOPL(OptimizationProgrammingLanguage)Aprogrammingsystemthatincludes

Predefinedconstraintswithpowerfulfilteringalgorithms－

ViaaconnectiontoILOGSolverconstraints

Example2－ChemicalCompany

SchedulingCustomPilotChemicalCompanyisachemicalmanufacturerthatproducesbatchesofspecialtychemicalstoorder.Principalequipmentconsistsofeightinterchangablereactorvessels,fiveinterchangeabledistillationcolumns,fourlargeinterchangeablecentrifuges,andanetworkofswitchablepipingandstoragetanks.Customerdemandcomesintheformofordersforbatchesofoneormorespecialtychemicals,normallytobedeliveredsimultaneouslyforfurtherusebythecustomer.Example2－数据结构Example2－数据组织Example2－调度模型Example2－调度结果强化节能减排实现绿色发展内容览要节能减排，世界正在行动为什么要节能减排什么是节能减排节能减排，我们正在行动0502010403目录CONTENTS一、什么是节能减排

在《中华人民共和国节约能源法》中定义的节能减排，是指加强用能管理，采取技术上可行、经济上合理以及环境和社会可以承受的措施，从能源生产到消费的各个环节，降低消耗、减少损失和污染物排放、制止浪费，有效、合理地利用能源。从具体意义上说，节能，就是降低各种类型的能源品消耗；减排，就是减少各种污染物和温室气体的排放，以最大限度地避免污染我们赖以生存的环境。二、为什么要节能减排1、节能减排是缓解能源危机的有效手段

当下，能源危机迫在眉睫，国外有关机构的统计结果显示：2010年中国的能源消耗超过美国，成为全球第一。2011年2月底，中国能源研究会公布最新统计数据显示，2010年我国一次能源消费量为32.5亿吨标准煤，同比增长6%，超过美国成为全球第一能源消费大国。统计数据称，2010年中国一次能源消费量为24.32亿吨油当量，同比增长11.2%，占世界能源消费总量的20.3%。美国一次能源消费量为22.86亿吨油当量，同比增长3.7%，占世界能源消费总量的19.0%。

根据全球已探明传统能源储量测算，按照当前能源消耗增长速度，传统的石化燃料（煤、石油、天然气）已经不够人类再使用一百年。目前新能源的开发利用方兴未艾，2010年全球有23%的能源需求来自再生能源，其中13%为传统的生物能，多半用于热能（例如烧柴），5.2%是来自水力，来自新的可再生能源（小于20MW的水力，现代的生物质能，风能，太阳，地热等）则只有4.7%。在再生能源发电方面，全球来自水力的占16%，来自新的再生能源者占5%。如果我们不对现有能源和资源节约使用，按照目前情况持续下去，有可能百年之后，人类将会部分进入一个“新石器时代”。2节能减排是保护自然生态环境的强力武器

这就是我们美丽的太阳系概念图从太空中拍摄到的蔚蓝色的精灵——地球如诗如画的乡间美景，逸趣横生的劳动生活！

这几乎就是我们每个人为之向往的家园！

然而我们目前不得不面对的却是自然生态环境的日益恶化！

“温室气体大量排放，发生温室效应，造成全球变暖，这已是不争的事实！”目前，在各种温室气体中，二氧化碳对温室效应的影响约占50%，而大气中的二氧化碳有70%是燃烧石化燃料排放的。我们可以了解到冰川融化、海平面上升、干旱蔓延、农作物生产力下降、动植物行为发生变异等气候变化带来的影响。我国最近两年干旱频发，有相当部分原因是受到全球气候变化问题的影响，而这也是我们目前面临的最复杂、最严峻的挑战之一。长江江西九江段裸露出来的江滩湘江长沙橘子洲以西河床（2009年）江西赣江南昌段裸露的桥墩（2009年）温室效应导致气候变化，打破降雨平衡，旱涝频发洪水泛滥——当大自然露出锋利的爪牙，

我们才发现自己原来是如此脆弱，不堪一击！温室效应导致冰川融化

北极熊等极地生命形态遭遇严重的生存危机受世界气候变化影响，曼谷遭遇洪水

温室效应导致的冰川融化还将造成海平面升高的后果，它将直接威胁到沿海国家以及30多个海岛国家的生存和发展。美国环保专家的预测更令人担忧，再过50年～70年，巴基斯坦国土的1/5、尼罗河三角洲的1/3以及印度洋上的整个马尔代夫共和国，都将因海平面升高而被淹没；东京、曼谷、上海、威尼斯、彼得堡和阿姆斯特丹等许多沿海城市也将完全或局部被淹没。

目前，在温室气体排放方面，我们国家正保持领先优势并有继续将其扩大的趋势！！！

马尔代夫倒计时：预计将于90年内被海水淹没。原因：全球变暖导致海平面上升.

马尔代夫是一个群岛国家，80%是珊瑚礁岛，全国最高的两座岛屿距离海平面只有2.4米。因此，它也是受到全球变暖影响最严重的国家.在过去一个世纪里，该国家海平面上升了约20厘米，根据联合国政府间气候变化问题研究小组的报告，2100年全球海平面有可能升高0.18米至0.59米。届时，马尔代夫将面临灭顶之灾。太平洋上的一颗美丽的翡翠——马尔代夫澄澈的碧蓝海水上徜徉着白云——这就是人间天堂婆娑的椰树，洁白的沙滩，舒适的躺椅

图瓦卢倒计时：预计将于未来50至100年消失。原因：气候变暖导致海平面上升.

这个由9座环形珊瑚岛群组成、平均海拔1.5米的小国家每逢二三月大潮期间，就会有30%的国土被海水淹没。近20年来，这些由珊瑚礁形成的海岛已被海水侵蚀得千疮百孔，土壤加速盐碱化，粮食和蔬菜已很难正常生长。事实上，图瓦卢人从2001年就已开始陆陆续续地告别自己的国家，迁往美国、新西兰等国。澳大利亚大堡礁倒计时：20年消