Capacitated dynamic lot-sizing problem with delivery/production time windows

被引：7

作者：

Hwang, H-C ^{[2
]}

Jaruphongsa, W. ^{[1
]}

Cetinkaya, S. ^{[3
]}

Lee, C-Y ^{[4
]}

机构：

[1] Chulalongkorn Univ, Sasin Grad Inst Business Adm, Bangkok 10330, Thailand

[2] Chosun Univ, Dept Ind Engn, Kwangju 501759, South Korea

[3] Texas A&M Univ, Dept Ind & Syst Engn, College Stn, TX 77843 USA

[4] Hong Kong Univ Sci & Technol, Dept Ind Engn & Logist Management, Kowloon, Hong Kong, Peoples R China

来源：

OPERATIONS RESEARCH LETTERS | 2010年 / 38卷 / 05期

关键词：

Dynamic lot-sizing model; Demand time window; Capacitated production model; ALGORITHM; MODEL; N);

D O I：

10.1016/j.orl.2010.04.009

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT(4)) time, where n is the number of demands and T is the length of the planning horizon. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：408 / 413

页数：6

共 22 条

[1] IMPROVED ALGORITHMS FOR ECONOMIC LOT-SIZE PROBLEMS [J].

AGGARWAL, A ;

PARK, JK .

OPERATIONS RESEARCH, 1993, 41 (03) :549-571

[2] Multi-item lot-sizing with joint set-up costs [J].

Anily, Shoshana ;

Tzur, Michal ;

Wolsey, Laurence A. .

MATHEMATICAL PROGRAMMING, 2009, 119 (01) :79-94

[3] COMPUTATIONAL-COMPLEXITY OF THE CAPACITATED LOT SIZE PROBLEM [J].

BITRAN, GR ;

YANASSE, HH .

MANAGEMENT SCIENCE, 1982, 28 (10) :1174-1186

[4] Capacitated multi-item lot-sizing problems with time windows [J].

Brahimi, Nadjib ;

Dauzere-Peres, Stephane ;

Najid, Najib M. .

OPERATIONS RESEARCH, 2006, 54 (05) :951-967

[5] A NEW DYNAMIC-PROGRAMMING ALGORITHM FOR THE SINGLE ITEM CAPACITATED DYNAMIC LOT-SIZE MODEL [J].

CHEN, HD ;

HEARN, DW ;

LEE, CY .

JOURNAL OF GLOBAL OPTIMIZATION, 1994, 4 (03) :285-300

[6] AN O(T2) ALGORITHM FOR THE NI/G/NI/ND CAPACITATED LOT SIZE PROBLEM [J].

CHUNG, CS ;

LIN, CHM .

MANAGEMENT SCIENCE, 1988, 34 (03) :420-426

[7]

Dauzere-Peres S., 2002, UNCAPACITATED LOT SI

[8] Algorithms for Capacitated Rectangle Stabbing and Lot Sizing with Joint Set-Up Costs [J].

Even, Guy ;

Levi, Retsef ;

Rawitz, Dror ;

Schieber, Baruch ;

Shahar, Shimon ;

Sviridenko, Maxim .

ACM TRANSACTIONS ON ALGORITHMS, 2008, 4 (03)

[9] A SIMPLE FORWARD ALGORITHM TO SOLVE GENERAL DYNAMIC LOT SIZING MODELS WITH N PERIODS IN 0(N LOG N) OR 0(N) TIME [J].

FEDERGRUEN, A ;

TZUR, M .

MANAGEMENT SCIENCE, 1991, 37 (08) :909-925

[10] DETERMINISTIC PRODUCTION PLANNING WITH CONCAVE COSTS AND CAPACITY CONSTRAINTS [J].

FLORIAN, M ;

KLEIN, M .

MANAGEMENT SCIENCE SERIES A-THEORY, 1971, 18 (01) :12-20

← 1 2 3 →