Comparison among the Feasibility Testing Heuristics for the Economic Lot Scheduling Problem

摘要

In this study, we compare four feasibility testing heuristics for the Economic Lot Scheduling Problem (ELSP). We proved that the feasibility testing problem for the ELSP is at least NP-hard in our previous study. Therefore, we proposed a new random search algorithm, i.e., Proc FT, to efficiently solve the feasibility testing problem. In order to test the performance of Proc FT, we compare it with three other most representative heuristics proposed by Boctor, Geng and Vickson and Park and Yun, respectively. In preparing our experimental data, we randomly generate 100 feasible problems for seven machine-utilization-rate (MUR) ranges. Note that Proc FT successfully confirms each one of these 700 problems to be feasible. However, the other three heuristics are unable to identify more than 50% of the problems to be feasible for some MUR ranges. Therefore, our experimental results show that Proc FT is the best heuristic for the feasibility testing problem in the ELSP.