1. 流水線標准工時計算方法
你的問題就有問題了，其實按我理解，你要問的就是一件產品走完整條流水線共用多少工時，如果你的問題是這樣的話，那我可以告訴你兩種不同的演算法，你可以兩種都用來算，最後再兩者進行比較下，一種是，你統計一天下來這條流水線的產量，那這條流水線上一件產品的工時就等於：一天的作業時間/一天的產量；另一種方法就是，你要劃分各個工作站的工序類別，之後再測出各個工序生產單件產品的標准工時（可能就是你上面的標准作業時間，因我不理解你的標准時間是啥工序或什麼之類的，你講得不夠清楚），之後將所有各個工序的標准工時相加即可，相加總和就是這條流水線上生產一件產品的標准時間了。
2. NP完全問題
網路名片 NP完全問題 NP完全問題，是世界七大數學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題，即多項式復雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。 目錄 基本簡介 問題詳解 搜索方法 近鄰法(nearest neighbor) 插入法(insertion) 模擬退火演算法(Recuit Algorithm) 遺傳演算法 神經網路演算法 難度結果 基本簡介 問題詳解 搜索方法 近鄰法(nearest neighbor) 插入法(insertion) 模擬退火演算法(Recuit Algorithm) 遺傳演算法 神經網路演算法 難度結果 展開 編輯本段基本簡介 數學上著名的NP問題，完整的叫法是NP完全問題，也即「NP COMPLETE」問題，簡單的寫法，是 NP=P？的問題。問題就在這個問號上，到底是NP等於P，還是NP不等於P。證明其中之一，便可以拿百萬美元大獎。 多流水線調度實際上是一個NP完全問題 這個獎還沒有人拿到，也就是說，NP問題到底是Polynomial，還是Non-Polynomial，尚無定論。 NP裡面的N，不是Non-Polynomial的N，是Non-Deterministic，P代表Polynomial倒是對的。NP就是Non-deterministic Polynomial的問題，也即是多項式復雜程度的非確定性問題。 美國麻州的克雷(Clay)數學研究所於2000年5月24日在巴黎法蘭西學院宣布了一件被媒體炒得火熱的大事：對七個「千僖年數學難題」的每一個懸賞一百萬美元。以下是這七個難題。 「千僖難題」之一： P (多項式演算法)問題對NP (非多項式演算法)問題 「千僖難題」之二： 霍奇(Hodge)猜想 「千僖難題」之三： 龐加萊(Poincare)猜想 「千僖難題」之四： 黎曼(Riemann)假設 「千僖難題」之五： 楊－米爾斯(Yang-Mills)存在性和質量缺口 「千僖難題」之六：納維葉－斯托克斯(Navier-Stokes)方程的存在性與光滑性 「千僖難題」之七：貝赫(Birch)和斯維訥通－戴爾(Swinnerton-Dyer)猜想 NP完全問題排在百萬美元大獎的首位，足見他的顯赫地位和無窮魅力。 編輯本段問題詳解 NP就是Non-deterministic Polynomial的問題，也即是多項式復雜程度的非確定性問題。 什麼是非確定性問題呢？有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導，按部就班一步步來，就可以得到結果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質數的問題。有沒有一個公式，你一套公式，就可以一步步推算出來，下一個質數應該是多少呢？這樣的公式是沒有的。再比如，大的合數分解質因數的問題，有沒有一個公式，把合數代進去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。 這種問題的答案，是無法直接計算得到的，只能通過間接的「猜算」來得到結果。這也就是非確定性問題。而這些問題的通常有個演算法，它不能直接告訴你答案是什麼，但可以告訴你，某個可能的結果是正確的答案還是錯誤的。這個可以告訴你「猜算」的答案正確與否的演算法，假如可以在多項式時間內算出來，就叫做多項式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項式時間內進行正確與否的驗算的話，就叫完全多項式非確定問題。 完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去，最終便能得到結果。但是這樣演算法的復雜程度，是指數關系，因此計算的時間隨問題的復雜程度成指數的增長，很快便變得不可計算了。 人們發現，所有的完全多項式非確定性問題，都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內計算，人們於是就猜想，是否這類問題，存在一個確定性演算法，可以在指數 時間內，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。 解決這個猜想，無非兩種可能，一種是找到一個這樣的演算法，只要針對某個特定NP完全問題找到一個演算法，所有這類問題都可以迎刃而解了，因為他們可以轉化為同一個問題。另外的一種可能，就是這樣的演算法是不存在的。那麼就要從數學理論上證明它為什麼不存在。 前段時間轟動世界的一個數學成果，是幾個印度人提出了一個新演算法，可以在多項式時間內，證明某個數是或者不是質數，而在這之前，人們認為質數的證明，是個非多項式問題。可見，有些看來好象是非多項式的問題，其實是多項式問題，只是人們一時還不知道它的多項式解而已。 上回說到可憐的旅行商想找出走遍所有城市的最短路徑。讓我們用計算機幫他搜索一下。 這就需要用到本篇文章中要介紹的第一門學科了：《人工智慧》。人類的許多活動，如解算題、猜謎語、進行討論、編制計劃和編寫計算機程序，甚至駕駛汽車和騎自行車等等，都需要"智能"。如果機器能夠執行這種任務，就可以認為機器已具有某種性質的"人工智慧"。現在我們就要利用人工智慧，用計算機模擬人的思維來搜索最短路徑。 想像一下，我們人思考問題時，有兩種方法：一種是精確搜索，就是試驗所有的可能性，找出最精確的一個方案。但它在搜索過程中不改變搜索策略，不利用搜索獲得的中間信息，它盲目性大，效率差，用於小型問題還可以，用於大型問題根本不可能；另一種叫做啟發式搜索，它在搜索過程中加入了與問題有關的啟發性信息，用以指導搜索向著一個比較小的范圍內進行，加速獲得結果。 編輯本段搜索方法近鄰法(nearest neighbor) 推銷員從某個城鎮出發，永遠選擇前往最近且尚未去過的城鎮，最後再返回原先的出發點。這方法簡單，也許是多數人的直覺做法，但是近鄰法的短視使其表現非常不好，通常後段的路程會非常痛苦。 插入法(insertion) 先產生連接部分點的子路線，再根據某種法則將其它的點逐一加入路線。比如最近插入法(nearest insertion)，先針對外圍的點建構子路線，然後從剩餘的點裡面評估何者加入後路線總長度增加的幅度最小，再將這個點加入路線。又比如最遠插入法(farthest，insertion)，是從剩餘的點裡面選擇距離子路線最遠的點，有點先苦後甜的滋味。 模擬退火演算法(Recuit Algorithm) 模擬退火演算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis准則，粒子在溫度T時趨於平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變數，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火演算法：由初始解i和控制參數初值t開始，對當前解重復「產生新解→計算目標函數差→接受或舍棄」的迭代，並逐步衰減t值，演算法終止時的當前解即為所得近似最優解。 遺傳演算法 遺傳演算法是模擬生物遺傳學和自然選擇機理，通過人工方式所構造的一類搜索演算法 遺傳演算法是解決NP問題的一種較理想的方法 ，從某種程度上說遺傳演算法是對生物進化過程進行的數學方式模擬。生物種群的生存過程普遍遵循達爾文進化准則，群體中的個體根據對環境的適應能力而被大自然所選擇或淘汰。進化過程的結果反映在個體的結構上，其染色體包含若干基因，相應的表現型和基因型的聯系體現了個體的外部特性與內部機理間邏輯關系。通過個體之間的交叉、變異來適應大自然環境。生物染色體用數學方式或計算機方式來體現就是一串數碼，仍叫染色體，有時也叫個體；適應能力是對應著一個染色體的一個數值來衡量；染色體的選擇或淘汰則按所面對的問題是求最大還是最小來進行。 神經網路演算法 根據一個簡化的統計，人腦由百億條神經組成 — 每條神經平均連結到其它幾千條神經。通過這種連結方式，神經可以收發不同數量的能量。神經的一個非常重要的功能是它們對能量的接受並不是立即作出響應，而是將它們累加起來，當這個累加的總和達到某個臨界閾值時，它們將它們自己的那部分能量發送給其它的神經。大腦通過調節這些連結的數目和強度進行學習。盡管這是個生物行為的簡化描述。但同樣可以充分有力地被看作是神經網路的模型。 編輯本段難度結果 雖然百萬美元的獎金和大量投入巨大卻沒有實質性結果的研究足以顯示該問題是困難的，還有一些形式化的結果證明為什麼該問題可能很難解決。 最常被引用的結果之一設計神喻。假想你有一個魔法機器可以解決單個問題，例如決定一個給定的數字是否為質數，但可以瞬間解決這個問題。我們的新問題是，若我們被允許任意利用這個機器，是否存在我們可以在多項式時間內驗證但無法在多項式時間內解決的問題？結果是，依賴於機器能解決的問題，P = NP和P ≠ NP二者都可以證明。這個結論的後果是，任何可以修改來證明該機器的存在性的結果不能解決問題。不幸的是，幾乎所有經典的方法和大部分已知的方法可以這樣修改（我們稱它們在相對化）。 如果這還不算太糟的話，1993年Razborov和Rudich證明的一個結果表明，給定一個特定的可信的假設，在某種意義下「自然」的證明不能解決P = NP問題。這表明一些現在似乎最有希望的方法不太可能成功。隨著更多這類的定理得到證明，該定理的可能證明有越來越多的陷阱要規避。這實際上也是為什麼NP完全問題有用的原因：若有一個多項式時間演算法，或者沒有一個這樣的演算法，對於NP完全問題存在，這將用一種相信不被上述結果排除在外的方法來解決P = NP問題。P=NP問題可以用邏輯命題的特定類的可表達性的術語來重新表述。所有P中的語言可以用一階邏輯加上最小不動點操作（實際上，這允許了遞歸函數的定義）來表達。類似地，NP是可以用存在性二階邏輯來表達—也就是，在關系、函數、和子集上排除了全域量詞的二階邏輯。多項式等級，PH中的語言對應與所有的二階邏輯。這樣，「P是NP的真子集嗎」這樣的問題可以表述為「是否存在性二階邏輯能夠表達帶最小不動點操作的一階邏輯的所不能表達的語言？」 普林斯頓大學計算機系樓將二進制代碼表述的「P=NP?」問題刻進頂樓西面的磚頭上。如果證明了P=NP，磚頭可以很方便的換成表示「P=NP！」。康奈爾大學的Hubert Chen博士提供了這個玩笑式的P不等於NP的證明：「反證法。設P = NP。令y為一個P = NP的證明。證明y可以用一個合格的計算機科學家在多項式時間內驗證，我們認定這樣的科學家的存在性為真。但是，因為P = NP，該證明y可以在多項式時間內由這樣的科學家發現。但是這樣的發現還沒有發生（雖然這樣的科學家試圖發現這樣的一個證明），我們得到矛盾。