Heuristics for partial and total dynamic W-T problems 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, ensuring to accomplish it before the due date deadline. In totally dynamics problems, other job attributes such as processing time pj, due date dj, and tardiness penalty wj, are also unknown. Our research proposes different approaches for resolution of Weighted Tardiness dynamic problems (partial and total) in a single machine environment. A first approach uses, as a list of dispatching priorities a final schedule, found as the best by another heuristic for a similar static problem: same job features, processing time, due dates and weights. A second approach uses as a dispatching priority the order imposed by a partial schedule created, at each decision point, by another heuristic. The details of implementation of the proposed algorithms and results for a group of selected instances are discussed in this work.