مدل MIP کارآمد برای مشکل برنامه ریزی تعیین اندازه دسته تولید ایجادشده با تنظیمات وابسته به توالی

This paper presents a novel mathematical programming approach to the single-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times and setup costs. The approach is partly based on the earlier work of Haase and Kimms [2000. Lot sizing and scheduling with sequence-dependent setup costs and times and efficient rescheduling opportunities. International Journal of Production Economics 66(2), 159–169] which determines during pre-processing all item sequences that can appear in given time periods in optimal solutions. We introduce a new mixed-integer programming model in which binary variables indicate whether individual items are produced in a period, and parameters for this program are generated by a heuristic procedure in order to establish a tight formulation. Our model allows us to solve in reasonable time instances where the product of the number of items and number of time periods is at most 60–70. Compared to known optimal solution methods, it solves significantly larger problems, often with orders of magnitude speedup.

This paper considers the lot-sizing and scheduling problem involving production of multiple items on a single finite capacity machine with sequence-dependent setup costs and setup times. In this problem, the decision maker must decide which items to produce in which periods, and must specify the exact production sequence and production quantities to satisfy deterministic dynamic demand over multiple periods that span a planning horizon, in order to minimise the sum of setup and inventory holding costs. The consideration of capacity limitations, significant sequence-dependent setup costs and non-zero setup times exacerbates the inherent difficulty in solving lot-sizing and scheduling problems and restricts the problem size that can be tackled in reasonable time. Ignoring these features when planning production aggravates costs and reduces productivity, particularly in process industries such as chemicals, drugs and pharmaceuticals, pulp and paper, food and beverage, textiles, or ceramics. Other examples include discrete manufacturing in industries such as aerospace, defense and automotive. All such manufacturers could benefit significantly from progress in this research area. Recent work by Haase and Kimms (2000) proposes an exact optimisation approach to the problem. Their approach is based upon a mixed-integer programming (MIP) formulation. They start by generating all possible efficient sequences of items, and then use binary variables in the MIP to denote whether a sequence is selected for a given time period. However, the applicability of their approach is limited to either a small number of items or a short planning horizon. In this paper, we present an alternative model, which also uses pre-generated efficient sequences, but employs binary variables to indicate whether or not an item is produced in a given period. This yields smaller models, but makes it harder to express constraints on the setup costs. A naive formulation of these constraints gives loose LP relaxations, and hence an inefficient model. We then develop a heuristic algorithm which generates much tighter constraints. We show experimentally that the proposed MIP model outperforms all previously known optimisation approaches to the capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setups. It gives up to two orders of magnitude speedup in solution time over the Haase and Kimms model, and can solve larger instances. We also show that the efficient sequences can be generated more effectively, and that the same underlying model can be applied to a number of variants of the problem with similar time performance. The practical implications of these are significant. The paper is organised as follows. In Section 2 we define the CLSP with sequence-dependent setups. Section 3 summarises previous work on this problem. In Section 4, we present an efficient dynamic program (DP) for generating the set of item sequences that might be applied in time periods in optimal solutions. Afterwards, we define a new MIP formulation of the problem (Section 5), and evaluate its performance on a set of randomly generated problem instances (Section 6). Finally, conclusions are drawn and directions of future research are outlined

This paper addressed the capacitated lot-sizing and scheduling problem with sequence-dependent setup times and costs (CLSPSD). We showed that the complexity of this large-bucket lot-sizing problem originates from the series of implicit sequencing problems that have to be solved for the items produced in each time period. We presented an efficient algorithm for determining during pre-processing all item sequences that could appear in an optimal solution. We introduced a novel MIP formulation of CLSPSD that relies on a compact representation of those sequences by using item-related binary variables. To ensure the MIP is correct, we added constraints which bound from below the setup costs for each time period, based on the efficient sequences, and we presented a heuristic algorithm for generating coefficients of these constraints which give tight LP relaxations. Given these new constraints and the compact model, the proposed MIP outperforms all previously known optimisation approaches: it solves problems with orders of magnitude speedup, and can solve instances of industrially relevant size. As one may expect, the stochastic variant of this problem is much more complex, but has still attracted attention in the literature due to its importance from both theoretical and practical points of view (see Kämpf and Köchel, 2006). Our future work will focus on extending these results to the stochastic version of the same problem, where demands are described by (not necessarily independent) random variables with known probability density functions. Departing from the MIP proposed in this paper, we defined a stochastic program in the Stochastic OPL Language (Tarim et al., 2006). Currently, we are experimenting with solving this stochastic program for instances with different sizes and characteristics, using different scenario reduction techniques. Our aim is to extend the applicability of this approach to realistic problem sizes.