【文章內(nèi)容簡介】 T） 和每個 循環(huán)得到的時間。對 于魯棒的問題，偏差（ gk）和循環(huán)時間（參見方程（ 8）和（ 9））給出。最好的解決方法標有符號 “ ” 。 注意，在問題 1中 至多有一個 操作 的 持續(xù)性是不確定的 ； 然而， 問題 2中則大幾乎 有一半都是。對于確定性問題， FS2（ 9 比 10）有最低的周期時間 。然而，對于魯棒問題 1， FS1 是最好的 （ 12 比 13），這是因為， 在確定性的情況下被忽略 的操作 5 的偏差相對來說較高。 盡管如此， FS2 和 FS1 在問題 1 中 有相同的目標函數(shù)值， FS3 則在問題 2 中明顯占優(yōu)勢。因為它包含一個有四個操作的工作站，其中 ? 4=2 被認為是有風險的。 其結(jié)果是， 計算偏差 將會 更高 而我們的魯棒方法 將永遠不會 把 FS3 作為候選 方案?？偨Y(jié)起來，這個例子告訴我們，每一種方法 （確定性或魯棒的）可能會產(chǎn)生不同的解決方案。第二 ，我們觀察到， 當考慮到不確定性因素時， 一條線在確定性的情況下 的 分配做得不錯的（ FS3）可能會導致不可接受的周期。 偏差公式（ 方程（ 8）和（ 9） ） 要求參數(shù) Mk 被定義 。然而，對于魯棒模型來說， 這個參數(shù)需要一個有效的上界 。 接下來，我們 要為 RSALBP2 制定嚴格的 上界，和介紹 基于 分解算法的解決方案。在算法的每一次迭代 中，較寬松的問題被解決了。因此對于 下界（ LB） 來說，在非降 迭代的次數(shù) 中則會產(chǎn)生。此外 ， 上界也因更好的解決方案而得到更新 。 魯棒模型的上界 肖勒在 1999 年 使用相關(guān)的并行多機調(diào)度問題，提出 SALBP2 的兩個上限 。第一個約束忽視了優(yōu)先關(guān)系。第二個是基于優(yōu)先關(guān)系 的解決方案。由于 在魯棒 問題 中， 一些執(zhí)行時間大于其標準值，這些 范圍 對于 RSALBP2是無效的 。對于 SALBP2給定一個由 d_C表示的上限值 ，我們用 r_C 來定義 RSALBP2的上限值。下面，我們將使用 兩個步驟 來介紹 。此過程假定 具有操作的 至少需要 d_C 時間單位然后再根據(jù) 最壞情況情況 對偏差 進行了計算。 表 負載 ? =0 ? =1 ? = FS K=1 K=2 K=3 ST1 ST2 ST3 C g1 g2 g3 C g1 g2 g3 C 1 1,2,3 4,5,6 7,8,9 10 7 9 10 2 4 3 12☆ 2 4 3 12☆ 2 1,3,4 2,5,6 7,8,9 8 9 9 9☆ 2 4 3 13 2 4 3 13 3 3,4,5,6 1,2,7 8,9 9 10 7 10 4 3 2 13 7 3 2 16 約束： 首先，忽略優(yōu)先級 約束 和設(shè)置將會在第二部中使用的初始上限具體步驟如下 ： ：第一步假定具有最大可能性的偏差的操作將會在 同一工作站被處理。然而，當優(yōu)先約 束被集成后，它們將會在裝配的不同階段被處理，一些是在開始，一些則會在最后，考慮到這些，我們建議了以下更加嚴格的約束： 魯棒 問題的所有參數(shù) ESj， LSj， SIj和 Mk 將會由 r_C 也就是 ESj（ r_C ） 計算出來。這個約束對于問題 1 和問題 2 都是有依據(jù)的。然而，對于問題 2 來說，我們考慮到了最壞情況并且將 ? 作為每個操作的最大值分配給工作站： ? =「 ? （ nK+1） 」 （ 10） 分解算法 首先我們給出一個算法來解決問題 1，其次我們來解釋怎樣改進這個算法使之解決問題 （ 8）中， gk（ x） 是一個具有飛空可行解的漸縮問題。松弛線性規(guī)劃有二進制松弛最優(yōu)解。 用 Uk（ x）定義的多面體可以由一個已制定頂點的凸集合計算出來。其中之一是最優(yōu)解。 （ 11） 因此，使用方程（ 11）， 模型 1 就可以由以下方程表示： Min C （ 12） （ 13） 和方程（ 2），（ 4），（ 5） 使用重組后的方程（ 13）， 一種 奔德斯分解算法 可以用來精確地解決這個問題。這種方法可以通過把問題分解為一些簡單的小問題用來解決大規(guī)模的線性規(guī)劃和集成問題：主要問題和次要問題。主要問題是來解決松弛類型的和給整數(shù)變量和最小值的上限集成實驗值。 次要問題時指那些整數(shù)變量暫時不變的一類問題。 在雙次要問題中插入可 行解和最優(yōu)解，當可行解得到滿足時，分解主要問題就會得到上限值。直到上限值和下限值收斂時，只要問題和次要問題才會迭代求解。因此，射線和極值點，可行性和最優(yōu)解 會根據(jù)需要產(chǎn)生。 奔德斯 分解在組合優(yōu)化中得到廣泛的使用，它的高效性在各種項目調(diào)度相關(guān)問題和網(wǎng)絡優(yōu)化問題中顯示出來。 我們注意到線平衡問題有共同的結(jié)構(gòu) ,特別是在資源受限的項目調(diào)度 中。我們注意到，它也可以很好的解決生產(chǎn)線平衡問題。 對應于 解決 RSALBP2來說，由于當前存在的兩個相關(guān)優(yōu)化問題（第一個問題時由方程（ 6）和方程（ 7）定義的，第二個最需要在方程（ 8）中解出 g（ x））的復雜性，分解方法就是十分適合的。 奔德斯 分解遵循迭代的方法，并在每一次迭代 后，較 簡單的問題都解決了。 指數(shù) t 用來表示迭代 t。 使 1t,0 ????Z ）（ — tt1 XSP 如果 t? 0，那么（不可見問題） 否則 解決次要問題 ）（ — tt2 XSP 設(shè) *k 是具有 最大負荷的機械和 tU 是最優(yōu)解 。 如果 tC 1tz 否則，停止并將 tx— 作為最優(yōu)解輸出。 結(jié)束 tPM ： tZ =Min? ?tx XC ?： ，讓 tx 作為最優(yōu)解。 4. t = t+1， tx— = 1tx 2 該算法解決了 在每個迭代過程中的 兩個子問題（ SP1 和 SP2） 。 SP1 是一個可行性檢驗 問題 （關(guān)于優(yōu)先級限制） 并產(chǎn)生可行性削減。然而 SP2 則 發(fā)現(xiàn)了最大負荷機器，它定義 周期時間和產(chǎn)生了最佳路徑 。請注意， SP1 包含一些 可行性的輔助變量， yj? ，也就是說， 如果 yj? =0， A?? ），（ ji ， tC 和 tZ 分別為上限和下限。 解決問題 2 之前為問題 1 設(shè)計的算法對于問題 2 來說并不適用，因為不確定變量的數(shù)目不是固定的（每個工作站不是 ? ）。這取決于隨著得帶過程而改變的分配給工作站的總數(shù)。因此，我們給悲觀水平模型引進了一個新的函數(shù)。首先，重組后的方程（ 9）如下所示 （ 14） 接下來，對于每個迭代 t，定義了以下函數(shù)： （ 15） 通過函數(shù) ? （ t， k） 解決了 t2SP 后，接下來的不等式如下： （ 16） 然而，論文不等式當且僅當 在 最優(yōu)解 中， 每個 機器 k 包含至少 jktj kx??M個 操作，以保證這個條件以下約束插在每 次迭代 t 中 。 （ 17）