Heuristic Algorithms for Single Processor Scheduling with Earliness and Flow Time Penalties

We consider the problem of scheduling a set of n tasks on a single processor. Each task has a processing time, a deadline, a flow time penalty and an earliness penalty. The objective is to minimize the total cost incurred by the penalties. The problem is NP-hard in the strong sense. Exact enumerative algorithms from the literature can solve random instances with n ≤ 50. We study a tabu search approach to the approximate solution of the problem and show, through computational experiments, that instance with n = 300 are effectively solved with short computing times.