莊曉霞 王軍

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

關(guān)鍵詞：流程型生產(chǎn)；訂單選擇；生產(chǎn)排序；非線性0-1規(guī)劃

中圖分類號：F273 文獻標(biāo)識碼：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 引 言

近年來，隨著我國經(jīng)濟增長速度的逐漸回落，中國經(jīng)濟進入新常態(tài)，倡導(dǎo)改變增長方式，調(diào)整產(chǎn)業(yè)結(jié)構(gòu)。這樣的背景下生產(chǎn)企業(yè)越來越重視進行產(chǎn)能規(guī)劃，尤其是流程型生產(chǎn)企業(yè)，訂單選擇問題已成為流程型生產(chǎn)企業(yè)產(chǎn)能規(guī)劃的關(guān)鍵問題。

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

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

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

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

1 Slotnick模型

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

模型如下：

maxxQ-wC-d （1）

st. （2）

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

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

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

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

2 新的訂單選擇模型

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

2.1 基本假設(shè)

（1）假設(shè)產(chǎn)品生產(chǎn)的產(chǎn)能有限，考慮單個計劃期內(nèi)的訂單選擇與排序。

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

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

2.2 模型描述

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

優(yōu)化模型如下：

Max∑∑xQ-wC-d （3）

st. （4）

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

2.3 模型驗證及分析

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

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

2.4 模型復(fù)雜度分析

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

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

3 結(jié)束語

傳統(tǒng)的訂單選擇問題把生產(chǎn)排序和訂單選擇分開進行考慮，訂單選擇的優(yōu)劣依賴于生產(chǎn)排序的結(jié)果。本文基于Slotnick訂單選擇模型，通過分析訂單選擇與生產(chǎn)排序之間的相互關(guān)系，研究了同時考慮訂單選擇與生產(chǎn)排序的流程型生產(chǎn)企業(yè)的訂單選擇問題，提出一個以利潤最大化為目標(biāo)的非線性0-1規(guī)劃模型。由于模型中0-1變量數(shù)量的增加，模型的計算復(fù)雜性提高，利用Lingo11.0對模型進行求解檢驗。結(jié)果表明，本模型在訂單規(guī)模較?。ú怀^16個）時，可在有效時間內(nèi)得到最優(yōu)解，對于大規(guī)模訂單，則需要相對較長的時間。此模型建立在一般性問題條件下，對大規(guī)模訂單求解問題有一定的限制性，后續(xù)還需要提出效率更高的求解非線性0-1規(guī)劃問題的算法，對大規(guī)模訂單問題進行求解分析。

參考文獻：

[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] 張人千. 考慮時間序列關(guān)聯(lián)的訂單選擇決策比較研究[J]. 管理科學(xué)學(xué)報，2009，12（3）：44-54.

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

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

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

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