Master production schedule generation in a multi-item single-machine capacited manufacturing system with sequence dependent setup times and costs

In this paper we address the problem of generating the Master Production Schedule in a Multi-Item Single- Machine Capacited manufacturing system, with sequence-dependent setup times and costs. For each time bucket in the MPS, deliveries of finite products are defined in terms of due dates and quantities to be shipped. Production capacity is finite, though it is possible to exploit a limited extra-capacity on the basis of availability of work-force overtime, which anyway implies additional production costs. Backlogging is not allowed, while a maximum earliness for each job is defined for each product. In the proposed approach, two sub-problems are identified: a Sequencing Problem which aims to determine the available production capacity for each period, and a Capacited Lot-Sizing Problem which aims to determine the production quantity for each product in each period. The former is modelled as a dynamic Asymmetric Travelling Salesman Problem which complies with sequence- dependent set-up costs and a rolling horizon and a genetic algorithm searches for sub-optimal schedules. We demonstrated the proposed heuristic effectiveness through a validation campaign performed in the Unilever S.p.A. manufacturing plant in Pozzilli, Italy.