تعیین اندازه دسته تولید و زمان بندی وابسته به توالی هزینه های راه اندازی و زمانها و فرصت های تغییر زمان کارآمد

This paper deals with lot sizing and scheduling for a single-stage, single-machine production system where setup costs and times are sequence dependent. A large-bucket mixed integer programming (MIP) model is formulated which considers only efficient sequences. A tailor-made enumeration method of the branch-and-bound type solves problem instances optimally and efficiently. The size of solvable cases ranges from 3 items and 15 periods to 10 items and 3 periods. Furthermore, it will become clear that rescheduling can neatly be done.

For many production facilities the expenditures for the setups of a machine depend on the sequence in which different items are scheduled on the machine. Especially when a machine produces items of different family types setups between items of different families are substantially more costly and time consuming than setups between items of the same family. In such a case a just-in-time philosophy will cause frequent setups, i.e. large total setup costs and long total setup times. To reduce the expenditures for the setups items may be produced in lots which satisfy the demand of several periods. The amount of a production quantity in a period which will be used to satisfy demand in later periods must then be held in inventory. This incurs holding costs. Therefore, we have to compute a schedule in which the sum of setup and holding costs is minimized. In the case of sequence-dependent setup costs the calculation of the setup costs requires the computation of the sequence in which items are scheduled, i.e. we have to consider sequencing and lot sizing simultaneously. Despite its relevance only little research has been done in the area of lot sizing and scheduling with sequence-dependent setups. Some papers have been published which are related to the so-called discrete lot sizing and scheduling problem [4], denoted as DLSP. In the DLSP the planning horizon is divided into a large number of small periods (e.g. hours, shifts, or days). Furthermore, it is assumed that the production process always runs full periods without changeover and the setup state is not preserved over idle time. Such an “all-or-nothing” policy implies that at most one item will be produced per period. In [1] a DLSP-like model with sequence-dependent setup costs was considered first. For the DLSP with sequence-dependent setup costs (DLSPSD) an exact algorithm is presented in [2]. There the DLSPSD is transformed into a traveling salesman problem with time windows which is then used to derive lower bounds as well as heuristic solutions. An exact solution method for the DLSP with sequence-dependent setup costs and times (DLSPSDCT) is proposed in [3]. The optimal enumeration method proposed by [4] is based on the so-called batch sequencing problem (BSP). It can be shown that the BSP is equivalent to the DLSPSDCT for a restricted class of instances. The solution methods for the DLSPSDCT and the BSP require large working spaces, e.g. for instances with six items and five demands per item a working space of 20 megabytes is required. Recently, another new type of model has been published which is called the proportional lot sizing and scheduling problem (PLSP) [5]. The PLSP is based on the assumption that at most one setup may occur within a period. Hence, at most two items are producible per period. It differs from the DLSP regarding the possibility to compute continuous lot sizes and to preserve the setup state over idle time. A regret-based sampling method is proposed to consider sequence-dependent setup costs and times. In [6] an uncapacitated lot-sizing problem with sequence-dependent setup costs is considered. A heuristic for a static, i.e. constant demand per period, lot-scheduling problem with sequence-dependent setup costs and times is introduced in [7]. In [8] the so-called capacitated lot-sizing problem with sequence-dependent setup costs (CLSD) is presented. As in the PLSP, the setup state can be preserved over idle time. But in contrast to the DLSP and PLSP many items are producible per period. Hence, the DLSP and PLSP are called small-bucket problems and the CLSD is a large-bucket problem. For a review of lot-sizing and scheduling models we refer to [5]. A large-bucket problem with sequence-dependent setup costs and times is not considered in the literature so far. In this paper we will close this gap. The text is organized as follows: in the next section we briefly describe the practical background that inspired our work on this subject. In Section 3, we give a mathematical formulation of the problem under concern. Afterwards, rescheduling is discussed in Section 4. In Section 5, an optimal enumeration method is outlined. The efficiency of the algorithm is tested by a computational study in Section 6.

In this paper we proposed a model for lot sizing and scheduling with sequence-dependent setups which was inspired from a practical case at Linotype-Hell AG. The key element for the efficiency of the method is based on an idea derived from problem specific insights. Roughly speaking, this idea is that if we know what items to produce in a period but we do not know the lot sizes yet, we can nevertheless determine the sequence in which these items are to be scheduled. In contrast to other approaches which suffer from large memory requests, the presented procedure requires modest capacities. This is mainly due to a novel idea for computing lower bounds to prune the search tree. Memorizing partial schedules seems to be avoidable now. Beside the low memory space usage, the lower bounding technique amazes with high speed-ups. The size of the instances that are solved is of practical relevance as it is proven by case studies in [2] (food industry) and [9] (discrete part manufacturing) where instances with less than 10 items occur.