The paper deals with the multi-level lot sizing and scheduling problem for job shop production in capacitated, dynamic and deterministic cases. Demand is to be fulfilled without backlogging. The multi-level lot sizing and scheduling models of the literature are small bucket problems such as the discrete lot sizing and scheduling problem (DLSP) and the proportional lot sizing and scheduling problem (PLSP). In contrast we develop a big bucket model for multi-product multi-level production. The multi-level general lot sizing and scheduling problem with multiple machines (MLGLSP_MM) is based on the general lot sizing and scheduling problem (GLSP) for single-level production. Our focus is on minimising the sum of sequence dependent setup costs, inventory costs, production costs and the costs of maintaining the setup conditions of the machines. Inventory costs will be calculated exactly. In addition sequence dependent setup times are considered. Finally, our approach minimises the lead-time of semi-finished goods and the throughput time of finished goods.
Lot sizing and scheduling are a part of operative production planning and control (cf. Gutenberg, 1983, p. 147 ff.). In lot sizing a lot indicates the quantity of a product manufactured on a machine continuously without interruption (cf. Gutenberg, 1983, p. 201). The task of scheduling is to determine the production sequence in which the products are manufactured on a machine. Simultaneous lot sizing and scheduling is essential if sequence-dependent setup costs and setup times occur during production.
In practice various models can be used to solve the problem of simultaneous lot sizing and scheduling. These differ with regard to their specific features. Among the characteristic features of the models for lot sizing and scheduling are the segmentation of the planning horizon, the time dependence of the model parameters, the information degree of the model parameters, the number of products and production stages, the production structure and the capacity restrictions (cf. Merecé and Fonton, 2003). The following study is limited to deterministic dynamic models with a finite planning horizon, which consider the production of several different products with a general production structure on different capacitated machines.
For practical purposes models for simultaneous lot sizing and scheduling for multi-product multi-level production must take into account different interdependences. One important interdependence is the relationship between lot sizing and scheduling when sequence-dependent setup costs and times occur. With the goal of minimising costs in lot sizing a lot size is determined which minimises the accruing costs. Among the costs, which are relevant for the decision, are the setup and storage costs (cf. Gutenberg, 1983, p. 194), the production costs, if alternative machines with different production costs are available at a production level, and the costs of maintaining the machines’ setup conditions during standstills. In case of sequence-dependent setup costs the minimal cost lot size determines the sequence in which the products are processed on the machines. On the other hand, if sequence-dependent setup times occur the lot sizes are also dependent on the schedule, because in the case of capacitated production this influences the machine capacity, which is available for production. A further interdependence is created in multi-level production. This interdependence can be divided into a vertical and a horizontal interaction (cf. Tempelmeier and Derstrof, 1993, p. 64). The vertical interaction considers that production on a production level can only begin if a sufficient amount of the product from the previous production level is available. If products from different production levels compete for the limited capacity of a machine this is referred to as level-overlapping resource competition, which describes the horizontal interaction.
Models of lot sizing and scheduling are divided in the literature into small bucket and big bucket problems (cf. Eppen and Martin, 1987, p. 832). Small bucket problems subdivide the finite planning horizon into a large number of shorter periods (cf. Fleischmann, 1990, p. 337, and Drexl and Haase, 1995). With big bucket problems the planning horizon consists of a few longer periods of the same length (cf. Haase, 1996). Small bucket problems for multi-level multi-product production are the multi-level discrete lot sizing and scheduling problem (MLDLSP) (cf. Kimms, 1996) and the multi-level proportional lot sizing and scheduling problem (MLPLSP) (cf. Kimms, 1993; Kimms and Drexl, 1996). Both models enable simultaneous lot sizing and scheduling, but limit the number of products to be manufactured in a period. The multi-level capacitated lot sizing problem (MLCLSP), a big bucket problem, does not have this disadvantage, but it cannot fix lot sizes and schedules simultaneously. In the literature an approach has been made to attempt to unite the advantages of the MLPLSP and the MLCLSP in the multi-level general lot sizing and scheduling problem (MLGLSP) (cf. Stammen and Hegener, 2002, p. 171 ff.), which was created on the basis of the single-level general lot sizing and scheduling problem (GLSP). In this paper we concentrate on the assumptions, the model formulation and the practical applicability of the extended multi-level general lot sizing and scheduling problem with multiple machines (MLGLSP_MM).
