Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and Complexity

Abstract

In many practical situations, batching of similar jobs to avoid set-ups is performed whilst constructing a schedule. On the other hand, each job may consist of many identical items. Splitting a job often results in improved customer service or in reduced throughput time. Thus, implicit in determining a schedule is a lot-sizing decision which specifies how a job is to be split. This paper proposes a general model which combines batching and lot-sizing decisions with scheduling. A review of research on this type of model is given. Some important open problems for which further research is required are also highlighted.

Keywords:

• Algorithms
• Batching
• Complexity
• Lot-Sizing
• Scheduling