On the feasibility testing of the economic lot scheduling problem using the extended basic period approach

Ming-Jong Yao*, Salah E. Elmaghraby, Ing Chine Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

In this paper, we present our research on the feasibility testing problem for the Economic Lot Scheduling Problem (ELSP) using the Extended Basic Period (EBP) approach, i.e., the ELSP(EBP). We review past contributions to the issue of the feasibility of a given ‘solution’ to the ELSP and we propose two integer linear programming (ILP) models for its resolution. In view of the difficulty in solving the ILP (we demonstrate that this problem is NP-hard), we propose a new heuristic, Proc FT, to solve it. Numerical experiments verify that Proc FT is efficient, since its run time is of cubic order of the problem size, i.e., it is approximately an O(n3) algorithm. Also, using a set of randomly generated problems, our experimental results provide some insights into how the difficulty of the problem grows with the parameters in the problem. Importantly, our experimental results demonstrate that Proc FT is more reliable than the other heuristics, especially, when the utilization rate of the production facility is more than 70%.

Original languageEnglish
Pages (from-to)435-448
Number of pages14
JournalJournal of the Chinese Institute of Industrial Engineers
Volume20
Issue number5
DOIs
StatePublished - 1 Jan 2003

Keywords

  • Comparison
  • Feasibility testing
  • Lot scheduling
  • Random search algorithm

Fingerprint Dive into the research topics of 'On the feasibility testing of the economic lot scheduling problem using the extended basic period approach'. Together they form a unique fingerprint.

Cite this