Scheduling household chores is hard. Say you have three loads of washing: a regular load that will take 110 minutes to wash and 120 to dry; a heavily soiled load that needs an extra 30 minutes to wash; and a sensitive one that will take 130 minutes to wash and 160 to dry. In which order do you wash them?
In the branch of applied maths known as operational research, this is called a two-machine problem. Lots of businesses have similar issues. One approach, to find the shortest overall time, is to identify the shortest step. If it is a wash, do that load first. If it is a dry, do that load last. This way, washing and drying the loads in the right order can save half an hour.
However, when I have a list of chores, it is often a set of tasks only I can do, making it a single-machine problem 鈥� I am the only 鈥渕achine鈥� that can process jobs, so every possible schedule takes equally long. The order is then irrelevant, in terms of saving time.
Advertisement
But there are occasions when factors other than saving time can still lead to an optimal task order for a single-machine problem. For these, we must consider what a 鈥渂est鈥� outcome is. Mathematically, what are we trying to optimise? We identify some measure that we are trying to make as large or as small as possible, given constraints.
For example, for tasks with due dates, you might simply do items in order of due date. If the grass needed cutting last week and the hedge only became due for a trim today, maybe cut the grass first. This is an attempt to minimise each item鈥檚 lateness by completing the tasks that are most overdue, or closest to becoming overdue, first. It is why call centres put you in a queue in the order you rang.
Sometimes we have items that will expire by a certain date. What if you simply don鈥檛 have time to eat all the food in your fridge? Do you try to minimise lateness, or minimise the number of items that spoil? The Moore-Hodgson algorithm works to minimise the number of late items. It sounds grand, but it is actually simple. First, we schedule items in order by due date. Whenever we get to an item where we will miss the due date based on this scheduling, we look back over the list so far and remove the 鈥渂iggest鈥� item from it (here, we choose not to eat the food that will take the most meals to get through). Then we repeat until we have considered all items.
Another factor can be priority: perhaps ordering a present for my son鈥檚 birthday is very important right now, and doing the dishes can wait. To deal with this, we can give tasks a score (called a 鈥渨eight鈥�), divide it by the duration for each, and tackle those with the highest value first. In business, if the scores are the income gained by doing a task, this approach can be used to decide which jobs a company contracts to perform.
Now it just remains to decide whether to give ordering my son鈥檚 present a higher or lower weight than making his tea.
Peter Rowlett is a mathematics lecturer, podcaster and author based聽at聽Sheffield Hallam University in the UK. Follow聽him @peterrowlett
For other projects visit newscientist.com/maker
