Production Scheduling with Sequence Dependent Setup Costs

The problem of scheduling products, with constant demand rates, on a single facility is difficult. This difficulty is compounded if the setup costs are not constant for each product but depend on the sequence in which the products are made. A heuristic that iterates between solving the scheduling problem with constant setup costs and solving a “traveling salesman” formulation with sequence dependent setup costs is presented. The heuristic works well in practice and always provides a feasible solution if one exists. Some computational experience is also given.