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