曾強，沈玲，吳立云，蘭建義

1.河南理工大學能源科學與工程學院，河南焦作 454000

2.河南理工大學安全科學與工程學院，河南焦作 454000

一種改進的綜合生產(chǎn)計劃動態(tài)規(guī)劃優(yōu)化方法

曾強1，沈玲2，吳立云1，蘭建義1

1.河南理工大學能源科學與工程學院，河南焦作 454000

2.河南理工大學安全科學與工程學院，河南焦作 454000

提出了一種改進的綜合生產(chǎn)計劃動態(tài)規(guī)劃優(yōu)化方法。以1999年甘應愛主編的《運籌學》第227～230頁給出的一類綜合生產(chǎn)計劃問題為研究對象，深入分析了原綜合生產(chǎn)計劃問題、數(shù)學優(yōu)化模型、動態(tài)規(guī)劃求解過程、計算方法存在的不足并提出了相應的改進措施。通過案例分析驗證了所提方法的有效性。

動態(tài)規(guī)劃；綜合生產(chǎn)計劃；計算機優(yōu)化

綜合生產(chǎn)計劃是指導生產(chǎn)的綱領(lǐng)。綜合生產(chǎn)計劃的優(yōu)劣決定了生產(chǎn)績效的高低，研究生產(chǎn)計劃優(yōu)化方法具有重要意義。按優(yōu)化目標可將綜合生產(chǎn)計劃優(yōu)化分為單目標優(yōu)化[1]和多目標優(yōu)化[2-3]。按計劃對象可將綜合生產(chǎn)計劃優(yōu)化分為單一產(chǎn)品綜合生產(chǎn)計劃優(yōu)化[4]和多產(chǎn)品綜合生產(chǎn)計劃優(yōu)化，多產(chǎn)品綜合生產(chǎn)計劃優(yōu)化更為復雜。按是否考慮能力約束可分為無限能力約束和有限能力約束下[5]的綜合生產(chǎn)計劃優(yōu)化。無限能力約束情況下的綜合生產(chǎn)計劃可執(zhí)行性差，常發(fā)生計劃不能按時完成的情況。按求解方法分為經(jīng)驗法、數(shù)學模型法。經(jīng)驗法是憑借計劃者的經(jīng)驗進行各期生產(chǎn)量的安排的方法，其計劃方案的優(yōu)劣取決于計劃者的經(jīng)驗，不同的計劃者做出的計劃可能相差較大。數(shù)學模型法則是指借助數(shù)學優(yōu)化模型，運用數(shù)學優(yōu)化方法如線性規(guī)劃法[3，6]、動態(tài)規(guī)劃法[4，7-9]、運輸法[4，7]等對數(shù)學模型進行求解。按計算方法可分為手工優(yōu)化和計算機輔助優(yōu)化兩種。手工計算僅適用于計算簡單、計算量小的場合，對于計算復雜、計算量大的綜合生產(chǎn)計劃優(yōu)化問題，手工計算的時效性差、準確性差，故需借助計算機輔助求解。從以上分析可見，綜合生產(chǎn)計劃優(yōu)化是一個復雜的系統(tǒng)優(yōu)化問題，針對不同的邊界條件，能組合出多種不同的優(yōu)化問題，現(xiàn)實中并不存在普遍適用的解決方案，需根據(jù)具體問題進行具體處理。

本文以文獻[4]提出的一類綜合生產(chǎn)計劃優(yōu)化問題為研究對象，它是一個單目標、單一產(chǎn)品、有限能力約束的多階段優(yōu)化決策問題，適合采用動態(tài)規(guī)劃方法對其求解。然而，文獻[4]所描述的綜合生產(chǎn)計劃優(yōu)化問題在問題假設(shè)、數(shù)學優(yōu)化模型、求解過程、計算方法四個方面均存在不足，有必要進行改進?；诖耍疚纳钊敕治隽宋墨I[4]中原綜合生產(chǎn)計劃優(yōu)化問題、數(shù)學優(yōu)化模型、求解過程、計算方法存在的不足并針對這些不足提出了相應的改進措施。

1 原綜合生產(chǎn)計劃問題改進

