1. A method of selective constant complexity dismissal in task scheduling of a plurality of tasks, each described by one of a plurality of task records, in a computing environment by a processor device, comprising: placing the plurality of task records in a task queue; implementing a strictly increasing function to generate a plurality of unique creation stamps, each of the plurality of unique creation stamps increasing over time pursuant to the strictly increasing function; labeling a new task to be placed with the plurality of tasks with a new unique creation stamp of the plurality of unique creation stamps; implementing a dismissal action by at least one of a list of dismissal rules against at least one of the plurality of tasks, wherein the one of the list of dismissal rules holds a minimal valid creation (MVC) stamp, the MVC stamp updated when the dismissal action for the one of the list of dismissal rules is executed; and dismissing each task of the plurality of tasks matching the one of the list of dismissal rules, and having a unique creation stamp lower than the MVC stamp.