University of Maryland

CIM Lab collage

Aggregation for Cyclic Scheduling

Principal Investigator

Background

Cyclic scheduling problems require finding a fair sequence that allocates capacity to competing demands in such a way that each demand receives, over any time period, a share of the capacity that is approximately proportional to its priority. The idea of fair sequences occurs in many different areas, including scheduling mixed-model, just-in-time assembly lines, planning preventive maintenance, inventory management, and controlling asynchronous transfer mode (ATM) networks. Finding fair sequences is related to multiple problems, including the product rate variation problem, generalized pinwheel scheduling, the hard real-time periodic scheduling problem, the periodic maintenance scheduling problem, stride scheduling, minimizing response time variability (RTV), and peer-to-peer fair scheduling.

This research project has systematically considered how aggregation can be used to find good solutions to these problems. Aggregation is a well-known and valuable technique for solving optimization problems, especially large-scale mathematical programming problems. Model aggregation replaces a large optimization problem with a smaller, auxiliary problem that is easier to solve. The solution to the auxiliary model is then disaggregated to form a solution to the original problem. Model aggregation has been applied to a variety of production and distribution problems, including machine scheduling problems.

Our results show that aggregation not only reduces the computational effort to find fair sequences but also finds better solutions in a variety of settings, including the response time variability problem, routing jobs to servers, and finding optimally balanced words for production planning and maintenance scheduling.

Publications

Return to University of Maryland | Jeffrey W. Herrmann

Last updated on July 15, 2011, by Jeffrey W. Herrmann.