Scheduling Perfectly Periodic Services Quickly with Aggregation
| dc.contributor.author | Herrmann, Jeffrey | |
| dc.date.accessioned | 2013-03-22T17:38:29Z | |
| dc.date.available | 2013-03-22T17:38:29Z | |
| dc.date.issued | 2013-03 | |
| dc.description.abstract | The 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.identifier.uri | http://hdl.handle.net/1903/13711 | |
| dc.language.iso | en_US | en_US |
| dc.relation.isAvailableAt | Institute for Systems Research | en_us |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_us |
| dc.relation.isAvailableAt | University of Maryland (College Park, MD) | en_us |
| dc.relation.ispartofseries | TR_2013-08 | |
| dc.subject | scheduling | en_US |
| dc.subject | aggregation | en_US |
| dc.title | Scheduling Perfectly Periodic Services Quickly with Aggregation | en_US |
| dc.type | Technical Report | en_US |