تعیین اندازه دسته تولید و بهینه سازی توالی در یک کارخانه تغذیه حیوانی

This paper studies a challenging case of joint lot sizing and scheduling in a manufacturing plant for animal feed compounds. A key characteristic of this industry is that certain products can perform a production line “cleaning” function if a sufficiently large lot is produced between two products that would otherwise require a cleaning setup. Thus the sequence-dependent setup times do not always obey the triangular inequality. A mixed integer programming model is applied and tested on multiple sets of real data from different seasons. The model takes too long to solve exactly and so alternative formulations and methods are developed to solve the model more quickly, based on two variants of the Relax and Fix heuristic. Test results demonstrate that the formulations are computationally effective and able to take economic advantage of the intermediate cleaning products. The model schedule substantially improves on that practiced at the plant and can be useful for similar companies in the animal-feed industry.

In a manufacturing system, many products often share valuable capacity which is wasted and not used productively when setting up (changing over) from one product to another. Although automation and process engineering has often reduced the magnitude of setups, a large number of companies still face substantial production setup costs and times within an increasing range of products, with consequent losses of production capacity and missed deadlines if setups are not well managed and controlled. Weak performance in this area generally results in backlogs of unmet demand, customer dissatisfaction and loss of company competitiveness. While many production lots or batches correspond to specific orders and so have a predetermined size, a product or part may instead feed into many small distinct orders with different deadlines. In such a situation, it makes sense to relate the product or part’s lot sizes to its total demand aggregated from the different orders. In other words, the problem becomes one of simultaneous scheduling and sizing of production lots or batches, based on forecasts of product orders and demand, often under limited production capacity (Askin & Standridge, 1993). This paper investigates such a challenge at Anifeed, a Brazilian animal feed compound company (whose real name has been altered to protect its identity). Two mixed integer programming (MIP) models for joint lot sizing and scheduling with sequence-dependent setup times are applied, taking into account that the setup times, like those in many feed plants, do not always obey the triangular inequality. The first model sequences each period independently of the others. The second model sequences all periods simultaneously, taking into account the linking setup states between periods. Tests on Anifeed data indicate that in general neither model can be solved optimally within an hour’s computing time. In particular, the incumbent solution after an hour is poor for the second model so several alternative formulations and methods are developed to accelerate the solution time, making use of Relax and Fix methods (Wolsey, 1998) on the integer lot sizes or binary setup variables over time. Computational tests show that the Relax and Fix acceleration is effective while maintaining quality. The solutions show that the second model is able to take advantage of the cleaning function that certain intermediate products can perform if a sufficiently large lot is produced between two products that would otherwise require a cleaning setup. The model’s schedules showed a very marked improvement over the schedules implemented at Anifeed. Randomly generated and perturbed data was then used to better evaluate the models and methods through experimental tests. The rest of this section describes Anifeed’s production process and its scheduling context. Section 2 reviews previous research while Section 3 proposes and explains the two optimisation models. Section 4 develops alternative solutions methods which are then tested and analysed in Section 5 and compared to Anifeed’s practice in Section 6. Finally Section 7 concludes and points out future directions for research.

This paper applied two mixed integer programming models for joint lot sizing and scheduling, motivated by an animal-feed plant where the sequence-dependent setup times were non-triangular. One model treats each period as having an independent sequence of lots, suitable for when the production line is cleaned between periods. A second model addresses the case when there is no time for cleaning between periods so that the periods’ sequences are linked and thus dependent on each other. Tested on data from the Anifeed plant, the models take too long to solve exactly. Several alternative formulations and methods were explored to solve the Dependent Sequences model more quickly so as to make it viable for operational use. The method that seems most promising is Relax and Fix on the integer lot sizes qisqis. The results confirm that the models are able to take advantage of the ”cleaning” function that certain intermediate product families can perform if a sufficiently large lot is produced between two families that would otherwise require a non-trivial setup. The model solution is a clear improvement on that practiced at the feed plant, but further testing of the RF on qisqis and other methods to properly compare them with Anifeed’s practice, particularly on the basis of rolling horizon usage. A continuing challenge is to develop both exact and approximate solution approaches that are much faster and yet obtain near-optimal solutions. To this end, the authors are considering the following research directions: (i) further development of relax-and-fix based heuristics for lot sizing and sequencing (Clark, 2003), including their application to overlapping periods (Almada-Lobo, Klabjan, Oliveira, & Carravilla, 2007); (ii) lot sequencing methods based on the Asymmetric Travelling Salesman problem (ATSP) methods that very efficiently solve a series of Assignment Problems with sub-tour elimination constraints (Lawler, Lenstra, Rinnoy Kan, & Shmoys, 1985); and (iii) alternative optimisation approaches based on modern metaheuristics such as memetic algorithms (Hart et al., 2005, Krasnogor and Smith, 2005 and Toledo et al., 2008).