Minimizing Total Costs in One-Machine Scheduling

Abstract

Suppose we have n jobs that arrive simultaneously to be processed on a continuously available machine that can handle only one job at a time. Each job has a fixed processing time and a cost function that is nondecreasing in its finishing time. We want to find a schedule that minimizes total costs. After reviewing the relevant work on this problem, we present a new algorithm for a general cost function. The algorithm is tested for the well known case of a weighted tardiness criterion.