This paper addresses the identical parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs and uncertain processing times. The evolution of the uncertain parameters is modelled by means of a scenario tree, giving rise to a multistage stochastic mixed-integer program. Fix-and-relax procedures, exploiting the specific structure of the problem, are developed and compared. Computational results on a large set of randomly generated instances show that the gap between the best heuristic solutions and the lower bounds provided by a truncated branch-and-bound never exceeds 3%.
Lot-sizing and scheduling problems have been an area of intensive research activity starting from the seminal paper of Wagner and Whitin (1958). Since then, there have been several contributions aimed at incorporating real-world features (such as backlogging, production capacities, multiple items, multiple machines and multiple stages) into the basic model. We refer the reader to the surveys of Wolsey (1997), Drexel and Kimms (1997), Staggemeier and Clark (2001) and to the recent up-to-date tutorial of Pochet (2001).
Lot-sizing and scheduling problems involving set-ups play a key role in many industries. Whenever a set-up only affects a machine idle time, set-up costs are directly proportional to set-up times in which case schedules optimal with respect to set-up times are also optimal with respect to set-up costs. On the other hand, when set-ups require skilled workforce, set-up costs are typically high while set-up times may be low. See (Allahverdi et al., 1999; Pinedo, 1995) for in-depth reviews on this topic.
While deterministic lot-sizing and scheduling problems have received significant coverage in the literature, their stochastic counterparts have been addressed only recently. See (Sox et al., 1999) for a survey of the current research literature on stochastic lot scheduling problems.
This paper deals with a stochastic version of the lot-sizing and scheduling problem with identical parallel machines and sequence-dependent set-up costs (LSIPMSC) in which processing times are uncertain. In the LSIPMSC problem, a number of identical parallel machines have to manufacture a set of products over a discrete planning horizon. The problem consists of determining the schedule that minimizes the total set-up cost while satisfying the demand of each product over the time horizon. Applications of the LSIPMSC arise in several industrial settings, e.g. in the textile and fiberglass industry (Dearing and Henderson, 1984).
The deterministic LSIPMSC problem, which is NP-hard, is addressed in a number of papers: Clark and Clark (2000), Meyer (2002), Staggemeier et al. (2002) examine the case of heterogeneous machines whereas Beraldi et al. (submitted) studies the case of homogeneous machines. However, to our knowledge, all the efforts have been concentrated on models where input data are assumed deterministically known. This assumption is rather restrictive since in real-world different sources of uncertainty (e.g. processing times, product demands, etc.) may affect lot-sizing and scheduling decisions. As a consequence, the solution provided by a deterministic model where the uncertain parameters are replaced by either mean or worst case estimations may be of little value.
In this paper we use a multistage stochastic programming framework to explicitly deal with uncertain processing times. In the last few decades, stochastic integer programming has been the subject of intense research activity. However, most papers deal with two-stage programs while very few papers address the multi-stage case. See Sen (2003) and the references listed at http://mally.eco.rug.nl/spbib.html, for an updated survey on stochastic programming. Also see (Lulli and Sen, to appear) for a list of references on economic lot-sizing models under uncertainty.
In this paper we present novel optimization-based heuristics for the stochastic LSIPMSC problem, based on the fix and relax framework introduced by Dillenberger et al. (1994) in a deterministic setting. The main idea of this approach is to decompose the original problem into a sequence of subproblems where the requirement of integrality is imposed on a limited number of variables. The remainder of the paper is organized as follows. Section 2 presents a multi-stage stochastic integer programming formulation of the LSIPMSC problem with uncertain processing times. Section 3 is devoted to the presentation of some heuristic strategies. The performance of the fix-and-relax procedures has been numerically tested on a variety of medium and large size problems. The results are reported in Section 4. Finally, conclusions and future research directions follow in Section 5.
In this paper we have proposed a multi-stage stochastic mixed-integer programming formulation of the lot-sizing and scheduling problem with uncertain processing times. In order to generate sub-optimal solutions, we have designed efficient heuristic strategies, based on the idea of decomposing the original problem into a sequence of smaller subproblems. Computational results on a large set of test problems have shown that our approach is able to provide high quality feasible solutions within a short amount of time.
