Single-Machine Scheduling to Minimize a Function of K Maximum Cost Criteria

摘要

A number of jobs has to be scheduled on a single machine, which can handle nomore than one job at a time. Each job requires processing during a given positive uninterrupted time. For each job, there are K arbitrary nondecreasing penalty functions. The quality of a schedule is measured by K performance criteria, the kth one being given by the maximum value of the kth penalty function that is attained by any job. The problem is to find the set of Pareti optimal points with respect to these performance criteria. An algorithm for this problem that is polynomial for fixed K is presented. These algorithms are shown to be still applicable if precedence constraints exist between the jobs or if all penalty functions are nonincreasing in the job completion times.