Solving dynamic tardiness problems in single machine environments

Dynamic scheduling can be classified as partial or total. In simplest partially dynamic problems the only unknown attribute of a job is its arrival time r_j. In some totally dynamic problems, other job attributes such as processing time p_j, due date d_j, and weights w_j, are also unknown until processing. This paper proposes two approaches to face dynamic tardiness problems in single machine environments. The first approach uses, as a dispatching rule the job order provided by a total schedule S generated by an evolutionary algorithm, or by conventional heuristics for a similar static problem: same job features, processing time, due dates and weights. The second approach uses conventional heuristics and a hybrid evolutionary algorithm to reorder jobs in the waiting queue. Details of implementation of the proposed algorithms and results for a group of selected instances are discussed in this work.