文獻[4]研究的綜合生產(chǎn)計劃優(yōu)化問題描述如下：設(shè)某公司對某種產(chǎn)品要制定一項n期的生產(chǎn)計劃。已知它的初始庫存為0，每期生產(chǎn)該產(chǎn)品的數(shù)量有上限，每期市場對該產(chǎn)品的需求量已知，公司保證各期的供應（不允許缺貨），在第n期的終結(jié)庫存為0，問該公司如何制定各期的生產(chǎn)計劃，使總成本最低。

由上述問題描述可以看出，原生產(chǎn)計劃問題存在如下不足：（1）假設(shè)期初和期末庫存為0，大大限制了應用范圍。實際生產(chǎn)實踐中，由于存在瓶頸期和生產(chǎn)能力的共同制約，很有可能需要在期初保有一定的庫存以滿足瓶頸期的需求，故期初庫存可能大于0。同樣的道理，為滿足下一計劃期中的瓶頸期的需求，需要在上一計劃期多安排生產(chǎn)使期末庫存大于0，上一計劃期的期末庫存也就成為下一計劃期的期初庫存。（2）假設(shè)各期生產(chǎn)能力上限相同，也與生產(chǎn)實際不一定相符。實際生產(chǎn)實踐中，由于受計劃期中各期人力、設(shè)備、工具、工作日歷及管理等因素波動的影響，各期的生產(chǎn)能力上限不一定相等?；谝陨戏治觯疚奶岢鋈缦碌母倪M措施：將約束條件放寬，即假設(shè)期初庫存大于等于0、期末庫存大于等于0，各期生產(chǎn)能力上限可不同。

2 綜合生產(chǎn)計劃數(shù)學優(yōu)化模型改進

（1）變量及函數(shù)定義

n為計劃期的總期數(shù)；k為第k期，k∈[0,n]；Dk為第k期需求量；Xk為第k期生產(chǎn)量；Vk為第k期期末庫存；Ck(Xk)為第k期生產(chǎn)量為Xk時的生產(chǎn)成本；Hk(Vk)為第k期期末庫存為Vk時發(fā)生的存貯成本；m為生產(chǎn)能力上限。

（2）原生產(chǎn)計劃數(shù)學優(yōu)化模型

根據(jù)問題描述及變量定義，可得到如式（1）（2）表示的數(shù)學優(yōu)化模型。

（3）改進后生產(chǎn)計劃數(shù)學優(yōu)化模型

根據(jù)對生產(chǎn)計劃問題的改進措施，新定義變量Uk為各期生產(chǎn)能力上限，對上述數(shù)學優(yōu)化模型進行了改進得到如式（3）（4）表示的數(shù)學優(yōu)化模型。

3 動態(tài)規(guī)劃求解過程改進

若對式（1）（2）數(shù)學優(yōu)化模型采用動態(tài)規(guī)劃方法來求解，其狀態(tài)轉(zhuǎn)移方程和順序遞推關(guān)系如式（5）、（6）所示。

4 綜合生產(chǎn)計劃動態(tài)規(guī)劃計算機求解方法

由文獻[4]對原問題的計算過程可以看出，其計算量很大，隨著計劃期、需求量、生產(chǎn)能力的增加，計算量將呈指數(shù)式增長，使得手工計算時效性差，并且手工計算具有出錯率高的特點，因此它無法適應復雜的動態(tài)規(guī)劃問題的求解。基于此，本文針對改進后的一類綜合生產(chǎn)計劃優(yōu)化問題、數(shù)學優(yōu)化模型及動態(tài)規(guī)劃求解過程的特點，研究并提出一種計算機輔助求解方法。下面對該方法進行簡要闡述。

表1 變量定義

4.1 變量定義

為便于計算機編程和后續(xù)內(nèi)容的描述，對所用到的變量說明如表1所示。

4.2 工作表設(shè)計

