A Genetic Algorithm with Modified Adaptive Penalty Function for Raw Milk Purchasing Plan

Abstract

Abstract:

The dairy processing plant purchases raw milk mainly from its headquarters, sometimes from local market, where the former can be viewed as production and the latter as outsourcing.Owing to the production capacity and management policy,both production and outsourcing levels are bounded.Raw milk supply can be backlogged because of dairy postponement allowed by customers.All of production,outsourcing and inventory/backlogging costs were as general concave functions.The problem was to satisfy all demands in the planning horizon by minimum total costs.To solve the problem,a novel adaptive penalty scheme was devised based on the feasible status of population and the degree of constraint violation for individuals.Furthermore,a new adaptive genetic algorithm was developed to solve the constrained optimization problem by using the penalty scheme.In order to test the performance of the proposed algorithm,we first made a selection examination to obtain the fittest operator combination and genetic operators' probabilities.Then,for four planning problems,by 50 runs of the algorithm,the advantages of the penalty scheme were verified by comparing with other common four penalty methods. 

Key words: raw milk purchasing plan, outsourcing, genetic algorithm, adaptive penalty function

摘要：

奶制品加工厂主要从总部采购鲜奶（生产），也会从当地奶农采购部分鲜奶（外包）。出于能力和策略的考虑，两种来源的鲜奶采购量均有限;考虑到客户允许奶制品延期交货，相应的鲜奶也可延期交货，生产、外包和库存/延期交货成本均为一般凹函数，问题是以最小的总成本来满足规划期的鲜奶需求。为求解该问题，设计了一种新的基于群体可行状态和个体约束违背程度的自适应惩罚方案，据此设计了求解该问题的遗传算法。为测试算法的性能，先进行了算子组合和遗传算子概率的选择实验，选出最适合的算子和算子概率;在此基础上，针对4个问题实例，通过50次运行，测试了所提自适应罚函数相对4种常见罚函数的优势。

关键词: 鲜奶采购计划, 外包, 遗传算法, 自适应罚函数

CLC Number:

ZHONG Jin-Hong-1, 2, HUANG Ling-2. A Genetic Algorithm with Modified Adaptive Penalty Function for Raw Milk Purchasing Plan[J]. China Mechanical Engineering, 2012, 23(10): 1194-1199.

钟金宏1, 2, 黄玲2. 鲜奶采购计划的改进自适应罚函数遗传算法[J]. 中国机械工程, 2012, 23(10): 1194-1199.

References

[1]Wagner H M,Whitin T M. Dynamic Version of the Economic Lot-size Model[J]. Management Science,1958,5(1) :89-96.
[2]Florian M, Lenstra J, Kan A R. Deterministic Pro- duction Planning: Algorithms and Complexity [J]. Management Science, 1980,26(7) : 669-679.
[3]Bitran G, Yanasse H. Computational Complexity of the Capacitated Lot Size Problem [J]. Management Science, 1982,28(10) : 1174-1186.
[4]Florian M, Klein M. Deterministic Production Planning with Concave Costs and Capacity Constraints [J]. Management Science, 1971,18(1) : 12-20.
[5]Janannathan R, Rao M. A Class of Deterministic Production Planning Problems[J]. Management Science,1973,19(11):1295-1300.
[6]Hoesel C P,Wagelmans A P. An O(T3) Algorithm for the Economic Lot-sizing Problem with Constant Capacities[J]. Management Science, 1996,42 (1) :142-150.
[7]Chung C, Lin C. An O (T^2) Algorithm for the NI/ G/NI/ND Capacitated Lot Size Problem[J]. Management Science,1988,34(2) :420-426.
[8]Heuvel W,Wagelmans A P. An Efficient Dynamic Programming Algorithm for a Special Case of the Capacitated Lot-sizing Prohlem[J]. Computers Operations Research, 2006,33 (12): 3583-3599.
[9]Aksen D, Altinkemer K, Chand S. The Single- item Lot-sizing Problem with Immediate Lost Sales[J]. Eur. J. Oper. Res. ,2003,147(3):558-566.
[10]Chu F, Chu C. Single-item Dynamic Lot Sizing Models with Bounded Inventory and Outsourcing [J]. IEEE Transactions on Systems, Man and Cybernetics,Part A: Systems and Humans, 2008,30(1):70-77.
[11]Sandbothe R A,Thompson G L. A Forward Algorithm for the Capacitated Lot Size Model with Stockouts[J]. Operation Research, 1990, 38 ( 3 ) : 474-486.
[12]Sandbothe R A,Thompson G L. Decision Horizons for the Capacitated Lot Size Model with Inventory Bounds and Stockouts[J]. Computers & Operations Research,1993,20(5) :455- 465.
[13]Atamttirk A, Hochbaum D S. Capacity Acquisition,Subcontracting, and Lot Sizing[J]. Management Science,2001,47(8): 1081-1100.
[14]Coelto C A. Theoretical and Numerical Constraint -Handling Techniques Used with Evolutionary Algorithms:a Survey of the State of the Art[J]. Computer Methods in Applied Mechanics and Engineering, 2002,191 (11/12):1245-1287.
[15]Hadj- Alouane A B, Bean J C. A Genetic Algorithm for the Multiple-Choice Integer Program [J]. Operations Research,1997,45(1) :92-101.
[16]Dadios E P, Ashraf J. Genetic Algorithm with Adaptive and Dynamic Penalty Functions for the Selection of Cleaner Production Measures:A Constrained Optimization Problem [J]. Clean Tech. Environ Policy,2006,8(2) :85-95.
[17]Homaifar A,Qi C X,Lai S H. Constrained Optimization Via Genetic Algorithms [J]. Simulation 1994,62(4) :242-254.
[18]Joines J, Houck C R. On the Use of Non-stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problems with Gas[C]// Proceedings of the First IEEE International Conference on Evolutionary Computation. Orlando, 1994:579-584.
[19]Kazarlis S, Petridis V. Varying Fitness Functions in Genetic Algorithms: Studying the Rate of Increase in the Dynamic Penalty Terms[C]//Proceedings of the 5th Int. Conf. on Parallel Problem Solving from Nature. Berlin, 1998: 211-220.