Scheduling Production on One Machine with Changeover Costs

Abstract

Abstract A single machine is used to produce several products so as to satisfy known demands over a fixed number of periods. Each time switches are made between products, there are changeover costs as described by a matrix C=[cij ], where cij is the cost of switching from product i to product j. The problem is to find a schedule of production that minimizes the total changeover penalty while meeting the due dates of all customer orders. The function used in a forward-time dynamic program is shown to have a monotonicity property that can be used to advantage when seeking an optimal solution to the problem. This monotonicity property is applied in developing an efficient backward-time search procedure for solving the problem.