A parallel algorithm for the dynamic lot-sizing problem

Jrjung Lyu, Ming Chang Lee

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

The dynamic lot-sizing model (DLS) is one of the most frequently used models in production and inventory system because lot decisions can greatly affect the performance of the system. The practicality of DLS algorithms is hindered by the huge amount of computer resources required for solving these models, even for a modest problem. This study developed a parallel algorithm to solve the lot-sizing problem efficiently. Given that n is the size of the problem, the complexity of the proposed parallel algorithm is O(n2p) with p processors. Numerical experiments are provided to verify the complexity of the proposed algorithm. The empirical results demonstrate that the speedup of this parallel algorithm approaches linearity, which means that the proposed algorithm can take full advantage of the distributed computing power as the size of the problem increases.

Original languageEnglish
Pages (from-to)127-134
Number of pages8
JournalComputers and Industrial Engineering
Volume41
Issue number2
DOIs
Publication statusPublished - 2001 Nov 1

Fingerprint

Parallel algorithms
Distributed computer systems
Experiments

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Engineering(all)

Cite this

@article{898a13f4039841e18401cceb2d69c610,
title = "A parallel algorithm for the dynamic lot-sizing problem",
abstract = "The dynamic lot-sizing model (DLS) is one of the most frequently used models in production and inventory system because lot decisions can greatly affect the performance of the system. The practicality of DLS algorithms is hindered by the huge amount of computer resources required for solving these models, even for a modest problem. This study developed a parallel algorithm to solve the lot-sizing problem efficiently. Given that n is the size of the problem, the complexity of the proposed parallel algorithm is O(n2p) with p processors. Numerical experiments are provided to verify the complexity of the proposed algorithm. The empirical results demonstrate that the speedup of this parallel algorithm approaches linearity, which means that the proposed algorithm can take full advantage of the distributed computing power as the size of the problem increases.",
author = "Jrjung Lyu and Lee, {Ming Chang}",
year = "2001",
month = "11",
day = "1",
doi = "10.1016/S0360-8352(01)00047-X",
language = "English",
volume = "41",
pages = "127--134",
journal = "Computers and Industrial Engineering",
issn = "0360-8352",
publisher = "Elsevier Limited",
number = "2",

}

A parallel algorithm for the dynamic lot-sizing problem. / Lyu, Jrjung; Lee, Ming Chang.

In: Computers and Industrial Engineering, Vol. 41, No. 2, 01.11.2001, p. 127-134.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A parallel algorithm for the dynamic lot-sizing problem

AU - Lyu, Jrjung

AU - Lee, Ming Chang

PY - 2001/11/1

Y1 - 2001/11/1

N2 - The dynamic lot-sizing model (DLS) is one of the most frequently used models in production and inventory system because lot decisions can greatly affect the performance of the system. The practicality of DLS algorithms is hindered by the huge amount of computer resources required for solving these models, even for a modest problem. This study developed a parallel algorithm to solve the lot-sizing problem efficiently. Given that n is the size of the problem, the complexity of the proposed parallel algorithm is O(n2p) with p processors. Numerical experiments are provided to verify the complexity of the proposed algorithm. The empirical results demonstrate that the speedup of this parallel algorithm approaches linearity, which means that the proposed algorithm can take full advantage of the distributed computing power as the size of the problem increases.

AB - The dynamic lot-sizing model (DLS) is one of the most frequently used models in production and inventory system because lot decisions can greatly affect the performance of the system. The practicality of DLS algorithms is hindered by the huge amount of computer resources required for solving these models, even for a modest problem. This study developed a parallel algorithm to solve the lot-sizing problem efficiently. Given that n is the size of the problem, the complexity of the proposed parallel algorithm is O(n2p) with p processors. Numerical experiments are provided to verify the complexity of the proposed algorithm. The empirical results demonstrate that the speedup of this parallel algorithm approaches linearity, which means that the proposed algorithm can take full advantage of the distributed computing power as the size of the problem increases.

UR - http://www.scopus.com/inward/record.url?scp=0035501297&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035501297&partnerID=8YFLogxK

U2 - 10.1016/S0360-8352(01)00047-X

DO - 10.1016/S0360-8352(01)00047-X

M3 - Article

VL - 41

SP - 127

EP - 134

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

SN - 0360-8352

IS - 2

ER -