Abstract:

A single machine problem with $n$ jobs is considered. The jobs are processed in a given order on a continuously available machine. At any time the machine can handle at most one job, and no preemption is permitted. Every job requires a positive processing time. If a job is not processed within a specified time interval, then a positive penalty is incurred, which is a function of starting time of the job in question. An algorithm is proposed for determining starting times that minimize the maximum penalty subject to the condition that every job must be started within a given time interval. Some extensions to more general objective functions are also presented.