AbstractThis study deals with a class of production scheduling problems characterized by a variable known demand and a fixed cost associated with each production run. The investigation originated from a problem encountered by a petroleum refinery. The refinery management was concerned with the high cost of manufacturing grease cans used for packaging of its grease products. This high cost resulted from the set-up cost incurred whenever the equipment (which was normally used to manufacture oil cans) was converted for manufacturing a relatively small quantity of grease cans with lithographed grade marking. The length of the production runs for making grease cans was severely restricted by a limited storage capacity. In order to meet the radically varying demand, the refinery frequently had to hand-stencil the grade on cans without grade marking. The problem faced by the management was to find a procedure for deciding when grease cans with lithographed grade marking should be produced so as to operate optimally.