Transforming an MRP plan into a short-term schedule

Abstract

A new approach for transforming MRP orders, planned periodically, e.g. on a weekly base, into a detailed sequence of jobs is presented. In this model for a single machine environment, the jobs are partitioned into families and a family specific set-up time is required at the start of each period and of each batch, where a batch is a maximal set of jobs in the same family, that are processed consecutively. An integer program is formulated for both the problem of minimizing the number of overloaded periods and the problem of minimizing the total overtime. These programs generate benchmark results for the heuristic approach. A heuristic model is developed that constructs a schedule in which overloaded periods are relieved and set-up time is saved. In this approach, the job sequence is constructed by repeatedly solving a knapsack problem. The weights used in this knapsack problem relate to the preferred priorities of the jobs not yet scheduled and determine the quality of the final sequence. The different features of the heuristic model are compared using a large set of test problems. The results show that the quality of the final sequence depends on an appropriate choice for the weights.

Keywords:

• job families
• lotsizing
• MRP planning
• single machine scheduling

Acknowledgments

HERMAN A. J. CRAUWELS is Senior Lecturer in the Department of Industrial Sciences of the De Nayer Institute, Belgium. He received a MSc in Computer Sciences and in Industrial Management and a PhD in Industrial Management from the Katholieke Universiteit Leuven. His research interests are in the area of metaheuristics and scheduling. His recent publications have appeared in Annals of Operations Research, European Journal of Operational Research and INFORMS Journal on Computing.

DIRK L. VAN OUDHEUSDEN is Professor of Industrial Management at the Katholieke Universiteit Leuven, Belgium. He also taught at the Asian Institute of Technology, Thailand. He obtained a PhD in Applied Mathematics from the Vrije Universiteit Brussel. His research interests include production and logistics planning, and public transportation systems. He recently published in the Journal of the Operational Research Society, the Journal of Scheduling, the European Journal of Operational Research, the International Journal of Production Economics, the International Journal of Production Research and O. R. Insight.