Solutions to the dynamic average tardiness problem in single machine environments

Abstract

In dynamic scheduling arrival times as well, as some or all job attributes are unknown in advance. Dynamism can be classified as partial or total. In simplest partially dynamic problems the only unknown attribute of a job is its arrival time rj. A job arrival can be given at any instant in the time interval between zero and a limit established by its processing time, in order to ensure finishing it before the due date deadline. In the cases where the arrivals are near to zero the problem becomes closer to the static problem, otherwise the problem becomes more restrictive. In totally dynamics problems, other job attributes such as processing time pj, due date dj, and tardiness penalty wj, are also unknown. This paper proposes different approaches for resolution of (partial and total) Dynamic Average Tardiness problems in a single machine environment. The first approach uses, as a list of dispatching priorities a final (total) schedule, found as the best by another method for a similar static problem: same job features, processing time, and due dates. The second approach uses as a dispatching priority the order imposed by a partial schedule created by another heuristic, at each decision point. The details of implementation of the proposed algorithms and results for a group of selected instances are discussed in this work.