【正文】 reschedule for 2 weeks Any Question? Example制藥發(fā)酵過程調度 菌種 種子 培養(yǎng) 發(fā)酵 過濾 粗品 層析 萃取 離交 萃取 層析 成品 結晶 培養(yǎng) 精制 Example－流程 種子罐、培養(yǎng)罐與發(fā)酵罐均為間歇操作，菌種在種子罐與培養(yǎng)罐的培養(yǎng)時間一般為 2030小時和 7080小時，在發(fā)酵罐內需要的發(fā)酵時間則較長，一般為 67天左右 ，因此它是主要的瓶頸工序。 Supply Chain Customers Retailers Distribution centers Warehouses/ Assembly points Production Facilities Material Flow Order Flow Scheduling within Supply Chain I Excess capacity: Changeover to “ idle” sometimes very expensive (. furnaces, mills) Heavilyloaded plants: Include backlog costs (usually as multiple of holding cost) Long planning horizons Production Targets Deliveries only at specified dates High peaks in demand (production targets) Major Tradeoff: Changeover Cost vs. Inventory Cost 0 2 4 6 8 10 12 (months) Scheduling within Supply Chain II Minimization of cost over a long time horizon with due dates Existing Models in ChemE Literature Mathematical Programming Models (95%) ? Maximization of production。 智能方法－ Agent ? 自主性：根據(jù)自己的需要，自主地控制其行為 ? 合作性：可與其他 Agent交互協(xié)商，通過合作共同完成 ? 感應性：可以主動而有選擇地觀察外部環(huán)境，及時采取動作 ? 存在性：不斷觀察環(huán)境，更新內態(tài)，選擇并執(zhí)行相應的動作 MAS是由若干具有一個或多個目標的 Agent按照一定的信息關系、控制關系以及問題求解能力的分布模式而組成的，是一個松散耦合的 Agent網絡，其內部 Agent之間的組織結構可靈活改變。 endwhile endproc 智能方法 遺傳算法 ? 遺傳算法是一種隨機搜索算法，能夠在比較短的時間在解空間的不同區(qū)域內搜索。 約束規(guī)劃－ 收縮 ? Domain filtering … Da={1,2}, Db={1,2,3} … ab Value 1 can be safely removed from Db. Constraints are used actively to remove inconsistencies from the problem. ? Arc consistency 約束規(guī)劃－ 搜索 Consistency techniques are (usually) inplete. We need a search algorithm to resolve the rest! ? depthfirst search ? assign a value to the variable ? propagate = make the problem locally consistent ? backtrack upon failure … X in 1..5≈X=1 ∨ X=2 ∨ X=3 ∨ X=4 ∨ X=5 In general, search algorithm resolves remaining disjunctions! X=1 ∨ X≠1(standard labeling) X3 ∨ X≥3(domain splitting) XY ∨ X≥Y(variable ordering) constraint satisfaction tree search algorithms while not solved and not infeasible do check consistency if a dead end is detected then try to escape from dead end else select variable select value for variable endif endwhile The algorithm CheckConsistency proc CheckConsistency ForwardCheck。 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) ? Highly Expressive ? Effective local search ? Search is based on constraint propagation Mathematical vs. Constraint Programming Constraint Programming ? Fast algorithms for special problems Computationally effective for highly constrained, feasibility and machine sequencing problems Not effective for optimization problems with plex structure and many feasible solutions Mathematical Programming ? Intelligent search strategy but putationally expensive for large problems Computationally effective for optimization problems with many feasible solutions Not effective for feasibility problems and machine sequencing problems MAIN IDEA Depose problem into two parts ? Use MP for highlevel optimization decisions ? Use CP for lowlevel sequencing decisions Proposed Strategy Production Z* Upper bound Feasible solution 0 2 4 6 8 10 Iterations 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 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 ? Problem is highly constrained: suitable for CP ? If feasible, obtain lower bound ? Add integer cut and continue until bounds converge Solve MIP Master Problem max production . RELAXATION Obtain UB Solve CP Sub problem max production . ALL CONSTRAINTS w/ fixed no/type of tasks Obtain LB Solve MIP Master Problem max production . 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 converge Proposed Formulation Solve MIP Master Problem max production . RELAXATION Obtain UB CP Sub problem(CP) max production . ALL CONSTRAINTS w/ fixed no/type of tasks Obtain LB MIP Master Problem(MP) max production . SOME CONSTRAINTS Obtain UB Fix no/type of tasks,assignment to units Add integer cuts Tasks ? Activities Units ? Unary Resources Utilities ? Discrete Resources States ? Reservoirs Zic = 1 if batch c of task i is carried out Integer Cuts INTsCSCciZZsBBSSciZBBZBjMSZDssicici cicIiti cicOitsicMAXiicicMINijIi cicic???????????????????? ?? ?? ? ||, , 10)(?? Generalization of Deposition Framework I Multipurpose Batch Plant S3 10% 90% Heat S4 60% Reaction 3 S7 40% Separation Reaction1 Reaction3 Reaction2 70% 30% S5 S6 S2 S1 Heat Master MIP Problem CP Sub problem Zic = 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 ? ? ?