排程邏輯詳解概述本系統(tǒng)是一個基于約束規(guī)劃 (Constraint Programming)的生產(chǎn)排程系統(tǒng)使用求解器來解決作業(yè)車間調度問題 (Job Shop Scheduling Problem, JSSP)。系統(tǒng)的核心目標是在滿足所有約束條件的前提下找到使總完工時間makespan最小的排程方案。問題定義輸入數(shù)據(jù)訂單 (Orders)訂單號、產(chǎn)品編碼、數(shù)量、交期、優(yōu)先級工藝路線 (Processes)產(chǎn)品編碼、工序號、工序名稱、工序順序單件標準工時分鐘、所需設備、前置工序設備 (Equipment)設備編號、狀態(tài)、效率系數(shù)每日工作時長小時、可用時間窗口輸出結果每個工序的開始時間、結束時間、分配設備總完工時間makespan設備利用率、交期達成率、瓶頸設備核心流程1. 數(shù)據(jù)預處理 (_preprocess_data)目的將原始數(shù)據(jù)轉換為求解器可用的結構構建索引以提高查詢效率。構建的數(shù)據(jù)結構# 產(chǎn)品到工藝路線的映射product_to_processes:Dict[str,List[Process]]# 例如: {P01: [工序1, 工序2, 工序3]}# 設備組到設備列表的映射equipment_group_to_equipment:Dict[str,List[Equipment]]# 例如: {M01,M02: [設備M01, 設備M02]}# 設備每日工作時長分鐘equipment_daily_capacity:Dict[str,float]# 例如: {M01: 480.0} # 8小時 480分鐘# 所有需要排程的(訂單, 工序)對job_operations:List[Tuple[Order,Process]]時間范圍估算# 計算總工作量total_work_minutesΣ(訂單數(shù)量 × 單件工時)# 估算需要的天數(shù)添加2倍緩沖estimated_days(total_work_minutes/平均每日產(chǎn)能)×2estimated_daysmax(estimated_days,30)# 至少30天# 計算時間范圍horizonhorizonestimated_days ×24小時 ×60分鐘說明horizon 是求解器搜索空間的上界設置得太小可能無解太大會影響求解效率。2. 構建優(yōu)化模型 (build_model)決策變量對每個工序(訂單i, 工序j)創(chuàng)建以下變量變量類型說明取值范圍----rt_var開始時間[0, horizon] 分鐘end_------ 結束時間[0, horizon] 分鐘–resence_var是否在設備k上執(zhí)行{0, 1} 布爾值-----rval_var時間區(qū)間[start, duration, end]##--------制如果一個工序可以在多臺設備上執(zhí)行例如 “M01,M02”系統(tǒng)會為每臺可用設備創(chuàng)建一個presence_var和interval_var添加約束sum(presence_vars) 1必須選擇恰好一臺設備求解器自動選擇最優(yōu)的設備分配示例工序:車削,可用設備:[M01,M02]變量:-presence_M01:是否在M01上執(zhí)行-presence_M02:是否在M02上執(zhí)行-interval_M01:在M01上的時間區(qū)間可選-interval_M02:在M02上的時間區(qū)間可選 約束:-presence_M01presence_M021工序持續(xù)時間計算duration單件標準工時 × 訂單數(shù)量示例單件工時5分鐘訂單數(shù)量100件持續(xù)時間500分鐘3. 添加約束 (add_constraints)約束1工藝順序約束規(guī)則工序必須按照工藝路線的順序執(zhí)行# 對于同一訂單的連續(xù)工序工序i的結束時間工序i1的開始時間# 對于有顯式前置工序的情況前置工序的結束時間當前工序的開始時間示例訂單SO001的工藝路線車削 → 銑削 → 檢驗 約束 - 車削.end_time 銑削.start_time - 銑削.end_time 檢驗.start_time約束2設備互斥約束規(guī)則同一臺設備不能同時執(zhí)行多個工序model.AddNoOverlap(設備k的所有區(qū)間變量)這個約束確保分配到同一設備的所有工序在時間上不重疊。示例設備M01上的工序 - 訂單1的車削: [0, 500] - 訂單2的車削: [500, 1000] ? 不重疊 - 訂單3的車削: [450, 950] ? 與訂單2重疊不允許約束3時間約束規(guī)則結束時間 開始時間 持續(xù)時間end_timestart_time(單件工時 × 訂單數(shù)量)約束4時間窗口約束規(guī)則所有工序的開始時間必須非負start_time0擴展可以根據(jù)設備的available_start和available_end添加更復雜的時間窗口約束。4. 設置優(yōu)化目標 (set_objective)目標函數(shù)最小化總完工時間makespanmakespanmax(所有工序的結束時間)minimize(makespan)目標變量# 創(chuàng)建makespan變量makespan_varmodel.NewIntVar(0,horizon,makespan)# 添加約束makespan 所有工序的結束時間foreach operation:model.Add(makespan_varoperation.end_time)# 設置優(yōu)化目標model.Minimize(makespan_var)其他可能的優(yōu)化目標雖然當前系統(tǒng)使用 makespan 作為目標但也可以考慮最小化總延期時間最小化設備切換次數(shù)最大化設備利用率多目標優(yōu)化加權組合5. 求解 (solve)求解流程1.構建模型(build_model)2.添加約束(add_constraints)3.設置優(yōu)化目標(set_objective)4.創(chuàng)建求解器5.設置求解器參數(shù)6.執(zhí)行求解7.提取結果求解器參數(shù)solver.parameters.max_time_in_seconds60.0# 最大求解時間60秒求解狀態(tài)狀態(tài)說明---MAL找到最優(yōu)解并證明了最優(yōu)性F--- E找到可行解但未證明最優(yōu)----- IBLE無可行解約束沖突OWN求解超時或其他原因#### |約束過于嚴格交期太緊設備產(chǎn)能不足工藝路線沖突數(shù)據(jù)錯誤工序順序錯誤設備類型不匹配時間估算不合理6. 提取結果 (extract_solution)步驟1獲取工序時間從求解器獲取每個工序的開始和結束時間工作分鐘start_timesolver.Value(start_var)# 例如: 0end_timesolver.Value(end_var)# 例如: 500durationend_time-start_time# 例如: 500分鐘步驟2確定分配的設備檢查哪個presence_var的值為 1forequipmentinavailable_equipment:ifsolver.Value(presence_var[equipment])1:assigned_equipmentequipmentbreak步驟3轉換為日歷時間核心函數(shù)_work_minutes_to_datetime轉換邏輯# 輸入工作分鐘數(shù)連續(xù)時間# 輸出日歷datetime考慮每日工作時長# 1. 計算是第幾個工作日work_day工作分鐘//每日工作分鐘# 2. 計算當天的工作分鐘數(shù)minutes_in_day工作分鐘%每日工作分鐘# 3. 計算實際日期時間result_date基準日期work_day天 result_datetimeresult_date的8:00minutes_in_day示例設備M01每日工作:480分鐘8小時 基準日期:2024-03-0608:00工作分鐘1000work_day1000//4802第2天 minutes_in_day1000%48040result_datetime2024-03-0808:40為什么需要轉換求解器使用連續(xù)時間工作分鐘進行優(yōu)化用戶需要看到實際的日歷時間考慮每天的工作時間轉換確保結果符合實際生產(chǎn)場景步驟4計算 makespan# 找到最早開始和最晚結束min_start_timemin(op.start_timeforopinoperations)max_end_timemax(op.end_timeforopinoperations)# 計算日歷時間跨度小時makespan(max_end_time-min_start_time).total_seconds()/3600.0算法特性? 優(yōu)勢全局最優(yōu)CP-SAT 求解器能找到全局最優(yōu)解在時間限制內不會陷入局部最優(yōu)靈活的設備分配自動選擇最優(yōu)設備實現(xiàn)負載均衡支持設備組概念嚴格的約束保證100% 遵守工藝順序絕對不會出現(xiàn)設備沖突保證所有約束條件考慮實際工作時間每臺設備獨立的工作時長自動跳過非工作時間結果以日歷時間呈現(xiàn)批量生產(chǎn)支持正確處理訂單數(shù)量工時 單件工時 × 數(shù)量?? 局限性求解時間大規(guī)模問題可能需要較長時間當前限制60秒簡化假設假設設備從時間0開始可用未考慮設備故障、維護未考慮人員限制優(yōu)化目標單一僅優(yōu)化 makespan未考慮成本、能耗等因素完整示例輸入數(shù)據(jù)訂單訂單號: SO001 產(chǎn)品: P01 數(shù)量: 100件 交期: 2024-03-10工藝路線產(chǎn)品P011. 車削: 單件5分鐘, 設備: M01,M02 2. 銑削: 單件3分鐘, 設備: M03 3. 檢驗: 單件1分鐘, 設備: M04設備M01: 車床, 每日8小時 M02: 車床, 每日8小時 M03: 銑床, 每日8小時 M04: 檢驗臺, 每日8小時求解過程1. 數(shù)據(jù)預處理job_operations[(SO001,車削),(SO001,銑削),(SO001,檢驗)]總工作量(531)×100900分鐘2. 構建模型# 為車削工序創(chuàng)建變量start_車削IntVar(0,horizon)end_車削IntVar(0,horizon)duration_車削5×100500分鐘 presence_M01BoolVar()presence_M02BoolVar()約束:presence_M01presence_M0213. 添加約束# 工藝順序end_車削start_銑削 end_銑削start_檢驗# 設備互斥AddNoOverlap(M01的所有區(qū)間)AddNoOverlap(M02的所有區(qū)間)...# 時間約束end_車削start_車削500end_銑削start_銑削300end_檢驗start_檢驗1004. 求解求解器找到最優(yōu)解:-車削在M01上執(zhí)行:0-500分鐘-銑削在M03上執(zhí)行:500-800分鐘-檢驗在M04上執(zhí)行:800-900分鐘5. 轉換為日歷時間基準日期:2024-03-0608:00M01每日工作:480分鐘 車削:start:0分鐘 →2024-03-0608:00end:500分鐘 →2024-03-0708:20(第1天:0-480,第2天:480-500)銑削:start:500分鐘 →2024-03-0708:20end:800分鐘 →2024-03-0809:40檢驗:start:800分鐘 →2024-03-0809:40end:900分鐘 →2024-03-0811:20輸出結果訂單: SO001 總完工時間: 51.33小時2天3小時20分 工序詳情: ┌────────┬──────┬─────────────────┬─────────────────┬──────────┐ │ 工序 │ 設備 │ 開始時間 │ 結束時間 │ 工時(h) │ ├────────┼──────┼─────────────────┼─────────────────┼──────────┤ │ 車削 │ M01 │ 03-06 08:00 │ 03-07 08:20 │ 8.33 │ │ 銑削 │ M03 │ 03-07 08:20 │ 03-08 09:40 │ 5.00 │ │ 檢驗 │ M04 │ 03-08 09:40 │ 03-08 11:20 │ 1.67 │ └────────┴──────┴─────────────────┴─────────────────┴──────────┘ 設備利用率: - M01: 16.2% - M02: 0% - M03: 9.7% - M04: 3.2% 交期達成: ? (完工時間 交期)擴展方向1. 多目標優(yōu)化# 加權目標函數(shù)objectivew1 × makespanw2 × 延期懲罰w3 × 設備切換成本2. 動態(tài)排程支持插單、急單實時調整排程考慮在制品狀態(tài)3. 高級約束設備維護時間窗口人員技能匹配物料可用性能源消耗限制4. 啟發(fā)式算法對于超大規(guī)模問題可以結合遺傳算法模擬退火禁忌搜索5. 機器學習學習歷史數(shù)據(jù)預測工時智能調整優(yōu)先級預測瓶頸設備總結本排程系統(tǒng)通過約束規(guī)劃技術將復雜的生產(chǎn)排程問題轉化為數(shù)學優(yōu)化問題由求解器自動找到最優(yōu)解。系統(tǒng)的核心優(yōu)勢在于自動化無需手動編寫復雜的調度規(guī)則最優(yōu)性在時間限制內找到全局最優(yōu)解靈活性易于添加新的約束和目標可靠性保證所有約束條件得到滿足這使得系統(tǒng)能夠高效地處理實際生產(chǎn)中的復雜排程問題。| |