Lot-sizing and scheduling problem with earliness tardiness and setup penalties

We consider the problem of determining the production lot sizes and their schedules so that the sum of setup cost, holding cost, and tardy cost is minimized. There are n orders waiting to be processed. Each order has its own due date, earliness penalty and tardiness penalty. The production is done in lots, which is the manufacturing of the same product continuously. No early delivery is allowed. Each order is delivered once, on the due date or immediately after the production of the order is completed. We present an algorithm, based on the use of the assignment problem, to optimally solve the problem with zero setup cost. For the problem with setup cost, the Backward Search algorithm is proposed to solve the small size problem. To deal with the large size problem, two heuristics which are Sequencing with Optimal Timing and Genetic Algorithm are presented.