الگوریتم های اکتشافی برای برنامه ریزی حجم زیادی با کاربرد در صنعت دخانیات

We investigate a production planning problem which appears in many industries. We present an example from the tobacco industry. The basic question is how tasks of different types can be scheduled on machines in lots such that the number of changeovers is minimized. These changeovers occur if two tasks of different types are scheduled in sequence on a machine. We analyze the problem in detail and present heuristics for the single and multiple machine case. We evaluate these heuristics and give recommendations for their application to serial production systems.

The problem we investigate exists in many industries. Let us concentrate on an application we found in a company of the tobacco industry. The company produces different types of cigarettes according to the process whose description is shown in Fig. 1.The process starts with the production of the filter tips and the preparation of the tobacco. To produce the filter tips acetate, filter paper and tip paper are needed. Tobacco preparation requires raw tobacco and generates cut tobacco. Filter tips and cut tobacco are merged with cigarette paper to produce a cigarette. The cigarettes are wrapped and packed over several stages and are sent to the customers. The production of cigarettes is carried out on production lines. The company we investigate currently produces about 20 cigarette types regularly with several production lines belonging to different shops. When a line changes production from one cigarette type to another a changeover activity has to be carried out. Cigarette production is currently organized on three levels. There are two planning levels and a physical one. The planning levels are mid term and short term. For the mid term level production data is provided by a sales forecast system. On the short term level a MRP II system generates production schedules for the different shops. On the physical level several parallel and identical production lines are producing the cigarettes. Mid term decisions relate to the determination of production orders. A production order defines which type of cigarette should be produced in which quantity until which deadline within the next mid term period. These decisions are based on data on expected sales. On the short term level the MRP II system provides data to generate production schedules for the shops from the production orders. A production schedule is defined by the cigarette type it relates to, the lotsize with which it has to be produced, the production line it is assigned to, and the time interval in which production has to take place. The production lines produce the cigarettes according to the production schedules. Decisions are passed from upper levels to lower levels and feedback information flows from lower levels to upper levels. The production planning system and the decision hierarchy are shown in Fig. 2.A major requirement by the management for ‘good’ production schedules is that only a small number of changeovers between the cigarette types to be produced should occur. Although such changeovers can be carried out while a production line is operating, they require additional resources like manpower, which are costly. The goal is to reduce the number of changeovers in order to be able to reduce the number of employees required to perform them. These changeover costs do not depend on the cigarette types involved and can therefore be assumed to be constant. The cigarettes leave the shops at given deadlines in given quantities irrespectively of the production lots. Therefore, the work-in-process inventory holding costs can also be assumed to be constant. The decisions that generate the schedules are carried out by human planners. They are supported by software that checks the feasibility of their decisions. The humans use rules for determining the production schedules, but, so far, make no efforts towards minimizing the number of changeovers. The cigarette company aims at improving the current production planning system following two requirements: 1. It should be possible to update the production schedules whenever this is necessary. This should be done by a rolling horizon planning approach that freezes parts of the schedule while other parts are subject to revision. 2. The total changeover costs in a schedule should be reduced. To fulfill the above requirements the production planning system will be extended by a scheduling system as shown in Fig. 3. In this paper, we concentrate on the model and the algorithms for the scheduling system. The analysis is organized as follows. In Section 2, we introduce the model in detail, discuss complexity issues and review existing results. In Section 3, we present four heuristic algorithms which are evaluated in Section 4. We differ between results for single machine and multiple machine problems. We finish with some conclusions.

Motivated by a production scheduling application from the tobacco industry we investigated the problem of minimizing the number of changeovers with arbitrary number of deadlines, task types and machines. For this general problem no polynomial algorithm exists and only enumerative methods and heuristics can be applied. We presented four heuristics for the one machine case of which two were also applied to the multiple machine case. We performed an empirical analysis and showed that for the one machine problem with the exception of a special case the heuristics with lookahead generate much better solutions than the myopic ones. They have a good mean relative performance based on the optimum and find solutions in a very short time while the calculation of an optimal solution can take several hours. In the case of multiple machines, we presented a new heuristic and compared it with the one currently used by the tobacco company. The empirical analysis showed that the new heuristic generates solutions in a very short time and that the schedules generated are about 30–40% better in terms of changeovers compared with the current scheduling rule. The same percentage of costs for manpower needed to perform the changeovers can now be saved by the company. This new heuristic is suited to fulfill both requirements for the scheduling system as defined in Section 1. In case of changing input for the lotsize scheduling problem the heuristic can generate new schedules in a short time, thus addressing requirement 1. It also delivers a superior solution concerning changeover costs, thus addressing requirement 2. A challenging open question is to find better heuristics and better lower bounds for the multiple machine case.