Multi-level single machine lot-sizing and scheduling with zero lead times

A pharmaceutical company raised the question whether an increased product portfolio could still be manufactured on the existing machinery. The proportional lot-sizing and scheduling problem (PLSP) seemed to be most appropriate to answer this question. However, although there are papers dealing with a multi-level PLSP none allows a zero lead time offset which is a prerequisite for the case considered here. In this paper we will extend and modify an existing mixed integer linear programming (MIP) model formulation in two ways: first, we will extend the single-level single machine PLSP to a multi-level single machine PLSP (PLSP-ML-SM) with a zero lead time offset. Second, we will describe a new and more compact model formulation incorporating period overlapping setup times and batch size constraints. Based on the real-world application several test instances have been generated to provide insights into those characteristics which make instances of the PLSP-ML-SM difficult to solve by a standard MIP solver. (C) 2010 Elsevier B.V. All rights reserved.