Computer Science 789 Online Algorithms

Fall 1999 The Buzzer Problem

A lazy night-shift worker's only job is to shut down a reactor in case of nuclear war. In order to keep him alert, the company has devised a task for him to do during the night.

The worker must respond to either of two buzzers by pressing a button. There are two buttons, one for each buzzer, and he must press the correct button. Buzzers buzz many times during the night, but never simultaneously.

At any given time, the worker has no idea which buzzer will buzz next. When a buzzer buzzes, the worker must press the correct button within 30 seconds.

There are three stools in the room. There is one stool right next to each button, and one in the middle. The worker can push a button easily from the nearby stool, or with some difficulty from the middle stool. The buttons are placed in such a way that he must be sitting in a stool to press a button. He does not like changing stools.

Let us assign 0 to the cost of pushing a button from the nearby stool, and 1 to the cost of pushing either button from the middle stool. He cannot reach a button from the stool near the other button. We assign 2 to the cost of changing stools.

The worker could, for example, always sit near a button, paying 2 each time he is forced to change stools. That is the greedy strategy. Alternatively, he could sit in the middle stool all the time, and pay 1 each time any buzzer buzzes. Or, perhaps, he could do something else, such as sit in the middle stool unless one of the buzzers buzzes twice in a row, in which case he moves to the stool nearest the proper button.

Formulate the problem as a metrical task system.

Back to Course Page

Back to Assignment Page