生产计划与调度研讨课

《生产计划与调度研讨课》由会员分享，可在线阅读，更多相关《生产计划与调度研讨课（14页珍藏版）》请在装配图网上搜索。

1、生产计划与调度研讨课 论文综述东南大学自动化学院Introduction 题目：USING LAG RANG EAN TECHNIQUES TO SOLVE HIERARCHICAL PRODUCTION PLANNING PROBLEMS* 作者：STEPHEN C. GRAVES 文章信息：MANAGEMENT SCIENCE-Vol. 28, No. 3, March 1982Printed in U.S.A.Abstract decomposition of a large scale production planning problem a mixed-integer linear

2、 program hierarchical procedure two subproblems:-the aggregate planning subproblem-the detailed scheduling subproblem Lagrange multipliersIntroduction What is Production planning and scheduling?acquisition, utilization, and allocation of production resourcesto best satisfy customer requirements at m

3、inimum production cost How to make the production decisions?the work force levelthe scheduling of overtimeproduction run quantitiesthe sequencing of their production.Objectives of PPS The objectives of pps is one best and one mimimum-The best service-The miminum cost Two wh- and one how Need what Wh

4、en need how to allocateTypical method a monolithic approach a hierarchical approachmonolithic approach a large mixed-integer linear programming problem Lagrangean relaxation the dual to the mixed-integer programmonolithic approach Advantage of monolithic approach:a well-defined model formulation-mea

5、ningful optimization Limitations of monolithic approach:-computational complexityGreat amount of detailed demand dataHierarchical Approach Partitions of a hierarchy of subproblems the upper hierarchy the lower hierarchyHierarchical Approach Advantages of Hierarchical Approach:- computationally simpl

6、er- less detailed demand data- correspondence to the organizational and decision-making echelons Limitation of Hierarchical Approach:-optimization each of these subproblemsNew Method Combination of two typical methods division of problems-the aggregate planning subproblemthe detailed scheduling subp

7、roblem a Lagrangean relaxation a hybrid approachProduct Disaggregation Items-family-types Type-the same seasonal demand pattern and the same production rate as measured by inventory investment produced per unit timefamily Family-a common setupsimple, single-resource modelmin z = Z C。+ Z 4/)+ Z $ 户 x

8、jtsuject to zj 1VZ,r(2)/得,+，J / I f if =,“llI 1llllN ijt - iit = ojuT3工 kF, -Ot rt iVr(3)VZ,r(4)V/,r(5)V/,r(6)VZ,./,r(7)V/,r(8)H-M S hierarchical system Hax and Meal solve the aggregate planning subproblem as a linear program, and solve the family disaggregation subproblem for the immediate time per

9、iod by a heuristic. solve the aggregate planning subproblem by minimizing overtime and holding costs subject to constraints (2), (3), and (7) The family disaggregation subproblem can then be solved, that is, family setup cost is minimized subject to constraints(4) (8) where the inventory levels for

10、each type in (4) are taken from the aggregate planning model. A critical distinction of the Hax and Meal approach detailed family demand estimates only for the immediate time periodeasier to implementH-M S hierarchical system Limitation:-the primary costs are those costs associated with the aggregat

11、e planning subproblem-when the family setup costs are dominant? a conceptual gap in the original hierarchical framework ignoring its impact on total setup costs as determined by the family disaggregation subproblemAn Iterative Procedure OBJECTIVES: sends cost information on setup costs back to the a

12、ggregate planning subproblem. The solution procedure consists of examining a Lagrangean relaxation to solve a dual problem to (PPS) by an iterative procedure.L(；t) = min z + 汇4 Z /厂/(9)L) .s 九 z = Z(C/。+Z%/)+ ZZs,X# (10)fij tand (2), (3),(6),(7),The dual problem to (PPS) is max L(A) (11) /tTo solve

13、the dual problem, an iterative procedure is proposed which is consistent with the Hax-Meal hierarchical framework. To see this, note that the Lagrangean relaxation as given in (9)-(10) may be separated into the following subproblems:(AP) minz. = Z(q/+Z/(44)g) min =汇工内力+ A/Q(AP) min z.=2(ctOt 一4，) (F

14、D) minZe=WX.+44) J t (AP) is just an aggregate planning model dealing with the planning of product types; (FD) is a family disaggregation model dealing with the scheduling of product families.Feedback Process the determination of the appropriate multipliers Az7 may be interpreted as a feedback proce

15、ss in the hierarchical framework, The dual problem is to find A, to maximize the Lagrangean一 (a) set k = 0, chose 4)(b) solve (AP) for 4一 (c) solve (FD) for 4(d) if the current solution to the Lagrangean satisfies some preset stopping criteria, stop; otherwise set k = k + 1, update % and return to (

16、b).A Primal Feasible Solution to PPS The solution of the dual problem given in (11) need not, and usually will not, identify a primal feasible solution to PPS. In such instances, a duality gap is said to exist and the dual solution provides just a lower bound for the optimal value to PPS. Two proced

17、ures to solve the gap/ Use the dual problem for generating bounds in a branch and bound or implicit enumeration procedure./ Incorporate the solution of the dual problem into a heuristic procedure.The computational results The computational results presented indicate that the Lagrangean procedure may

18、 be quite effective for generating good production schedules for quite difficult combinational problems. Indeed for the 36 test problems the best solutions were always within 4.4% of a lower bound to the optimum, and were within 3.1% of the lower bound to the optimum in all but five cases. These res

19、ults seem reasonably robust with respect to the problem specification and problem size. In addition, the Lagrangean procedure gave significantly better solutions that a hierarchical procedure for 27 test problems. JHLimitation of The Method The procedure for converting a dual solution into a feasibl

20、e solution to PPS that we used in our computational tests, need not be applicable for more complex production planning problems. It may be unrealistic to expect to be able to generate meaningful demand forecasts for the families for the later periods in the planning horizon. How types and families a

21、re defined?Assumption of The Method Assumption: all demand is known with certainty and all schedules are to be frozen over the planning horizon. However, most production planning seems to be done on a periodic(rolling schedule) base in which the demand data is continually being revised as the demand

22、 forecasts become less uncertainty. Another assumption: the production schedules that are generated periodically from static planning models, are effective when implemented in a dynamic setting.So, the validity of this assumption should be taken further examination.Extensions of The Method Some arti

23、cles are presented to solve the problems with uncertainty. The existent articles on the PP problems with uncertainties mostly focus on uncertainties of the demand, capacity and material supply in the single-period or infinite-horizon setting.(Bassok&Akella,1991;Ciarallo,Akella&Morton,199 4;lshikura,

24、1994;Kasilingam,1995;Metters,1997;H wang&H.S.Yan/Computers&lndustrial Engineering 38(2000)435455 436Medini,1998).Extensions of The Method Kira eta I. propose a stochastic linear programming approach to solve hierarchical production planning problems under uncertain demand (Kiraetal.,1997) Hong-Sen Yan propose a new stochastic interaction/prediction approach involving not only the three kinds of uncertainties(demands, capacities and material supply), but also the uncertainties of processing times, rework and waste products.(Hong-SenYan, 2000)Thank you !