When should procrastinators do their Christmas shopping?
Press release issued: 22 December 2010
Researchers at the University of Bristol, State University of New York and Aristotle University of Thessaloniki have devised a ‘scheduling algorithm’ for procrastinators that will help order the jobs they need to do, while making sure that no job is unreasonably late.
In the procrastinators’ schedule a number of jobs arrive in succession and there is a deadline by which each has to be done, but when should people do which job. Researchers at the University of Bristol, State University of New York and Aristotle University of Thessaloniki devised a ‘scheduling algorithm’ for procrastinators that will help order the jobs they need to do, while making sure that no job is unreasonably late.
Assuming, as a procrastinator, everything is going to be late, you firstly have to have a measure of lateness, which is defined as a function of how long the job was meant to take in the first place. Therefore a job that takes a year plus a day is not nearly as late as one that takes a day plus a year.
Dr Raphaël Clifford, Senior Lecturer in the Department of Computer Science and Head of the Algorithms Group at Bristol University and one of the authors on the paper, said: “Instinctively, there are any number of things one assumes would happen. One might decide to do the job that’s the most overdue, or the one that has the closest deadline. It turns out, however, that the best strategy is to do nothing at all until at least one job is a factor of two late. At which point, do the job you were given most recently. That, it turns out, guarantees that no job will be more than a factor of four late.”
What this means is that if a job that should have taken two weeks is already two weeks late, don’t bother with that one, but do the job that just came in. This will guarantee that no job will be unreasonably late.
In the real world, computers have a huge number of tasks they need to perform in order to complete an activity and such tasks have to be scheduled according to what needs to be achieved. More generally, many common scheduling problems in both daily life and industry involve tasks where the processing times are time-dependent.
For example, a construction project that is behind schedule may need more workers assigned to it, and a shipment that is late may be delivered faster by using an alternative, more expensive means of transportation. Indeed, a major reason for the success of overnight courier companies could be that the world is filled with scheduling problems executed by procrastinators.
The authors of the paper Scheduling Algorithms for Procrastinators are Dr Raphaël Clifford, Senior Lecturer in the Department of Computer Science and Head of the Algorithms Group at the University of Bristol; Professor Michael Bender at the State University of New York (SUNY), USA and Professor Kostas Tsichlas, at the Aristotle University of Thessaloniki, Greece.