Production planning of processors located within in a facility or distributed across facilities is a routine and crucial industrial activity. So far, most attempts at this have treated planning horizon as a decision variable, and have limited their scope to sequence-independent setups. In this two-part paper, we present a new and improved methodology for solving the single machine economic lot scheduling problem (ELSP) with sequence-dependent setups and a given planning horizon. We decompose the entire complex problem into two subproblems; one involving lot sizing and the other involving lot sequencing and scheduling. In this part, we present a novel mixed integer nonlinear programming (MINLP) formulation for the lot-sizing problem. Using a multi-segment separable programming approach, we transform this MINLP into a MILP and propose one rigorous and two heuristic algorithms for the latter. Based on a thorough numerical evaluation using randomly simulated large problems, we find that our best heuristic gives solutions within 0.01% of the optimal on an average and in much less time than the optimal algorithm. Furthermore, it works equally well on problems with sequence-independent setups. Overall, our methodology is well suited for real-life large-scale industrial problems.