Abstract
In this thesis we mainly consider single-machine capacitated lot-sizing and scheduling problems with initial inventory and sequence-dependent setup time. We provide a simple procedure to convert the problem into the one without initial inventory. To deal with small size problem we propose a mixed-integer programming formulation which generalizes the former models in the literatures. For large-scale programs, we provide a heuristic method which will generate a feasible schedule in reasonable time. The heuristic comprises two stages. In stage one a backward method is used to generate a good feasible schedule and the schedule is refined in stage two. Moreover, the proposed problem and algorithm are extended to parallel-machine and flow shop problems.