برنامه ریزی زیاد اقتصادی چرخه مشترک در تولید کارگاهی انعطاف پذیر: در مورد افق محدود

This paper addresses the common cycle multi-product lot-scheduling problem in deterministic flexible job shops where the planning horizon is finite and fixed by management. This problem consists of a combinatorial part (machine assignment and sequencing sub-problems) and a continuous part (lot-sizing and -scheduling sub-problems). To account for these two elements, a new mixed integer nonlinear program (MINLP) is developed which simultaneously determines machine allocation, sequencing, lot-sizing and -scheduling decisions. In order to reduce computational complexity, instead of solving this MINLP directly, we propose an efficient enumeration method to determine optimal solution for this model. The performance of the proposed method is evaluated by some numerical experiments. Two other applicable cases (zero setup costs and lot streaming) are also studied and required modifications in the model formulation and the solution procedure are described. Moreover, a numerical example is presented to illustrate applicability of the proposed mathematical model and the solution method.

A flexible job shop (FJS) is one of the most usual production systems in manufacturing discrete parts that can be considered as an extension of two classical systems, namely the job shop and parallel shop. This production facility involves several work centers (production stages) where each stage has one or more parallel identical machines. Each product requires a sequence of operations in different stages based on its unique process route, and must be processed by at most one machine at each stage, but some products may skip some stages. In this paper, we consider the production scheduling problem in such systems where all parameters (such as demand rates) are deterministic and constant over a given finite planning horizon. This problem is common in supply chain environments, where a supplier produces multiple products in a flexible job shop for an assembly facility. In such cases, the product demand rates are deterministic and fairly constant based on contract between supplier and assembler and supplier's production capacity. Moreover, delivery of each finished product to assembler is continuous with fixed rate per time unit. An example for this situation is a large assembly facility such as an automotive assembly plant (customer) and its immediate suppliers. The most of the contributions reported in the literature dealing with static demand lot-sizing and -scheduling problems, have focused on particular policies, the cyclic schedules. In a cyclic schedule, i.e., a schedule that is repeated periodically, one of the following approaches is adopted: • The common (or rotation) cycle approach that restricts all of the product's cycle times to an equal length. This approach has the main advantage of always finding a feasible schedule if one exists. Moreover, it has other advantages such as: ease of implementation in practice, simplify the modeling, and obtaining near-optimal solution in many practical cases (Jones and Inman, 1989). Because of these advantages, researchers and practitioners often use this approach to obtain a cyclic schedule (see for example: Carreno, 1990; Dobson and Yano, 1994; El-Najdawi and Kleindorfer, 1993; Fatemi Ghomi and Torabi, 2002; Galvin and Van Deusen, 1988; Giri and Moon, 2004; Hsu and El-Najdawi, 1990; Ouenniche and Boctor, 1998 and Ouenniche and Boctor, 1999; Pesenti and Ukovich, 2003; Ware and Keown, 1987). • The basic period approach that allows different cycle times for different products, but restricts each product's cycle time to be an integer multiple of a time period called a basic period. Under this approach, it is NP-hard to find a feasible schedule, given the number of production runs per global cycle (i.e., the least common multiple of individual cycle times) for each product. This is the main disadvantage of basic period approach, but in general it gives better solutions than the common cycle approach (Ouenniche and Bertrand, 2001; Ouenniche and Boctor, 2001). • The time varying lot sizes approach that allows multiple runs for each product at each cycle with different lot sizes over a cyclic schedule, and always gives a feasible schedule if one exists. Modeling a problem with this approach is more complicated than the other approaches, but usually gives better solutions (Moon et al., 2002; Zipkin, 1991). However, in this paper we have adopted the common cycle approach because of its various advantages to the problem. This assumption allows constructing production schedules that are easy to implement and generally preferred in real-life situations (Ouenniche and Boctor, 1998). Moreover, according to contract between supplier and assembler, we assume that planning horizon is finite and fixed by management. It is noted that in the most of previous contributions on economic lot scheduling, planning horizon is assumed to be infinite. There are several reasons for this assumption. First, constructing a mathematical model for infinite case is easier. Further, this assumption makes feasible solution space larger and consequently may lead to better solutions. However, this assumption considerably reduces the usefulness of the proposed contributions, because in practice, planning horizons are always finite and rarely longer than 12 months. Further, in most cases, the schedules obtained by infinite horizon assumption could not be repeated an integer number of times during the finite planning horizon chosen in practice. Thus practitioners usually adjust such schedules to meet this condition, which may lead to a nonnegligible increase in the total cost (Ouenniche and Boctor, 1998). Literature review in economic lot-scheduling problems reveals that the most of contributions are related to infinite planning horizon case at the single-stage systems with only one machine (Giri and Moon, 2004; Moon et al., 2002; Zipkin, 1991), the single-stage systems with parallel identical or nonidentical machines (Bollapragada and Rao, 1999; Carreno, 1990; Pesenti and Ukovich, 2003), and the flow shop systems (Dobson and Yano, 1994; El-Najdawi and Kleindorfer, 1993; Fatemi Ghomi and Torabi, 2002; Hsu and El-Najdawi, 1990; Ouenniche and Boctor, 1999 and Ouenniche and Boctor, 2001). Moreover, in the finite horizon case there are only two contributions from Ouenniche and Boctor (1998) and Ouenniche and Bertrand (2001). In these works, the production scheduling problem in job shops is studied under constant demand rates over a finite planning horizon length either using the common cycle approach (Ouenniche and Boctor, 1998) or the multiple cycle approach (Ouenniche and Bertrand, 2001), to obtain a cyclic schedule. They have developed an optimal solution method in common cycle case and an efficient heuristic method to obtain a near-optimal solution in multiple cycle case. However, to the author's best knowledge, there is no contribution for economic lot-scheduling problem in flexible job shops under constant demand rates over a finite planning horizon. Thus, in this paper, a new mathematical model and efficient solution method is developed for the finite horizon economic lot-scheduling problem in flexible job shops. It is noted that the classical job shop problem has attracted the attention of many researchers. This problem consists of determining the production sequences and the starting times for a given set of nonsplittable jobs to optimize an objective function such as minimization of the makespan (Adams et al., 1988; Van Laarhoven et al., 1992) or tardiness minimization (Baker, 1984). This problem is quite different from the problem considered here because the classical job shop problem does not deal with machine assignment and lot-sizing issues. The outline of this paper is as follows. In Section 2, problem description as well as notations used for the problem formulation is presented. In Section 3, a mathematical model for the problem is developed and in Section 4, an optimal solution method is presented. Numerical experiments are presented in Section 5. Two other applicable cases of original problem (zero setup costs and lot streaming) as well as required modifications in the model formulation and the solution method are studied in Section 6. Finally, Section 7 is devoted to conclusions and some recommendations for future studies.

In this paper, we have considered the common cycle approach to solve the economic lot-sizing and -scheduling problem in deterministic flexible job shops. First, we developed a new mixed zero-one nonlinear model to solve the problem to optimality. Then, to avoid solving this complex mixed nonlinear program directly, we have suggested an efficient enumeration method to determine an optimal solution. With some numerical experiments it is shown that the proposed solution method is suitable for small- and moderately medium-size problems. Two other applicable cases of Problem P (zero setup costs and lot streaming) are also presented and required modifications in the model formulation and the solution procedure for these cases are described. Moreover, through a numerical example, applicability of this formulation and its solution method is shown. However, applying the proposed solution method to determine optimal solution in medium- and large-size problems requires solving several large-scale mixed zero–one programs that need high computational efforts. Therefore, further research to develop efficient heuristic methods is on our research line. Moreover, there are other different directions for future studies. Among them, the following topics are recommended: • Modeling Problem P using the basic period (multi-cyclic) or time-varying lot size approaches, • Considering nonidentical parallel machines at each stage, • Allowing the backlogging.