流程型生產企業訂單選擇問題及方法研究

莊曉霞 王軍

摘 要：近年來，隨著我國經濟增長速度的逐漸回落，生產企業越來越重視進行產能規劃，流程型生產企業進行產能規劃的關鍵在于訂單選擇。傳統的訂單選擇問題把生產排序和訂單選擇分開進行考慮，訂單選擇的優劣完全依賴排序的結果。文章研究了流程型生產訂單選擇與生產排序的相互關系，提出一個以利潤最大化為目標的非線性0-1規劃模型，模型同時考慮訂單排序和選擇。利用Lingo 11.0對模型進行求解檢驗，結果表明，當訂單規模不超過16個時，可以在有效時間內得到模型最優解；對大規模訂單選擇問題，還需要提出效率更高的求解非線性0-1規劃問題的算法。

關鍵詞：流程型生產；訂單選擇；生產排序；非線性0-1規劃

中圖分類號：F273 文獻標識碼：A

Abstract： In recent years， along with the economic growth of China declining slowly， the process production enterprises pay more and more attention to the production capacity planning. Order selection problem becomes the key to the production capacity planning in the process production enterprise. The traditional order selection problem separates production scheduling and order selection. The merits of the order selection depend entirely on sorting result. This paper studies the relationship of the order selection and the production scheduling on process production orders and proposes a nonlinear 0-1 programming model aiming at profit maximization， simultaneously considering the order sorting and selection. The model is solved by using Lingo 11.0 inspection. And results show that model optimal solution can be obtained in the effective time， when the order size is less than 16. For large-scale order selection problem， a more efficient algorithm for solving the nonlinear 0-1 programming problem still need to be put forward.

Key words： process production； order selection； production scheduling； nonlinear 0-1 programming

0 引 言

近年來，隨著我國經濟增長速度的逐漸回落，中國經濟進入新常態，倡導改變增長方式，調整產業結構。這樣的背景下生產企業越來越重視進行產能規劃，尤其是流程型生產企業，訂單選擇問題已成為流程型生產企業產能規劃的關鍵問題。

流程型生產企業，如化工、冶金、飼料等行業，由于其自身生產的特殊性，訂單的生產轉換成本很高，一個訂單完成后下一個訂單才會開始。在企業進行產能規劃的背景下，產能往往是有限的，訂單延期會導致成本增加或懲罰，而訂單提前會導致庫存成本增加，這就使得生產排序和訂單選擇顯得尤為重要。

訂單選擇問題的研究已經持續了二十年。訂單選擇問題的研究通常是在訂單按照某種規則排序后進行的，常用的排序規則有先到先得（FCFS）、最早完工時間（EDD）、最短工作時間（SPT）和最大利潤等規則，而后再對排序后的訂單進行篩選。Slotnick開創性地研究了在工廠生產能力有限、存在延遲懲罰情況下，怎樣從大量的訂單中篩選利潤最大化的訂單集合[1]。在引入與生產次序相關的生產準備時間的情況下，對于批量訂單，Wester提出了單機器環境下的訂單接受策略[2]。Luebbe R提出用約束理論確定生產優先權的方法，從而建立了基于約束理論的訂單選取模型[3]。李娟等提出將外包、聲譽損失與訂單選擇結合起來，研究在企業利潤最大化下對訂單的選擇性接受問題[4]。

訂單排序問題的研究通常是在假設已經確定訂單的情況下進行的。由于不同訂單的完工時間存在差異，考慮到延遲懲罰成本及機器空閑浪費等因素，訂單過多或過少也會影響企業的服務水平和利潤。宋華明等研究了流水線平衡與產品排序對流水線完工時間的交互影響，提出了一種協同進化算法，優化混合裝配流水線完工時間[5]。廖朝輝等研究了基于層次分析法和模糊綜合評價的訂單優先等級策略，從交貨期指標、訂單金額、客戶重要性等方面確定評價指標，用層次分析法確定權重，以評語等級比例確定模糊評價矩陣，最后以各等級分數的總和作為訂單優先級別的依據[6]。

