流水車間調(diào)度問題Flow Shop Scheduling Problem是生產(chǎn)制造和運籌優(yōu)化領(lǐng)域里一個繞不開的經(jīng)典命題也是很多工廠排產(chǎn)系統(tǒng)、APS高級計劃排程軟件的核心算法內(nèi)核。我剛?cè)胄心菚阂詾榕女a(chǎn)就是按訂單順序往下發(fā)真正接觸車間數(shù)據(jù)之后才發(fā)現(xiàn)同樣的訂單、同樣的設(shè)備換個加工順序整條產(chǎn)線的交付周期能差出三成甚至更多。后來我把這套問題啃了一遍從兩機Johnson算法一路做到多機迭代貪婪才算摸到點門道。這篇東西就是把這些年踩過的坑、驗證過的方案整理出來主要寫給兩類人一類是做生產(chǎn)管理、排產(chǎn)優(yōu)化的工程師想搞明白機器排程背后的計算邏輯另一類是做算法、運籌優(yōu)化方向的朋友需要一個能直接跑起來、能復(fù)現(xiàn)的參考實現(xiàn)。全文圍繞流水車間調(diào)度這個核心把建模、算法選型、代碼落地、參數(shù)調(diào)優(yōu)、常見故障排查都講一遍力求你看完之后能自己動手把一套車間排產(chǎn)求解器搭起來。1. 先把問題說清楚流水車間調(diào)度到底在解決什么1.1 用車間場景還原問題本身流水車間調(diào)度問題描述起來其實很樸素。假設(shè)你有一條產(chǎn)線上面按固定順序排著m臺機器比如下料機、沖壓機、焊接機、噴涂機?，F(xiàn)在有n個待加工的工件要做每個工件都必須在這些機器上依次走一遍走完一臺才能進下一臺而且所有工件走過的機器順序完全一樣。這就是“流水”兩個字的由來——工件的工藝路線是固定的、單向的流水線。真正讓人頭疼的地方在于機器一次只能加工一個工件工件在機器上不能被打斷每臺機器加工不同工件的時間還不一樣。于是問題就變成這n個工件到底按什么順序上第一臺機器才能讓最后一件活兒最早離開最后一道工序這個“最后一件活兒離開最后一道工序的時間點”行業(yè)內(nèi)叫最大完工時間英文是makespan是衡量排產(chǎn)方案好壞最常用的指標。你可以把它理解成整批訂單的總工期。流水車間調(diào)度要解決的核心就是找一個工件的加工序列讓整條產(chǎn)線的makespan盡可能小。聽起來比作業(yè)車間調(diào)度Job Shop簡單——因為工藝路線統(tǒng)一了嘛少了路徑?jīng)Q策。但別高興太早工藝路線統(tǒng)一反而讓約束之間的耦合變得更緊一臺機器上的順序調(diào)整會像多米諾骨牌一樣影響后面所有機器這也是它在數(shù)學(xué)上依然很難的根本原因。1.2 數(shù)學(xué)建模三要素記法與目標函數(shù)在正式動手前得先把問題寫成一個規(guī)范的數(shù)學(xué)模型否則代碼寫出來是散裝的沒法驗證。運籌學(xué)里描述調(diào)度問題有一套標準的三字段記法α|β|γ。第一個字段描述機器環(huán)境流水車間就是Fm臺機器就寫成Fm第二個字段寫約束和特征比如所有工件都可用、不考慮機器故障這些第三個字段是優(yōu)化目標makespan就是Cmax。所以最常見的流水車間調(diào)度問題標準寫法是 Fm||Cmax。把這個模型展開核心變量和約束是這樣的。設(shè)工件集合J{1,2,...,n}機器集合M{1,2,...,m}工件i在機器j上的加工時間記為p(i,j)。決策變量是每臺機器上工件的加工順序本質(zhì)上是一個排列。目標函數(shù)就是最小化makespan。約束有幾條必須寫清楚每個工件在每臺機器上只能加工一次每個工件必須先完成前一道工序才能開始后一道同一臺機器同一時刻只能處理一個工件加工過程不可中斷。我個人習(xí)慣在建模階段就把完工時間用遞推的方式表達出來這樣后面寫評價函數(shù)最直接。設(shè)C(i,j)表示工件i在機器j上的完工時間那么C(i,j) max(C(前一個工件, j), C(i, j-1)) p(i,j)這個遞推公式是整個流水車間調(diào)度的計算心臟。它的含義是某工件在某臺機器上的完工時間取決于“這臺機器上一個工件啥時候騰出來”和“我自己上一道工序啥時候做完”這兩個時間的最大者再加上我在當前機器上的加工時長。把這個公式嚼透后面所有的makespan計算、甘特圖繪制、鄰域評估都從這里長出來。1.3 為什么它是NP-hard復(fù)雜度那點事流水車間調(diào)度問題在m≥3的時候?qū)儆贜P-hard問題這句話不是嚇唬人的。n個工件在每臺機器上的順序只要機器數(shù)大于等于2理論上可能的調(diào)度方案就有(n!)種量級。做個小算術(shù)10個工件就是10的階乘約362萬種15個工件是1.3萬億種20個工件直接上天約2.4×10^18種。你想用暴力枚舉把所有方案都試一遍別說跑一天跑到宇宙盡頭也列不完。這里我得補充一句常見誤解有人覺得流水車間的解空間比作業(yè)車間小所以更好解。恰恰相反雖然工件路徑固定砍掉了一大堆分支但因為所有機器共享同一個工件序列序列里隨便調(diào)換兩個相鄰工件就可能同時改變多臺機器上的等待時間局部改動引發(fā)全局連鎖導(dǎo)致解空間里到處是陷阱和懸崖。這就是為什么精確算法只能啃小規(guī)模規(guī)模一大就必須換啟發(fā)式。從工程落地角度說我一般按規(guī)模分檔工件數(shù)n≤8、機器數(shù)m≤5這種小case可以用分支定界或者直接整數(shù)規(guī)劃求解器拿到最優(yōu)解一旦n超過10、m超過5我個人就果斷轉(zhuǎn)向啟發(fā)式因為精確解的邊際收益抵不上那指數(shù)級膨脹的求解時間。這個經(jīng)驗閾值不是絕對的但上手時拿來參考很靠譜。2. 算法選型從精確解到啟發(fā)式的取舍邏輯2.1 小規(guī)模為什么可以直接枚舉值不值得規(guī)模小的時候最省事的做法就是全排列枚舉加剪枝。n≤8的時候全排列也就四萬種量級現(xiàn)代計算機眨個眼就跑完了。我早期做設(shè)備排產(chǎn)的驗證工具就是先寫一個暴力枚舉版本專門用來給后續(xù)的啟發(fā)式算法當“標準答案”對照。這個做法看著土但極其有價值——你需要一個可靠的最優(yōu)解標桿才能判斷自己的啟發(fā)式到底差多少。不過枚舉法也有講究。硬枚舉所有排列再逐個算makespan純屬浪費。正確的姿勢是帶剪枝的搜索比如分支定界一邊構(gòu)造序列一邊算當前部分序列的下界一旦下界已經(jīng)超過當前最優(yōu)解這條分支直接砍掉。這樣能砍掉大量明顯不可能更優(yōu)的路徑把有效搜索空間壓縮好幾個數(shù)量級。我的實測體會是小規(guī)模加剪枝能把可求解上限從n6提到n9左右代價是代碼復(fù)雜度上升得小心下界函數(shù)別寫錯寫錯反而漏掉最優(yōu)解。這里給一個判斷依據(jù)如果你的業(yè)務(wù)場景是研發(fā)階段的算法驗證、教學(xué)演示、或者單機少量工件的排產(chǎn)直接上枚舉或分支定界完全合理。但如果是真實車間每天幾百上千個工件的排產(chǎn)就別執(zhí)著于最優(yōu)解了啟發(fā)式給的近似解足夠用而且快得不是一個量級。2.2 兩機問題的Johnson算法唯一的精確多項式解法流水車間里有一個特例特別漂亮就是兩機問題 F2||Cmax它存在多項式時間的精確解這就是經(jīng)典的Johnson算法。這個算法的存在讓兩機場景下的排產(chǎn)有了教科書級的確定答案。它的規(guī)則非常簡潔但背后的直覺值得好好說說。Johnson算法的步驟是這樣的把所有工件分成兩組。第一組是“在第一臺機器上加工時間不超過第二臺機器”的工件第二組是反面。然后第一組里按第一臺機器的加工時間升序排列第二組里按第二臺機器的加工時間降序排列最后把第一組接在第二組前面就得到了最優(yōu)序列。用代碼表達就幾行def johnson(times): # times[job] (t_machine1, t_machine2) group_u [i for i in range(len(times)) if times[i][0] times[i][1]] group_v [i for i in range(len(times)) if times[i][0] times[i][1]] group_u.sort(keylambda i: times[i][0]) # 第一臺機器時間升序 group_v.sort(keylambda i: times[i][1], reverseTrue) # 第二臺機器時間降序 return group_u group_v為什么這個規(guī)則能保證最優(yōu)我理解的直覺是讓“在前道快、后道慢”的工件盡早開工讓“前道慢、后道快”的工件盡量往后排這樣能最大限度壓縮第二臺機器也就是瓶頸機器的等待空檔。這個思路后來被推廣成CDS啟發(fā)式專門用來對付多機問題后面會講。Johnson算法雖然只適用于兩機但它是理解流水車間排序邏輯最好的一把鑰匙。2.3 構(gòu)造式啟發(fā)式NEH與CDS這對搭檔規(guī)模一上來就是啟發(fā)式算法的天下了。構(gòu)造式啟發(fā)式里最有名的兩個一個是NEH一個是CDS它們思路不太一樣但經(jīng)常配合使用。NEH算法的名字來自三位作者Nawaz、Enscore和Ham的縮寫思路是貪心插入。它先給工件排個初始優(yōu)先級把所有工件的總加工時間加起來按從大到小排序總工時長的工件先排。然后取前兩個工件試試兩種順序誰更優(yōu)選makense小的那個。接著把第三個工件插入到當前序列的每個可能位置看哪個位置makespan最小就放哪。以此類推直到所有工件都插進去。NEH的完整實現(xiàn)我習(xí)慣這么寫def makespan(seq, times): n, m len(seq), len(times[0]) C [[0]*m for _ in range(n)] for i, job in enumerate(seq): for j in range(m): p times[job][j] if i 0 and j 0: C[i][j] p elif i 0: C[i][j] C[i][j-1] p elif j 0: C[i][j] C[i-1][j] p else: C[i][j] max(C[i-1][j], C[i][j-1]) p return C[n-1][m-1] def neh(times): n len(times) order sorted(range(n), keylambda j: sum(times[j]), reverseTrue) seq [order[0]] for k in range(1, n): job order[k] best_seq, best_c None, float(inf) for pos in range(len(seq)1): cand seq[:pos] [job] seq[pos:] c makespan(cand, times) if c best_c: best_c, best_seq c, cand seq best_seq return seq, best_cNEH的優(yōu)點是實現(xiàn)簡單、效果穩(wěn)定很多工業(yè)排產(chǎn)系統(tǒng)的第一版都會拿它當基線。但它的計算復(fù)雜度是O(n2m)工件一多還是會慢而且它是純構(gòu)造、不回溯容易陷在局部里。CDS算法則是Johnson算法的推廣它把多機問題通過合并相鄰機器的方式轉(zhuǎn)成一個個兩機子問題每個子問題用Johnson算法求一個序列最后從這些候選序列里挑makespan最小的。CDS通常比NEH略慢但解質(zhì)量有時更好我一般兩個都跑取更優(yōu)的作為后續(xù)元啟發(fā)式的初始解。2.4 元啟發(fā)式遺傳、模擬退火與迭代貪婪想要更接近最優(yōu)解就得請出元啟發(fā)式算法。這塊我踩過不少坑也總結(jié)出一套自己的偏好。遺傳算法GA在流水車間里用得非常多。編碼方式一般是工件排列也就是“排列編碼”交叉算子常用順序交叉OX或者PMX變異用交換或逆序。GA的優(yōu)點是全局搜索能力強但需要調(diào)的參數(shù)多——種群大小、交叉率、變異率、代數(shù)哪個調(diào)不好都跑不出好結(jié)果。我早期的經(jīng)驗是參數(shù)別貪多種群控制在一兩百交叉率0.8到0.9變異率0.05到0.1代數(shù)先跑個幾千代看收斂曲線。模擬退火SA我個人更偏愛因為它實現(xiàn)起來更輕參數(shù)更少只有一個初始溫度T0、降溫系數(shù)alpha和終止溫度。核心就三步隨機擾動產(chǎn)生新序列、算新解、按Metropolis準則接受差解。import random, math def sa(times, init_seq, T0100, T_end0.1, alpha0.95, iters100): seq init_seq[:] best seq[:] best_c cur_c makespan(seq, times) T T0 while T T_end: for _ in range(iters): new_seq seq[:] i, j random.sample(range(len(seq)), 2) new_seq[i], new_seq[j] new_seq[j], new_seq[i] # 交換鄰域 new_c makespan(new_seq, times) if new_c cur_c or random.random() math.exp((cur_c - new_c) / T): seq, cur_c new_seq, new_c if cur_c best_c: best_c, best cur_c, seq[:] T * alpha return best, best_c模擬退火的關(guān)鍵在于降溫要慢alpha一般取0.9到0.98之間太快的降溫會退化成局部搜索太慢又費時間。鄰域結(jié)構(gòu)也很講究交換兩個工件只是最樸素的我后來改用“插入”鄰域把一個工件抽出來插到別處效果明顯更好因為插入更貼合序列調(diào)整的本質(zhì)。迭代貪婪算法IG是我最后壓箱底推薦的。它把破壞和構(gòu)造結(jié)合起來先從當前序列里隨機抽走d個工件破壞階段再用NEH的策略把這d個工件一個個重新插回最優(yōu)位置構(gòu)造階段插入過程里帶點隨機性以便跳出局部最優(yōu)。IG的核心理念就四步破壞、構(gòu)造、局部搜索、接受準則。它不需要像GA那樣調(diào)一堆參數(shù)又比純SA收斂得更穩(wěn)在標準算例上經(jīng)常能打到接近最優(yōu)的水平。我現(xiàn)在的默認方案就是“NEH生成初始解 IG主循環(huán)優(yōu)化”簡單又抗造。3. 動手實現(xiàn)一套可復(fù)現(xiàn)的求解框架3.1 數(shù)據(jù)結(jié)構(gòu)與評價函數(shù)的設(shè)計要點動手寫代碼之前數(shù)據(jù)結(jié)構(gòu)選對了能省一半事。我用得最順手的結(jié)構(gòu)是二維列表timestimes[job][machine]表示工件job在機器machine上的加工時間工件和機器都用從0開始的整數(shù)下標。這樣做的好處是索引直觀后面畫甘特圖、做機器維度的統(tǒng)計分析都不用轉(zhuǎn)來轉(zhuǎn)去。評價函數(shù)就是前面那個遞推公式但實現(xiàn)的時候有個坑要避開不要每次都重新開一個大矩陣規(guī)模大的時候內(nèi)存分配本身就很耗時。如果只是臨時評估、不算甘特圖完全可以用一維數(shù)組滾動更新只保留每臺機器當前的可用時間。def makespan_fast(seq, times): m len(times[0]) machine_free [0] * m # 每臺機器當前空閑時刻 job_done 0 # 當前工件上一道工序完工時刻 for job in seq: job_done 0 for j in range(m): start max(machine_free[j], job_done) job_done start times[job][j] machine_free[j] job_done return machine_free[-1] # 最后一臺機器的完工時刻即makespan這個版本把空間壓到只剩機器的狀態(tài)評估速度提升很明顯。我在n100、m20的算例上對比過滾動版本比全矩陣版本快了差不多40%因為它省掉了大量的矩陣寫入。這個優(yōu)化看著不起眼但在元啟發(fā)式里評價函數(shù)會被調(diào)用幾十萬次累積下來差距就大了。3.2 從初始解到局部搜索的完整流程一套能用的求解框架我一般按五步走。第一步用NEH生成初始解拿到一個不錯的起點。第二步在初始解上套一個局部搜索把交換、插入、逆序三種鄰域都試一遍哪個方向能降makespan就往哪走直到所有鄰域都動不了為止。第三步進入迭代貪婪主循環(huán)破壞幾個工件再重新構(gòu)造構(gòu)造過程里加入一定概率接受次優(yōu)位置防止過早收斂。第四步設(shè)置一個接受準則新解比當前解好就接受差一點點也在一定條件下接受越往后接受差解的概率越低。第五步記錄全局最優(yōu)跑夠迭代次數(shù)或者時間到就返回。局部搜索的鄰域選擇我有過一輪實測。交換鄰域swap計算簡單但每次只動兩個工件爬坡慢插入鄰域insertion動作大一點往往一步能跨過好幾個局部坑逆序鄰域reversal適合消除序列里的長距離倒置。我的做法是三種輪著來先插入、再交換、最后逆序每輪都記下當前最優(yōu)直到一整輪下來沒有任何改進才停。這套組合拳比單用交換鄰域平均能多降2%到5%的makespan別小看這幾個點放到真實產(chǎn)線上就是實打?qū)嵉漠a(chǎn)能。3.3 結(jié)果可視化把序列變成看得懂的甘特圖算法跑完光給一個makespan數(shù)字車間主任是看不懂的你得把排產(chǎn)結(jié)果畫成甘特圖。甘特圖橫軸是時間縱軸是機器每個工件在對應(yīng)機器上畫一個色塊塊的長度就是加工時長。一眼就能看出哪臺機器有空閑空檔哪臺是瓶頸機器。用Python的matplotlib畫很方便核心就是把每個工件的每道工序的起止時間算出來。import matplotlib.pyplot as plt def gantt(seq, times): m len(times[0]) machine_free [0] * m colors plt.cm.tab20.colors fig, ax plt.subplots(figsize(12, 6)) for idx, job in enumerate(seq): job_done 0 for j in range(m): start max(machine_free[j], job_done) dur times[job][j] ax.barh(j, dur, leftstart, height0.6, colorcolors[job % len(colors)]) machine_free[j] start dur job_done start dur ax.set_yticks(range(m)) ax.set_yticklabels([fM{j1} for j in range(m)]) ax.set_xlabel(Time) plt.show()畫出甘特圖之后我習(xí)慣重點盯兩個地方一個是瓶頸機器它上面幾乎沒有空檔說明整條線的節(jié)拍被它卡死另一個是序列里前后相鄰的工件之間如果某臺機器反復(fù)在等前道說明局部順序還有優(yōu)化空間。這兩處一看往往就能給下一輪優(yōu)化指方向。3.4 完整求解器串起來的骨架把上面的模塊拼起來就是一個能跑的求解器。主流程大概是讀入加工時間矩陣NEH出初始解局部搜索精修IG主循環(huán)迭代期間不斷更新全局最優(yōu)最后輸出最優(yōu)序列、makespan和甘特圖。我建議一開始把所有參數(shù)都寫成可配置的常量方便調(diào)參。def solve(times, max_iter200, destroy_size4): seq, best_c neh(times) best seq[:] for it in range(max_iter): # 破壞 destroyed random.sample(seq, destroy_size) remain [j for j in seq if j not in destroyed] # 構(gòu)造帶隨機性的NEH插入 for job in destroyed: best_pos, best_local 0, float(inf) for pos in range(len(remain)1): cand remain[:pos] [job] remain[pos:] c makespan_fast(cand, times) if c best_local: best_local, best_pos c, pos remain.insert(best_pos, job) seq remain c makespan_fast(seq, times) if c best_c: best_c, best c, seq[:] return best, best_c這段骨架看著簡單但where the magic happens就在那個接受和破壞的邏輯里。destroy_size這個參數(shù)是核心太小了跳不出局部最優(yōu)太大了跟重新來一遍沒區(qū)別一般取4到8之間工件多的時候可以適當放大。max_iter根據(jù)你的時間預(yù)算定跑個幾百到幾千次都行。4. 調(diào)參、踩坑與性能評估4.1 參數(shù)到底怎么調(diào)才不白跑調(diào)參這事我踩過最多的坑就是“一把梭”——把所有參數(shù)都往某個經(jīng)驗值上一設(shè)然后抱怨算法沒效果。其實不同規(guī)模、不同加工時間分布最優(yōu)參數(shù)差別很大。先說破壞規(guī)模destroy_size。工件數(shù)少的時候n20取3到4比較合適工件數(shù)到50以上取5到8上百個工件取10左右甚至可以用自適應(yīng)前期大一點幫助探索后期小一點幫助精修。我一般設(shè)成工件數(shù)的某一個比例比如max(3, n//15)。再說迭代次數(shù)和接受準則。捏威脅的其實是接受準則太寬松導(dǎo)致解到處亂跳收斂不了。我的做法是維護一個會衰減的“溫度”或者“容忍閾值”前期允許接受比當前差2%以內(nèi)的解后期衰減到只接受更好的解。針對模擬退火降溫系數(shù)alpha我實測下來0.92到0.96是個比較穩(wěn)的區(qū)間。低于0.9降溫太快容易早熟高于0.98跑起來慢得讓人懷疑人生。初始溫度T0的設(shè)定有個小技巧先用初始解隨機擾動幾次算出平均惡化幅度再讓初始接受概率大概在0.8左右反推T0比拍腦袋定強得多。4.2 常見問題速查表下面這張表是我這些年遇到的高頻問題和處理辦法直接照著排就行?，F(xiàn)象可能原因排查與解決算法結(jié)果波動很大每次跑都不一樣隨機種子沒固定固定random.seed方便復(fù)現(xiàn)和對比收斂后長時間不改進陷入局部最優(yōu)加大破壞規(guī)模增加接受差解概率大規(guī)模算例跑不動評價函數(shù)太慢用滾動數(shù)組版本緩存重復(fù)評估結(jié)果比手工排的還差初始解太爛或鄰域不合適換NEHCDS初始解增加插入鄰域甘特圖顯示瓶頸機器一直滿負荷節(jié)拍被卡死嘗試調(diào)整瓶頸機器前的工件順序makespan算出來偏小不合理遞推公式寫錯漏了max檢查max(C[i-1][j], C[i][j-1])這張表里我特別想強調(diào)評價函數(shù)寫錯這個坑。很多人第一次實現(xiàn)的時候會寫成簡單累加忘了同一臺機器要等上一個工件也忘了工件要等自己上一道工序。這兩個約束一個都不能漏漏一個結(jié)果就全錯而且錯得很隱蔽因為數(shù)字看起來還是“像那么回事”的。我的習(xí)慣是寫完評價函數(shù)先拿n3、m3的小例子手算一遍對上了再跑大規(guī)模。4.3 評價基準與算例選擇評估一個調(diào)度算法好不好不能光看自己的數(shù)據(jù)得用公開的標準算例。流水車間調(diào)度領(lǐng)域有一套經(jīng)典的基準算例比如Taillard算例集規(guī)模從20×5到500×20都有業(yè)界公認的最優(yōu)解或已知最好解都公開可查。你跟這些基準對比一下就知道自己的算法處在什么水平——離已知最好解差1%以內(nèi)算優(yōu)秀差3%左右算及格差10%以上基本說明算法邏輯有問題。我衡量算法還有兩個維度一個是解的質(zhì)量就是跟基準的gap另一個是求解時間。真實車間排產(chǎn)往往有實時性要求比如每天早上8點前必須出排產(chǎn)計劃你算法再準跑8個小時沒人受得了。所以我的原則是在gap和耗時之間找平衡點寧可少優(yōu)化一個百分點也要把時間壓進業(yè)務(wù)能接受的窗口。一般來說幾百個工件的規(guī)模要求10分鐘內(nèi)出結(jié)果是比較常見的訴求IG這類算法基本能滿足。5. 從標準問題到真實車間擴展與落地建議5.1 真實場景里的常見變體教科書上的流水車間很理想但真實車間總有很多附加約束這就是一堆變體問題的來源。最常見的是零等待流水車間意思是工件加工完必須馬上進下一臺機器一刻都不能等常見于鋼鐵、玻璃這類不能冷卻斷裂的連續(xù)工藝。還有阻塞流水車間機器之間沒有緩沖區(qū)下游機器沒空位上游工件就堵在那兒出不來這類問題在化工和半導(dǎo)體里不少見。再復(fù)雜一點的是混合流水車間也就是某個工序有并行多臺機器工件可以選其中一臺加工這就多了個機器分配決策難度直接上一個臺階。還有帶準備時間的、帶機器故障的、帶交貨期約束的每一種都有對應(yīng)的研究和工程方法。我的建議是不要一上來就追求建模全真實場景先把標準Fm||Cmax跑通把評價函數(shù)、初始解、局部搜索這套基礎(chǔ)設(shè)施搭穩(wěn)。加約束的時候主要在評價函數(shù)里做文章零等待就是在遞推時強制start等于前道完成時間阻塞就是限制工件不能隨意離開機器。只要基礎(chǔ)設(shè)施扎實加約束就是改幾行邏輯的事。5.2 落地時的幾條實戰(zhàn)建議最后分享幾條我在項目里總結(jié)出來的經(jīng)驗都是從踩坑里換來的。第一先做驗證再做優(yōu)化。別一上來就上花哨的元啟發(fā)式先用NEH跑出個基線看看結(jié)果合不合理同時寫一個暴力枚舉版本在小規(guī)模上對拍確認評價函數(shù)沒寫錯。這一步花不了多少時間但能省下后面debug的無數(shù)個小時。第二把排產(chǎn)結(jié)果和人工經(jīng)驗對照。算法排出來的序列交給車間老師傅看一眼他們往往能指出哪里不對勁——可能是某個必須優(yōu)先的急單被排到了后面也可能是某臺機器換了工件要清洗這些都是純數(shù)學(xué)模型里沒寫進去的隱性約束。把這些隱性規(guī)則抽象成約束或者優(yōu)先級加回模型里結(jié)果才真正能用。第三留出人工干預(yù)的口子。純自動排產(chǎn)在真實車間幾乎不現(xiàn)實總有臨時插單、設(shè)備故障、質(zhì)量問題。所以我的設(shè)計里一定有一個“鎖定”機制允許人工把某幾個工件釘死在指定位置算法只優(yōu)化剩下的部分。這個功能看著簡單卻是排產(chǎn)系統(tǒng)能不能被一線接受的關(guān)鍵。第四指標別只看makespan。交貨期內(nèi)完成率、機器利用率、平均在制品數(shù)量這些指標有時候比makespan更重要。我見過為了壓makespan把大批工件堆在中間環(huán)節(jié)雖然總工期短了但在制品積壓嚴重管理者反而不滿意。所以落地的評價函數(shù)往往是多個目標的加權(quán)組合權(quán)重要跟實際業(yè)務(wù)負責人一起定。我個人在實際操作中的體會是流水車間調(diào)度問題看著是個純數(shù)學(xué)問題真正做起來其實是算法、業(yè)務(wù)、現(xiàn)場經(jīng)驗三者的結(jié)合。理論部分決定了你能不能算得又快又準業(yè)務(wù)理解決定了你的結(jié)果有沒有實際價值現(xiàn)場經(jīng)驗決定了這套東西能不能被一線真正用起來。缺了哪一塊算法跑出再漂亮的數(shù)字最后也是躺在報告里落灰。所以別怕麻煩多去車間走兩趟多跟排產(chǎn)員聊兩句很多建模時想不通的地方站在產(chǎn)線邊上就清楚了。