為便于利用Excel求解，需根據(jù)動態(tài)規(guī)劃問題的特點將相關(guān)數(shù)據(jù)映射成Excel工作表。程序計算過程中有關(guān)數(shù)據(jù)的輸入、中間計算結(jié)果、輸出均通過工作表進行。各表之間可能存在相互關(guān)聯(lián)的關(guān)系，如“計算過程”與“計算結(jié)果”之間彼此關(guān)聯(lián)，這通過各單元格的公式實現(xiàn)聯(lián)動，而這些公式的輸入則通過程序?qū)懭?。根?jù)所研究問題的特點，主要設(shè)計了四張工作表，即“生產(chǎn)需求及能力約束”、“計算過程”、“計算結(jié)果”、“最優(yōu)方案”。其中，“生產(chǎn)需求及能力約束”用于輸入各期需求量及生產(chǎn)能力上限，其結(jié)構(gòu)如表2所示；“計算過程”用于存儲整個計算的中間過程數(shù)據(jù)，以便追蹤計算的全部過程，其結(jié)構(gòu)如表3所示；“計算結(jié)果”用于存儲最終計算的生產(chǎn)計劃方案，其結(jié)構(gòu)如表4所示。“最優(yōu)方案”工作表結(jié)構(gòu)與“計算結(jié)果”的結(jié)構(gòu)完全相同，所不同的是它僅存儲系統(tǒng)輸出的最優(yōu)方案，是計算結(jié)果中的一部分內(nèi)容。

表2 生產(chǎn)需求及能力約束

表3 計算過程

表4 計算結(jié)果

4.3 計算流程

本文提出的綜合生產(chǎn)計劃動態(tài)規(guī)劃計算機求解方法總體思路如下：首先通過程序自動填充計算公式于“計算過程”和“計算結(jié)果”兩個工作表，然后根據(jù)用戶設(shè)置的期末目標庫存量自動輸出該期末庫存量下對應的最優(yōu)生產(chǎn)計劃。

自動填充“計算過程”和“計算結(jié)果”兩個工作表通過三層嵌套循環(huán)來實現(xiàn)。第一層（最外層）令k從1到n變化；第二層（中間層）令Vk從0到Vkmax變化；第三層（最內(nèi)層）令Xk從0到Sgmk變化。通過三層循環(huán)，將k、Vk、Xk的每種組合在“計算過程”工作表中以公式的形式在各單元格中輸出；同時，對于每個k，當進行了第二層和第三層循環(huán)之后，將最小Fk_Vk值對應的行輸出到“計算結(jié)果”中以備第k+1期查尋Fk_Vk值時使用。

輸出最優(yōu)方案采用“反向追蹤技術(shù)”實現(xiàn)，即通過用戶設(shè)置的最終庫存量Vn，在“計算結(jié)果”工作表中第n期對應的行中找到Vk列等于Vn值的行，從Vk-1列得到Vn_1值，并將此行輸出到“最優(yōu)方案”的n+2行，然后在第n-1期中尋找Vk列的值等于Vn-1的行，并將此行輸出到“最優(yōu)方案”的n+1行，依此類推，直到處理完第0期為止。

程序具體計算流程如圖1所示。

對圖1所示的計算流程的有關(guān)說明：

（1）S1：清除工作表。此步將“計算過程”除表頭以外的內(nèi)容清除，同時將“計算結(jié)果”中除表頭和第0期以外的內(nèi)容清除，以便存儲重新計算的結(jié)果?！坝嬎憬Y(jié)果”表中第0期（第二行）是期初庫存為V0時對應的參數(shù)，不參與循環(huán)計算，故不清除該行。

圖1 計算流程

（2）S2：變量賦初值。通過此步，將程序用到的輸入值賦給相關(guān)變量，主要有fr、fl、f1（初值2）、f2（初值2）、fl、n、Vnmax、Gd、Bd、h、M。

（3）S5：在jsgc的cells(fr，2)填充公式。

首先，自定義函數(shù)Vkmax()，其作用是返回第k期Vk的最大值，代碼如下：

其次，通過如下的代碼實現(xiàn)在Sheets（jsgc）.Cells（fr，2）中填充公式。

以上代碼的作用是若在“計算結(jié)果”第6列查找到Vk_1則返回其成本值Fk_1_Vk_1，否則返回M。

（6）S17：通過此步可以產(chǎn)生多個最優(yōu)解。

5 案例分析

以文獻[4，7]的案例，利用本文提出的方法進行了驗證。

