مشکل تعیین اندازه دسته تولید و زمان بندی با تاخیر-زودرسی و جریمه های راه اندازی

We consider the problem of determining the production lot sizes and their schedules so that the sum of setup cost, holding cost, and tardy cost is minimized. There are n orders waiting to be processed. Each order has its own due date, earliness penalty and tardiness penalty. The production is done in lots, which is the manufacturing of the same product continuously. No early delivery is allowed. Each order is delivered once, on the due date or immediately after the production of the order is completed. We present an algorithm, based on the use of the assignment problem, to optimally solve the problem with zero setup cost. For the problem with setup cost, the Backward Search algorithm is proposed to solve the small size problem. To deal with the large size problem, two heuristics which are Sequencing with Optimal Timing and Genetic Algorithm are presented.

Production planning and scheduling is one of the most challenging tasks facing managers today. For companies involved in batch or lot production (for example, plastic injection, steel, or chemical production), planning production lot sizes for the finished products and deciding when to process them are two important problems requiring careful analysis in the production planning and scheduling. These can be termed the lot-sizing and scheduling problem. There are several lot-sizing and scheduling models being evolved for different situations. In traditional lot-sizing and scheduling models, the production lot sizes and their schedules should be made in such a way that demand is satisfied on time (no backorders) and the sum of total setup costs and total holding costs are minimized. Surveys of various lot-sizing and scheduling models can be found in the works of Bahl et al., 1987 and Drexl and Kimms, 1997. In the last decade, significant research involving scheduling problems under the Just-In-Time (JIT) philosophy has been conducted. With the JIT concept, customers are unwilling to receive early or tardy shipments. The most common scheduling objective is to minimize the deviation of job completion times around their due dates. A well known scheduling model involving the JIT concept is the earliness tardiness (E/T) scheduling problem. The objective is to determine the job schedule in order to minimize the sum of earliness and tardiness penalties. In the general E/T problem, the lot-sizing decision is not considered. A comprehensive review of E/T scheduling was provided by Baker and Scudder (1990). The problem considered in this paper is to relax the assumption of no backorders and apply the concept of E/T problem to the lot-sizing and scheduling problem. This problem will be called the earliness tardiness lot-sizing and scheduling (ETLS) problem. Simply stated, the ETLS is the problem of determining the production lot sizes and deciding their schedules such that the sum of setup cost, holding cost and tardy cost is minimized. Similar to other lot-sizing and scheduling problems, the model assumes that delivery for each order (demand) is done only once. If the order is completed before or on its due date, it will be delivered on the due date. Otherwise, the order will be delivered immediately after its production is completed. The concept of discrete lot-sizing and scheduling problem (DLSP) along with the chemical batch scheduling will be applied to construct the ETLS model. According to Hoesel and Kolen (1994), the DLSP problem which assumes a discrete time period, time varying demand, and finite planning horizon, is a suitable model for the short term or the operational level. The DLSP was first studied by Lasdon and Terjung (1971) with an application to production scheduling in a tire company. Complexity results for several types of DLSP were examined by Salomon et al., 1991 and Bruggemann and Jahnke, 1997. Fleischmann (1990) presented a branch and bound procedure, using Lagrangean Relaxation for determining both lower bounds and feasible solutions, for solving the DLSP with sequence independent setup costs. Cattrysse, Salomon, Kuik, and Wassenhove (1993) extended the work of Fleischmann (1990) by including setup times. Both setup costs and setup times were sequence independent. In each period the machine is either in setup or in production for at most one item, or the machine is idle. The authors presented a heuristic based on dual ascent and column generation techniques for solving the problem. Fleishmann (1994) discussed the DLSP with sequence dependent setup costs. However, setup times were not included in the model. The authors presented a solution procedure based on the equivalence of the DLSP and a traveling salesman problem with time windows (TSPTW). Jordan and Drexl (1998) studied the DLSP with sequence dependent setup times and sequence dependent setup costs. They showed the equivalence between the DLSP and the batch sequencing problem (BSP). The authors proposed a branch and bound algorithm which is accelerated by bounding and dominance rules to solve the BSP model. Recently, the earliness and tardiness penalties in the batching and scheduling problem are discussed in batch chemical scheduling. Dessouky, Kijowski, and Verma (1999) studied the tradeoff between the earliness and tardiness penalties for a single-stage chemical processing environment with fixed batch sizes, sequence-independent setup times, and identical processing times. They presented a heuristic based on the transportation problem and assignment problem to solve the problem. The same problem but with sequence dependent setup costs was discussed by McGraw and Dessouky (2001).

The Earliness Tardiness Lot-sizing and Scheduling problem was discussed. Unlike other lot-sizing and scheduling problems, the ETLS problem allows any order to be tardy. The problem objective is to determine the size and the schedule of each production lot such that the sum of the setup cost, holding cost, and tardy cost is minimized. The Clustering and Assigning algorithm was proposed to solve the problem with zero setup cost optimally. For the problem with setup cost, the Backward Search algorithm was presented to solve the small size problem. In order to solve the large size problem, two heuristics were presented. In the first heuristic, Sequencing with Optimal Timing, only the permutation of real batches are considered. The optimal timing algorithm is applied in this heuristic to assign the position of each batch in a given sequence. Another heuristic proposed to solve the large size problem is the Genetic Algorithm heuristic. From the experimental results, when the ratio of setup cost rate/holding cost rate is increased, the performance of the CA will be decreased. On the other hand, when the ratio of the tardy cost rate/holding cost rate is decreased, the performance of the SOT heuristic is decreased. In addition to the evaluation of the performance of the individual heuristic, the performance of the GA heuristic was compared to the SOT heuristic at different problem sizes (Factor A), ratios of tardy cost rate/holding cost rate (Factor B), and ratios of setup cost rate/holding cost rate (Factor C). The results show that the main effects of factors A and B are significant on the percentage deviation of the two heuristics.