Show simple item record

Scheduling Perfectly Periodic Services Quickly with Aggregation

dc.contributor.authorHerrmann, Jeffrey
dc.description.abstractThe problem of scheduling periodic services that have different period lengths seeks to find a schedule in which the workload is nearly the same in every time unit. A time unit’s workload is the sum of the workloads of the services scheduled for that time unit. A level workload minimizes the variability in the resources required and simplifies capacity and production planning. This paper considers the problem in which the schedule for each service must be perfectly periodic, and the schedule length is a multiple of the services’ period lengths. The objective is to minimize the maximum workload. The problem is strongly NP-hard, but there exist heuristics that perform well when the number of services is large. Because many services will have the same period length, we developed a new aggregation approach that separates the problem into subproblems for each period length, uses the subproblem solutions to form aggregate services, schedules these, and then creates a solution to the original instance. We also developed an approach that separates the problem into subproblems based on a partition of the period lengths. Computational experiments show that using aggregation generates high-quality solutions and reduces computational effort. The quality of the partition approach depended upon the partition used.en_US
dc.titleScheduling Perfectly Periodic Services Quickly with Aggregationen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtInstitute for Systems Researchen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, MD)en_us

Files in this item


This item appears in the following Collection(s)

Show simple item record