一種改進的綜合生產計劃動態規劃優化方法

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

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

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

一種改進的綜合生產計劃動態規劃優化方法

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

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

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

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

動態規劃；綜合生產計劃；計算機優化

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

本文以文獻[4]提出的一類綜合生產計劃優化問題為研究對象，它是一個單目標、單一產品、有限能力約束的多階段優化決策問題，適合采用動態規劃方法對其求解。然而，文獻[4]所描述的綜合生產計劃優化問題在問題假設、數學優化模型、求解過程、計算方法四個方面均存在不足，有必要進行改進。基于此，本文深入分析了文獻[4]中原綜合生產計劃優化問題、數學優化模型、求解過程、計算方法存在的不足并針對這些不足提出了相應的改進措施。

1 原綜合生產計劃問題改進

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

由上述問題描述可以看出，原生產計劃問題存在如下不足：（1）假設期初和期末庫存為0，大大限制了應用范圍。實際生產實踐中，由于存在瓶頸期和生產能力的共同制約，很有可能需要在期初保有一定的庫存以滿足瓶頸期的需求，故期初庫存可能大于0。同樣的道理，為滿足下一計劃期中的瓶頸期的需求，需要在上一計劃期多安排生產使期末庫存大于0，上一計劃期的期末庫存也就成為下一計劃期的期初庫存。（2）假設各期生產能力上限相同，也與生產實際不一定相符。實際生產實踐中，由于受計劃期中各期人力、設備、工具、工作日歷及管理等因素波動的影響，各期的生產能力上限不一定相等。基于以上分析，本文提出如下的改進措施：將約束條件放寬，即假設期初庫存大于等于0、期末庫存大于等于0，各期生產能力上限可不同。

2 綜合生產計劃數學優化模型改進

（1）變量及函數定義

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

（2）原生產計劃數學優化模型

根據問題描述及變量定義，可得到如式（1）（2）表示的數學優化模型。

（3）改進后生產計劃數學優化模型

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

3 動態規劃求解過程改進

若對式（1）（2）數學優化模型采用動態規劃方法來求解，其狀態轉移方程和順序遞推關系如式（5）、（6）所示。

4 綜合生產計劃動態規劃計算機求解方法

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

表1 變量定義

4.1 變量定義

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

4.2 工作表設計

為便于利用Excel求解，需根據動態規劃問題的特點將相關數據映射成Excel工作表。程序計算過程中有關數據的輸入、中間計算結果、輸出均通過工作表進行。各表之間可能存在相互關聯的關系，如“計算過程”與“計算結果”之間彼此關聯，這通過各單元格的公式實現聯動，而這些公式的輸入則通過程序寫入。根據所研究問題的特點，主要設計了四張工作表，即“生產需求及能力約束”、“計算過程”、“計算結果”、“最優方案”。其中，“生產需求及能力約束”用于輸入各期需求量及生產能力上限，其結構如表2所示；“計算過程”用于存儲整個計算的中間過程數據，以便追蹤計算的全部過程，其結構如表3所示；“計算結果”用于存儲最終計算的生產計劃方案，其結構如表4所示。“最優方案”工作表結構與“計算結果”的結構完全相同，所不同的是它僅存儲系統輸出的最優方案，是計算結果中的一部分內容。

表2 生產需求及能力約束

表3 計算過程

表4 計算結果

4.3 計算流程

本文提出的綜合生產計劃動態規劃計算機求解方法總體思路如下：首先通過程序自動填充計算公式于“計算過程”和“計算結果”兩個工作表，然后根據用戶設置的期末目標庫存量自動輸出該期末庫存量下對應的最優生產計劃。

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

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

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

對圖1所示的計算流程的有關說明：

（1）S1：清除工作表。此步將“計算過程”除表頭以外的內容清除，同時將“計算結果”中除表頭和第0期以外的內容清除，以便存儲重新計算的結果。“計算結果”表中第0期（第二行）是期初庫存為V0時對應的參數，不參與循環計算，故不清除該行。

圖1 計算流程

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

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

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

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

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

（6）S17：通過此步可以產生多個最優解。

5 案例分析

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

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

表5 文獻[4]最優方案

圖2 Uk=6時期量圖

表6 文獻[4]V0=4時最優方案

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

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

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

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

圖3 Uk不相等時期量圖

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

表11 文獻[7]最優方案一

表12 文獻[7]最優方案二

6 結論

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

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

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

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

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

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

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

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

[8]秦宣云.基于優先缺貨權的工廠生產計劃的動態規劃模型[J].系統工程，2002，20（4）：20-24.

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

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

[11]王成春.Excel VBA 2003程序設計實例導航[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）；河南省教育廳科學技術研究項目（No.12B120005）；河南理工大學博士基金資助項目（No.B2011-088）。

曾強（1975—），男，博士，副教授，研究領域：工業工程、生產管理；沈玲（1980—），女，講師，研究領域：安全工程、工業工程；吳立云（1972—），女，在讀博士，副教授，研究領域：工業工程；蘭建義（1972—），男，在讀博士，副教授，研究領域：工業工程。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