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%.
|Number of pages||14|
|Journal||Journal of the Chinese Institute of Industrial Engineers|
|State||Published - 1 Jan 2003|
- Feasibility testing
- Lot scheduling
- Random search algorithm