文獻[4]中Gd=3千元，Bd=1千元，h=0.5千元。表5是V0=0，Vnmax=3，Vn=0時的最優(yōu)方案，圖2是其對應的期量圖。從表5和圖2可見，在上述參數(shù)設(shè)置下第1和4期各安排了6臺，其他各期均未安排生產(chǎn)計劃，其總成本最低，最低總成本是22.5千元。表6是V0=4，Vnmax=0，Vn=0的最優(yōu)方案，可見，因計算期初已有4臺產(chǎn)品，可滿足第1、第2期的1+3=4臺產(chǎn)品需求，使最優(yōu)方案總生產(chǎn)量由12臺減少為8臺，相應的總成本由22.5萬元減少到18.5千元。表7是V0=0，Vnmax=3，Vn=2時的最優(yōu)方案，可見，為滿足Vn=2的目標，使生產(chǎn)總量由12臺增加到14臺，生產(chǎn)成本由22.5千元增加到27.5千元。表8是Vnmax=0，Vn=0，U3＜D3時的最優(yōu)方案，可見，由于第3期的需求量大于其生產(chǎn)能力，使第2期提前生產(chǎn)超過其需求的量6-3=3以彌補第3期生產(chǎn)能力的不足。表9是V0=0，Vnmax=0，Vn=0，Uk不相同時的最優(yōu)方案，圖3是其對應的期量圖。從表9可見，各期的生產(chǎn)能力Uk不同，最優(yōu)方案中各期生產(chǎn)量Xk不超過Uk。由于Uk有所減小且各期不同，使安排生產(chǎn)的期數(shù)由2期增加到5期，各期生產(chǎn)量較接近Uk，表明更有效利用了每期的實際生產(chǎn)能力。表10是h=1千元時的最優(yōu)方案，與表5相比可見，若單位存儲成本上升到一定程度，會使原來在前期安排的生產(chǎn)計劃后期推遲，安排生產(chǎn)的期數(shù)增加，至于具體推遲到哪期，則取決于批固定成本Gd、單位變動成本Bd及各期生產(chǎn)能力Uk的相對關(guān)系，但可以肯定的是，最優(yōu)方案對應的批固定生產(chǎn)成本的增加值必小于等于存儲成本的減少值；相反，可以預見，隨著批生產(chǎn)成本Gd增加，會使安排生產(chǎn)計劃的期數(shù)減少，最優(yōu)方案對應的批固定生產(chǎn)成本的減少值必大于等于存儲成本的增加值。

表5 文獻[4]最優(yōu)方案

圖2 Uk=6時期量圖

表6 文獻[4]V0=4時最優(yōu)方案

文獻[7]中Xk取值范圍為0～2 500件，范圍過寬，組合量巨大，使計算量過大，時效性差，另一方面也沒有必要使Xk從0～2 500件進行遍歷，故需對該案例進行“數(shù)據(jù)變換”。變換方式如下：找出各期需求量及生產(chǎn)能力約束的公約數(shù)（建議取最大公約數(shù)），將各期需求量和生產(chǎn)能力約束上限除以此公約數(shù)，將單位變動成本Bd、單位存儲成本h乘以此公約數(shù)，計算結(jié)果中Xk、Vk則需乘以此公約數(shù)進行反變換。基于以上思路，文獻[7]計算過程中取Gd=5萬元，Bd=100萬元，h=5萬元。表11、表12是文獻[7]的兩個最優(yōu)解。

表7 文獻[4]V0=0，Vn max=3，Vn=2時最優(yōu)方案

表8 文獻[4]V0=0，Vn max=0，Vn=0，U3＜D3時最優(yōu)方案

表9 文獻[4]V0=0，Vn max=0，Vn=0，Uk不相同時最優(yōu)方案

圖3 Uk不相等時期量圖

表10 文獻[4]V0=0，Vn max=0，Vn=0，h=1時最優(yōu)方案

表11 文獻[7]最優(yōu)方案一

表12 文獻[7]最優(yōu)方案二

6 結(jié)論

