برنامه ریزی تولید و برنامه ریزی در صنعت ظروف شیشه ای: یک رویکرد VNS

Inspired by a case study, this paper reports a successful application of VNS to the production planning and scheduling problem that arises in the glass container industry. This is a multi-facility production system, where each facility has a set of furnaces where the glass paste is produced in order to meet the demand, being afterwards distributed to a set of parallel molding machines. Since the neighborhoods used are not nested, they are not ordered by increasing sizes, but by means of a new empirical measure to assess the distance between any two solutions. Neighborhood sizes decrease significantly throughout the search thus suggesting the use of a scheme in which efficiency is placed over effectiveness in a first step, and the opposite in a second step. We test this variant as well as other two with a real-world problem instance from our case study.

Inspired by a case study, a variant of the variable neighborhood search (VNS) is introduced to tackle the production planning (especially lotsizing) and scheduling problem (PPS) that arises at the long-term planning level of the glass container industry. A typical company has several plants equipped with furnaces. Each furnace distributes glass to a set of parallel molding machines. The production planning main constraint is the color of glass melted in the furnace. The goal is to define a 12 month rolling horizon plan that assigns colors to furnaces, schedules color campaigns within each furnace, and assigns products to machines monthly. Due to the very high sequence dependent setup times in color changeovers, color campaigns lotsizing and scheduling have to be done simultaneously. Furthermore, products cannot be aggregated into families, thus increasing the complexity of the problem. Only major setups (multiple family joint setups) are considered, i.e., changeovers between two products sharing the same color are disregarded. The review (Karimi et al., 2003) pinpoints the scarce literature devoted to lotsizing and scheduling problems with family joint setups, regarded as an interesting research area to develop heuristics. (Schaller, 2007) considers the problem of scheduling on a single machine when family setup times exist, but the author does not deal with lotsizing. Many real-world production planning problems are combinatory and multi-objective by nature. Modeling even simplified abstractions of those problems often leads to untractable NP-hard problems (see, for instance, (Bouchriha et al., 2007) for the capacitated lotsizing problem (CLSP) that appears on a paper machine). Consequently, several heuristic procedures have been proposed over the years to solve large scale instances. Local search (or neighborhood search) heuristics are improvement algorithms that start with an initial solution and try to find iteratively better solutions in the neighborhood of the incumbent solution. Naturally, both their effectiveness and efficiency are closely related to the neighborhood structures used. Several frameworks have been developed to improve the performance of local search heuristics, avoiding the entrapment in local optima through different search schemes that cross barriers in the solution space typology. VNS is a recent local search based approach that makes use of systematic changes of the neighborhood structure during the search (Hansen and Mladenovic, 2001). Throughout the search, neighborhood sizes decrease significantly, thus suggesting the use of a scheme in which efficiency is placed over effectiveness in a first step, and the opposite in a second step. We make use of a new empirical measure to assess the distance between two solutions that allows us to order different neighborhoods. This new VNS scheme combines features of other two, to obtain a compromise between efficiency and effectiveness. In Section 2 we first present the glass container production system and the production planning and scheduling problem that arises at a tactical level. We then propose an exact formulation of this problem. In Section 3 we explain the solution approach to tackle this problem. Numerical experiments are given in Section 4. The paper ends with a short summary and outlook.

Our work is motivated by the production planning and scheduling problem faced by a large glass container company at the long-term planning level. It is a complex problem, in which the scheduling of color campaigns on furnaces and the loading of products on machines are done simultaneously. Since color campaigns may be merged (to tackle the machine balancing constraints), neighborhood sizes decrease significantly throughout the search. Therefore, it seems reasonable to speed up the search whilst it is possible to achieve better solutions without a big effort, and to search thoroughly afterwards. The approach proposed in this work turns out to be a compromise between RVNS efficiency and VNS effectiveness through computational tests performed on a real-life instance. The sequencing of neighborhoods through a new distance function proved to be an effective approach, improving the performance of VNS variants. More work is desirable to assess this distance function in other production planning and scheduling environments and the new VNS variant in other type of problems.