Separable programming for aggregate production planning: A high-order cost case

Meij, J. T. Article Separable programming for aggregate production planning: A high-order cost case South African Journal of Business Management Provided in Cooperation with: University of Stellenbosch Business School (USB), Bellville, South Africa Suggested Citation: Meij, J. T. (1982) : Separable programming for aggregate production planning: A high-order cost case, South African Journal of Business Management, ISSN 2078-5976, African Online Scientific Information Systems (AOSIS), Cape Town, Vol. 13, Iss. 1, pp. 18-22, https://doi.org/10.4102/sajbm.v13i1.1166 This Version is available at: https://hdl.handle.net/10419/217786 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Separable programming for aggregate production planning - A high-order cost case J.T. Meij Department of Mechanical Engineering, University of Stellenbosch Many production managers are faced with the problem of planning production, inventory and work-force under the constraint of limited resources to meet a seasonal demand. Considerable research has been done on this planning problem and various planning models have been introduced. In those cases where linearity of the cost functions of an undertaking may reasonably be assumed. an ordinary linear programming model suffices. In many cases. however, this simple linear approach to certain essentially non-linear cost functions is unacceptable owing to the gross approximation made. Separable programming (SEP) is introduced as a solution methodology to this aggregate production planning problem in a complex. high-order cost structure case. The cost structure was used by Goodman for the application of goal programming (GP) in this field. The Goodman GP model makes provision for positive or negative slack for the production level, work-force level and inventory level with penalty costs for these slack-deviations. Goodman also made use of a 'sectioning search' model for this high-order cost case to serve as a measure for his GP model. A comparison is made between the results of these three approaches. SEP offered an improvement of more than 4% in total cost in comparison with the sectioning search model, and performs 26% better than the GP model. S. Afr. J. Bus. Mgmt. 1982, 13: 18-22 Baie produksiebestuurders word gekonfronteer met die probleem van die beplanning van produksiehoeveelheid, voorraadvlak en arbeidsmag met inagneming van die beperkte bronne tot die onderneming se beskikking vir die bevrediging van 'n seisoenale aanvraag. Heelwat navorsing is al oor hierdie beplanningsprobleem gedoen en 'n verskeidenheid wiskundige en ander modelle is getoets. In die gevalle waar lineere kostefunksies by 'n onderneming met 'n groot mate van sekerheid aanvaar kan word, kan van gewone lineere programmeringsmodelle gebruik gemaak word. In baie ander gevalle is die aanname van 'n lineere kostestruktuur egter onaanvaarbaar weens growwe aannames wat gemaak word. Skeibare programmering (SEP) word voorgestel as 'n oplossingsmetodiek vir die taktiese produksiebeplanningsprobleem in ·n komplekse, h<*orde, kostestruktuurgeval. Hierdie kostestruktuur is deur Goodman gebruik vir die toepassing van doelwit-programmering (GP) in die gebied. Die Goodman doelwit-programmeringsmodel maak voorsiening vir positiewe en negatiewe afwykings vir die produksievlak arbeidsmagvlak en voorraadvlak met boete-koste vir die afwykings. ' Goodman gebruik ook 'n 'verdeling-soek'-model, vir hierdle hot-orde koste-geval, vir vergelykingsdoeleindes teen sy GP-model. ·n Vergelyking word gemaak tussen die resultate van hlerdie drie benaderings. Die SEP-model loon 'n verbetering van 4% op die totale koste van die verdeling-soek-model en presteer 26% beter as die GP-model. S.-Afr. Tydskr. Bedryfsl. 1982, 13: 18 - 22 I.T. MelJ Professor, Department or MC(:hanicaJ Enaincerina, Univenity of Stellenbosch Stellenbosch 7600, Republic of South Africa ' Received September 1981 ; accepted November 1981 The aggregate production planning problem, in its simplest form, may be stated as follows: To develop the lowest cost production plan given a fluctuating demand pattern and limited production resources. Various solution methodologies to solve this opt1m1zation problem have been suggested. Holt, Modigliani, Muth and Simon 1•2 developed the Linear Decision Rule (LOR) approach for assumed quadratic cost structures. Their published application of LOR at a paint factory served as a yardstick for many different models. Hanssman and Hess3 used the LOR model as a basis for the development of their programming model because ... 'it appears, however, that in the majority of practical applications and theoretical models the cost functions are assumed to be linear'. Based on this approach Goodman 4•5 presented an alternative linearization method and used goal programming (GP) to solve the paint factory problem. In comparison with linear programming (LP) and LOR, goal programming gave good results for the quadratic cost function case. However, in the case of the higher-order cost function used by Goodman, the GP approach failed in comparison with a computer search method (sectioning search). In this paper the use of separable programming (SEP) for the case of high-order cost functions is shown to give excellent results. The advantage of this method lies in the fact that ordinary linear programming algorithms can be used to solve the model. To develop his fourth-order cost function Goodman made use of a hypothetical real world set of data, reproduced in Table 1. SEP is also applied to this set of data to test its ability to fit the real world situation. Goal programming model The Goodman GP model was developed to fit the hypothetical historical cost data-set shown in Table 1. In this table only the absolute values of changes are shown. It is assumed that the costs are symmetrical about the zero cost point of each variable. The cost model is constructed as follows. Define: P, = Production rate in period t D, = Demand in period t I, = Inventory level at the end of period t W, = Work-force level in period t By fitting curvilinear segments to a set of the hypothe· S. Afr. J. Bus. Mgmt 1982, 13(1) tical cost data the following cost functions were obtained: 340 w, Regular payroll. 0,2 (P, - 6 W,>4 Overtime and idletime 64( w, - W, _ / Hiring and layoff. O,l(P, - P,_ / Production level increase and decrease. O, 1(/, -320)4 Inventory and shortages. These cost functions lead to the following total cost model. Minimize the total cost: °t (340 W, + 0,2(P, -6 W,)4 /= I + 0,1(/, - 320)4) Subject to: for t = 1,2,3 .... n Goodman solved this model with goal programming. It is based upon the notion that each of the fourth-order cost terms becomes zero when the expression inside the parentheses is zero. Minimization of each cost term is regarded as a goal and is formulated as a constraint. It is necessary to allow positive and negative slack in these constraints because it is not possible to minimize simultaneously all the cost terms while at the same time satisfying the demand requirements. The resulting goal constraints can be expressed as: P, - 6W, + Q,+ Q,- = 0 WI Wt-I + R+ I RI = 0 P, P,-1 + s+ I sI =0 1r 320 + r+ I rI =0 /1_1 + P, -D, = I, P, ;?I; 0 w, ;?I; 0 t = 1,2 .... n, where Q, R, Sand Tare slack variables. Positive coefficients are assigned to the slack variables in the objective function. The effect is to penalize deviations from the desired goals. The objective function is given by: Min J1 [340 W, + CtQ/ + C,Q, -+ CzR/ + CzR,- + C3S,+ + c~,- + C4T,+ + c.r,-1 19 The coefficients C1, C2, C3 and C4 must be selected to give good cost approximations of the cost terms that they represent. This is done by approximating the cost functions by linear segments. The slopes of these linear segments give the desired cost coefficients. (See Figure 1.) The slopes are set so that area A is equivalent to area B, for example: Figure 1 Approximation of a cost function by a linear segment (Goodman). Separable programming formulation In separable programming the same principle is applied as in goal programming. The main difference is that the cost terms are now approximated by several linear segments. (See Figure 2.) COST COST VARIABLE Fl11ure 2 Approximation of high-order cost function by several linear segments. 20 The following model can thus be formulated. Define: OT = Overtime OA = Idle time HT = Increase in work-force (Number of people) HA = Decrease in work-force (Number of people) PT = Increase in production rate PA = Decrease in production rate VT = Inventory VA = Shortages W = Normal work-force P = Production rate I = Net inventory level D = Demand t = Time period T = Number of time periods (Planning horizon) b, c, d, e, J, g, u, s = Constants from piecewise approximations for variables B, C, D, E, F, G, U, S = Cost constants from piecewise approximation i, j, k, I, m, n, q, r = Inter-subscripts determining thesequence of the piecewise segments. G = Number of piecewise segments required (kept constant to simplify the formulation) a = Regular work-force cost coefficient Z = Ratio of production to work-force (productivity constant). The separable programming model can be expressed as: Minimize the objective function: ;i [aw, + J1 B; OT;, + J1 cj OAj, + J1 DkHTkT+ I E1 HA 11 + J1 Fm PTm, + Ji GnPAn, + JI uq VTq, + IS, VA,,] Subject to the constraints: W, - W,_ 1 - HT, + HA, = O P, - P,_ 1 - PT, + PT, = O I, - 320 -VT, + VA, = 0 P, -6 w, -OT, + OA 1 = 0 S.-Afr. Tydskr. Bedryfsl. 1982, 13(1) P, -I, + I, -I = D, w, ;;i. 0 P, ;;i. 0 f b;OT;, - OT,+ ZW, = 0 i=I f J = I eiOAi, - OA, + ZW, = 0 JI d*HT*, - HT,= 0 i e1 HA 1 , - HA, = 0 f m=I fmPTm, - PT,= 0 ! n=I g n PA nt - PA 1 = 0 ! q=I u VT - q qt VT-'+ 320 = 0 I G :I: r=I s VA - r rt VA,+ 320 = 0 for all t = 1,2 .... T. Note: G may vary for each variable depending on the desired quality of the fit of the linear segments to the cost structure. Application of the separable programming model The separable programming model was applied to two alternative cost structures: The first run was done using costs as given by the fourth-order cost functions developed by Goodman. Each cost function was approximated by six piecewise linear segments. Thus G = 6 in the formulation. This run will be called SEP (model application). The second run was done by using directly the hypothetical historical cost data shown in Table l. Six piecewise linear segments were used to approximate each variable. This run will be called SEP (direct application). The cost terms of both cost structures were graphed to determine the function values of the linear segments and the associated cost coefficients. It must be emppasized that the model developed when fitting the linear segments to the real world cost structure given in Table l must be Table 1 Hypothetical-historical cost data by Goodman 1 1w,-w,_ 1 1 Cost IP,-P,-11 Cost II, - fl Cost IP,-ZW,I Cost 0 0 1 1 1 0 0 66 2 2 2 2 2 1 001 4 24 3 9 2 4 3 .S 210 .s 68 4 28 3 14 4 20 100 7 225 6 122 .s 131 .s 38 120 10 1 049 8 392 7 457 7 86 300 16 6 310 11 1 370 10 1 876 9 139 200 22 26 100 l.S .S 417 12 3780 12 224 400 34 123 400 21 18 240 14 7 79.S 14 279 600 52 487 200 39 231 200 19 401 100 18 20 600 87 1 140 000 .SI 474 400 22 34 900 2.S 698 700 I.SO 2 224 000 70 702 500 30 58 200 S. Afr. J. Bus. Mgmt 1982, 13(1) 21 Table 2 Aggregate production plan using separable programming applied to the high-order cost model and applied to the real-world cost structure Production (Units) Work-force (Men) Inventory (Units) Period Demand Model application Direct application Model application Direct application Model application Direct application 0 4SO 4SO 7S 7S 320 320 I 430 446 441 73 73 336 331 2 447 431 424 71 70 319 308 3 440 409 402 67 67 289 271 4 316 378 380 64 6S 3SO 33S s 397 361 37S 62 63 314 313 6 37S 349 368 60 62 289 30S 7 292 364 368 62 62 360 381 8 4S8 39S 390 64 64 297 312 9 400 383 383 63 63 280 29S 10 3SO 3S2 361 60 61 282 30S 11 284 361 3S3 64 61 3S9 374 12 400 401 37S 69 64 360 348 13 483 441 464 74 7S 318 329 14 S09 478 486 79 79 288 30S IS soo 493 soo 84 82 280 30S 16 475 508 492 89 84 313 322 17 soo 548 Sl3 94 88 360 33S 18 600 600 629 99 104 360 364 19 700 668 663 108 109 328 327 20 700 708 68S 113 112 337 312 21 72S 668 663 108 109 280 2SO 22 600 600 600 103 102 280 2SO 23 432 S60 572 98 97 408 390 24 61S S49 S60 94 9S 342 33S Total cost -(Calculated by using costs in Table I)} Model application: R9 817 794 Direct application: R9 818 227 Table 3 Aggregate production plan using the sectioning search and goal programming models of Goodman Production (Units) Work-force (Men) Inventory (Units Period Demand Sectioning search Goal programming Sectioning search Goal programming Sectioning search Goal programming I 430 431 4SO 7S 7S 301 320 2 447 440 447 72 74 294 320 3 440 426 403 69 67 280 283 4 316 392 37S 6S 63 3S6 342 s 397 374 37S 62 63 333 320 6 37S 348 37S S9 63 306 320 7 292 348 37S 60 63 362 403 8 4S8 386 37S 63 63 290 320 9 400 391 37S 64 63 281 29S 10 3SO 3SS 3S3 61 S9 286 298 11 284 3S6 3S3 63 59 3S8 367 12 400 399 353 68 S9 3S7 320 13 483 444 483 73 30 318 320 14 S09 481 496 78 83 290 307 IS soo 488 496 83 83 278 303 16 47S sos 496 88 83 311 324 17 soo SS2 496 94 83 363 320 18 600 607 600 101 100 370 320 19 700 662 700 107 117 332 320 20 700 699 700 112 117 331 320 21 72S 6S9 700 107 117 26S 29S 22 600 600 S57 101 93 26S 2S2 23 432 S4S SS7 9S 93 378 377 24 6IS SS3 SS7 93 93 316 319 Total cost -(Calculated by using costs in Table I) Sectioning search: RIO 625 200 Goal programming: R12 237 846 22 S.-Afr. I yJ,kr. UeJryhl. 1982, 13(1) Table 4 A comparison of the cost areas and total cost associated with each solution methodology (All costs calculated using Table 1) Separable programming: Separable programming: Sectioning search Goal programming Application of model costs Direct cost application Costs (last 13 periods) (last 13 periods) (last 13 periods) (24 periods) (last 13 periods) (24 periods) R R R R R R Regular work-force 408 000 (100) 8 408 340 (100) 412 080 (IOI) 653 480 408 000 (100) 649 740 Change in production rate 3 856 718 (100) 6 783 299 (176) 3 724 148 ( 97) 4 074 351 3 838 973 ( 99) 3 954 773 Changes in workforce 602 981 (100) I 859 610 (308) 578 620 ( 96) 635 312 749 782 (124) 765 339 Overtime and idletime 179 565 (100) 46 ( 0) 270 616 (151) 320 716 44 941 ( 25) 53 406 Inventory and shonages 3 015 479 (100) 1 376 231 ( 46) 2 733 031 ( 91) 4 133 935 2 744 128 ( 91) 4 394 969 Total cost 8 062 743 (100) IO 427 520 ( 129) 7 718 495 ( 96) 9 817 794 7 785 824 ( 97) 9 818 227 "Numbers in brackets are percentages. regarded as the better model -the fit to the Goodman model was done for control purposes. Results and comparison In order to compare the results of the two SEP models with that of the two approaches, goal programming and sectioning search used by Goodman, a twenty-fourperiod planning horizon was used. The production plans for both SEP models are given in Table 2 and can, for all practical purposes, be regarded as similar. The total cost difference is negligible. The comparison between the sectioning search model and the goal programming model for this planning period is given in Table 3. These results illustrated clearly that the cost structure used is very sensitive, so that small deviations from the global optimum plan involves large changes in the total cost. Costs are calculated for each of the production plans from the cost data in Table 1 using interpolation where necessary. A comparison was made between the results of the four models mentioned above, on the basis of costs in the various cost areas. The starting conditions used by Goodman were unknown and therefore only the last 13 periods ~e co_mpared to eliminate its effect. The comparison is given m Table 4. SEP (model application) offered an improvei:nent of m~re than 40/o in the total cost in comparison with the sectioning search model and performs 260Jo better than the GP models. These improvements are s?mewhat lower in the case of the SEP (direct application) - 3,40Jo and 2SOJo respectively. A percentage-wise comparison is also made between the models in Table 4 The sectioning search results are used as a basis for thi~ c~mpari.son. Major differences can be summarised as indicated m Table 5. Concluslon In conclusion the foil owing advantages of the SEP a _ proach.must be ~nderlined. This is a mathematical pr~- grammmg t~hmque that can be used in a very flexible way. More linear segments may be added in cases where Table 5 A comparison between the various models, using sectioning search results as a basis Major differences compared to the sectioning Model search results Goal Changes in the work-force is dominant (approximateprogramming ly three times more), no overtime/undertime and less inventory. Higher total cost. SEP (model application) SEP (direct application) More overtime/undertime and less inventory. Total cost less. More changes in the work-force, less overtime/ undertime and less inventory. Total cost less. more accuracy is needed. In the case of monotonous cost increases (e.g. concave cost structures), the ordinary simplex algorithm may be used to solve the problem. The linear segments can be fitted graphically to real-world cost data without deriving, by means of laborious curve fitting methods, a complex mathematical model. In many cases ordinary linear curves, while in other instances (e.g. ~vertime pay as a linear function of normaltime pay) hnear segments, represent the real world. References I. ~OLT, C., MODIGLIANI, F. & SIMON, H.A. 'A Linear Decis10.n Rule for Production Employment Scheduling', Manage. Sc,., October 1955. 2. ~O~T, ~-, MODIGLIANI, F., SIMON, H.A. & MUTH, J.F. Derivation of a Linear Decision Rule for Production and Employment', Manage. Sci., January 1956. 3. HANSSMANN, F. & HESS, W. 'A Linear Programming Approach to Production and Employment Scheduling', Manage. Technol., January 1960, 1(1). 4. GOOD~AN, D.A. 'A New Approach to Scheduling Aggregate Production and Work Force', AIIE Transactions June 1973 Vol. S. ' ' 5. GOODM~N, D.A. 'A Goal Programming Approach to Aggrega~e Planning of Production and Work Force'' Manage. Sc1.,August 1974, 20(12), p.1569.