Using aggregation to reduce response time variability in cyclic fair sequences
Tóm tắt
Fair sequences are useful in a variety of applications, including manufacturing and computer systems. This paper considers the generation of cyclic fair sequences for a given set of products, each of which must be produced multiple times in each cycle. The objective is to create a sequence so that, for each product, the variability of the time between consecutive completions is minimized. Because minimizing response time variability is known to be NP-hard and the performance of existing heuristics is poor for certain classes of problems, we present an aggregation approach that combines products with the same demand, creates a sequence for the aggregated instance, and then disaggregates this solution into a feasible sequence for the original instance. Computational experiments show that using aggregation can reduce response time variability dramatically and also reduces computational effort.
Tài liệu tham khảo
Balinski, M. L., & Young, H.P. (1982). Fair representation. New Haven: Yale University Press.
Bar-Noy, A., Bhatia, R., Naor, J., & Schieber, B. (2002a). Minimizing service an operation costs of periodic scheduling. Mathematics of Operations Research, 27, 518–544.
Bar-Noy, A., Nisgah, A., & Patt-Shamir, B. (2002b). Nearly optimal perfectly periodic schedules. Distributed Computing, 15, 207–220.
Campbell, A. M., & Hardin, J. R. (2005). Vehicle minimization for periodic deliveries. European Journal of Operational Research, 165, 668–684.
Corominas, A., Kubiak, W., & Palli, N. M. (2007). Response time variability. Journal of Scheduling, 10, 97–110.
Garcia, A., Pastor, R., & Corominas, A. (2006). Solving the response time variability problem by means of metaheuristics. In M. Polit, T. Talbert, & B. Lopez (Eds.), Artificial intelligence research and development (pp. 187–194). Amsterdam: IOS Press.
Herrmann, J. W. (2007). Generating cyclic fair sequences using aggregation and stride scheduling (Technical Report 2007-12). Institute for Systems Research, University of Maryland, College Park. Available online at http://hdl.handle.net/1903/7082.
Herrmann, J. W. (2008). Constructing perfect aggregations to eliminate response time variability in cyclic fair sequences (Technical Report 2008-29). Institute for Systems Research, University of Maryland, College Park. Available online at http://hdl.handle.net/1903/8643.
Herrmann, J. W. (2009). Generating cyclic fair sequences for multiple servers. In: Multidisciplinary international conference on scheduling: theory and applications (MISTA 2009), Dublin, Ireland, 10–12 August 2009.
Inman, R. R., & Bulfin, R. L. (1991). Sequencing JIT mixed-model assembly lines. Management Science, 37(7), 901–904.
Kubiak, W. (2004). Fair sequences. In J. Y.-T. Leung (Ed.), Handbook of scheduling: algorithms, models and performance analysis. Boca Raton: Chapman & Hall/CRC.
Miltenburg, J. (1989). Level schedules for mixed-model assembly lines in just-in-time production systems. Management Science, 35(2), 192–207.
Moreno, N. (2002). Solving the product rate variation problem (PRVP) of large dimensions as an assignment problem. Doctoral thesis, DOE, UPC.
Nowicki, E., & Smutnicki, C. (1989). Worst-case analysis of an approximation algorithm for flow shop scheduling. Operations Research Letters, 8, 171–177.
Park, K. S., & Yun, D. K. (1985). Optimal scheduling of periodic activities. Operations Research, 33, 690–695.
Rock, H., & Schmidt, G. (1983). Machine aggregation heuristics in shop scheduling. Methods of Operations Research, 45, 303–314.
Rogers, D. F., Plante, R. D., Wong, R. T., & Evans, J. R. (1991). Aggregation and disaggregation techniques and methodology in optimization. Operations Research, 39(4), 553–582.
Steiner, G., & Yeomans, S. (1993). Level schedules for mixed-model, just-in-time processes. Management Science, 39(6), 728–735.
Waldspurger, C. A., & Weihl, W. E. (1995). Stride scheduling: deterministic proportional-share resource management. Technical Memorandum MIT/LCS/TM-528, MIT Laboratory for Computer Science, Cambridge, Massachusetts.
Wei, W. D., & Liu, C. L. (1983). On a periodic maintenance problem. Operations Research Letters, 2(2), 90–93.