A survey of results for sequencing problems with controllable processing times (Q908846)

This paper reviews algorithms and complexity results for scheduling problems in which the processing time of a job is a decision variable. For each job, an upper and lower bound on its processing time is specified and a processing cost, which is a linear decreasing function of processing time, is given. In addition to the processing cost, a schedule cost (maximum completion time, maximum lateness or total weighted completion time, for example) is associate with completion times of the jobs. Most results relate to the problem of scheduling a single machine to minimize the processing plus schedule cost. Throughout the paper, a typical algorithm first selects a processing order of the jobs and then solves a linear program to fix the processing times; this linear program can often be solved very efficiently. For some problems, this type of algorithm provides an exact solution; for others, it is a heuristic and worst-case performance bounds are available.