Having recently spent some time outside the US, I found, upon my return, that many of the Apps on my iPhone needed to be updated. No big deal: I clicked “Update all”, typed in my password, and let the operating system finish the job. After watching the update process for a minute or so, I noticed one interesting fact: Apps were updated (i.e. downloaded+installed) in the order the updates became available (chronologically increasing), rather than by increasing order of the size of the update (in bytes). If you’re asking “why does it matter?”, read on.
During my grad school years at Carnegie Mellon, I had the pleasure of taking the Sequencing and Scheduling class with Egon Balas (I later sat in the class again as his TA, and finally taught it to the MBA students in 2004). So let’s start with some terminology: given a machine (the iPhone) and a set of tasks (Apps) to be executed (updated) on the machine, the completion time of a task is the time at which it is finished. For example, let’s assume the Concorde TSP App needs an update. If time zero is the moment I enter my iTunes password, the completion time of task “Concorde TSP” is the earliest time at which this App’s latest version is ready to run on my iPhone. The total completion time of a set of tasks is simply the sum of the completion times of all tasks, and the makespan is the completion time of the task that gets updated last.
The App update process has no release dates (all outdated Apps are ready to be updated at time zero), is non-preemptive (once started, the update of an App continues until it’s finished; ignoring crashes and other issues), and doesn’t involve sequence-dependent setup times (as soon as an App finishes updating, the next App in line can start its update right away). Under these circumstances, the makespan of a group of outdated Apps is always the same, regardless of the order in which they get updated. For example, if App A takes 15 seconds to download and install, and App B takes 10 seconds to download and install, it will take me 25 seconds to update both of them, regardless of which one is updated first. So far, so good. But let’s see what happens with the total (or average) completion time.
Continuing with the two-App example above, if I update the Apps in the order A, B, the completion time of A is 15, and the completion time of B is 25. The total completion time is 15+25=40, and the average completion time is 40/2=20 seconds. If the Apps are updated in the reverse order B, A, the completion time of B is 10, and the completion time of A is 25. The total completion time now is 10+25=35, and the average completion time decreases to 35/2=17.5 seconds. If there were other Apps being updated before or after the pair A, B, swapping them to make sure that B goes before A (because B takes less time) would have the same effect (the A, B swap doesn’t change the completion time of other Apps). What I just explained is called an exchange argument. It proves that whenever two Apps are out of order (in the sense that a smaller one is placed after a larger one), swapping them reduces the total/average completion time. Therefore, the minimum total/average completion time is obtained when the Apps are sorted by increasing order of duration. In the scheduling literature, this is called the SPT rule (Shortest Processing Time first).
I still haven’t answered the question of whether all of this matters because the makespan doesn’t depend on the order of Apps (updating A and B always takes 25 seconds). The answer is I don’t know! It’s a psychological effect. Shorter completion times may give the user the impression that the update process is going fast because a bunch of small Apps get updated quickly. By updating larger Apps first, the user may have the impression that the process is taking longer because, after a while, there are still many Apps to go. Should Apple worry about this? I’ll leave that question to my colleagues in the Marketing department who specialize in Consumer Behavior. If the answer turns out to be “yes”, then you now know what to do.
P.S. I’d like to know what other mobile operating systems do. Do they use SPT? Please let me know in the comments.