A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup times

The consideration of sequence-dependent setup times is one of the most diff icult aspects of production scheduling problems. This paper reports on the development of a heuristic procedure to address a realistic production and inventory control problem in the presence of sequence-dependent setup times . The problem considers known monthly demands, variable production rates, h olding costs, minimum and maximum inventory levels per product, and regular and overtime capacity limits. The problem is formulated as a Mixed-Integer Program (MIP), where subtour elimination constraints are needed to enforce the generation of job sequences in each month. By relaxing the subtour eli mination constraints, the MIP formulation can be used to find a lower bound on the optimal solution. CPLEX 3.0 is used to calculate lower bounds for r elatively small instances of this production problem, which are then used t o assess the merit of a proposed heuristic. The heuristic is based on a sim ple short-term memory tabu search method that coordinates linear programmin g and traveling salesperson solvers in the search for optimal or near-optim al production plans.