A heuristic algorithm for master production schedule generation with finite capacity and sequence dependent setups

Correct formulation of the master production schedule is critically important for the optimization of the management of a production planning and control system. Most of the models described in the literature solve the problem in two separate sequential stages: lot sizing and then sequencing. This often produces an MPS which is not optimized or even not feasible. On the other hand, when the problem is tackled with models based on mixed integer linear programming, then dimensional constraints have to be respected which can limit the field of applications of the model itself. A complete heuristic algorithm is presented in this paper which solves the problem of lot-sizing and sequencing in a single logic stage, together with the results of an extensive series of tests carried out to compare, in different types of production systems, the performances of the proposed heuristic and those of another algorithm taken from literature. The model concerns a single production line situation with relevant setup problems; on this production line component availability constraints are not considered (the model refers to mono-level bill of material products, but it can be applied also to the most critical level in multi-levels production systems).