Analyzing SRPT for preemptive scheduling
DOI:
https://doi.org/10.26481/marble.2013.v1.135Abstract
Imagine a car garage with three car lifts that can be used to lift a car so it can be repaired. All the time, customers are coming in with their broken cars. Some are very broken and need a lot of time to repair while others may only need a short amount of time. The manager of the garage needs to decide which cars he is going to repair first. His goal is to get the most cars out of his garage as fast as possible. Unfortunately, deciding what cars to repair first is a very hard problem. It is comparable to solving the famous Travelling Salesperson Problem, where a businessperson has to visit a lot of cities and wants to find the shortest route between them. A simple way of deciding the order of repairing the cars is starting with the cars that will take the shortest time to repair, and leave the longer repairs for later. This may seem like a very logical rule, but it may produce a repair schedule that is not ideal. But, how far from ideal could this simple schedule be? That is the main topic of my thesis. In the thesis, I first explain what research has been done already on the subject. Then I use the program I wrote to make schedules using the simple rule and optimal schedules for a lot of examples. What I found out is that the examples where the difference between the two schedules is the largest all look similar. Finally, I analyze the general form of the examples with large differences. I show in the paper that when we restrict ourselves to the form of the examples with the largest differences, the simple rule schedule can be at most 1,105 times worse than the ideal schedule. In practice, this means that at the very worst, the cars in the garage will only have to stay 10,5% longer in the garage. This last result is new and if someone can prove that the form of the examples I found is indeed the worst form of example, we know that the simple rule produces quite well preforming schedules that can be at most 1,105 times worse than the ideal schedule. Then, if the small factor of 1,105 is not a problem, garage managers and other people who encounter problems like this can apply the "short jobs first" rule with confidence.
References
Baptiste, P., Brucker, P., Chrobak, M., Drr, C., Kravchenko, S., & Sourd, F. (2007). The complexity of mean flow time scheduling problems with release times. Journal of Scheduling, 10, 139-146.
Chung, C., Nonner, T., & Souza, A. (2010). Srpt is 1.86-competitive for completion time scheduling. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 1373-1388, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics.
Du, J., Leung, J., & Young, G. (1990). Minimizing mean flow time with release time constraint. Theoretical Computer Science, 75(3), 347 -355.
Graham, R., Lawler, E., Lenstra, J., & Rinnooy Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In E.L. Johnson P.L. Hammer and B.H. Korte (eds.), Discrete Optimization II Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium co-sponsored by IBM Canada and SIAM Ban, Aha. and Vancouver, volume 5 of Annals of Discrete Mathematics, pages 287 - 326. Elsevier.
Lu, X., Sitters, A., & Stougie, L. (2003). A class of on-line scheduling algorithms to minimize total completion time. Operations Research Letters, 31(3), 232- 236.
Phillips, C., Stein, C., & Wein, J. (1998). Minimizing average completion time in the presence of release dates. Mathematical Programming, 82, 199-223.
Sitters, R. (2010). Efficient algorithms for average completion time scheduling. In F. Eisenbrand & F. Shepherd (eds.), Integer Programming and Combinatorial Optimization, volume 6080 of Lecture Notes in Computer Science, 411-423. Springer Berlin / Heidelberg.
Vestjens, A. (1997). Online Machine Scheduling. PhD thesis, Technische Universiteit Eindhoven.
