【正文】 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。 ? 方案的質(zhì)量因為成本函數(shù)上的界限不能獲得，所以估價起來有困難。通過為約束傳播者封裝不同的算法，能把適合特定的問題的求解算法考慮進去，使得柔性成為可能。 運籌學(xué)和人工智能融合 ? 兩類方法采用了不同的模型，不同的術(shù)語，各有其特點，但都未能真正解決調(diào)度與計劃決策問題。 缺點： 盡管通用算法很有效，但也往往不能在可行時間內(nèi)得到一個可行解。 ? NUDM直接通過使用連續(xù)變量來表示所有事件（如：任務(wù)的開始和結(jié)束）的發(fā)生時間，而不是分布在每個人為分成的等間隔時間段上，從而達到減少變量的數(shù)目的目的。 Castro et al. (2023) Special cases: No batch splitting/mixing, no resource constraints other than units. 優(yōu)化調(diào)度模型－ 時間表示方式 ? 標準時間分布 (UDM)， 以所有的工廠任務(wù)的最短操作時間為劃分標準等分時間，并假定所有操作 (生產(chǎn)任務(wù)開始、約束、資源的變化、設(shè)備失效等 )均發(fā)生在各時間段的邊界上。類似于 Jobshop 各個產(chǎn)品的生產(chǎn)工藝不相同，同一產(chǎn)品生產(chǎn)存在多個備選生產(chǎn)路徑，其生產(chǎn)路途并不是預(yù)先確定的，可以通過設(shè)備的組織安排來調(diào)整，因此其調(diào)度問題比多產(chǎn)品過程更復(fù)雜。 ? 連續(xù)過程的特點為其物料 (中間品 )可以為多個工序使用，并生產(chǎn)不同的產(chǎn)品，調(diào)度問題的目的在于合理調(diào)配物料，使之能夠獲得最大的經(jīng)濟效益。為了在特定的時間段上將設(shè)備分配給特定的工藝流程，調(diào)度成為最重要的功能。 硬約束與軟約束： 硬約束是必須要滿足的 ， 如交貨期 ， 生產(chǎn)能力等 ， 而軟約束只需達到一定的滿意度即可 ， 如生產(chǎn)成本等 。 ? 先進控制將生產(chǎn)過程的狀態(tài)、過程模型的參數(shù)的更新反饋至生產(chǎn)調(diào)度。 APS中的啟發(fā)式規(guī)則 預(yù)先確定任務(wù)的參數(shù)類規(guī)則 如升序定單屬性值 ， 優(yōu)先級 、 反向優(yōu)先級 最小化任務(wù)延遲類規(guī)則 如先到先服務(wù) 最小化任務(wù)流程時間類規(guī)則 適用于最小時間的控制 ， 提高工時利用率 。 ? “約束”上一個小時的損失則是整個系統(tǒng)的一個小時的損失。 M1 M2 M3 M4 P1 P2 設(shè)備 產(chǎn)品 流水車間調(diào)度問題，常用 表示，即個 n工件 /m臺機器 /流水車間 /最大流程時間 。 ? 執(zhí)行中的意外即動態(tài)調(diào)度可由車間進行有限的局部調(diào)度，但當(dāng)其影響到生產(chǎn)計劃時，只能反饋至計劃部門，由計劃部門統(tǒng)一調(diào)整。 車間作業(yè)調(diào)度的特點 ? 離散制造過程中，工件生產(chǎn)時間較短，工件切換加工成本低但庫存成本很高。 m a x/// cFmn Flowshop問題示例 假設(shè)有 A、 B、 C、 D四種零件，都需要進行先車后銑，其加工時間如表所示。 ? “非約束”節(jié)省的一個小時無益于增加系統(tǒng)有效產(chǎn)出 。 如完成日期 最大設(shè)備能力類規(guī)則 適用于是計劃設(shè)備效率來最大化整個設(shè)備的生產(chǎn)能力 。 動態(tài)調(diào)度 ? 動態(tài)調(diào)度又稱再調(diào)度：處理突發(fā)事件，如某項生產(chǎn)控制指標超出臨界值，設(shè)備的故障、資源突然短缺以及能源供應(yīng)中斷等。 這些約束一般情況是確定的 ， 在進行調(diào)度時大都作為確定性因素考慮 。 中間貯罐協(xié)調(diào)工序間差異 中間貯罐： 某些需要較長加工時間的工序成為生產(chǎn)過程的瓶頸，它屬于時間瓶頸。 ? 由于關(guān)鍵中間品的生產(chǎn)能力存在瓶頸，可稱為有限能力下最大利潤問題。 Example A B B1 C A B C 原生產(chǎn)過程中， A加工時間 1h， B加工時間 4h， C加工時間 2h，原來每批次循環(huán)時間為 4小時，現(xiàn)增加一個設(shè)備 B1，批次循環(huán)時間降為 2小時； A工序上的等待時間減少了 2h ， C設(shè)備上空閑時間由原來的 2小時降為零 0 １ ２ ３ 4 5 6 7 8 9 10 11 0 １ ２ ３ 4 5 6 7 8 9 Scheduling Problems Property Different Constraints ? Sequence (in)dependent setup times ? Release/due times Different Objective Functions ? Maximize throughput over a fixed period of time ? Minimize pletion time (makespan) for a given set of orders Scheduling in Chemical Industry Man uf act uri ng I ndus t ry C hem i cal I ndus t ry O r der Si ngl e un i t ( . c ar ) V ar i abl e am ount of che m i cal ( . 1. 5 t on of s ul f ur aci d) P r oduc t i on A s s em bl y / addi t i on of par t s M i xi ng of i nt er m edi at e c hem i cal s i n v ar i ous r at i os ? Variable batch sizes ? Recycle streams, batch splitting/mixing ? Different storage policies。 ? 非標準連續(xù)時間分布 (NUDM)，將時間表達為連續(xù)變量，時間段的劃分為非均勻方式，時間段的個數(shù)與長度非預(yù)先確定，它可以在整個調(diào)度期內(nèi)的任意一點開始。問題最后表示為MINLP，模型較為復(fù)雜。必須針對特定問題，開發(fā)和使用特殊的算法。 ? 由于生產(chǎn)環(huán)境的動態(tài)性，生產(chǎn)領(lǐng)域知識的多樣性，調(diào)度問題的復(fù)雜性，必須將人、數(shù)學(xué)方法和信息技術(shù)結(jié)合起來研究生產(chǎn)領(lǐng)域的管理調(diào)度問題。 ? 約束規(guī)劃適合于處理含有大量約束的調(diào)度與再調(diào)度問題。 ? 算法的收斂速度很難預(yù)測。 implement one week。 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。 ? 由于它一次產(chǎn)生一組方案，它也適合于使用并行處理。 ? 約束規(guī)劃適合于實現(xiàn)柔性化，高效率的調(diào)度系統(tǒng)。對于提高計算效率起到了重要的作用； ? 采用人工智能的方法 (如各種搜索的方法、專家系統(tǒng)的方法等 ) 對于解決具體的調(diào)度問題，不僅可以簡化問題，而且能獲得合乎實際的滿意解。即使求解過程在達到到最佳解之前終止，對于凸問題也能夠得到達到全局最優(yōu)解的范圍，能夠有效地評價方案的質(zhì)量。但模型規(guī)模與加工時間有關(guān)，可能產(chǎn)生計算復(fù)雜性問題。 Lee et al. (2023)。 ? 多用途 (MultiPurpose) 過程調(diào)度。 ? 物流與能源流的連續(xù)、操作任務(wù)連續(xù)執(zhí)行是連續(xù)過程的本質(zhì)特點。 由于設(shè)備可由多項流程共享，工藝描述與設(shè)備描述是不同且獨立的，在設(shè)備管理的同時還亟需工藝管理。 生產(chǎn)過程的約束 約束條件： 生產(chǎn)調(diào)度受到諸多因素的限制 ， 一般有：產(chǎn)品的投產(chǎn)期 ， 交貨期 （ 完成期 ） ， 生產(chǎn)能力 ， 加工順序 ， 加工設(shè)備和原料的可用性 ， 批量大小 ，加工路徑 ， 成本限制等 ， 這些都是所謂的約束條件 。 聯(lián)系： ? 產(chǎn)品生產(chǎn)率和產(chǎn)品質(zhì)量指標直接由調(diào)度下達至先進控制。 ? 啟發(fā)式規(guī)則無法分析與判斷其方案的質(zhì)量。 APS先進計劃調(diào)度 ? 基于約束理論 ? 能夠處理生產(chǎn)類型和工序約束 ? 自動的 ， 可視化的作業(yè)計劃 TOC約束理論一 ? “約束資源”， “瓶頸” ? 約束資源決定企業(yè)有效產(chǎn)出與庫存 企業(yè)有效產(chǎn)出受到企業(yè)的生產(chǎn)能力和市場的需求量的制約 ? “非約束”應(yīng)與“約束”同步 庫存水平只要能維持“約束”上的物流連續(xù)穩(wěn)定即可 ? “非約束”的利用程度不由其本身決定，而是由系統(tǒng)的“約束”決定的。 問題目標：求個工件在機器上最優(yōu)的加工順序，使最大流程時間最小。 ? MRP II內(nèi)主要采用啟發(fā)式規(guī)則進行作業(yè)調(diào)度與優(yōu)先級控制，提供一個建議的作業(yè)計劃，在訂單下達時，包括開工日期與完工日期，但已考慮了時間余量，因此，車間調(diào)度有一定的緩沖余地。 ? 主要解決多個產(chǎn)品對設(shè)備的爭用問題。 零件名稱 車床工時（時） 銑床工時（時） A 15 4 B 8 10 C 6 5 D 12 7 合計 41 26 ( D , 1 , 1 )( C , 1 , 1 )( A , 1 , 1 ) ( B , 1 , 1 )0 15 23 41( D , 2 , 2 )( C , 2 , 2 )( A , 2 , 2 )0 19 3833( B , 2 , 2 )15 23 4829M1（ 車床）M2（銑床）甘特圖 調(diào)度結(jié)果甘特圖 (A,1,1) (C,1,1) B,1,1) (D,1,1) 0 8 20 41 (D,2,2) (C,2,2) (A,2,2) 0 20 41 32 (B,2,2) 18 27 45 26 M1 （ 車床 ） M2 （ 銑床 ） 優(yōu)化調(diào)度結(jié)果： 調(diào)度問題不同特點 Flowshop 問題中各個產(chǎn)品的生產(chǎn)路徑相同，產(chǎn)品加工工序的順序與設(shè)備的順序?qū)?yīng)，因而某個設(shè)備的加工任務(wù)順序就表示產(chǎn)品的加工順序。 APS約束類型 ?資源約束 a，單一資源 b，無限資源 c，并發(fā)資源 d，共享資源 e，可調(diào)整共享資源 ?順序約束 ?庫存約束 ?特別約束 APS計劃算法一 ?有限能力計劃 a，算法順序計劃 b，向前順序計劃 c，向后順序計劃 b，雙向計劃或瓶頸計劃 ?基于模擬的計劃 基于模擬規(guī)則產(chǎn)生一個優(yōu)化的計劃 APS計劃算法二 ? 向前順序計劃固定了開始時間 ， 決定結(jié)束時間 ， 也許會違反完成日期 。 如閑散時間 定制規(guī)則 流程工業(yè)調(diào)度特點 ? 產(chǎn)品配方 、 產(chǎn)品混合 、 物料平衡等問題 ? 需要考慮主產(chǎn)品 、 副產(chǎn)品 、 協(xié)產(chǎn)品 、 半成品 ? 循環(huán)和回流