將文獻[4]的綜合生產(chǎn)計劃優(yōu)化問題進行了改進從而拓寬了其應用范圍，針對改進后的一類綜合生產(chǎn)計劃優(yōu)化問題，通過對原數(shù)學優(yōu)化模型和動態(tài)規(guī)劃過程進行改進，形成了新的數(shù)學優(yōu)化模型和動態(tài)規(guī)劃過程，在此基礎(chǔ)上以Excel為開發(fā)平臺，提出了一種計算機輔助求解方法，最后通過案例研究驗證了本文方法的有效性。研究結(jié)果表明，本文方法是有效的，具有較強的理論意義和應用價值。

[1]陳杰，潘衛(wèi)剛.VMI策略下的綜合生產(chǎn)計劃研究[J].運籌與管理，2004，13（3）：137-140.

[2]黃景平，李彤，馮珊.企業(yè)綜合生產(chǎn)計劃的一種設(shè)計及優(yōu)化方法[J].華中理工大學學報，1999，27（1）：7-10.

[3]于麗英，楊雷.生產(chǎn)計劃的雙目標混合整數(shù)規(guī)劃模型及其求解[J].上海交通大學學報，2001，35（7）：1100-1102.

[4]甘應愛，田豐.運籌學[M].北京：清華大學出版社，1999：227-230.

[5]林中偉，謝強.基于遺傳算法的多級有限能力生產(chǎn)計劃[J].小型微型計算機系統(tǒng)，2003，24（1）：123-126.

[6]呂志民，宋肖青，董紹華.鋼鐵聯(lián)合企業(yè)中期生產(chǎn)計劃建模及算法[J].計算機集成制造系統(tǒng)，2011，17（1）：89-94.

[7]李懷祖.生產(chǎn)計劃與控制[M].北京：中國科學技術(shù)出版社，2010：125-128.

[8]秦宣云.基于優(yōu)先缺貨權(quán)的工廠生產(chǎn)計劃的動態(tài)規(guī)劃模型[J].系統(tǒng)工程，2002，20（4）：20-24.

[9]李嫦，趙磊，趙曉波.組裝線生產(chǎn)計劃和庫存策略的優(yōu)化[J].清華大學學報：自然科學版，2010，50（5）：669-672.

[10]王鴻儒.Excel VBA程序設(shè)計[M].北京：中國鐵道出版社，2005.

[11]王成春.Excel VBA 2003程序設(shè)計實例導航[M].北京：中國鐵道出版社，2005.

ZENG Qiang1,SHEN Ling2,WU Liyun1,LAN Jianyi1

1.School of Energy Science and Engineering,Henan Polytechnic University,Jiaozuo,Henan 454000,China
2.School of Safety Science and Engineering,Henan Polytechnic University,Jiaozuo,Henan 454000,China

An improved method to optimize aggregate production planning based on dynamic programming is proposed. The aggregate production planning problem given from page 227 to page 230 in the book“Operation Research”editored by Gan Ying’ai is taken as the subject investigated in this paper.The shortage of the original optimizing problem of aggregate production planning,mathematic optimizing model,dynamic programming process and computation method is analyzed deeply in sequence and the corresponding improved measures are proposed for them.The effectiveness of the proposed method is tested by case study.

dynamic programming;aggregate production planning;computer optimization method

A

TP391；C93-03

10.3778/j.issn.1002-8331.1210-0022

ZENG Qiang,SHEN Ling,WU Liyun,et al.Improved method to optimize aggregate production planning based on dynamic programming.Computer Engineering and Applications,2014,50（21）：248-253.

國家自然科學基金（No.51104056）；河南省教育廳科學技術(shù)研究項目（No.12B120005）；河南理工大學博士基金資助項目（No.B2011-088）。

曾強（1975—），男，博士，副教授，研究領(lǐng)域：工業(yè)工程、生產(chǎn)管理；沈玲（1980—），女，講師，研究領(lǐng)域：安全工程、工業(yè)工程；吳立云（1972—），女，在讀博士，副教授，研究領(lǐng)域：工業(yè)工程；蘭建義（1972—），男，在讀博士，副教授，研究領(lǐng)域：工業(yè)工程。E-mail：zengqiang@cqu.edu.cn

2012-10-08

2012-12-19

1002-8331（2014）21-0248-06

CNKI出版日期：2013-01-11，http://www.cnki.net/kcms/detail/11.2127.TP.20130111.0951.002.html