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.
The dynamic lot sizing (DLS) model is one of the most frequently used models in production and inventory system. If the demand for every period in n periods is known, the DLS model is used to determine the optimal lot size. The objective is to keep production and holding costs to a minimum ( Federgruen & Tzur, 1991). Wagelmans, Hoesel and Kolen (1992) also pointed out that when the production structure is more complicated, it is essential for MRP software to construct an efficient solution to solve the DLS model. Their arguments can be extended to a modern computerized production system such as Manufacturing Resource Planning (MRP II) ( Kim & Hosni, 1998) and Enterprise Resources Planning (ERP) ( Chung & Synder, 2000). However, under certain special structures, DLS problems are classified as NP-hard problems.
In general, there are two approaches to solve the DLS problems: optimum solution methods and heuristic methods. A heuristic method, such as part-period balancing, applies single stage lot sizing sequentially to acquire the solution without considering the dependence during processing (e.g. Choo & Chan, 1989). The heuristic methods cannot reach optimum but require less computer resources. The optimum solution approach, on the other hand, is applied when calculation resources are abundant or when the lot decisions can affect the cost structure tremendously. At least three different kinds of methods (dynamic planning, integer planning, and branch and bound methods) have been proposed during the past few years (such as Afentakis et al., 1984, Aggarwal and Park, 1993 and Bitran et al., 1984). However, all of these methods require enormous calculation time for even a modest problem. Many researchers (e.g. Saydam and McKnew, 1987 and Evans et al., 1989) have therefore proposed algorithms to save computer memory or to reduce CPU time.
The availability of cost-effective parallel computers means the potential for using distributed computing power to solve mathematical programming problems faster and the ability to solve larger problems. Some previous studies (such as Lyu et al., 1995 and Romeijn and Smith, 1999) have found inspiring results in this area. Despite the availability of numerous software tools for the distributed computing environment, it remains very difficult to convert a conventional application into a parallel application. To develop a parallel algorithm for the lot sizing problem is not easy due to the communication complexity between processors, which often becomes a bottleneck during the execution process. To our knowledge, there is no published research in exploiting the parallelism of a DLS algorithm so far.
The main objective of this paper is to present a parallel algorithm for solving the DLS problem. The proposed algorithm is implemented in a portable distributed computing environment for empirical experiments. We will demonstrate the efficiency of this algorithm by showing its complexity analysis and experimental results.
This study developed a parallel DLS algorithm on workstation clusters and evaluated its performance. The complexity of the proposed algorithm is O(n3) for the sequential version and is O(n2p) for the parallel version, where p is the number of processors. Numerical results for this algorithm are consistent with the analytical analysis, which suggests the speedup of this algorithm approaches linearity. The presented algorithm appears efficient and becomes a useful solution model for the DLS problem.
As the Internet is becoming widely embraced, a distributed computing environment is becoming common in industry today. While setting up a PVM, learning how to master parallel algorithms is not an easy task, this study shows that the development of parallel methods in the production control discipline is feasible and practical. For an industrial engineer interested in computer applications, research into the procedures for designing an efficient parallel algorithm is becoming vital. The authors are currently extending their efforts into the study of other areas of the MRP system.
