M. Laguna
IIE Transactions, vol. 31, no. 2, pp. 125-134 (1999)
The consideration of sequence-dependent setup times is one of the most difficult aspects of production scheduling problems. This paper reports 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 and variable production rates. Other relevant data include holding 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 elimination 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 relatively small instances of this production problem, which are then used to assess the merit of a proposed heuristic. The heuristic is based on a simple short-term memory tabu search method that coordinates linear programming and traveling salesperson solvers in search for optimal or near-optimal production plans.
Full text
