【正文】 re (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。 while domains have changed do 2ConsCheck。 SequencingCheck。 RCPCheck。 endwhile endproc 智能方法 遺傳算法 ? 遺傳算法是一種隨機搜索算法，能夠在比較短的時間在解空間的不同區(qū)域內(nèi)搜索。 ? 由于它一次產(chǎn)生一組方案，它也適合于使用并行處理。 ? 方案的質(zhì)量因為成本函數(shù)上的界限不能獲得，所以估價起來有困難。 ? 算法的收斂速度很難預測。 智能方法－ Agent ? 自主性：根據(jù)自己的需要，自主地控制其行為 ? 合作性：可與其他 Agent交互協(xié)商，通過合作共同完成 ? 感應性：可以主動而有選擇地觀察外部環(huán)境，及時采取動作 ? 存在性：不斷觀察環(huán)境，更新內(nèi)態(tài)，選擇并執(zhí)行相應的動作 MAS是由若干具有一個或多個目標的 Agent按照一定的信息關(guān)系、控制關(guān)系以及問題求解能力的分布模式而組成的，是一個松散耦合的 Agent網(wǎng)絡(luò)，其內(nèi)部 Agent之間的組織結(jié)構(gòu)可靈活改變。 “針對時間而設(shè)計 (designtotime)”的實時 Agent調(diào)度方案 ExPlanTech ExPlanTech – a production planning system with a functionality to: ?estimating due dates and resources requirements ?providing a project plan ?implementing replanning Multi Agent system(MAS) fa ct or y ha r dw a r e /s of tw a r ePPAPMAPMAPMAPMAPMAPAPAPAPAPAPAPMAPMAent . re sou rcep la n n i n gh u m a n re sou rc esac cou n t in gent er p risem ac h i n er ym at er ia l re sou rc ei ntr a en ter pr i se P r o Pl a nTPPAPPAi ntr a en ter pr i semeta a gen t Multi Agent system(MAS) ? operator: an instance of the ppa and pma classes – project configuration and deposition, management of the overall project ? workshop: an instance of the pa class – scheduling and resource allocation on a department or CNC machine ? database agent: an instance of the pa class – an integration agent, integrates ExPlanTech with factory ERP ? material agent: an instance of the pa class – integrates an MRP material resource planning system ? Special visualization and user manipulation metaagent 仿真模擬 ? 仿真模擬提供對全部任務，次序 ,先后和時間選擇決定的結(jié)果的直接觀察，能夠以較低的計算成本對方案進行快速而詳細的分析。 ? 仿真模擬的方法能夠用來測試用戶提出的各種候選方案。 ? 如果它與一個較為粗略但卻快速的調(diào)度求解方法結(jié)合，通過不斷的重復仿真與求解，從而能夠?qū)崿F(xiàn)在線調(diào)度。 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。 minimization of makespan ? Short time horizons ? Very expensive when account for due dates Other Models (5%) ? Minimization of makespan ? Short time horizons ? Due dates effectively addressed Research Objective: Develop efficient models for Supply Chain Long time horizons。 due dates Account for transportation holding costs at downstream nodes (?) Account for demand uncertainty (?) Future Directions 1. Use sophisticated solution techniques for MIP models ? New cutting planes ? Specialized branching techniques for cardinality constraints ? Exploit work structure of supply chains ? Lagrangean deposition 2. Hierarchical deposition schemes: planning – scheduling sub problems ? Planning MIP master – Scheduling CP sub problem ? Planning aggregate MIP master – Scheduling detailed MIP sub problem 3. Rolling horizon approaches ? Production targets determined by planning problem ? Detailed scheduling for 2 weeks。 implement one week。 reschedule for 2 weeks Any Question? Example制藥發(fā)酵過程調(diào)度 菌種 種子 培養(yǎng) 發(fā)酵 過濾 粗品 層析 萃取 離交 萃取 層析 成品 結(jié)晶 培養(yǎng) 精制 Example－流程 種子罐、培養(yǎng)罐與發(fā)酵罐均為間歇操作，菌種在種子罐與培養(yǎng)罐的培養(yǎng)時間一般為 2030小時和 7080小時，在發(fā)酵罐內(nèi)需要的發(fā)酵時間則較長，一般為 67天左右 ，因此它是主要的瓶頸工序。提煉工序在發(fā)酵放罐后才開始運行，屬于連續(xù)操作，其能力大于發(fā)酵能力。 Example－車間設(shè)備 M4 發(fā)酵設(shè)備 萃取提煉線 離交提煉線 菌種 成品 成品 M2 M6 M3 發(fā)酵設(shè)備 萃取提煉線 離交提煉線 菌種 成品 成品 M1 M5 Example－ STN 成品 2 S4 發(fā)酵任務 3 發(fā)酵任務 4 S 5 1 S 5 2 離交任務 1 離交任務 2 S6 菌種 2 中間 品 2 T 1 2 T 2 2 T 5 2 T 6 2 中間品 2 成品 1 菌種 1 S1 發(fā)酵任務 1 發(fā)酵任務 2 中間品 1 T 1 1 S2 1 S2 2 萃取任務 1 萃取任務 2 S3 T 2 1 T 3 1 T 4 1 中間品 1 Example－任務設(shè)備 任務名稱 任務代碼 生產(chǎn)車間 設(shè)備代碼 阿佛菌素發(fā)酵 T 11 抗 五車間 M1 阿佛菌素發(fā)酵 T 21 抗一車間 M 2 阿佛菌素萃取 T 31 抗五車間 M 3 阿佛菌素萃取 T 41 抗一車間 M 4 阿霉素發(fā)酵 T 12 抗五車間 M1 阿霉素發(fā)酵 T 22 抗一車間 M2 阿霉素離交提煉 T 52 抗五車間 M 5 阿霉素離交提煉 T 62 抗一車間 M6 Example－ STN參數(shù)存儲 任務名稱 任務編碼 消耗材料 比例 T_name T_id T_material T_prop Char(20) Integer Integer number(4,2) 任務名稱 任務編碼 產(chǎn)出材料 產(chǎn)出工時 產(chǎn)出比例 T_name T_id T_product T_protime T_prop Char(20) Integer integer Number(10,2) Number(4,2) 任務名稱 任務編碼 消耗資源