Algorithms to solve the dynamic weighted tardiness problem

Abstract

In static scheduling problems it is assumed that jobs are ready at zero time or before processing begins. In dynamic scheduling problems a job arrival can be given at any instant in the time interval between zero and a limit established by its processing time, ensuring to accomplish it before the due date deadline. In the cases where the arrivals are near to zero the problem comes closer to the static problem, otherwise the problem becomes more restrictive. This paper proposes two approaches for resolution of the dynamic problem of Total Weighted Tardiness for a single machine environment. The first approach uses, as a list of dispatching priorities a schedule, which an evolutionary algorithm found as the best for a similar static problem: same job features, processing time, due dates and weights. The second approach uses as a dispatching priority a schedule created by a robust non-evolutionary heuristic. The details of implementation of the proposed algorithms and results for a group of selected instances are discussed in this work.