(Joint work with Kai Olsen)

We discuss a scheduling problem faced by a Norwegian producer of propellers. The propellers are made to order, which implies that there is a given due date for each order. An order consists of a given number of propeller blades of equal shape and size. It is assumed that all orders are given at the start of the planning periode. Due to production considerations the blades of an order should be produced on consecutive days. A propeller blade is produced in a box that matches the size of the propeller blade. There are six different sizes of boxes, and hence the orders are categorized into six different groups. Mainly due to restricted storage space only a limited number of these boxes can be used at the same time. The production capacity is given by how many boxes of each type that can be used simultaneously. The objective of the scheduling problem is to minimize the total tardiness for a given set of orders. A mathematical formulation is given and discussed, and different heuristics are tested.