Online scheduling to minimize modified total tardiness with an availability constraint (Q1034623): Difference between revisions

The problem to be considered is one of online scheduling tasks on a single machine, subject to weighted total tardiness minimization. The authors show that there is no finite competitive ratio for this problem and different arrival times and deadlines. However, it is shown that 3-competitive algorithm exists for the same problem but with modified criterion that is increased by deadline itself for each task. To denote problems, the authors use the three field notation with a non-standard usage of the res symbol. In a standard denotation it was used to denote additional resources, here it means resumable models of task processing. This may lead to some misunderstandings.