Lot sizing problems with strong set-up interactions
IIE Transactions - 1997
Tóm tắt
We address the problem of coordinated replenishment of products when the products can be produced only in fixed proportion to each other. Such problems commonly arise in the manufacture of sheet/plate metal parts or die-cast parts. The problem is a variant of the well-known Joint Replenishment Problem. We call this problem the Strong Interaction Problem (SIP). After giving a mathematical formulation of the problem, we show that the general problem is NP-hard. An important variant of the problem, in which products are unique to a family, is shown to be polynomially solvable. We present several lower bounds, an exact algorithm and a heuristic for the problem. Computational testing on randomly generated problems suggests that our exact algorithm performs very well when compared with a commercially available integer programming solver. The heuristic method also gives good solutions.
Từ khóa
Tài liệu tham khảo
Gilmore, P.C. and Gomory, R.E. (1961) A linear programming approach to the cutting stock problem. Operations Research, 9, 849–859.
Gilmore, P.C. and Gomory, R.E. (1963) A linear programming approach to the cutting stock problem: part II. Operations Research, 11, 863–888.
Haesler, R. (1980) Controlling pattern changes in one dimensional trim problems. Operations Research, 28, 1001–1005.
Gilmore, P.C. and Gomory, R.E. (1965) Multistage cutting stock problems of two and more dimensions. Operations Research, 13, 94–120.
Aksoy, Y. and Erenguc, S.S. 1988. Multi-item inventory models with coordinated replenishments. International Journal of Operations and Production Management, 8, 63–73.
Federgruen, A. and Tzur, M. (1994) The joint replenishment problem with time-varying costs and demands: efficient, asymptotic and ε-optimal solutions. Operations Research, 42, 1067–1086.
Stowers, C.L. and Palekar, U.S. (1993) A dual ascent procedure for the joint replenishment problem. Working paper, Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, Urbana, IL.
Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability-A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., New York.
Federgruen, A. and Tzur, M. (1991) A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(nlogn) or O(n) time. Management Science, 37, 909–925.
Arkin, E., Joneja, D. and Roundy, R. (1989) Computational complexity of uncapacitated multi-echelon production planning problems. Operations Research Letters, 8, 61–66.
Geoffrion, A.M. (1974) Lagrangian relaxation for integer progamming. Mathematical Programming Study, 2, 82–114.
Stowers, C.L. (1993) Uncapacitated lot-sizing problems with set-up interactions. Ph.D. dissertation, Dept. of Mech. and Ind. Eng., Univ. of Illinois at Urbana-Champaign.