生產計劃與管理——單機作業排程/極小化平均流程時間， 不同線性規劃模型—— 從累死CPLEX的模型到秒解...
知識點
排程問題的“衝突迴避概念”建模 -- 累死CPLEX的模型1
排程問題的“圖( 論) 概念”建模
排程問題的“排序概念”建模
排程問題的“P-演算法”建模 -- 秒解模型
單機作業排程/極小化平均流程時間
單機作業排程是指將n個作業依次地在一臺機器上完成，不同作業不能同時佔用這臺機器，且一旦機器被分配給該作業，則該機器必須完成該作業才能交付下一個作業使用。
假設作業i的作業時間為T[i], 且其開始作業時間為 t[i] 則其流程時間(即完成時間）為 t[i]+T[i]。極小化平均流程時間，即目標為：
min sum{i=1,...,n}(T[i]+t[i])/n
資料：假設有10個作業，其作業時間分別為 13 15 21 9 10 12 5 14 11 20
模型1——“衝突迴避”模型
考慮任務i,j且i<>j（即i不等於j), 則有兩種情況：或者i作業先於j作業加工 或者 反之。如果是前者，則
t[j] >= t[i] + T[i]
如果是後者，則
t[i] >= t[j] +T[j]
兩個約束顯然是互斥的，不能同時成立。因此必須用或關係將他們加入模型。加入或關係的方法是引進0-1變數u[i][j]，如果u[i][j]=1前一個約束成立，否則如果u[i][j]=0後一個約束成立。此時配合一個足夠大的數bigM,則可把上面兩個或約束表示成：
t[j]-t[i] >= T[i] - (1 - u[i][j])bigM //（1）
t[i]-t[j] >= T[j] - u[i][j]bigM // （2）
完整模型：
min sum{i=1,...,n}(T[i]+t[i])
subject to
t[j]-t[i] >= T[i] - (1 - u[i][j])bigM | i=1,...,n; j=1,...,n; i<>j//（1）
t[i]-t[j] >= T[j] - u[i][j]bigM | i=1,...,n; j=1,...,n; i<>j//（2）
where
n is an integer
bigM is a number
T is a set
t[i] is a variable of nonnegative number | i=1,...,n
u[i][j] is a variable of binary | i=1,...,n; j=1,...,n; i<>j
data_relation
n=_$(T)
bigM =sum{i=1,...,n}T[i]
data
T={13 15 21 9 10 12 5 14 11 20}
模型2——“圖(論)概念”模型
把作業看成是圖的節點，作業之間的直接銜接關係看成是邊。則單機作業問題 可以看成是一個特殊的樹，即成一條直線的樹。
首先根據圖論中給出的樹的性質：樹的邊數是節點數減一。以0-1變數e[i][j]表示邊，於是有約束：
sum{i=1,...,n;j=1,...,n;i<>j} e[i][j] = n-1 // (3)
其次，每個節點的入次和出次小於等於1：
sum{i=1,...,n;i<>j} e[i][j] <=1 | j=1,...,n // (4)
sum{j=1,...,n;i<>j} e[i][j] <=1 | i=1,...,n // (5)
滿足（3）-（5）之後並不能保證作業成直線布排，因為環同樣會符合約束（3）-（5）。為了防止環的出現，使用時間箭頭約束（時間是不能周而復始的！）：
t[j]>=t[i]+T[i] - bigM*(1-e[i][j]) | i=1,...,n;j=1,...,n;i<>j //（6）
即如果作業i和j銜接，則e[i][j]=1，上述約束變成t[j]>=t[i]+T[i]，符合時間箭頭邏輯。否則i,j之間並不直接銜接，上式右端的 - bigM*(1-e[i][j]) 等於-bigM，約束式恆成立，等於不存在。
完整模型為：
min (sum{i=1,...,n}(t[i]+T[i]))
subject to
sum{i=1,...,n;j=1,...,n;i<>j}e[i][j]=n-1//（3）
sum{i=1,...,n;i<>j}e[i][j]<=1|j=1,...,n//（4）
sum{j=1,...,n;i<>j}e[i][j]<=1|i=1,...,n//（5）
t[j]>=t[i]+T[i] - bigM*(1-e[i][j])|i=1,...,n;j=1,...,n;i<>j//（6）
where
n is an integer
bigM is a number
T is a set
e[i][j] is a variable of binary|i=1,...,n;j=1,...,n;i<>j
t[i] is a variable of nonnegative number|i=1,...,n
data_relation
n=_$(T)
bigM=sum{i=1,...,n}T[i]
data
T={13 15 21 9 10 12 5 14 11 20}
模型3— “排序概念”模型
所謂排程即排序，在之前的博文“ofollow,noindex" target="_blank">使用 線性規劃 解決 數字 排序問題, +Leapms模型 “中提到過線性規劃可以做數字排序，方法是定義排序物件的次序數變數。
首先為每個作業定義一個次序數變數nd[i]，其下界是0，上界是1. 其次每個作業的開始加工時間顯然必須小於所有作業的作業時間之和TT，於是有約束：
nd[i] <=n-1 | i=1,...,n // （7）
t[i] <= TT | i=1,...,n // （8）
次序數是一個先後的概念，必須與時間t[i]符合向前的時間箭頭邏輯：
如果： nd[i] <= nd[j]+1 (即作業i在作業j之前）則 ：t[i]+T[i] <= t[j] （即作業j的開始加工時間要大於作業i的開始加工時間加上作業i的作業時間）
寫成命題邏輯式相當於：
nd[i] <= nd[j]+1 → t[i]+T[i] <= t[j]
從數理邏輯知道，上式相當於
nd[i ]<= nd[j]+1 or t[i]+T[i] <= t[j]
成為一個或關係邏輯。對或關係的處理方法是引入0-1變數u[i][j], 寫成：
nd[i]>=nd[j]+1 - u[i][j]n | i=1,...,n;j=1,...,n;i<>j // （9）
t[i]+T[i]<=t[j]+(1-u[i][j])TT | i=1,...,n;j=1,...,n;i<>j// （10）
完整模型為：
min sum{i=1,...,n}(T[i]+t[i])
subject to
nd[i]<=n-1|i=1,...,n // （7）
t[i]<=TT|i=1,...,n// （8）
nd[i]>=nd[j]+1 - u[i][j]n | i=1,...,n;j=1,...,n;i<>j// （9）
t[i]+T[i]<=t[j]+(1-u[i][j])TT | i=1,...,n;j=1,...,n;i<>j// （10）
where
n is an integer
TT is a number
T is a set
nd[i] is a variable of nonnegative number|i=1,...,n
u[i][j] is a variable of binary|i=1,...,n;j=1,...,n;i<>j
t[i] is a variable of nonnegative number|i=1,...,n
data_relation
n=_$(T)
TT=sum{i=1,...,n}T[i]
data
T={13 15 21 9 10 12 5 14 11 20}
模型4——“P-演算法”模型
單機作業排程/極小化平均流程時間 問題具有P演算法，方法是優先加工作業時間較小的作業。此時用時間作業時間大小過濾箭頭即可，即：
t[i]+T[i]<=t[j] | i=1,...,n;j=1,...,n;i<>j;T[i]<T[j] //（11）
t[i]+T[i]<=t[j] | i=1,...,n;j=1,...,n;i<j;T[i]==T[j] //（12）
完整模型為：
min (sum{i=1,...,n}(t[i]+T[i]))
subject to
t[i]+T[i]<=t[j] | i=1,...,n;j=1,...,n;i<>j;T[i]<T[j] //（11）
t[i]+T[i]<=t[j] | i=1,...,n;j=1,...,n;i<j;T[i]==T[j] //（12）
where
n is an integer
TT is a number
T is a set
e[i][j] is a variable of binary|i=1,...,n;j=1,...,n;i<>j
t[i] is a variable of nonnegative number|i=1,...,n
data_relation
n=_$(T)
TT=sum{i=1,...,n}T[i]
data
T={13 15 21 9 10 12 5 14 11 20}
四種模型的試算比較
對四種模型在經過+Leapms解析後使用CPLEX12.6.3試算，第一個模型的計算時間在2-5分鐘左右，最後一個模型無論是CPLEX還是+leapms的內建求解器都能在<0.01秒內完成求解。
預計當任務數大於20時，前3個模型CPLEX計算時間將在10分鐘以上。
以下是+Leapms生成的第一個模型和第二個模型的.lp模型，可在CPLEX上試解。
==================================\ \Problem SingleMachine1 \.lp file gnerated by +Leapms \==================================\ Minimize Obj: t1+t2+t3+t4+t5+t6+t7+t8+t9+t10+130 Subject to C1: -t1+t2-130u1_2>=-117 C2: -t1+t3-130u1_3>=-117 C3: -t1+t4-130u1_4>=-117 C4: -t1+t5-130u1_5>=-117 C5: -t1+t6-130u1_6>=-117 C6: -t1+t7-130u1_7>=-117 C7: -t1+t8-130u1_8>=-117 C8: -t1+t9-130u1_9>=-117 C9: -t1+t10-130u1_10>=-117 C10: t1-t2-130u2_1>=-115 C11: -t2+t3-130u2_3>=-115 C12: -t2+t4-130u2_4>=-115 C13: -t2+t5-130u2_5>=-115 C14: -t2+t6-130u2_6>=-115 C15: -t2+t7-130u2_7>=-115 C16: -t2+t8-130u2_8>=-115 C17: -t2+t9-130u2_9>=-115 C18: -t2+t10-130u2_10>=-115 C19: t1-t3-130u3_1>=-109 C20: t2-t3-130u3_2>=-109 C21: -t3+t4-130u3_4>=-109 C22: -t3+t5-130u3_5>=-109 C23: -t3+t6-130u3_6>=-109 C24: -t3+t7-130u3_7>=-109 C25: -t3+t8-130u3_8>=-109 C26: -t3+t9-130u3_9>=-109 C27: -t3+t10-130u3_10>=-109 C28: t1-t4-130u4_1>=-121 C29: t2-t4-130u4_2>=-121 C30: t3-t4-130u4_3>=-121 C31: -t4+t5-130u4_5>=-121 C32: -t4+t6-130u4_6>=-121 C33: -t4+t7-130u4_7>=-121 C34: -t4+t8-130u4_8>=-121 C35: -t4+t9-130u4_9>=-121 C36: -t4+t10-130u4_10>=-121 C37: t1-t5-130u5_1>=-120 C38: t2-t5-130u5_2>=-120 C39: t3-t5-130u5_3>=-120 C40: t4-t5-130u5_4>=-120 C41: -t5+t6-130u5_6>=-120 C42: -t5+t7-130u5_7>=-120 C43: -t5+t8-130u5_8>=-120 C44: -t5+t9-130u5_9>=-120 C45: -t5+t10-130u5_10>=-120 C46: t1-t6-130u6_1>=-118 C47: t2-t6-130u6_2>=-118 C48: t3-t6-130u6_3>=-118 C49: t4-t6-130u6_4>=-118 C50: t5-t6-130u6_5>=-118 C51: -t6+t7-130u6_7>=-118 C52: -t6+t8-130u6_8>=-118 C53: -t6+t9-130u6_9>=-118 C54: -t6+t10-130u6_10>=-118 C55: t1-t7-130u7_1>=-125 C56: t2-t7-130u7_2>=-125 C57: t3-t7-130u7_3>=-125 C58: t4-t7-130u7_4>=-125 C59: t5-t7-130u7_5>=-125 C60: t6-t7-130u7_6>=-125 C61: -t7+t8-130u7_8>=-125 C62: -t7+t9-130u7_9>=-125 C63: -t7+t10-130u7_10>=-125 C64: t1-t8-130u8_1>=-116 C65: t2-t8-130u8_2>=-116 C66: t3-t8-130u8_3>=-116 C67: t4-t8-130u8_4>=-116 C68: t5-t8-130u8_5>=-116 C69: t6-t8-130u8_6>=-116 C70: t7-t8-130u8_7>=-116 C71: -t8+t9-130u8_9>=-116 C72: -t8+t10-130u8_10>=-116 C73: t1-t9-130u9_1>=-119 C74: t2-t9-130u9_2>=-119 C75: t3-t9-130u9_3>=-119 C76: t4-t9-130u9_4>=-119 C77: t5-t9-130u9_5>=-119 C78: t6-t9-130u9_6>=-119 C79: t7-t9-130u9_7>=-119 C80: t8-t9-130u9_8>=-119 C81: -t9+t10-130u9_10>=-119 C82: t1-t10-130u10_1>=-110 C83: t2-t10-130u10_2>=-110 C84: t3-t10-130u10_3>=-110 C85: t4-t10-130u10_4>=-110 C86: t5-t10-130u10_5>=-110 C87: t6-t10-130u10_6>=-110 C88: t7-t10-130u10_7>=-110 C89: t8-t10-130u10_8>=-110 C90: t9-t10-130u10_9>=-110 C91: t1-t2+130u1_2>=15 C92: t1-t3+130u1_3>=21 C93: t1-t4+130u1_4>=9 C94: t1-t5+130u1_5>=10 C95: t1-t6+130u1_6>=12 C96: t1-t7+130u1_7>=5 C97: t1-t8+130u1_8>=14 C98: t1-t9+130u1_9>=11 C99: t1-t10+130u1_10>=20 C100: -t1+t2+130u2_1>=13 C101: t2-t3+130u2_3>=21 C102: t2-t4+130u2_4>=9 C103: t2-t5+130u2_5>=10 C104: t2-t6+130u2_6>=12 C105: t2-t7+130u2_7>=5 C106: t2-t8+130u2_8>=14 C107: t2-t9+130u2_9>=11 C108: t2-t10+130u2_10>=20 C109: -t1+t3+130u3_1>=13 C110: -t2+t3+130u3_2>=15 C111: t3-t4+130u3_4>=9 C112: t3-t5+130u3_5>=10 C113: t3-t6+130u3_6>=12 C114: t3-t7+130u3_7>=5 C115: t3-t8+130u3_8>=14 C116: t3-t9+130u3_9>=11 C117: t3-t10+130u3_10>=20 C118: -t1+t4+130u4_1>=13 C119: -t2+t4+130u4_2>=15 C120: -t3+t4+130u4_3>=21 C121: t4-t5+130u4_5>=10 C122: t4-t6+130u4_6>=12 C123: t4-t7+130u4_7>=5 C124: t4-t8+130u4_8>=14 C125: t4-t9+130u4_9>=11 C126: t4-t10+130u4_10>=20 C127: -t1+t5+130u5_1>=13 C128: -t2+t5+130u5_2>=15 C129: -t3+t5+130u5_3>=21 C130: -t4+t5+130u5_4>=9 C131: t5-t6+130u5_6>=12 C132: t5-t7+130u5_7>=5 C133: t5-t8+130u5_8>=14 C134: t5-t9+130u5_9>=11 C135: t5-t10+130u5_10>=20 C136: -t1+t6+130u6_1>=13 C137: -t2+t6+130u6_2>=15 C138: -t3+t6+130u6_3>=21 C139: -t4+t6+130u6_4>=9 C140: -t5+t6+130u6_5>=10 C141: t6-t7+130u6_7>=5 C142: t6-t8+130u6_8>=14 C143: t6-t9+130u6_9>=11 C144: t6-t10+130u6_10>=20 C145: -t1+t7+130u7_1>=13 C146: -t2+t7+130u7_2>=15 C147: -t3+t7+130u7_3>=21 C148: -t4+t7+130u7_4>=9 C149: -t5+t7+130u7_5>=10 C150: -t6+t7+130u7_6>=12 C151: t7-t8+130u7_8>=14 C152: t7-t9+130u7_9>=11 C153: t7-t10+130u7_10>=20 C154: -t1+t8+130u8_1>=13 C155: -t2+t8+130u8_2>=15 C156: -t3+t8+130u8_3>=21 C157: -t4+t8+130u8_4>=9 C158: -t5+t8+130u8_5>=10 C159: -t6+t8+130u8_6>=12 C160: -t7+t8+130u8_7>=5 C161: t8-t9+130u8_9>=11 C162: t8-t10+130u8_10>=20 C163: -t1+t9+130u9_1>=13 C164: -t2+t9+130u9_2>=15 C165: -t3+t9+130u9_3>=21 C166: -t4+t9+130u9_4>=9 C167: -t5+t9+130u9_5>=10 C168: -t6+t9+130u9_6>=12 C169: -t7+t9+130u9_7>=5 C170: -t8+t9+130u9_8>=14 C171: t9-t10+130u9_10>=20 C172: -t1+t10+130u10_1>=13 C173: -t2+t10+130u10_2>=15 C174: -t3+t10+130u10_3>=21 C175: -t4+t10+130u10_4>=9 C176: -t5+t10+130u10_5>=10 C177: -t6+t10+130u10_6>=12 C178: -t7+t10+130u10_7>=5 C179: -t8+t10+130u10_8>=14 C180: -t9+t10+130u10_9>=11 Binaries u1_2 u1_3 u1_4 u1_5 u1_6 u1_7 u1_8 u1_9 u1_10 u2_1 u2_3 u2_4 u2_5 u2_6 u2_7 u2_8 u2_9 u2_10 u3_1 u3_2 u3_4 u3_5 u3_6 u3_7 u3_8 u3_9 u3_10 u4_1 u4_2 u4_3 u4_5 u4_6 u4_7 u4_8 u4_9 u4_10 u5_1 u5_2 u5_3 u5_4 u5_6 u5_7 u5_8 u5_9 u5_10 u6_1 u6_2 u6_3 u6_4 u6_5 u6_7 u6_8 u6_9 u6_10 u7_1 u7_2 u7_3 u7_4 u7_5 u7_6 u7_8 u7_9 u7_10 u8_1 u8_2 u8_3 u8_4 u8_5 u8_6 u8_7 u8_9 u8_10 u9_1 u9_2 u9_3 u9_4 u9_5 u9_6 u9_7 u9_8 u9_10 u10_1 u10_2 u10_3 u10_4 u10_5 u10_6 u10_7 u10_8 u10_9 End \==================================\
\==================================\ \Problem singlemachine4 \.lp file gnerated by +Leapms \==================================\ Minimize Obj: t1+t2+t3+t4+t5+t6+t7+t8+t9+t10+130 Subject to C1: t1-t2<=-13 C2: t1-t3<=-13 C3: t1-t8<=-13 C4: t1-t10<=-13 C5: t2-t3<=-15 C6: t2-t10<=-15 C7: -t1+t4<=-9 C8: -t2+t4<=-9 C9: -t3+t4<=-9 C10: t4-t5<=-9 C11: t4-t6<=-9 C12: t4-t8<=-9 C13: t4-t9<=-9 C14: t4-t10<=-9 C15: -t1+t5<=-10 C16: -t2+t5<=-10 C17: -t3+t5<=-10 C18: t5-t6<=-10 C19: t5-t8<=-10 C20: t5-t9<=-10 C21: t5-t10<=-10 C22: -t1+t6<=-12 C23: -t2+t6<=-12 C24: -t3+t6<=-12 C25: t6-t8<=-12 C26: t6-t10<=-12 C27: -t1+t7<=-5 C28: -t2+t7<=-5 C29: -t3+t7<=-5 C30: -t4+t7<=-5 C31: -t5+t7<=-5 C32: -t6+t7<=-5 C33: t7-t8<=-5 C34: t7-t9<=-5 C35: t7-t10<=-5 C36: -t2+t8<=-14 C37: -t3+t8<=-14 C38: t8-t10<=-14 C39: -t1+t9<=-11 C40: -t2+t9<=-11 C41: -t3+t9<=-11 C42: -t6+t9<=-11 C43: -t8+t9<=-11 C44: t9-t10<=-11 C45: -t3+t10<=-20 End \==================================\
討論
1、建立排程問題的線性規劃模型可以有不同的方法，例如可以從衝突迴避角度、圖角度、排序角度、P-演算法角度多種思路去考慮。所建立的模型的執行效率是不同的，甚至相差極大。
2、線性規劃模型是一種問題的描述方法，目前的求解器基本上採用的是鬆弛—分支方法去求解，儘管加入了很多前處理，還沒有能夠做到根據模型本身所描述約束情況的推知問題的性質從而進行高效求解的地步。
3、有P演算法的問題，當依據該演算法發現的性質進行線性規劃建模後，其求解效率會相應被提高。
By: 陸戰之王 (2018-12-5)