Heuristic algorithms for lotsize scheduling with application in the tobacco industry

We investigate a production planning problem which appears in many industries. We present an example from the tobacco industry. The basic question is how tasks of different types can be scheduled on machines in lots such that the number of changeovers is minimized. These changeovers occur if two tasks of different types are scheduled in sequence on a machine. We analyze the problem in detail and present heuristics for the single and multiple machine case. We evaluate these heuristics and give recommendations for their application to serial production systems. (C) 2001 Elsevier Science Ltd. All rights reserved.