流程型生產(chǎn)企業(yè)訂單選擇問題及方法研究

莊曉霞 王軍

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

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

中圖分類號(hào)：F273 文獻(xiàn)標(biāo)識(shí)碼：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ì)增長(zhǎng)速度的逐漸回落，中國經(jīng)濟(jì)進(jìn)入新常態(tài)，倡導(dǎo)改變?cè)鲩L(zhǎng)方式，調(diào)整產(chǎn)業(yè)結(jié)構(gòu)。這樣的背景下生產(chǎn)企業(yè)越來越重視進(jìn)行產(chǎn)能規(guī)劃，尤其是流程型生產(chǎn)企業(yè)，訂單選擇問題已成為流程型生產(chǎn)企業(yè)產(chǎn)能規(guī)劃的關(guān)鍵問題。

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

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

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

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

1 Slotnick模型

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

模型如下：

maxxQ-wC-d （1）

st. （2）

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

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

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

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

2 新的訂單選擇模型

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

2.1 基本假設(shè)

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

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

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

2.2 模型描述

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

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

Max∑∑xQ-wC-d （3）

st. （4）

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

2.3 模型驗(yàn)證及分析

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

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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