傳統的訂單選擇問題把生產排序和訂單選擇分開進行考慮，訂單選擇的優劣完全依賴生產排序的結果。而在流程型生產中，生產排序直接影響訂單選擇決策，而訂單選擇又反過來影響生產排序。許紹云等（2014）將不被選擇投放的訂單視為推遲投放，考慮推遲投放加上機器閑置以及訂單拖期的總懲罰成本，研究了流水車間的訂單投放問題，通過建立以最小化總懲罰成本為目標的整數規劃模型，對單個計劃期內的訂單投放和訂單排序進行聯合決策[7]。本文通過分析流程型生產訂單選擇與生產排序之間的相互關系，在Slotnick模型的基礎上提出一個以最大化利潤為目標的新模型，同時考慮訂單排序和訂單選擇。

1 Slotnick模型

假設企業產能有限，訂單存在延遲懲罰，以利潤最大化為目標，企業選擇部分訂單進行生產。假設n個訂單按照i=1…n順序進行了排序（訂單i的處理順序優先于訂單i+1）；Q表示按時完成訂單i將獲得的收益；p表示訂單j的處理時間；d表示訂單i的最遲交貨期限；w表示訂單i的延期處罰權重；C表示選擇并完成訂單i的時間。

模型如下：

maxxQ-wC-d （1）

st. （2）

模型設定了一個0-1變量x，x=1時表示接受訂單，x=0時表示放棄該訂單。模型以最大化利潤為目標，表示當訂單的完工時間超過了該訂單要求的交貨期時受到的懲罰。如果提前完成訂單，對企業不產生影響，即沒有任何意義。

Slotnick模型在不同的訂單排序規則下，得到的訂單選擇問題的最優解不同。例如有以下4個訂單，按序到達，每個訂單的利潤Q、在機器上的處理時間批p、延期交貨處罰權重w及交貨期d的數值如表1所示。

我們以先到先得（FCFS）排序原則進行排序，訂單順序為1-2-3-4，Slotnick模型給出的最優解為選擇訂單順序1-2-3，放棄訂單4，利潤值為64，訂單3導致延期處罰4個單位，實現凈利潤為60。以最短工作時間（SPT）排序原則進行排序，訂單順序為2-3-1-4，Slotnick模型給出的最優解為選擇訂單順序2-3-1，放棄訂單4，由于沒有延期處罰，實現凈利潤值為64。

Slotnick訂單模型將訂單選擇與生產排序分開考慮，在不同的訂單排序規則下，得到的最優訂單選擇不同，不能保證得到整個問題的全局最優解，因此研究同時考慮生產排序和訂單選擇，提出一個求解整個問題全局最優解的模型具有理論和現實意義。

2 新的訂單選擇模型

在流程型生產中，生產排序直接影響訂單選擇決策，而訂單選擇又反過來影響生產排序。基于Slotnick模型，通過分析流程型生產訂單選擇與生產排序之間的相互關系，提出一個新的訂單選擇模型，同時考慮訂單排序和訂單選擇。

2.1 基本假設

（1）假設產品生產的產能有限，考慮單個計劃期內的訂單選擇與排序。

（2）假設企業在選定的某個時刻（定為0時刻）接到所有訂單并根據已經收到的訂單的具體信息（包括每個訂單的處理時間，到期時間，利潤，延期處罰權重）進行選擇并處理。

（3）假設訂單從生產到處理完成過程中，沒有庫存，不考慮庫存成本。

2.2 模型描述

假設訂單j，j∈1，2，…，n，n為訂單總數；Q表示訂單j的收益；p表示訂單j的處理時間；d表示訂單j的交貨期；w表示訂單j的權重；C表示選擇并完成訂單j的時間；S表示第i順序生產的訂單的完成時間；x為決策變量，若x=1表示選擇訂單j且將其放在第i順序加工處理，否則x取0。對每個訂單j來說，如果不接受，則訂單不存在排序問題，如果接受，則必須將訂單安排在一個順序上生產。即每個訂單至多被允許排在一個順序上生產，約束條件為∑x≤1， j=1，2，…，n。同樣，對每個順序i來說，至多允許在此順序上生產一個訂單，考慮約束條件∑x≤1， i=1，2，…，n。對上述2個約束條件，若其同時等于1，表示選擇所有訂單并排序，這類似于指派問題。當2個約束條件不同時為1時，表示只選擇部分訂單進行排產。通常企業以利潤最大化為目標，并且由于自身產能有限，一般不會選擇所有訂單，而只是選擇部分訂單進行排產。

