Order selection on a single machine with high set-up costs (Q1309884)

A single resource is used to produce a number of different part-types. A large set-up cost is incurred when switching the resource from one part- type to another, but the per item cost for each part-type is small. As a result, it is economical to produce only large batches of each part-type. Customer orders require one or more part-types. Revenue is received for an order only if it is completely filled. The goal is to maximize short- term profit. It is assumed that resource availability during the ``short- term planning horizon'' is not sufficient to produce all of the orders. Then, to optimize short-term profit, one must select the most profitable set of orders that can feasibly be produced. This problem is formulated as an integer linear program. Then the authors consider an approximation to this model which is more amenable to the solution techniques of mixed-integer programming. They present a heuristic for the solution of this problem. The heuristic performs quite will on randomly generated test problems. The heuristic is also used to provide good lower bounds and cutting planes for the solution by branch- and-cut methods.