بحث اکتشافی دو مرحله ای برای تعیین اندازه دسته تولید توانا شده ی ماشینی منفرد و برنامه ریزی با هزینه های راه اندازی وابسته به توالی

This paper considers a single machine capacitated lot-sizing and scheduling problem. The problem is to determine the lot sizes and the sequence of lots while satisfying the demand requirements and the machine capacity in each period of a planning horizon. In particular, we consider sequence-dependent setup costs that depend on the type of the lot just completed and on the lot to be processed. The setup state preservation, i.e., the setup state at the end of a period is carried over to the next period, is also considered. The objective is to minimize the sum of setup and inventory holding costs over the planning horizon. Due to the complexity of the problem, we suggest a two-stage heuristic in which an initial solution is obtained and then it is improved using a backward and forward improvement method that incorporates various priority rules to select the items to be moved. Computational tests were done on randomly generated test instances and the results show that the two-stage heuristic outperforms the best existing algorithm significantly. Also, the heuristics with better priority rule combinations were used to solve case instances and much improvement is reported over the conventional method as well as the best existing algorithm.

Lot-sizing and scheduling is to determine the lot sizes and the sequence of lots while satisfying the demand requirements over a planning horizon under certain objective functions. Many researchers and practitioners have been focusing on the problem due to its wide applications, especially to the process industry such as petroleum, steel, paper, and impacts on various system performances. However, most lot-sizing and scheduling problems are known to be very difficult to solve optimally due to their inherent combinatorial complexity. According to Drexl and Kimms (1997), lot-sizing and scheduling problems can be classified into several types. The most representatives are: (a) discrete lot-sizing and scheduling problem (DLSP); (b) proportional lot-sizing and scheduling problem (PLSP); and (c) capacitated lot-sizing and scheduling problem (CLSP). First, the DLSP assumes that at most one item can be produced in each period, i.e., all-or-nothing. Therefore, the length of a period in DLSP is generally much smaller than those in PLSP and CLSP, i.e., macro periods are divided into micro periods. See Fleischmann (1990) for an exact branch and bound algorithm for the DLSP. Second, the PLSP is the problem under the assumption that at most one setup may occur in a period, and hence at most two items can be produced in a period. Finally, the CLSP is a general case that several items can be produced in a period, i.e., a large bucket problem. See Drexl and Kimms, 1997 and Karimi et al., 2003 and Quadt and Kuhn (2008) for relevant literatures on the CLSP and its extensions. This study was originally motivated from a production planning problem occurred in a paper manufacturing system that produces various corrugated cardboards according to raw material types and production methods after collecting waste papers. Since the system is a type of the process industry, the entire system can be regarded as a single machine. Also, the setup costs are dependent on the sequence of lots. Based on these observations, we define the problem as the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup costs. After reviewing previous research on the problem, we find that the best existing heuristic can be improved with more sophisticated improvement methods. The CLSP is the problem of determining the lot sizes and the sequence of lots while satisfying the demand requirements and the machine capacity in each period of a given planning horizon. In general, the CLSP is known to be NP-hard (Bitran and Yanasse, 1982 and Florian et al., 1980). Also, Maes, McClain, and van Wassenhove (1991) reported that even finding a feasible solution for the problem with setup times is NP-complete. As an extension of the ordinary problem, the sequence-dependent setup costs are additionally considered that depend on the type of the lot just completed and on the lot to be processed. Also, we consider the setup state preservation in which the setup state for the last item on some period (pre-period) is carried over to the first item of the next period. See Gopalakrishnan, Ding, Bourjolly, and Mohan (2001) for the reduction in total cost through the setup state preservation. Various studies have been done on lot-sizing and scheduling with sequence-dependent setups. (See Zhu and Wilhelm (2006) and Jans and Degraeve (2008) for literature review on lot-sizing and scheduling with sequence-dependent setups.) Dilts and Ramsing (1989) consider the uncapacitated lot-sizing and scheduling problem with sequence-dependent setup costs, and Dobson (1992) suggest a heuristic algorithm for the static lot-sizing problem with a constant demand per period and sequence-dependent setup costs/times. Fleischmann (1994) consider the DLSP with sequence-dependent setup costs in which at most one item can be produced in each period. Haase (1996) considers the CLSP with sequence-dependent setup costs on a single machine and suggested a heuristic while considering the setup state preservation, and showed that the heuristic outperforms the previous one of Fleischmann (1994). Later, Fleischmann and Meyr (1997) suggest a heuristic algorithm after dividing macro periods into micro periods for the CLSP with sequence-dependent setup costs, but it could not outperform the algorithm of Haase (1996). To cope with more complex system configurations, Kang et al., 1999 and Clark and Clark, 2000, and Marinelli, Nenni, and Sforza (2007) considered parallel machines and Sikora (1996) and Sikora, Chhajed, and Shaw (1996) flow shops. Also, some articles consider the sequence-dependent setup times and costs. See Meyr, 2000, Gupta and Magnusson, 2005, Almada-Lobo et al., 2007 and Kovacs et al., 2009 and Almada-Lobo and James (2010) for examples. As stated earlier, this study considers the single machine CLSP with sequence-dependent setup costs while preserving the setup state between two consecutive time periods. In fact, the problem considered here is the same as that of Haase (1996). To improve the best existing algorithm of Haase (1996), we suggest a two-stage heuristic in which an initial solution is obtained and then it is improved using a backward and forward improvement method with various priority rules to select the items to be moved among periods. Computational experiments were done on a number of test instances and the results are reported. In particular, the heuristics with better priority rule combinations were tested on the case data obtained from a paper manufacturing system and a significant amount of improvement is reported. This paper is organized as follows. In the next section, the problem is briefly described. The two-stage heuristic is explained in Section 3, and the computational results are reported in Section 4. Finally, conclusions and further research directions are discussed in Section 5.

In this paper, we have considered the problem of determining the lot sizes and the sequence of lots on a single machine, called the CLSP in the literature, while satisfying the demand requirements and the machine capacity in each period of a given planning horizon. In particular, sequence-dependent setup costs were additionally considered because the CLSP considered in this study was motivated from a paper manufacturing system in which setup costs, not setup times, are highly dependent on the sequence of lots. Since the problem is proved to NP-hard, we suggested a two-stage heuristic for the objective of minimizing the sum of setup and inventory holding costs over the planning horizon. In the two-stage heuristic, an initial solution is obtained and then it is improved using a new backward and forward method with a set of priority rules to select the items to be moved. Computational results showed that the two-stage heuristic is significantly better than an existing one due to the sophisticated backward and forward improvement method. (The amount of improvement was up to 44.3% in overall average.) In particular, significant improvement was shown over the conventional method for the paper manufacturing system. This research can be extended in several directions. First, it is needed to extend the problem with sequence-dependent setup times. Second, it is worth considering other system configurations, e.g., serial and parallel machines.