A small business-say, a photocopying service with a single large machine-faces the following scheduling problem. Each morning they get a set of jobs from customers. They want to do the jobs on their single machine in an order that keeps their customers happiest. Customer i's job will take t; time to complete. Given a schedule (i.e., an ordering of th