優化模型如下：

Max∑∑xQ-wC-d （3）

st. （4）

該模型仍然以利潤最大化為最優目標，但不再是在已知生產排序的情況下單獨考慮訂單選擇，而是同時集中考慮訂單選擇與生產排序。設定變量S，等式S=S+∑px表示第i順序生產的訂單完成時間等于第i-1順序生產的訂單完成時間與第i順序生產的訂單處理時間之和，C表示完成訂單j的時間。

2.3 模型驗證及分析

為了驗證模型的有效性，取上述4個訂單的算例進行分析和求解。4個訂單共有64種排列組合方式，通過計算比較每種排列組合方式實現的利潤大小，可知當選擇訂單1、2、4，放棄訂單3，并按照訂單4-2-1順序排產時，利潤最大為79。調用Lingo軟件對新建的模型進行運行求解，得到模型最優解，如表2所示。

表2顯示，通過構建的模型得到的最優解為選擇訂單1、2、4，放棄訂單3，訂單依次按照4-2-1的順序排產，實現的利潤值為79，與上述計算得到的結果一致。由此證明此模型是有效可行的。

2.4 模型復雜度分析

本文構建的模型為非線性0-1規劃模型，隨著訂單數的增加，模型計算量呈指數增長。為了測試該模型的運行效率，隨機產生5組訂單進行計算（訂單數n分別取4、8、12、16、20），計算機處理器頻率2.20GHZ，內存2.0G，通過Lingo逐一運行，每組運行10次，得到模型計算效率如表3，單位為秒。

由表3可知，在訂單規模不超過16個的情況下，流程型生產企業的訂單選擇和排序問題可通過本文建立的模型在一定的有效時間內得到最優解。而且從前3組實驗結果可以看出，模型的計算時間隨訂單數的增加大致上呈指數增長，這與非線性整數規劃的求解理論相一致，研究同時考慮訂單選擇和生產排序的聯合優化問題屬于NP-hard問題。

3 結束語

傳統的訂單選擇問題把生產排序和訂單選擇分開進行考慮，訂單選擇的優劣依賴于生產排序的結果。本文基于Slotnick訂單選擇模型，通過分析訂單選擇與生產排序之間的相互關系，研究了同時考慮訂單選擇與生產排序的流程型生產企業的訂單選擇問題，提出一個以利潤最大化為目標的非線性0-1規劃模型。由于模型中0-1變量數量的增加，模型的計算復雜性提高，利用Lingo11.0對模型進行求解檢驗。結果表明，本模型在訂單規模較小（不超過16個）時，可在有效時間內得到最優解，對于大規模訂單，則需要相對較長的時間。此模型建立在一般性問題條件下，對大規模訂單求解問題有一定的限制性，后續還需要提出效率更高的求解非線性0-1規劃問題的算法，對大規模訂單問題進行求解分析。

參考文獻：

[1] Susan A. Slotnick， Thomas E. Morton. Order Acceptance with Weighted Tardiness[J]. Computers & Operations Research， 2007，34：3029-3042.

[2] W Wester， J Wijgaard， M Zijm. Order Acceptance Strategies in a Production-to-Order Environment with Setup Times and Due—dates[J]. International Journal of Producction Research， 1992，30（6）：1313-1326.

[3] 張人千. 考慮時間序列關聯的訂單選擇決策比較研究[J]. 管理科學學報，2009，12（3）：44-54.

[4] 李娟，王軍. 基于外包的流程型生產訂單選擇問題研究[J]. 物流科技，2014，37（2）：68-70.

[5] 宋華明，馬士華. 混合裝配流水線上最小makespan的協同優化[J]. 系統工程理論與實踐，2007，27（2）：153-160.

[6] 廖朝輝，胡盛強，張畢西，等. 基于層次分析法和模糊綜合評價的訂單優先等級策略[J]. 科技管理研究，2011，31（24）：191-194.

[7] 許紹云，李鐵克，王柏林，等. 修復式約束滿足算法求解流水車間訂單投放問題[J]. 制造業自動化，2014（3）：1-6.