Integrated lot-sizing and scheduling with overlapping for multi-level capacitated production system

摘要

In this paper, multi-product multi-period integrated lot-sizing and scheduling problem with a new practical condition, overlapping in operations, is discussed in a capacitated multi-stage production system. In many real situations, products are carried using pallets or conveyers, so there is no constraint to complete the entire process of products lots and then transfer them to the next stage. To consider this issue in the problem an approach, named overlapping in operations, is developed in this paper. For each product, embedded operations on the two consecutive machines can be performed due to overlapping consideration in which each operation of certain product may be overlapped with the another operation of the same product on the next machine. A novel mixed-integer programming (MIP) model is proposed for the problem to minimise the maximum makespan over the planning horizon for the corresponding production plan. The mathematical model is impractical to solve large-scale problems in reasonable time. So, two MIP-based heuristics using reduced size MIP models and simulated annealing algorithm is proposed to solve non-small instances of the problem. Moreover, a MIP method is used to validate the proposed solution approaches. The presented algorithms explore the solution space for both lot-sizing and scheduling problems. A combination of production plan and sequence that is feasible and close to optimum can be found using these algorithms. Computational experiences show that the proposed algorithms can find good quality solution for the problem in a reasonable time. The computational experiences also confirm that the makespan measure and machines utilisation rate can be improved by overlapping consideration.