Production scheduling based on Tabu and Scatter Search techniques

The problem of production scheduling and inventory control for those facilities with high setup times can be of particular interest in process industry. The problem can be resumed as to find a master production schedule which can meet monthly demands and minimize total working overtime and inventory costs. The related production plans, however, may be infeasible even after a rough - cut capacity planning has been applied to it. One simple way of addressing the capacity problem is to add a capacity requirements planning (CRP) module to the MRP systems; this module, in fact, analyses the work loads at each center and generates a report that the scheduler can use to take corrective measures. The difficulty is compounded by CRP reports which concentrate on the loads generates by current MRP solution instead of on the impact of potential solution changes. The scheduler is then forced to perform a trial–and–error process between MRP and CRP until a satisfactory solution is reached. The origin of the problem may be traced to the techniques used to determine single (e.g. periodic order quantity, economic order quantity, etc.) lot sizes. It is notoriously known that these techniques calculate lot sizes by balancing the trade-off between set-up and inventory costs while ignoring the amount of resources needed at each work center during the different period in the planning time and the stochastic dependencies existing between activities. In this paper we propose a two-stage decisions approach; in the first one we analyse our production cycle in order to model it and to identify its constraints while in the second, in order to introduce the dependencies between activities, we generate a feasible set of scenarios. The core procedure is based on Tabu Search and Scatter Search methodology, with which a population of paths “evolves” until a stopping criterion is satisfied yielding the best path. The approach has been tested in an aeronautical firm, where we have obtained encouraging results which indicate that the adaptation of meta-heuristic procedures could open the door to the development of procedures for solving several types of scheduling problems.