مطالعه مقایسه ای الگوریتم های هیوریستیک مساله زمانبندی اقتصادی بار

The Economic Lot Scheduling Problem (ELSP) has been well-researched for more than 40 years. As the ELSP has been generally seen as NP-hard, researchers have focused on the development of efficient heuristic approaches. In this paper, we consider the time-varying lot size approach to solve the ELSP. A computational study of the existing solution algorithms, Dobson’s heuristic, Hybrid Genetic algorithm, Neighborhood Search heuristics, Tabu Search and the newly proposed Simulated Annealing algorithm are presented. The reviewed methods are first tested on two well-known problems, those of Bomberger’s [Bomberger, E. E. (1966). A dynamic programming approach to a lot size scheduling problem. Management Science 12, 778–784] and Mallya’s [Mallya, R (1992). Multi-product scheduling on a single machine: A case study. OMEGA: International Journal of Management Science 20, 529–534] problems. We show the Simulated Annealing algorithm finds the best known solution to these problems. A similar comparison study is performed on various problem sets previously suggested in the literature. The results show that the Simulated Annealing algorithm outperforms Dobson’s heuristic, Hybrid Genetic algorithm and Neighborhood search heuristics on these problem sets. The Simulated Annealing algorithm also shows faster convergence than the best known Tabu Search algorithm, yet results in solutions of a similar quality. Finally, we report the results of the design of experiment study which compares the robustness of the mentioned meta-heuristic techniques.

The Economic Lot Scheduling Problem (ELSP) deals with the production assignment of several different products on a given single production facility to minimize the total cost. A typical ELSP as described in Maxwell (1964) has the following features: 1. Only one product can be produced at a time on the machine. 2. Each product has a deterministic and constant demand and production rates. 3. The set-up cost and set-up times are independent of the production sequence. 4. The production facility is assumed to be capable of satisfying demand predicted during the planning horizon. 5. The inventory holding cost is directly proportional to the amount of inventory. With the ELSP generally viewed as NP-hard, the focus of most research efforts has been to generate near optimal repetitive schedule(s). To date, several heuristic solutions have been proposed using any one of the common cycle, basic period, or time-varying lot size approaches. The common cycle approach always produces a feasible schedule and is the simplest to implement, however in some cases, the solution when compared to the Lower Bound (LB) is of poor quality. Unlike the common cycle approach, the basic period approach allows different cycle times for different products, however the cycle times must be an integer multiple of a basic period. Although the basic period approach generally produces a better solution to the ELSP than the common cycle approach, but getting a feasible schedule is NP-hard (Bomberger, 1966). Lastly, the time-varying lot size approach is more flexible than the other two approaches, allowing for different lot sizes for the different products in a cycle. Dobson (1987) showed that the time-varying lot size approach always produced a feasible schedule, as well as giving a better quality solution.

In this research, we present the development of a new heuristic using Simulated Annealing (SA) algorithm to solve ELSP. In a series of numerical experimentation with the algorithm we show that the algorithm is robust in its performance and has a faster convergence in comparison with the best known Tabu Search algorithm to the problem. The robustness of SA algorithms is tested using statistical DOE under three distinct performance measures. The SA algorithm is found quite robust in maintaining its optimum performance with respect to its control parameters. The numerical experimentation is also carried out with two well known problems reported in Bomberger, 1966 and Mallya, 1992. SA algorithm is able to find the best known solution to the Bomberger’s (1966) problem, as well as, it enables determination of an alternative solution to Mallya (1992) problem yet producing a quality similar to that of TS algorithm reported in Raza et al. (2006). Furthermore, following an experimental setup presented in Dobson (1987), an extensive computational experimentation is carried out comparing the proposed SA, and the existing algorithms, DH, GA, NSaNSa, View the MathML sourceNSb, and TS. Computational results clearly show that the SA algorithm is able to outperform DH, GA, NSaNSa, View the MathML sourceNSb, as well as be very competitive to the TS algorithm. Furthermore the SA algorithm had a faster convergence than the TS in most test problems. Later, a statistical analysis based on a multiple paired compared is also reported which establishes an evidence that the performance of SA is competitive to TS and also superior to the rest of the heuristic tested in this study. As previously noted, the ELSP has been well researched, though there have been many aspects of the problem related to uncertainty that have not been explored yet. An important aspect of this study was examining the ELSP under certain stochastic circumstances, often observed in a manufacturing environment. Among those to be considered are random demand effects, machine failure and the effect of random production rates. The real time lot scheduling and the parallel machine lot sizing problems would also be further interesting areas to investigate.