Modeling and scheduling of production systems by using max-plus algebra

Max-plus algebra provides mathematical methods for solving nonlinear problems by using linear equations. These kinds of the problems arise in areas such as manufacturing, transportation, allocation of resources, and information processing technology. In this paper, the scheduling of production systems consisting of many stages and different units is considered, where some of the units can be used for many stages. If a production unit is used for different stages cleaning is needed in between, while no cleaning is needed between stages of the same type. Cleaning of units takes a significant amount of time, which is considered in the scheduling. The goal is to minimize the total production time, and such problems are often solved by using numerical optimization. In this paper a max-plus formalism is used for the modeling and scheduling of such production systems. Structural decisions such as choosing one unit over another proved to be difficult in the latter case, but this can be viewed as a switching max-plus linear system. No switching (and thus no cleaning) is considered as a base case, but for larger production batches the durability constraints will require switches. Switching as seldom as possible is shown to be optimal. Scheduling of a small production system consisting of 6 stages and 6 units is used as a case study.